A week of 22

The Aug 7 - Aug 13 week was centered around Google Code Jam final rounds. First off, the 21 finalists competed in the Distributed Code Jam final round on Thursday (problems, results, top 5 on the left, analysis). ecnerwala has snatched the first place with just 3 minutes left in the contest on his 6th attempt on D-small - here's for perseverance :) Congratulations!

One day later, the traditional Google Code Jam final round saw its 26 finalists compete for the first place (problems, results, top 5 on the left, analysis, commentary stream). Gennady.Korotkevich has won the Code Jam for the fourth year in a row - well done! He has given everybody else a chance this time by solving only two large inputs, but his competitors could not catch up for various reasons. SnapDragon was leading going into the system test phase, but he knew himself that his solution for D-large was incorrect as it was not precise enough. Second-placed zemen could have claimed the victory had he solved C instead of E-small or F-small or both in the last hour.

I have set the said problem C for this round, which went like this: you are given a number k between 3 and 10000. Output any simple undirected graph with at most 22 vertices that has exactly k spanning trees. I don't think it is solvable just in one's head, but if you have some time to experiment on a computer, I think it's an interesting problem to try!

In my previous summary, I have mentioned a TopCoder problem: given a tree with n<=250 vertices, you need solve a system of at most 250 equations on this tree with m<=250 variables x₁, x₂, ..., x_m , where each variable must correspond to some vertex in the tree. Several variables can correspond to the same vertex. Each equation has the following form: in the path from vertex x_ai to vertex x_bi the vertex closest to vertex p_i must be the vertex q_i.

If we look at the tree as rooted at vertex p_i, the corresponding equation means that both x_ai and x_bi must be in the subtree of the vertex q_i, and there must be no child of q_i such that both x_ai and x_bi are in the subtree of this child. At this point one had to strongly suspect this problem will reduce to a 2-SAT instance with boolean variables corresponding to "this variable is in this subtree". The equations are already in 2-SAT form on these boolean variables as described above, but the tricky part is to come up with additional clauses that guarantee that the values of boolean variables are consistent and we can pick one vertex for each variable.

First difficulty is that the tree is rooted differently for each equation. However, we can notice that each subtree of any re-rooting of the given tree is either a subtree of this tree when rooted at the first vertex, or a complement of such subtree. So if we have boolean variables for "x_i is in the subtree of vertex y when rooted at vertex 1", then the complementary subtrees can be expressed simply as negations of those variables, as each x_i must go to some vertex.

Second difficulty is ensuring that when we look at all subtrees which contain a given x_i according to our boolean variables, they have exactly one vertex in their intersection that we can assign x_i to. It turns out that this can be achieved using simple clauses "if x_i is in the subtree of a vertex, it's also in the subtree of its parent, and not in subtrees of its siblings", which are handily in 2-SAT form. We can then find the deepest vertex containing x_i in its subtree according to the values of the boolean variables, and it's not hard to see that all clauses will be consistent when x_i is placed in that vertex.

Thanks for reading, and check back later for more competitive programming news!