TopCoder Open 2012 Semifinal 1 Commentary

11:07 - that’s all for Semifinal 1. Join me later today for Semifinal 2, and then for the Wildcard! Semifinal 2 starting time: http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO+2012+Semifinal+2&iso=20121002T13&p1=867

11:06 - and the results are in! Tom’s 250 and Dlougach’s 1000 did fail indeed, so did Tom’s 500. All other solutions passed. Egor, ACRush, RAVEman to the finals, iwi, SergeiFedorov, Romka and sdya to the wildcard round.

10:56 - not much news from contestants. It looks like Tom’s 250 and Dlougach’s 1000 will fail, no news about other solutions.

10:49 - PaulJefferys got -25 on Tom’s 500 (not 250 which we know to have a bug), and on iwi’s 500, sdya got -25 on dolphiningle’s 500 in the last seconds. Waiting for systest!

10:47 - sdya killed exod40's 500. Apparently his resubmit was not for nothing.

10:45 - Since the difference between 7th and 8th place is 60 points now, it looks like it’s almost riskless for 7th or 6th place to challenge blindly.

10:43 - No more challenges yet, most people are reading Egor’s and ACRush’s solutions.

10:40 - Romka has killed Dlougach’s 250.

10:38 - dolphinigle has resubmitted both his 250 and his 500, sdya has resubmitted his 500. It would seem that dolphinigle has the best chance at challenging.

10:35 - And Dlougach submits 250 just 7 seconds before the end! Now it’s Egor, ACRush, Dlougach at the top. MikhailOK suggests the best challenge opportunity is integer overflow in 250.

10:33 - Some other contestants from China are recording ACRush's duplicate screen using a camera on their laptop. And he does submit his 1000 just 1 minute before the end! Egor has given up on his stresstesting since his stupid solution doesn't work on the first sample.

10:24 - Egor is writing a stupid solution for 1000 to compare with his solution on random testcases - great thinking! I think that's the best thing he can spend his time on now. Meanwhile, Dlougach submits 1000, not sure if he has changed his matrix to be of size k or have optimized his solution in some other way.

10:15 - And Egor submits 1000! I was right that his solution looks good.

10:10 - ACRush, Egor and Dlougach all seem on the right track in the 1000 - they have matrix power, and they have some formulas for the matrix. Actually, Egor seems to be the closest to our solution as his matrix has explicit formulas and has size k, which is the right thing to do. ACRush computes the matrix in some complicated way which doesn’t work. Dlougach seems to have the examples passing, but his matrix is not of size k but of size k^2, which presumably causes timeouts.

10:03 - ACRush, Egor and SergeiFedorov solved 250+500, iwi solved 500, everybody else except Dlougach solved 250, Dlougach still working on 1000. His projected score on 1000 is approaching scores everybody else has on 500, though.

9:59 - most people are implementing something with disjoint-set-union structure for the 500, so it seems that everybody is on the right track and we’ll see many 500 solutions, so many people will try to solve 1000 and thus it’s possible all three finalists will solve everything.

9:51 - ACRush and Egor have 250+500, everyone but the two people who started with 1000 have 250.

9:47 - 1000 solution - it was right there, but we were missing it for some time :) So we should do a DP with “how many last numbers are linearly independent” as the state. It’s straightforward to count how many ways are there to transition from a state to another state, since all situations are essentially the same: if we know that x last numbers are linearly independent, it doesn’t actually numbers what the numbers are themselves. And of course we do fast matrix power to handle that n can be up to 10^9.

9:39 - Meanwhile, ACRush has submitted 250 and 500 and 7 other people have submitted 250.

9:37 - The problem statement looks like Burrows-Wheeler Transform, but it doesn’t seem relevant to the solution.

9:34 - The 500: given a prefix of a permutation, find the lexicographically smallest permutation with that prefix that is one big cycle. I’ve test-solved this problem before the TCO so I already know the solution, but it’s actually quite straightforward anyway. When placing each unknown number in the permutation, we place it to the smallest possible number unless that number would form a cycle, in which case we place the second smallest possible number - it will not form a cycle in that case.

9:31 - it seems that Tom’s solution in 250 has an overflow bug.

