EDIT. The contest is over, I won't be updating the document anymore. Here are the problem statements: https://docs.google.com/file/d/0B2d37tm1YmE3dnNtOFBNOU85QzQ/edit?usp=sharing. And here's the log:
15:04 - so we seem to have 8 problems, penalty time 1178. Thanks to everybody who was following our contest! I’m sorry we didn’t post much in the last couple hours - things got really intense and we were too drawn into solving problems. For example, in the last 10 minutes Jakub was working as a mutex by physically blocking either me or Bruce from using the keyboard.
15:01 - several switches between K and E, but couldn’t get either to work :( So we’re done with 8 problems. What’s our penalty time?
14:48 - Submitted I :) K or E? I accepted.
14:30 - Jakub proposed a much better solution for K - for every substring (set of letters that appear consecutively in all 3 strings) and a combination of three recursion methods, find the lex-smallest tree that is produced from that substring. Finishing E, then going to do this for K.
14:18 - now comes the hardest time - to choose what to do :( After we finish E, should we write I or optimize K?
14:13 - Sped up K a bit, finally submitted - time limit exceeded.
14:03 - we’ve read the statement for I, and it turns out to be not that difficult :) Apparently we can iterate over left and right boundaries and then the problem becomes 1-dimensional and simple.
13:52 - we’ve submitted B, Bruce is back to E. B is accepted!
13:41 - we seem to have got rid of numerical stability issues in B, the only question is to pick boundaries now. Going to try nested binary search.
13:33 - Bruce still coding E, Petr and Jakub are simplifying the formula in B. Getting close to a solution there!
13:16 - Petr tried to add some pruning, but it turns out to be not so easy. Bruce resumed E. While Petr was doing pruning, Bruce and Jakub could speed up the solution for E a bit :)
13:02 - Petr finished coding K, but it’s too slow without any pruning. Will need to add pruning at some point, right now Bruce started on E.
12:37 - we decided to write K first, Jakub will just look at his code in the meantime.
12:34 - Jakub found a bug in his code, now the hypothesis works for the sample input! We have to speed it up to work properly on “99.99 49.99” case, Jakub is working on that.
12:29 - The hypothesis doesn’t work out at the moment, so Petr is starting on K. Basically checking all possibilities, with some pruning.
12:23 - But ITMO already has 7 :) It will be hard to catch them. Now Jakub is testing a quick hypothesis in B.
12:22 - Petr got H accepted. The idea is somewhat standard - what is the smallest number of steps required to assemble each subsegment. The straightforward implementation is O(n^4) though, so one has to eliminate one n from the DP transition.
12:04 - J accepted as well! The bug was: to check if a circle arc is inside or outside the polygon, we should take the middle of the arc, not the middle of its base segment.
12:02 - C accepted!
12:00 - while Jakub was coding C, Petr and Bruce have re-read the solution for J and found one bug. Now submitted C and fixing the bug in J.
11:47 - got WA on J, Jakub is starting on C. It’s simply maximum flow.
11:42 - well, we can just try all trees - there should be only so many rooted trees with 26 vertices (with labeled left and right subtrees for each vertex).
11:36 - K looks approachable. There are only so many possible Pre/Post/In combinations, and then we need to somehow build the tree. The problem is, of course, is that we don’t know when we descend and when we ascend.
11:31 - Bruce has coded almost complete solution for J, now Jakub is typing a formula for the area of a “circle trapezoid” over his shoulder.
11:28 - meanwhile, Jakub is ready to code C and Petr is ready to code H. Now that we have a solution for all problems that have been solved by at least one team, let’s try the difficult ones :)
11:10 - now Bruce started writing a solution for G. It looks like it’s simply taking a hundred of linear constraints on a toroid... But how to solve two equations on a toroid? So Bruce started on J instead. There we simply need to intersect segments with a circle, and then take a signed sum of areas of trapezoids in the usual way.
11:09 - We got D accepted on our third try. Interestingly, the only optimization we added is memoization of DP states across test cases.
11:01 - A is accepted!
11:00 - The most difficult part was to notice that pieces can be reflected. Without that property, the problem is much more difficult. Submitted.
10:54 - Petr going to solve A. Just check if a graph has cycles.
10:49 - apparently Jakub didn’t factor in the fact that we have 1000 testcases. Optimizing now :)
10:44 - sent D, time limit exceeded :( And another TLE.
10:35 - Accepted! Hopefully we’ll get faster from now on :) Jakub still coding D.
10:33 - Petr found a bug: integer overflow :( Resubmitted.
10:27 - Jakub started by writing D, then thought his solution is too slow (O(num_divisors * log^2(n)), so Petr started solving F, got two Wrong Answers. Now Jakub is continuing to solve D, while Petr is trying to find bugs in F. Statement of B looks easy but somehow we can’t find a solution yet.
10:09 - we spent about 10 minutes looking for a room, didn’t find one, so now we’re solving in the hall. Jakub is solving D!
9:50 - John Clevenger explains the final technical aspects. Just 7 minutes to go.
9:44 - They’re using the big under-the-roof hockey scoreboard! Right now it shows a lot of Windows console java.net...Exceptions :)
9:40 - Roman Elizarov is trying to make teams nervous by emphasizing how great the competition is, using the microphone :)
9:39 - The scoreboard at http://myicpc2.icpcnews.com/ confirms 11 problems.
9:31 - There are special balloons for the first team to solve each problem, and one (heart-shaped :)) for the very first successful submission. So the very first successful submissions yields 3 balloons.
9:30 - According to the balloon color guide, there are 11 problems: A - Red, B - Black, C - Turquoise, D - Yellow, E - Dark Pink, F - Blue, G - Burgundy, H - Green, I - Orange, J - Pink, K - Teal.
9:24 - The link to submit problems after the contest starts: https://icpc.kattis.com/problems.
9:18 - the scoreboard still shows Dress Rehearsal results, and links to Dress Rehearsal problem statements.
9:14 - apparently the contest starts at 10, not 9:30. So about 45 more minutes before the official contestants see the problems, about an hour before we see the problems.
9:10 - a lot of people around have red badges - apparently those are press representatives. This makes it easier for teams to ignore them during the contest, I guess :)
9:04 - Egor’s blog at http://codeforces.ru/blog/Egor is awesome in many ways, but one of those ways is that he seems to be going to post a lot of pictures :) There won’t be too many pictures here, so don’t forget to check updates from Egor, too!
9:03 - You can ask questions at petr-mitrichev.blogspot.com/2013/07/acm-icpc-2013-world-finals-live.html, we’ll do our best to answer them.
8:56 - live comments about the teams and various scoreboard links are at http://codeforces.ru/blog/Egor.
8:52 - Unfortunately the public version of this document updates every 5 minutes or so. I couldn’t find a better way to have 3 people update the same text and have it viewable publically at the same time.
8:50 - Here’s our plan for today: myself, Bruce Merry and Jakub Pachocki will solve the contest together with the actual World Finals participants (only starting about 15 minutes later, as the statements are distributed to the public), and while one of us will be using his/her own laptop to code a solution, the other two will solve other problems and share our thoughts here.
8:48 - Press are trying to interview contestants, but those are quite nervous.
8:45 - People are gathering inside and around the Yubileyniy ice hockey rink. Apparently there’s no traffic when you have a police escort, and buses arrived here early :)
No comments:
Post a Comment