World Finals 2012: live coverage

The ACM ICPC 2012 World Finals are about to start at 10:00 local time (about 15 minutes from now). I will post live commentary here, please refresh this post to see more. There's also live TV stream at http://icpclive.com/ and a better scoreboard at http://zibada.ru/finals/.

9:49 - the teams are actually on the floor now, everybody is getting ready. There are 14 colors of balloons, so there are at most 14 problems. I bet for 12. The TV broadcasters announced the results of the poll, and apparently Warsaw is leading by far. They didn't see Petrozavodsk results :) Predictions at SnarkNews favor ITMO heavily.
9:59 - just one minute before start! Everything is very official and seems to go smoothly.
10:00 - the contest has started! The TV broadcasters have the problem set. When do we get it? There are L, meaning 12, problems.
10:11 - the problem statement pictures are being uploaded to https://picasaweb.google.com/108329321411299197209/WorldFinals2012Statements. Now on to solving problems :)
10:15 - problem B looks straightforward maths - count the volume of a circular solid bounded by a polynomial, which is integral of a polynomial as well (pi*poly^2). And restrictions are such that there's no precision issues.
10:15 - and Stanford solves B!
10:20 - MSU and SPb IFMO solve B, Warsaw and Tsinghua solve D. Usual suspects :)
10:24 - problem D is also straightforward: given a Fibonacci word, count how many times a substring appears in it. So we iterate over the size of the Fibonacci word, and count how many times it contains the substring, what is the longest prefix that is a suffix of the substring, and that is the longest suffix that is a prefix of a substring. When the fibonacci word is a part of the substring, we should probably remember all its hit positions. A bit of careful coding and you should be done.
10:25 - the TV broadcasters tell that Moscow IPT's solution on B was printing more than two digits after the decimal point, while the problem statement asks for exactly two. Moscow SU attempt K.
10:28 - Taiwan solves K.
10:30 - A simple solution for K by Pavel Mavrin (pashka): for each boundary a+0.5, we should have at most one stack after all splits that crosses this boundary. This makes it easy to make the splits greedily.
10:32 - PDF problem statements are at http://home.a-eskwadraat.nl/~kink/icpc2012.pdf. I will not repost the statements themselves for speed.
10:34 - Warsaw now has both B and D solved and is in the first place as the only team with two problems.
10:43 - A solution for C by Michael Levin (Michael_Levin) and Ilya Kornakov (ilyakor): first, for each subset we pre-calculate the shortest path that starts at 0, goes through this subset, and ends at i (for each i). Similarly, we do the same for paths starting at n-1. Then, we iterate over the subset of h/2 size, and combine the pre-calculated answers to find the best path when this subset is the "first half".
10:43 - Meanwhile, Moscow and SPb IFMO find bugs in their D's and have two problems each now.
10:44 - The broadcasters tell that the submitted solutions for L are too far from being correct, and that the submission on C is the first Time Limit Exceeded of the contest. Saratov also has B and D now.
10:48 - correction: all submitted solutions for L except the one that got OK :)
10:49 - IFMO solves K and moves to the first place with 3!
10:51 - A correction by Pavel Mavrin: we didn't cover the case where there's an initial set that has all plates equal, for example: "1,2,3" and "2,2,2". Probably that's why all teams are failing? It seems that in this case we just have to split one of "1,2" or "2,3".
11:03 - We've discussed L for some time. It looks like the game works like this: when it's my turn and I have the largest number, I should kill the largest number of the opponent. When it's my turn and I don't have the largest number, I should merge my two largest values. Does anybody have a counterexample?
11:10 - A solution for E by Ilya Kornakov, Alexei Tolstikov and Pavel Irzhavski: apparently the we can always get log(n)-sized cover greedily - by taking the vertex with the largest out-degree, which will be at least n/2 every time. For 75, we get a cover of at most 6. So we can iterate over all subsets of size 5 (there aren't too many), and if none of those gives an answer, we can get an answer of size 6 greedily. Beautiful!
11:12 - meanwhile, there are 4 teams with 3 problems: ITMO, Warsaw, Taiwan, Moscow.
11:18 - problem A: for each pair of edges, there are at most two moments when they become equal in length (since squared length is a parabola). So we can sort all such events, and then we can iterate over them, and each time a pair of edges changes order, we should check if removing the old-shorter one from the tree and adding new-shorter to it makes the tree still a tree. Quite straightforward. Solution by Michael Levin.
11:26 - apparently they've removed one wrong attempt by Moscow IPT on B since they were not sure "exactly 2 digits" was specified clearly enough.
11:30 - problem J seems to be mostly concerned with implementation: we should find out which pairs of airports can be connected by a path that lies completely within permitted circles. Since the circles are convex, so there's no "internal tangent" for them, the only places where we'll need to make turns is intersections of circles. Now we build a graph from airports and intersections of circles, and for each edge in that graph we check if it's completely covered by circles - by finding which segment inside that edge does each circle cover. Circular geometry makes this very difficult to implement, though.
11:38 - problem I also looks mostly-implementation. First, we trace the laser from the source and from the destination (this can be done in nlogn time by iterating over all mirrors in a row and in a column to find the "next reflection" for each reflection). Then, we have to find an intersection - a horizontal segment of the first path that intersects a vertical segment from the second path. This is a standard problem solved by a scanning line, for example: we go from left to right, and maintain a set of coordinates that have a horizontal line from the first set going, and the same for the second set, and use a range query to see if a given vertical segment intersects any horizontal line.
11:38 - citing a comment by Onufry:
------
The strategy you proposed for L does not work, but I hoped multiple people would think it does :) See, for example:
11 8
9 9 9 9
If you beat in your first move, you're dead. If you merge, you win.

