An algorithm for solving Google Code Jam tutorial problem C

Question

I'd like to understand the algorithm that solves Google Code Jam, Tutorial, Problem C. So far I wrote my own basic implementation that solves the small problem. I find that it's unable to deal with the large problem (complexity O(min(n, 2*k)! which is 30! in the larger data set).

I found this solution page, but the solutions are of course not documented (there's a time limit to the context). I saw that at least one of the solutions used the Union Find data structure, but I don't understand how it's applied here.

Does anyone know of a page with the algorithms that solve these problems, not just code?

Answer 1

Not sure if there's a better way to deal with this near duplicate of GCJ - Hamiltonian Cycles, but here's my answer from there:

The O(2^k)-based solution uses the inclusion-exclusion principle. Given that there are k forbidden edges, there are 2^k subsets of those edges, including the set itself and the empty set. For instance, if there were 3 forbidden edges: {A, B, C}, there would be 2³=8 subsets: {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

For each subset, you calculate the number of cycles that include at least all the edges in that subset . If the number of cycles containing edges s is f(s) and S is the set of all forbidden edges, then by the inclusion-exclusion principle, the number of cycles without any forbidden edges is:

 sum, for each subset s of S: f(s) * (-1)^|s|

where |s| is the number of elements in s. Put another way, the sum of the number of cycles with any edges minus the number of cycles with at least 1 forbidden edge plus the number with at least 2 forbidden edges, ...

Calculating f(s) is not trivial -- at least I didn't find an easy way to do it. You might stop and ponder it before reading on.

To calculate f(s), start with the number of permutations of the nodes not involved with any s nodes. If there are m such nodes, there are m! permutations, as you know. Call the number of permutations c.

Now examine the edges in s for chains. If there are any impossible combinations, such as a node involved with 3 edges or a subcycle within s, then f(s) is 0.

Otherwise, for each chain increment m by 1 and multiply c by 2m. (There are m places to put the chain in the existing permutations and the factor of 2 is because the chain can be forwards or backwards.) Finally, f(s) is c/(2m). The last division converts permutations to cycles.

Answer 2

The important limit imposed on the input data is that the number of forbidden edges k<=15.

You can proceed by inclusion and exclusion:

• calculate the number of all cycles ((n-1)!),
• for each forbidden edge e, substract the number of cycles that contains it ((n-2)!/2, unless n is very small),
• for each pair of forbidden edges e,f, add the number of cycles that contain both of them (this will depend on whether e and f touch),
• for each triple ..., substract ...,
• etc.

Since there are only 2^k <= 32768 subsets of F (the set of all forbidden edges), you will get a reasonable bound on the running time.

The analysis of the google code jam problem Endless Knight uses a similar idea.

Answer 3

Hamiltonian cycle problem is a special case of travelling salesman problem (obtained by setting the distance between two cities to a finite constant if they are adjacent and infinity otherwise.)

These are NP Complete problems which in simple words means no fast solution to them is known.

For solving questions on Google Code Jam you should know Algorimths Analysis and Design though they can be solved in exponential time and don't worry Google knows that very well. ;)

The following sources should be enough to get you started:

1. MIT Lecture Videos: "Introduction to Algorithims"

2. TopCoder Tutorials

3. http://dustycodes.wordpress.com

4. Book: Introduction to Algorithms [Cormen, Leiserson, Rivest & Stein]

5. The Algorithm Design Manual [Steven S. Skiena]