Problem D. Treasure - Qualification Round 2013 - Google Code Jam


Dashboard - Qualification Round 2013 - Google Code Jam
Following an old map, you have stumbled upon the Dread Pirate Larry's secret treasure trove!
The treasure trove consists of N locked chests, each of which can only be opened by a key of a specific type. Furthermore, once a key is used to open a chest, it can never be used again. Inside every chest, you will of course find lots of treasure, and you might also find one or more keys that you can use to open other chests. A chest may contain multiple keys of the same type, and you may hold any number of keys.
You already have at least one key and your map says what other keys can be found inside the various chests. With all this information, can you figure out how to unlock all the chests?
For example, suppose the treasure trove consists of four chests as described below, and you began with exactly one key of type 1:

Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             |  1                       |  None
2             |  1                       |  1, 3
3             |  2                       |  None
4             |  3                       |  2
You can open all the chests in this example if you do them in the order 2, 1, 4, 3. If you start by opening chest #1 first, then you will have used up your only key, and you will be stuck.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing two positive integers K and N, representing the number of keys you start with and the number of chests you need to open.
This is followed by a line containing K integers, representing the types of the keys that you start with.
After that, there will be N lines, each representing a single chest. Each line will begin with integers Ti and Ki, indicating the key type needed to open the chest and the number of keys inside the chest. These two integers will be followed by Ki more integers, indicating the types of the keys contained within the chest.

Output

For each test case, output one line containing "Case #x: C1 C2 ... CN", where x is the case number (starting from 1), and where Ci represents the index (starting from 1) of the ith chest that you should open.
If there are multiple ways of opening all the chests, choose the "lexicographically smallest" way. In other words, you should choose to make C1 as small as possible, and if there are multiple ways of making C1 as small as possible, choose the one that makes C2 as small as possible, and so on.
If there is no way to open all the chests, you should instead output one line containing "Case #x: IMPOSSIBLE".
https://northanapon.wordpress.com/2013/04/18/google-code-jam-qualification-2013-treasure/
Pre-checking
If there is no valid solution, then don’t need to try. We can pre-check the number of keys and locks before doing anything else. Make sure we have enough numbers of key types for every lock. If so, the case is good to go.
http://ivoroshilin.com/2013/09/11/google-code-jam-qualification-round-2013-problem-d-treasure/
1. Check that the number of chests matches the number of corresponding key types. A simple arithmetic to count. Otherwise there is no solution as we don’t have enough keys to open all chests.
2. All vertices in a graph G should be reachable from vertex v0.
The restriction isn't annoying: it is a very strong clue indicating the nature of the solution (branch and bound with lexical enumeration).

int N, K;

int initialKeys[40];
int chests[20][40];
int chestKeys[20];
int chestType[20];

vector<int> mem[1<<20]; 

void solve( ostream& cout ) {
    // base case:
    mem[0] = vector<int>(0);
    const int INF = N*(N + 1);
    // Try each of them:
    for (int mask=1; mask <(1<<N); mask++) {
        // A single element containing infinite is our way to mark a state
        // as having no possible solution.
        mem[mask] = vector<int>(1, INF);
        
        // Count the number of keys of each type:
        map<int, int> keys;
        for (int i = 0; i < K; i++) {
            keys[ initialKeys[i] ]++;
        }
        
        for (int j=0; j < N; j++) {
            if ( !( (1<<j) & mask ) ) {
                keys[ chestType[j] ]--;
                for (int k = 0; k < chestKeys[j]; k++) {
                    keys[ chests[j][k] ]++;
                }
            }
        }
        // don't worry, if any number of keys is negative, this state will
        // never be reached from an upper state, so its result would not matter
        for (int j=0; j < N; j++) {
            if  ( (1<<j) & mask ) {
                if (keys[ chestType[j] ] > 0) { // We can open chest j.
                    // Find out what happens if we open chest j:
                    vector<int> other = mem[ mask - (1<<j) ];
                    // If there is a solution, append j:
                    if ( (other.size() == 0) || (other[0] != INF) ) {
                        vector<int> nw( other.size() + 1);
                        nw[0] = j+1;
                        for (int i=1; i<nw.size(); i++) {
                            nw[i] = other[i-1];
                        }
                        // Remember the best solution so far.
                        mem[mask] = std::min( mem[mask], nw) ;
                    }
                }
            }
        }
    }
    // Result is f( (1<<N) - 1):
    vector<int> &res = mem[ (1<<N) - 1];
    
    if (res[0] != INF)  {
        cout << res[0];
        for (int i = 1; i < N; i++) {
            cout << " "<<res[i];
        }
    } else {
        cout << "IMPOSSIBLE";
    }
    cout << endl;
}
Read full article from Dashboard - Qualification Round 2013 - Google Code Jam

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