ACM ICPC 2011 World Finals

Here's my (hopefully) live commentary from the ACM ICPC 2011 World Finals. This post will be updated as the contest goes on.

8:31 - there's a big countdown screen that shows 28 minutes before the start of the contest. The rumor has it that the Peabody ducks will walk on the contest floor before the contestants :)

8:38 - 21 minutes before the contest start, the teams are coming in, right after 5 ducks.

8:43 - 16 minutes before, everyone is seated. I guess it's now up to Bill to entertain everybody.

8:50 - 9 minutes before, Bill is trying hard.

8:53 - to Adrian: I would expect after about 1 hour of the contest. We might try to publish the photos if we get them earlier :)

8:53 - 1 minute before! It looks like they decided to skip some minutes.

8:55 - the contest has started! It looks like there's 11 colored balloons.

8:56 - unlike yesterday, the scoreboard on the big screen is working. Teams are sorted alphabetically for now.

8:58 - no problem statements for spectators yet.

8:59 - no submits yet.

9:02 - live scoreboard from Kattis appears at http://scrool.se/icpc/wf2011/.

9:05 - we got the problem statements from Tatyana Churina!

9:13 - SPbSU and SPbSU ITMO solved K! No other submissions were visible before the scoreboard went down.

9:14 - according to zibada's chat, Perm solved K as well.

9:19 - photos of problem statements are being uploaded to Picasa. Sorry for the poor quality, hopefully it's still readable.

9:22 - 13 teams have solved K, no other submits. Time to look at the problem statements…

9:24 - problem K is classical: find the two parallel lines closest to each other that will fit the given polygon (maybe rotated) between them. It's not hard to see that the line must be parallel to the line connecting some pair of vertices, so you can just try them all. For even faster solution, we should just check adjacent vertices of the convex hull.

9:28 - problem C is quite straightforward as well. You are given 6 pictures of hieroglyphs, and need to write an OCR that will recognize them. The constraints say that the hieroglyphs in input may be distorted by the shape will be "topologically equivalent" to one of the 6 given pictures. The pictures are chosen such that one can just check the number of connected components of the white pixels (kudos to andrewzta for noticing that).

9:30 - meanwhile, there are lots of teams that solved 1 problem. All solved K except Tsinghua, who solved C, and Shanghai, who solved E.

9:33 - problem E is: given at most 500K points on a 1000x1000 grid, and at most 20 queries X, find the X by X square in (x+y, x-y) coordinates that has the most points inside.

9:34 - the constraints are so low that I believe the straightforward solution should pass: using inclusion-exclusion we can find the number of points in each square in O(1), then we can just check 20 million squares.

9:36 - it looks like official problem statements are up at http://cm.baylor.edu/digital/icpc2011.pdf. I hope you've enjoyed my photos in the meantime :)

9:39 - problem J, which several teams have attempted but failed, is: given a number C, represent it as a sum of numbers of form a_i=i*(i+1)*(2i+1)/6, b_i=4*i*(i+1)*(2i+1)/6, c_i=a_(2i+1)-b_i (sums of squares, sums of even squares, sums of odd squares). Each a_i, b_i, c_i may be used at most once. If there are several representations, choose the one with the smallest number of addends. If there are still several ones, pick the lexicographically largest one.

9:43 - meanwhile, three teams have 2 problems: SPbSU and SaratovSU have J and K, Tsinghua has C and K.

9:44 - 6 teams with 2 problems now: NNSU and Hangzhou have E+K, Taurida has J+K.

9:45 - I would expect that simple backtracking (trying all possible choices for the next number in decreasing order, and truncating the search when current best answer is less than remaining sum divided by the maximum possible value for the rest) works for J, since the numbers are quite dense and thus the be split will always be found very quickly.

9:48 - 3 problems solved for Tsinghua, C+J+K.

9:50 - problem A, which is the only remaining problem that has attempts on it, is the following: given two numbers a and m, and two segments [p, q], [r, s], one must create such sequence of operations +a and *m that will transform every number in [p, q] into some number in [r, s].

9:51 - moreover, one should output the program of minimum length, and smallest lexicographically among those with minimum length.

