Google Code Jam. Qualification Round 2013. Problem D – Treasure. Solved.

1

This was the problem I wasn’t able to optimise with given time constraint in April.  Later I killed half a day to complete it thinking of different algorithms from the graph theory such as Eulerian path
and Chinese postman problems. I was surprised at that time this problem was put into qualification round as it is really challenging. In order to solve one the graph problem should be refined and modeled properly. During modeling a graph I used to always map only one type of entity to vertices.  As a counter-example a Bipartite graph has vertices which are divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V. The solution to this one has nothing to do with Bipartite graph attacking approaches except that there are 2 types of vertices.

The solution

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.

Construct a directed graph G=(V,E), where K is a set of all keys and C is a set of all chests:

  • V = {K} U {C} U {0}.
  • {0} = v0 is a starting vertex corresponding to the root vertex. Outgoing edges from it are key(s) given us initially.
  • E = {Set of all directed edges connecting K and C}. (i,j) ∈ E if either {i=chest, j=key} or {i=key, j=chest}

In simple words we have a directed graph where each vertex is either a chest or a key, directed edges form a  connection in between. We need to check that there’s a directed path between vertex v0 and every other vertex ∈ E, otherwise we cannot open all chests and solution is impossible. Note that we need to check directed paths to all key-vertices from v0. This is a standard single-source reachability and can be done applying a Depth-First-Search algorithm:

void dfs(Graph g, int v) {
marked[v] = true;
for (int w : g.adj(v)) {
if (!marked[w]) dfs(G, w);
}
 }

Technically, if there are unmarked vertices, the problem is unsolvable. Time complexity is O(E+V). This check cuts lots of branches saving us time.

Now let’s demonstrate the above on a real example. Our treasure trove consists of four chests, and you began with exactly one key of type 1.

See the table with input data:

Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             |  1                       |  None
2             |  1                       |  1, 3
3             |  2                       |  None
4             |  3                       |  2

Let’s draw a graph where v0 is a staring point of traversal (i.e. initial key of type = 1)

graph

As depicted there are 2 solvable configurations – <2,1,4,3> and <2,4,3,1>. All paths from v0 to the keys are reachable. The proof of this condition can done by induction and left to the reader.

3. Find a “lexicographically smallest” solution. This last condition added real hardness to the problem. If there are multiple solutions then we find a “lexicographically smallest” way to open the boxes. Each vertex is always traversed from lowest to highest, this can be achieved by constructing a graph using adjacency lists that reflect numbers of keys and chests in increasing order and we subsequently iterate them applying a bit optimized Depth-First-Search. Minimal configuration starts from v0. If we have  >= 1 key initially given, we just have to traverse from all of them increasingly. On each step we always update a number of keys in possession. If we’ve run out of keys then we cut the branch and backtrack, starting again where we left off with the next configuration. E.g. opening a chest No. 1 at the very first time will lead to the deadlock (actually this one is a trivial case as it is on step No 1). Such cases are not on critical path and we need backtrack only to the previous calling vertex.

Conclusion: There are not so many configurations unlike straightforward brute force. Many optimization problems like this one are met in algorithmic contests. Just algorithms and data structures are not sufficient. To pass given time constraint there should be the right strategy to cut unsolvable branches. That’s it!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s