I'm glad it caught you :)
------
11:41 - so we've still to solve F,G,H and L.
11:44 - meanwhile, the scoreboard doesn't change much. ITMO and Tokyo have 4, lots of teams have 3.
11:54 - Moscow IPT is now leading the contest with 5!
11:54 - problem G: suppose we've fixed the water pressure. After removing all vertices that are higher, the graph is split into components. Now we need to get from first component to last component while plugging all holes in those components that we visit. If we were able to connect multiple pipes to one open hole, that the rest would just be a shortest path...
11:54 - but "at most one pipe to a hole" restriction doesn't matter: if a shortest path tries to exit from the same hole that it entered, it will be shorter to just skip that component. So all we need is to properly merge components as we raise the water pressure and new vertices become available. Since there are just 400 important heights, it looks like we can get an O(n^3) solution that just reconstructs the entire graph each time. Hopefully that's fast enough.
12:14 - meanwhile, ITMO leads with 5, MIPT has 5, everybody else has less.
12:21 - problem H, again solution by Michael Levin: we need two observations. First, we need to pass all sides of the polygon in order, because if we don't, our path will be self-intersecting and thus could be made shorter. Second, if we pass a side of a polygon, then we must do it like a light ray does, otherwise the path won't be shortest again. Then, we can build a graph where vertices are polygon vertices, and edges mean "what is the shortest length to cover all intermediate edges", and those can be found by reflecting the polygon appropriately and connecting with a straight line. Since we can find all edges out of one vertex in one pass, this seems to be a O(n^3) solution which seems very fast for n=100.
12:26 - meanwhile, ITMO has 6, Moscow IPT and Moscow SU have 5, everybody else has less.
13:06 - sorry for not updating for so long. I've been trying to figure out the solution for L in the past 40 minutes, still trying.
13:24 - here's another attempt at L, joint with Egor Kulikov and Michal Forisek. First idea: if, after the opponent merges his companies, we can kill the result of the merge, then we'll be able to do that every move after that, and win. Suppose the first move we make is a merge. Then, according to the above argument, the result must be higher than the highest number of the opponent (otherwise we lose) and the opponent must be able to overcome that with his merge, otherwise we're guaranteed to win. So the only interesting case there is a_0+a_1>b_0, but a_0+a_1<b_0+b_1.
Now let's prove that it's never beneficial to kill not the highest company of the opponent. Consider the last time that happens in an optimal game, so we can assume that all moves except the first one will be either killing the largest company or merging. It's easy to see that we shouldn't kill b_2 or further, since then after an opponent's merge he'll win because of a_0+a_1<b_0+b_1. Now, suppose we kill b_1. Our opponent has two choices: merging b_0 and b_2, or killing a_0. Since in the remaining game the only two possible moves are merge and killing the highest company of an opponent, the game will basically end as soon as the "kill" move happens after a "merge" move according to the above argument. So the only way we can win is that eventually a_0+a_1+…+a_k>b_0+b_2+…b_{k+2}. But then a_0+a_1+…+a_k>b_0+b_1+…+b_{k+1}, so we would've won by just following the merge strategy from the beginning. A similar approach works for "killing a_0" choice, so it seems that we've proven that we should never kill not the highest company of the opponent.
Finally, as there are only "merge two highest" (I didn't prove that, too, but that seems kind of obvious) and "kill highest" move, and the game basically ends as soon as a "kill" move happens after a "merge" move by the opponent, it seems that there's a linear number of possible games that we have to consider ("merge-merge-….-merge-kill" and "kill-merge-merge-….-kill"), as two kills in a row are impossible.

13:49 - problem F. I know it's already been explained in the TV, but I didn't listen so have to solve by myself :) First, suppose we've fixed all rings disconnection operations. Then we can easily figure out what to do with the keys: for each connected component of rings, we should choose one type of keys and stick to it, and that should obviously be the larger type. The only difficulty here is when all components become of one type, but we can tackle that case separately. Other than that, it looks like a simple dynamic programming on a tree - we calculate the best answer when the top connected component in a subtree has a given number of keys in each type (or maybe we can even reduce that to a difference in the number of keys of each type, but it doesn't seem necessary given the constraint of 26).
13:49 - that means that now, hopefully, we have solutions to all problems. The problemset looks very nice and balanced to me!
13:50 - meanwhile, on the scoreboard IFMO has 8, MIPT and Warsaw have 7, Waterloo and Harvard have 6, everybody else has 5 or less. The scoreboard will be frozen in 10 minutes.
13:55 - Warsaw has 8! Their penalty time is terrible, though.
14:13 - not much happening inside the contest room. No balloons are delivered to teams that have 4 or more problems, so the only way we can get new information is by looking at teams' reactions.
14:17 - I don't understand what happens with ITMO - why they don't even submit?..
14:23 - spectators (Sergey Poromov and Lidia Perovskaya) think that Warsaw's submits on A are incorrect: after the second submit, there was no happy reaction and the person at the keyboard (Tomek) continued working with code.
14:24 - I'll take a lunch break now.
14:36 - Apparently the ITMO team was also not happy about their submission.
15:05 - so it seems that both ITMO and Warsaw have 9 - Warsaw's tenth was unsuccessful, at least that's what the signs they make look like :) They don't let us to meet the teams.
15:05 - Waterloo ended with 6, Kharkiv with 5.
15:14 - MIPT 8, Shanghai 7, Moscow SU 6.
15:16 - they're going to start showing the results soon.
15:27 - apparently the results announcement is delayed - there's some technical problem with the "changing scoreboard". Maybe it was showing not the latest results?
15:27 - SPb SU 5, Nizhny Novgorod 5, Saratov 6.
15:32 - Belarusian SU 7, BSUIR 6.
15:36 - Apparently some journalists approached ITMO asking to interview the champions, which looks like a semi-official leak :)
15:38 - Stanford 6, Harvard 7.
15:40 - is there a rejudge?..
15:45 - no, a rejudge seems unlikely. Apparently, the scoreboard stopped showing "yellow" attempts in the last 5 minutes, and they were unfreezing that bad scoreboard, that seems to be the reason for the hiccup. Meanwhile, Tokyo 6.
15:40 - Taiwan 5. It looks like 6 might even be a silver medal result?..
15:52 - Bill Poucher has indeed announced that there was a caching bug with the "resolver" - the moving scoreboard. Now they're going to start showing the results again.
15:57 - going through the 2- and 3-problem teams now, Udmurt SU is in 80th place.
15:58 - Ufa 66th, Altai 67th, both with 3 problems.
15:58 - Tomsk 60th, 4 problems.
16:00 - Volgograd 40th, 4 problems.
16:00 - Ural 29th, Latvia 28th, 5 problems.
16:01 - SPbSU 23th, 5 problems.
16:02 - Nizhny 18th, Kazakh-British 16th, 5 problems.
16:02 - Saratov 13th, BSUIR 12th, 6 problems.
16:03 - Tokyo 11th.
16:04 - Moscow 10th, 6 ptoblems.
16:04 - Waterloo 9th, 6 problems.
16:04 - Chinese U Hong Kong 8th, 7 problems. Harvard 7th, 7 problems, Zhongshan 6th, 7 problems, Belarusian SU 5th, 7 problems.
16:05 - Shanghai JTU 4th, 7 problems. Moscow IPT 3rd, 8 problems.
16:06 - Warsaw 2nd, 9 problems. ITMO 1st, 9 problems. Woohoo!
16:09 - So we have another 2-time ACM ICPC World Champion - Evgeny Kapun (eatmore at TopCoder and CodeForces). Congratulations!
16:10 - And thus I'm concluding this coverage. Thanks a lot for reading!