Monday, December 30, 2013

This week in competitive programming

2117 programmers took part in Codeforces Round 221 on Tuesday (top 5 on the left). I didn't, so I can simply share the links to problems and results, and congratulate the winner Touma_Kazusa for whom this was just the third Codeforces round!

2075 programmers took part in TopCoder SRM 602 on Saturday (problems, results, my screencast, top 5 on the left). The 250 problem was simple dynamic programming, the 550 was a tricky case study with simple data structures, and 1000 was a mostly mathematical problem to be solved on paper. The 550 possessed an interesting property: despite being a very tricky case study when N is up to 100000, it allowed a very simple solution when N is around 5-10 that can be implemented in just a couple of minutes. That's why after submitting it, I've implemented that simple solution and compared it against my solution on thousands of random testcases. It helped discover a silly bug and I had to resubmit losing quite a few points, but I would've lost much more had my solution failed the system test. My point is that even in very short contests, like TopCoder, there are situations for such stress-testing against a simple solution.

2493 programmers took part in Codeforces Round 222 on Sunday (problems, results, my screencast that was unfortunately truncated after about an hour when I've locked my computer, top 5 on the left). The problems were fairly standard, but the last one required a great deal of accuracy. I'd like to highlight the easiest problem, though. The task was: given a connected set of cells on the grid and a number K, remove K cells from the set so that it remains connected. It is quite straightforward and can be solved in many ways, but it still requires some logical thinking and the statement is very easy to understand. I think this is a very good easy algorithmic problem.

One other peculiar fact about this week's Codeforces rounds is: today's top 5 are all from ex-USSR, while 4 out of Tuesday's top 5 are from China and Japan. There are several possible explanations. First, Tuesday's round was 1.5 hours later so it was less convenient for people in eastern timezones. Second, top 5 in a round is so random that there's nothing to explain at all. Third, one of the round's problems might be similar to a problem from an older contest that was only popular in a certain region. But these are the boring explanations :) Wouldn't it be interesting if different styles of education present in Russia vs Japan vs China led to different sets of skills that would in turn lead to such country-specific contest results? Has anybody seen more careful analysis of country distribution in algorithmic programming contest results?