9:59 - here's one idea: even if we add before we multiply, we still add a multiple of a. So in order to check what is the minimal number of steps required to transform a given segment [q, w] to become a segment inside [r, s], we can just iterate over how many times k we multiply, check that there's a multiple k*a of a that, after being added, will move the result inside [r, s], and the number of steps will be the number of multiplications plus the sum of digits in k when written in m-ary system (roughly). So in order to solve this we must solve a sub=problem: given a segment [l, r], what is the number with the smallest sum of digits (in m-ary system) inside that segment? That is a standard problem that is solved by considering the number of digits of that number that coincides with corresponding digits of l (or r).

10:04 - The above solution yields the lexicographically smallest representation as well if implemented carefully. This looks quite tricky to implement, though. KAIST is the only team to solve the problem.

10:06 - The top of the scoreboard is: Saratov, Zheijang, NNSU, Taurida, Tsinghua - all with 3 problems.

10:10 - Problem G is: you are given N segments connected in one row via flexible joints, and you need to assemble one or more polygons in such a way that every segment is a side of at most one polygon and the segments are not allowed to intersect except at endpoints. Your goal is to maximize the total area of the polygons.

10:14 - Tsinghua got 4! A+C+J+K.

10:16 - There are at most 500 segments in problem G. I guess the first question is does it ever make sense to form more than one polygon?

10:19 - Yes, obviously it does. Suppose one middle segment is much, much longer than the others so no polygon can be formed using it. In this case, the segments to the left and to the right of this segment should be treated independently. We can then build similar examples in each part to have the best answer include even more polygons.

10:21 - What doesn't make sense is to have one polygon have non-consecutive set of segments as its sides - we obviously can increase the total area by joining this polygon with the adjacent one then. So it seems that the solution should be: for every [l, r] part of the given sequence of segments, find the best polygon (this is a standard problem). Then, run a standard DP to find the best total area.

10:24 - The only trick I guess is to solve the "standard problem" for so many cases. The standard solution, as Google tells us, is that the optimal polygon with the given sides is a polygon inscribed in a circle, and we can find the radius of the circle by binary search. But that gives a running time of O(n^3*log(precision)) which may be too big.

10:30 - I would expect that it is fast enough, since n^3 is divided by 6 (the number of segments is n^2/2, and the average length of one is n/3). With the super-fast computers, that should be fast enough.

10:32 - Three teams have 4 problems: Zhejiang, Taurida, Tsinghua.

10:48 - problem H is: given a graph, you need to mark the smallest number of its vertices in such a way that after removal of any vertex, there's a path from any vertex to some marked vertex. Unless I'm missing some corner case, this is reasonably straightforward (suggested by Burunduk1): first, we find the tree of biconnected components of the graph, then we choose one vertex in each of the leaves of this tree (in each biconnected component that is a leaf, we must choose a vertex that is not the articulation point that connects this component to the rest of the graph). In case the entire graph is biconnected, we must mark any two different vertices. This is obviously less than the optimal answer since all those marks are required (what happens if we disconnect a leave of the biconnected component tree?), and it's not hard to see they are sufficient.

10:48 - SPbSU, NNSU, Warsaw and Ural also have 4 problems solved.

10:56 - as discussed offline, I expect the winner to solve 8 or 9 problems.

11:02 - problem D: you are given a 40x40 grid of ".", "/" and "C" letters. Your goal is to replace as many "."s by "W"s as possible in such a way that: the total number of "C"s and "W"s in each row and column is at most the given fraction of total number of "C"s and "W"s, and the total number of "C"s and "W"s in the first row is equal to the total number of "C"s and "W"s in the first column, the same for second row and second column, and so on.

11:14 - NNSU has 5.

11:18 - problem F: you are given 100000 machines, each described by the day it appears on (D_i), the price to buy it (P_i), the money you get when you get rid of it (R_i), and the profit it brings on each day (G_i). You may own at most one machine at a time, you can get rid of an old machine and buy a new one in one day, a machine brings profit only on days between the one when you bought it and the one when you got rid of it (exclusive). You can only buy a machine exactly on the day it appears on, and you start with the given amount of money C. What is the maximum possible profit?

11:21 - this actually looks solvable: first, let's start with straightforward N^2 DP: we solve the problem "what is the most money we can earn from the previous machines if we buy k-th machine on the day it appears" by iterating over which machine will we buy before k-th. Then, we will optimize the solution to work in O(N*polylog(N)). More specifically, suppose the previous machine is m-th. Then the maximum profit to get before buying k-th machine is ans[m]-P_m+R_m+G_m*(D_k-D_m-1), and we can only do this if ans[m]+C>=P_m. The second condition doesn't depend on k at all, and the first only depends on D_k. So essentially when choosing the best m for the given k we're choosing the highest among several linear functions of D_k. We can find that quickly, for example, by keeping track of the convex hull of the existing functions.

