https://community.topcoder.com/stat?c=problem_statement&pm=10620
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).
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; }