Monday, December 16, 2013

This week in competitive programming

 This week was very busy with contests. The week started with the second quaterfinal of the Kotlin challenge (problems in Russian, results in Russian, top 5 on the left). The round didn't go as smoothly as the first one, and the system had some downtime, so there will be a third quarterfinal to compensate those affected.

Then, Codeforces Round 219 took place on Friday (problems, results, top 5 on the left). Three out of four properties of an ideal contest held:
1) nobody solved all problems;
2) each problem got solved by somebody;
3) there's no problem solved by everybody.
The only missing part is
4) there's no contestant with zero problems solved.
But I guess the latter is quite hard to achieve in the Codeforces setting.

Saturday started with TopCoder SRM 600 which featured a T-shirt giveaway because of the round number (problems, results, my screencast, top 5 on the left). The screencast features two very long and probably boring situations: first, for the last 20 minutes of the coding phase I couldn't understand why my solution doesn't pass one of the samples, but couldn't. It turned out I was missing the fact that two lines can intersect in a point with non-integer coordinates, and it's unclear to me now how one can ignore this fact for so long. But even more disturbingly, during the last 13 minutes of the challenge phase I couldn't come up with a testcase for the medium problem with answer zero, but where there's exactly one way to reach zero. There's really no excuse for that.

Later that day, the second round of Facebook Hacker Cup happened (my screencast, top 5 on the left). With the format of competition penalizing very heavily for one's mistakes, the right strategy seemed to be to write two solutions for each problem, one fast and one slow, and compare them on many small testcases to make sure the fast solution is correct. That plan worked out well - but one may wonder if that strategy would be too slow to get into the top 25 in Round 3.

Just about 8 hours after the end of the Hacker Cup, on Sunday, the next stage of the Open Cup took place (top 5 on the left). The problems turned out to be too easy and the winner solved all of them in just over 2 hours. One must note the performance of the second-placed XZ team: I believe this is the first full team (as opposed to teams of just one person) regularly participating in the Open Cup from the Bay Area and from the USA in general. The convex hull of all participating teams on the globe (is there even such a thing on a sphere?..) just got bigger.

Later on Sunday, TopCoder SRM 600.5 took place (problems, results, top 5 on the left). It was a very unusual match, with 4 hours of coding and second and third problems being harder than the usual 'hard' problems from TopCoder. However, only those two problems got solved, with the grand total of 10 accepted submissions for about a thousand contestants and 4 hours.

The third problem was amazingly simply stated, and I still have no idea how to solve it (full problem statement). You are given a graph with N vertices numbered from 1 to N, where vertices A and B are connected by an edge if and only if abs(A-B) is in the given set S. How many connected components are there in this graph? N is up to 1018, S has up to 50 elements, each up to N. Any ideas?

Let me finish this very long post with a non-scoreboard picture, taken in Barcelona which I visited for 4 days and where I've solved most of the contests mentioned above:


No comments:

Post a Comment