Wednesday, September 27, 2017

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 x1, x2, ..., xm , 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 xai to vertex xbi the vertex closest to vertex pi must be the vertex qi.

If we look at the tree as rooted at vertex pi, the corresponding equation means that both xai and xbi must be in the subtree of the vertex qi, and there must be no child of qi such that both xai and xbi 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 "xi 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 xi must go to some vertex.

Second difficulty is ensuring that when we look at all subtrees which contain a given xi according to our boolean variables, they have exactly one vertex in their intersection that we can assign xi to. It turns out that this can be achieved using simple clauses "if xi 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 xi 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 xi is placed in that vertex.

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

Sunday, September 24, 2017

A 2-SAT week

The contests of July 31 - Aug 6 week started with the second competition day of IOI 2017 on Tuesday (problems, overall results, top 5 on the left). As expected, only the three highest scorers of day 1 had a real chance for the first place, and Yuta Takaya has grabbed this chance with the amazing score of 300 out of 300. Well done!

On Saturday, my fruitless attempts to qualify for the TopCoder Open onsite in Buffalo started with TopCoder Open 2017 Round 3A (problems, results, top 5 on the left, analysis). tourist has claimed the first place thanks to solving both the easy and the hard problem - congratulations - but qualification was also possible with easy+challenges, as Scott and Igor have demonstrated.

I could not figure out the solution for the hard problem in time, even though I suspected it would involve a reduction to 2-SAT from the very beginning. Can you see the way?

You were given a tree with n<=250 vertices and need solve a system of at most 250 equations on this tree with m<=250 variables x1, x2, ..., xm , 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 xai to vertex xbi the vertex closest to vertex pi must be the vertex qi.

Somewhat orthogonally to this particular problem, I felt like my general skill of reduction to 2-SAT could use some improvement. It seems that there are some common tricks that allow to replace complex conditions with just "or"s of two variables. For example, suppose we want a constraint "at most one of this subset of variables is true". It could naively be translated into n2 2-SAT clauses. However, we can introduce auxiliary variables to get by with only O(n) clauses: "bi must be true when at least one of the first i original variables ai is true" with clauses bi->bi+1 and ai->bi. Disallowing two true variables is then done via the clause bi->!ai+1.

What are the other cool 2-SAT reduction tricks?

Thanks for reading, and check back as I continue to remember August and September :)