11:34 - meanwhile, Zhejiang, Tsinghua and Saratov also got 5.

11:36 - and Tsinghua got 6.

11:49 - problem B is: you are given integer coordinates of 3 points before and after the following transformation: first, you rotate the plane such that Ox axis passes through an integer point on the border of [-10,10]x[-10,10] square. Then, you round the coordinates (up in absolute value if the fractional part is 0.5). Then, you multiply all coordinates in each axis by a non-zero integer (different for different axes). And then, you add an integer constant to all coordinates in each axis (different for different axes). You're asked whether there exists such transformation for the 3 given points, and if yes, whether those transformations transform each integer point in the same way. It looks like one can just iterate over all possible rotations, then find scaling and translation numbers based on linear equations, and then check the resulting transformation. The biggest difficulty I guess would be handling corner cases where all points have the same coordinates and suchlike.

11:50 - meanwhile, Zhejiang also got 6 and is in second place.

11:56 - SPbSU solves 6 and moves into second place.

11:58 - problem I is: you are standing in a cell of an infinite plane, and you have 100000 mummies going after you. Each mummy stands in some cell. You make moves in turn: first, you can move to any 8-adjacent cell. Then, each mummy moves to a 8-adjacent cell that is closest to you. You lose if at any point a mummy is in the same cell as you. What is the maximal number of moves you can survive?

12:02 - Moscow solves 5th problem but it's G! Now go for the easy ones! Saratov got 6.

12:32 - had a lunch break. Lots of teams with 6, teams with "standard" set of problems have better penalty time.

12:34 - and Tsinghua solves F. I didn't expect them fixing the problem so quickly.

12:47 - problem I solution together with FedorTsarev: first, let's assume that once the mummy catches us, it follows all our moves. It means that we need to find the largest time X such that we can be in a point distinct from all mummies at time X, and that can be done by binary search. To check a specific X, we believe the following proposition works: we take a 2X+1 times 2X+1 square with center in our position, and check if it's completely covered by 2X+1 times 2X+1 squares centered at mummies'. This relies on assumption that the way the mummies move in the problem statement is "optimal", but this is kind of obvious, since their move always provide strictly optimal distance to us both by x and by y. And checking if a square is covered by other squares can be done in O(NlogN) using the sweeping line method and keeping an interval tree that stores how many times each cell is covered.

12:47 - meanwhile, 1 team has 7 problems and 9 teams have 6 problems.

12:56 - the standings are frozen. The only problem for me to solve is D. I'm going to the contest room to watch the balloons brought to the teams.

13:13 - three teams in the 7/6 group have submitted problems, but none of them seems to have the corresponding balloon, so it looks those were wrong submissions.

13:20 - still no new top teams with non-standard balloon colors. Maybe they've stopped delivering them?..

13:30 - it looks like new balloons are indeed not delivered to top teams at all. Warsaw team were congratulating each other twice, so I assume they have 7.

13:32 - it looks like Moscow got A!

13:43 - no further updates. The only way to figure something out is to look at team's exctited/disappointed reaction.

13:45 - or maybe Warsaw actually has 6?

13:55 - the contest is over! Still no news.


13:59 - Saratov has 7.

14:08 - Taurida has 6.

14:15 - SPbSU, Saratov, Moscow, Nizhny Novgorod, FAU, Donetsk, Ural, Krakow all have 7.

14:17 - Zhejiang has 8! Warsaw and ITMO have 6.

14:20 - Waterloo has 7!

14:21 - Michigan has at least 7!

14:23 - most likely results: Zhejiang, Tsinghua, SpbSU, Nizhny, Saratov, FAU, Donetsk, Krakow, Moscow, Michigan, Ural, Waterloo.

14:29 - no, it's not! Zhejiang - 8, Michigan - 8, Tsinghua, SpbSU, Nizhny, Saratov, FAU, Donetsk, Krakow, Moscow, Ural, Waterloo - all 7.

14:40 - that's it. I'll probably not update this post anymore, unless some interesting comments surface. Thanks for following my blog today!