9:26 - Essentially, it means that each k consecutive numbers must be linearly dependent as vectors in Z_2^(log m). This is always true when k > log m. When k <= log m, it looks like when choosing the next number, the only thing that matters is the dimension of the space defined by the previous k-1 numbers.

9:24 - The 1000 problem: count how many ways are there to choose n numbers each up to m (where m is power of two minus one) so that for each consecutive segment of k of those numbers (segments [1st, 2nd, …, kth], [2nd, 3rd, …, (k+1)th], and so on) some non-empty subset of that segment xors to 0.

9:19 - Problem statements as contestants open them: http://apps.topcoder.com/forums/;jsessionid=0CE09A8F5F29689F1259D2D102B38B34?module=Thread&threadID=763756&start=0&mc=2.

9:18 - And ACRush readily submits the easy. It looks like there’s no catch, it’s indeed straightforward.

9:14 - This problem looks straightforward. The white connected components actually correspond to triples of consecutive equal characters in each string, and the ones adjacent to the boundary are those adjacent to the boundary in at least one string. So it looks like the answer is something like total_length_of_white_in_A*total_length_of_white_in_B*total_length_of_white_in_C+(same for black)-total_length_of_white_in_A_not_adjacent_to_bounary*(same for B)*(same for C)-(same for black).

9:11 - Dlougach and iwi start with 1000, everybody else with 250. 250 problem statement: you are given three strings A, B, C. Let’s color 3D cell (i,j,k) white if and only if A[i], B[j], C[k] are all the same. Now we need to count the number of white cells that are in the connected components adjacent to the boundary. A, B, C are up to 2500 characters.

9:08 - One minute before start.

9:05 - Spectators can log into the arena, but the contestants can’t see their messages. However, they can see who’s in the room. It looks possible to pass some information that way (as in “I will enter the room if your solution looks wrong”).

9:02 - Jessie tells everybody to line up for introductions.

9:02 - 250, 500, 1000.

8:58 - Almost nobody is preparing, people are just walking around and chatting.

8:54 - Jessie says ten minutes before start.

8:53 - There seems to be some admin activity onstage. Apparently one machine is not working?..

8:50 - Exclusive commentary from Gennady Korotkevich - it turns out Gena is closely following the TCO and is watching this semifinal. He says that it’s a pity that rng_58 doesn’t get to defend his title - couldn’t agree more.

8:48 - And here’s the (one of) prediction contest current standings: http://snarknews.info/showvote.cgi?data=tco2012.

8:45 - The overview of all semifinalists: http://snarknews.info/index.cgi?data=tco/2012/finalists&head=index&menu=index&year=2012&contest=tco&class=tco2012. This round includes those with “1” in the last column.

8:43 - It looks like we have two Java coders - Egor and theycallhimtom. Everybody else is in the ugly world of C++.

8:38 - The contestants started preparations. Not much to do since Arena and plugins are already set up, and there’s no Internet access to set up additional software. As usual, C++ coders are writing #includes.

8:33 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Semifinal 1. They’ve just opened the arena but haven’t let the contestants to start preparations yet, so 12 anxious people are walking around :) I will post commentary by updating this post.

TopCoder Open 2012 - more arena flyovers

Here are some more videos that illustrate how TopCoder Open works.

TopCoder Open 2012 - arena video overview

Here's a less serious view at TopCoder Open 2012 - a standard "overview of arena" video, this time from a flying camera though :) Unfortunately the arena is quite dark and picture quality is quite bad. I'm trying to explain what's going on in the audio.

TopCoder Open: problem difficulty

Tomorrow is the first day of TopCoder Open 2012, and I'll try to blog on its algorithm track.

Here's a small analysis of TopCoder Open problem difficulty.

Let's consider the time taken to solve the problem as the ultimate measure of problem difficulty. Then, we can estimate the difficulty of, say, a medium problem in a TopCoder Open semifinal by comparing the solving time for this problem for each competitor with the solving time for other medium problems for the same competitor. More precisely, for each competitor in each TopCoder Open onsite round, I've compared the solving time for each problem with the solving time for this competitor in all rounds that took place in the same year, and the percentage of problems that were easier plus half the percentage of problems that were of the same difficulty is the declared measure of difficulty of the onsite problem for this competitor. The median of those numbers over all competitors is the difficulty of the onsite problem.

Here's the result:

TCO '03 Semifinals 1 98% 69% 79%
TCO '03 Semifinals 2 89% 81% 73%
TCO '03 Semifinals 3 92% 87% 68%
TCO '03 Semifinals 4 82% 78% 82%
TCO '03 Finals 91% 90% 81%
TCO04 Semifinal 1 87% 80% 67%
TCO04 Semifinal 2 92% 79% 67%
TCO04 Semifinal 3 84% 51% 64%
TCO04 Wildcard 66% 88% 72%
TCO04 Finals 86% 79% 87%
TCO05 Semi 1 91% 76% 64%
TCO05 Semi 2 90% 71% 64%
TCO05 Semi 3 78% 81% 64%
TCO05 Wildcard 88% 81% 64%
TCO05 Finals 91% 77% 74%
TCO06 Semi 1 93% 77% 69%
TCO06 Semi 2 75% 77% 68%
TCO06 Semi 3 88% 77% 70%
TCO06 Wildcard 66% 84% 71%
TCO06 Finals 66% 85% 77%
TCO07 Semi 1 65% 79% 68%
TCO07 Semi 2 89% 77% 66%
TCO07 Semi 3 86% 83% 65%
TCO08 Semifinal 1 64% 81% 62%
TCO08 Semifinal 2 85% 79% 63%
TCO08 Semifinal 3 76% 80% 63%
TCO08 Wildcard 94% 44% 66%
TCO08 Championship 96% 86% 64%
TCO09 Semifinal 84% 59% 60%
TCO09 Championship 95% 87% 56%
TCO10 Semi 1 89% 84% 61%
TCO10 Semi 2 87% 75% 53%
TCO10 Wildcard 81% 86% 57%
TCO10 Final 90% 54% 61%
TCO11 Semifinal 1 74% 73% 55%
TCO11 Semifinal 2 91% 84% 57%
TCO11 Wildcard Round 87% 90% 56%
TCO11 Championship Round 83% 78% 62%

You can see that the numbers for the hard problem are lower than those for easy and medium; the reason is that I consider "not solved" to be equal to "not solved", and thus when a person solves just 60% of all hards, the perceived difficulty of any problem will not exceed 80%.

With that effect in mind, the above list reveals that 'easy' problems are hovering around 90% mark (more difficult than 90% SRM 'easy' problems), while 'medium' problems are sometimes around 80-85% difficulty but sometimes have huge drops to just average difficulty, around 50%.

Another interesting slice of the same data is the list of competitors ordered by decreasing average difficulty of onsite problems. Here's the list, limited to only those competitors with at least 5 onsite rounds:



PaulJefferys - 6 rounds - 58%
reid - 5 rounds - 59%
tomekkulczynski - 5 rounds - 64%
Eryx - 6 rounds - 65%
gawry - 7 rounds - 66%
Yarin - 5 rounds - 67%
bmerry - 7 rounds - 67%
nicka81 - 5 rounds - 67%
antimatter - 5 rounds - 70%
liympanda - 6 rounds - 70%
ACRush - 8 rounds - 71%
Im2Good - 5 rounds - 71%
Ying - 5 rounds - 71%
ploh - 6 rounds - 71%
grotmol - 6 rounds - 72%
marek.cygan - 10 rounds - 72%
John Dethridge - 9 rounds - 73%
cyfra - 5 rounds - 73%
misof - 5 rounds - 74%
andrewzta - 7 rounds - 75%
tomek - 10 rounds - 75%
SnapDragon - 8 rounds - 77%
Petr - 11 rounds - 81%

So for PaulJefferys and reid, the onsite rounds are actually not much more difficult than normal rounds (I guess partially because they don't do much SRMs, and thus "normal" rounds are the TCO qualification rounds for them), while I'm actually the one who struggles the most at the onsites :)

Russian Code Cup 2012

Tomorrow is the day of the final round of Russian Code Cup (http://russiancodecup.ru/). Just several days before Gena turns 18, our last chance as Egor puts it :) There will be live broadcast on the website. I need your support! Click for date/time in all timezones.

This event itself is just marvelous! Today was mostly board game day, met a lot of friends, the atmosphere is amazing. Here's a picture from the event's place:

Here are some more recent TopCoder screencasts (double-click on the video for full screen):

SRM 548:

SRM 547:

TCO12 Round 3A:

SRM 531:

SRM 529:

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!