TopCoder TheCardLineDivTwo


https://community.topcoder.com/stat?c=problem_statement&pm=10620
John and Brus are training for a card game tournament. During his off-time, Brus likes to occupy himself with the following game. The game is played with a subset of a standard deck of 52 distinct cards. Each card can be represented by a two-character string, where the first character is the rank ('2'-'9', 'T', 'J', 'Q', 'K', or 'A') and the second character is the suit ('S' for Spades, 'C' for Clubs, 'D' for Diamonds or 'H' for Hearts). All Spades and Clubs are black, and all Diamonds and Hearts are red. For example, the Jack of Spades is black and is represented as "JS", and the Nine of Hearts is red and is represented as "9H".
You are given a String[] cards containing the subset of the deck that Brus is playing with. Each element of cards represents a single card. He wants to place all of these cards in a line such that every pair of neighboring cards has the same rank or the same color (or both). Return the number of different ways he can do this modulo 1234567891.
 

Definition

    
Class:TheCardLineDivTwo
Method:count
Parameters:String[]
Returns:int
Method signature:int count(String[] cards)
(be sure your method is public)
    
 

Constraints

-cards will contain between 1 and 16 elements, inclusive.
-Each element of cards will contain exactly two characters, where the first character is '2'-'9', 'T', 'J', 'Q', 'K' or 'A', and the second character is 'S', 'C', 'D' or 'H'.
-All elements of cards will be distinct.
 

Examples

0)
    
{"KH", "QD", "KC"}
Returns: 2
There are two possible placements - KC-KH-QD and QD-KH-KC.
1)
    
{"JS", "JC", "JD", "JH"}
Returns: 24
All 24 permutations are valid.
2)
    
{"2S", "3C", "4C", "5S", "6C", "7S", "8S", "9H"}
Returns: 0
There is nothing we can do with the Nine of Hearts.
3)
    
{"KD", "KC", "AD", "7C", "AH", "9C", "4H", "4S", "AS"}
Returns: 2416

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

https://apps.topcoder.com/forums/?module=Thread&threadID=671561&start=0
Another advantage of encoding a set into an integer is that it becomes trivial to index an array with a set. TheCardLineDivTwo has a fairly common theme of counting the possible way to order some objects. 

We can solve it recursively, by keeping track of which cards are still available and which card was used last. Since the result of the recurse function depends only on its parameters (and the cards, which are fixed for one test case), we can cache the result of each call; and since the set of available cards is encoded as an integer, we can use the value to directly index a cache. Here we use the exclusive-or (^) operator to toggle an element in the set (in this case we know whether the element was previously present, so it is not the only way to do it).

    private static final int MOD = 1234567891;
 
    private String[] cards;
    private int[][] cache;
 
    private boolean red(int card)
    {
        char suit = cards[card].charAt(1);
        return suit == 'H' || suit == 'D';
    }
 
    /** Determine whether card1 and card2 can be adjacent in line */
    private boolean compatible(int card1, int card2)
    {
        char rank1 = cards[card1].charAt(0);
        char rank2 = cards[card2].charAt(0);
        return rank1 == rank2 || red(card1) == red(card2);
    }
 
    /**
     * Count the number of ways to finish off the line using the cards in
     * the set valid, given that the previously placed card was last.
     */
    private int recurse(int last, int valid)
    {
        if (cache[last][valid] != -1)
        {
            // Already solved this subproblem, use the cached value
            return cache[last][valid];
        }
        if (valid == 0)
        {
            // All cards placed, no further choices to make.
            return cache[last][valid] = 1;
        }
        long ans = 0;
        // Try all possibilities for the last card
        for (int i = 0; i < cards.length; i++)
            if ((valid & (1 << i)) != 0
                && compatible(last, i))
            {
                ans = (ans + recurse(i, valid ^ (1 << i))) % MOD;
            }
        return cache[last][valid] = (int) ans;
    }
 
    public int count(String[] cards)
    {
        this.cards = cards;
        int N = cards.length;
        cache = new int[N][1 << N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < (1 << N); j++)
                cache[i][j] = -1;   // mark as unknown
 
        long ans = 0;
        int all = (1 << N) - 1;
        for (int i = 0; i < N; i++)
            ans = (ans + recurse(i, all ^ (1 << i))) % MOD;
        return (int) ans;
    }




Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts