Thursday, February 25, 2010

Codeforces

My friends from Saratov are building a new system for hosting contests and beyond. They aim for everything there to be available both in English and in Russian. Today was its second beta-test, which was a contest under ACM ICPC rules for 2 hours with 3 problems. Results: http://codeforces.com/contest/2/standings. Problems: http://codeforces.com/contest/2.

Problem B is very nice. I scratched my head for a long time before getting it, yet the idea is very simple and beautiful. I won't spoil it yet - I hope you'll enjoy solving it as well :)

Problem C turned out to be a tough implementation problem for me (I solved a system of two quadratic equations on 2 variables by eliminating the squares to get a linear equation, substituting one variable from that linear equation into one of quadratic equations, and solving the result. This required a lot of care about precision issues and corner cases, and took an hour). However, I have a feeling that it is doable by some binary/ternary search. Any ideas?

Tuesday, February 23, 2010

World Finals Recap

Here're the comments that I've posted during the ACM ICPC 2010 World Finals in Harbin.

09:08 - Everyone is still waiting on the spectator balcony, teams
are still kept away from the competition room. Problem statements have just
been distributed to team workstations.

09:20 - Still nothing happens. The competition is more likely to start at 10 than at 9:30.

09:23 - Teams are starting to come in.

09:26 - spectators are cheering all the time as the teams take their seats.

09:32 - all teams are at their workstations.

09:35 - Bill promises to start the contest at 10am sharp.

09:43 - they're testing the new procedure for photographing the team with their first baloon and with the first baloon for any particular problem.

09:44 - by the way, is the video stream live yet? Maybe it's unnecessary for me to explain what's going on? Please answer at the forum thread above.

09:54 - I've moved to the watching auditorium so I'm watching the same video stream as everybody on the Internet (hopefully) does now.

09:58 - The contest has started!

10:00 - 11 problems. They promised to get the problems to spectators in several minutes.

10:04 - we got the problems. Hopefully they'll be available on the Internet soon as well.

10:06 - problem C is: given a n times m map, with at most w 1-cell-high horizontal walls, find out the number of cells from which you can't get to the top right corner by moving top and right. The coordinates are up to a million, w is up to a thousand. The solution seems obvious - first you compress the coordinates (find all distinct ones) to get at most 1000 distinct ones, and then do a simple DP.

10:11 - problem E is: given a 20 times 9 field with some cells occupied by rocks, find the longest path from top left corner to bottom right corner that doesn't touch itself. 20 times 9 dimensions point us to DP on subsets or something similar. I believe something like that should work: go through the table row-by-row, and keep which cells in the bottom row are connected to which, and which are not occupied at all. Quite hard to implement correctly, but the algorithm is not very complicated.

10:17 - problem G is: given at most 100 points on a plan with distinct x-coordinates, find the shortest cycle that passes through each point exactly once, goes from the leftmost point always to the right until it reaches the rightmost point, then goes always to the left until it gets back to the leftmost point. Additionally, two points are given such that the the path from left to right contains the first point, and the path from right to left contains the second point. This seems to be a very simple DP: after processing the last k points, and with the first path ending in point a and the second path ending in point b, what is the smallest total length to achieve that? This is O(n^2) states, transitions in O(n). We deal with the two special points by forcing the first path to contain the first one, and the second path contain the second one.

10:23 - problem J is: given a rectangle, is it possible to split it by repeatedly splitting it into two parts along a line parallel to a side into several rectangles with the given areas. Maybe we can solve that by trying to do a DP over (rectangle, part sizes multiset)? Since the area of the rectangle should match the sum of part sizes, it seems that the number of states will be reasonably small.

10:24 - Belarusian State University has solved problem J. Many wrong attempts on other problems.

10:29 - Cornell has solved G. I will probably stop commenting on most submissions since the scoreboard is readily available anyway.

10:33 - Problem D has been solved as well. The statement is: given a tree of castles, you need to capture them all. For each castle, you know how many soldiers you need to capture it, and how many will disappear during the process, and how many you should leave in the castle afterwards. It seems that you should just add up the last two numbers. Additionally, you may traverse each road at most twice, which essentially means you should do a normal tree traversal, and the only freedom you have is to choose the order of visiting the children of each vertex in the tree. So the solution seems to be: first, check all possible poits to start the attack - the root of the tree. Then, for each vertex we calculate the best way to capture the subtree rooted at each of its children, and then figure out the best order to visit that subtrees given the total number of soldiers required to capture each subtree X and the total number of soldiers that must be left in that subtree Y. Figuring out the order seems to be a classical problem after that - we should sort them by something like X-Y :)

10:50 - Problem I. When we split the path into four parts, each part has at most 16 cells, so we can just build all possible paths for each part (there're at most 3^16 of them, and in reality much less since we can't self-intersect, can't go outside the labyrinth and should reach the specific cell - so I hope there'll be just several thousands of those). Then, we group the paths by the set of cells they're visiting. Then, we combine the first part and the second part in all possible ways; then we combine the third and the fourth in all possible ways; then we use meet-in-the-middle to combine the complete path (for each subset covered by first two parts, we check if the complement can be covered by the last two parts).

11:12 - Problem B seems to be mostly about accuracy, as a lot of wrong submissions are showing, and many good teams are struggling with it. Generally, the first step of the solution is to separate narrow bars from large bars. To do that, let's take the smallest bar, and then all bars that are less than 50% larger than it should be narrow, and all others should be wide. After that, we should just check all given conditions carefully, and check that the lengths of the all narrow bars fall withing the specified plus-minus 5% of some number, the same for all wide bars.

11:21 - Problem A seems to be a not very complicated simulation. I expect some teams to attempt it in the first two-three hours. There's not much
I can say about the solution - you should just do what's written in the problem
statement, the constraints are reasonably small.

11:23 - the scoreboard is at Shanghai 4, Stanford and Moscow 3, others 2 and less.

11:31 - ACRush correctly suggests that the answer for problem I should be at most about 10000 (even without the constraints for 3 squares, it's in the millions), so pretty much any backtracking-style solution should work in time.

11:41 - Problem H doesn't have constraints, so it's unclear what is
the expected running time. Generally, the approach for this problem should
probably be the same as for the 2-dimensional case of this problem, which is
to go over the vertices from bottom to top, merging the lakes until they reach a point where the water can pour out of the lake. In 3-D this will require a lot of code, like finding the intersection of a horizional plane with the 3-D triangle, but the logical 'pouring' part should be the same as in 2-D case.

11:47 - ACRush points out that in problem B there's no example on the case where the barcode is reversed, which is mentioned only once in the problem statement and is easy to miss. Maybe that's why the teams are struggling with this problem.

11:56 - Problem F. The first step is to notice that since we need to find the total length, we can solve the problem separately for each triangle. Within each triangle, the countour lines are parallel to each other, so we should find one of them and the distance between them, and then carefully find the total length as the sum of two arithmetic progressions. This seems fairly easy to implement, but one has to be careful with the boundaries. There're at most 10K triangles, so we can afford some processing for each of them.

12:04 - Problem K seems to be straightforward from the algorithmic side as well. We try to place it on each side, and just have to carefully calculate
the position of the center of mass and check for stability. The geometric part
is quite standard 3-D routines (for rotating) and 2-D routines (for checking
that projection of the center of mass is at least 0.2 away from the border of the base). The most complicated part seems to be dealing with various possible 'bases' for the paperweight when the figure is not convex.

12:09 - so that's all for my guesses about each of the problems. It seems that there's no really complicated algorithmic background to any of them, and they mostly require careful implementation. Two of them are 3-D geometry, five of them
are DP, the rest are mostly straightforward but tricky implementations.

13:33 - The contest is going, there seem to be 5 problems that are solved by the top teams, and then there are 4 more problems that are solved by at least one team. The contest can still go to any of the top teams.

13:35 - Regarding competing together with ACRush - yeah, if they make an online contest next year, that should be a good thing to try :)

13:42 - They've finally enabled WiFi for coaches!

13:42 - From the 6 "remaining" problems, I think the ordering from the easiest to the hardest is K-F-A-I-E-H.

13:45 - They said they won't be distributing the balloons in the last hour, so I won't have any insider information to share :(

14:00 - So no more updates on accepted/rejected on the scoreboard. They're going to show the submitted runs, though.

14:03 - They told at the ICPC Live stream that SJTU have submitted their code for problem K on problem H, so it was either a mistake or they wanted to mislead other teams.

14:31 - Moscow State University and Warsaw University teams were happy
when they saw the outcomes of their respective runs, so it seems that they have
7 and 6 solved problems now, respectively.

15:16 - Results: Spb IFMO - 22nd. KTH - 12th. Fudan - 11th. Zhongshan - 10th. SpbSU - 9th. Warsaw - 8th. Saratov - 7th. Tsinghua - 6th. Petrozavodsk - 5th. KNU - 4th. Taiwan - 3rd. MSU - 2nd. SJTU - 1st.

16:23 - I've tried to upload a photo of the final scoreboard, but it turns out it is already available at http://uaimages.com/viewer.php?id=383434bord%201-21%20v2.png.

16:24 - Generally, SJTU obviously are very happy with their results, with many other medalists being disappointed they couldn't get better. For example the Bronze medal SpbSU have the same penalty time as the Silver medal Warsaw.

16:25 - Also, it seems that everyone here believes that Ural SU will also get a bronze medal for their 13th place since they're the only team except the first 12 to solve at least 6 problems.

16:25 - That's pretty much it, I think I won't be posting frequent updates here anymore, but may post some more news if I find them.

16:32 - The Moscow State University was trying to solve problem I as did the SJTU team, and both had a complete solution but failed to debug it. Spb IFMO team tried to solve two problems in the end and couldn't get any of them.

17:22 - The awards ceremony is going on. As Oleg Hristenko has rightly pointed out, we are still to announce some regional champions, and the results of the Russian teams that didn't make it to the first page of standings that was posted on the Internet.

18:00 - ICPC Challenge results: 4th place Saratov SU, 3rd place IME-USP, 2nd place Beijing Jiaotong, 1st place U of Canterbury.

18:24 - Tatiana Churina of Novosibirsk SU together with 6 other coaches (I'm being Russia-centric, I know :) got the Coaches' Award.

18:37 - Belarusian SU receives \$1000 for getting the first accepted solution.

18:38 - Moscow SU (F), National U of Taiwan (I), NTU KPI (D), Kiev NU (B), Spb IFMO (C), SJTU (E), U of Wroclaw (K), U Maryland (H), Cornell U (G), Fudan U (A), Belarusian SU (J) are recognized for being the first to solve a particular problem.

18:48 - Africa and Middle East champion - British U in Egypt. Latin America champion - UF Pernambuco. North America champion - Stanford U. South Pacific champion - U of Western Australia.

18:54 - the medals are official! 4 gold + 5 silver (including SpbSU) + 4 bronze (including Ural SU). You know the rest, so I won't be posting the teams winning the medals again :)

19:02 - going to the stage with the Moscow SU team :)

Thursday, February 4, 2010

ACM ICPC 2010 World Finals

I hope to be posting updates on the ACM ICPC 2010 World Finals here if I manage to get an internet connection in the Harbin Engineering University: http://77.41.63.3/icpc2010/finals.html.