This week in competitive programming

Contrary to last week's serenity, this week has been really busy in terms of contests. Early on Monday, Codeforces Round 285 started the sequence (problems, results, top 5 on the left). Competitors in places from second to fifth remained within one successful challenge from each other, but Boris was not within reach and achieved a commanding victory - congratulations!

TopCoder SRM 645 happened later on Monday (problems, results, top 5 on the left, my screencast). The medium problem required careful logical thinking to apply several relatively easy steps in sequence to obtain a working solution. You were given two sets of points on the plane, of the same size, which was at most 50, and also exactly three magic points on the same plane. In one step, you were allowed to pick one of the three magic points, and rotate all points in the first given set by 180 degrees with the selected magic point as the center of rotation. Note that all points are rotated at the same time and with the same center of rotation. Is it possible to obtain the second set of points via zero or more such steps from the first set of points?

TopCoder SRM 646 continued the fun early on Friday (problems, results, top 5 on the left). Tiancheng continued to show impressive form (previous post) and climbed into the 3rd spot (shared with Tomek) in all-time SRM wins stats - awesome performance, both this week and in the past years!

Facebook Hacker Cup Round 1 occupied 24 hours on the weekend (problems with Facebook login, results with Facebook login, top 5 on the left, my screencast). Of course, one didn't need to spend that much since the problems were relatively simple. The challenge, as usual with the Hacker Cup, was in the format that punishes every mistake very heavily: since the round lasted for 24 hours, many competitors who would not solve these problems in tighter time constraints got a chance to steadily work towards solving all four, and that, in turn, meant that most likely all 500 qualifying spots would be taken by people who solved everything, and thus almost any mistake could mean a good bye to the Hacker Cup. The cutoff ended up being 75 points, not 100 points, but still mistakes in solving the hardest "Corporate Gifting" problem were punished with elimination. Because of this, this round brought slightly different qualities into the limelight: testing one's solutions very carefully, the ability to read the statement without any omissions, and having a good proof for each and every mathematical solution. To put it another way, it was all about patience :)

Finally, Codeforces Round 286 ended the week late on Sunday (problems, results, top 5 on the left, my screencast). After reading all problems, I was unable to come up with an algorithm to any of the five problems, which is quite unusual for Codeforces since problems A and B are usually not that difficult. Given that all problems required thinking, I've decided that I might as well go after the one that was scored the highest, and that turned out to be too optimistic. The problem simply asked to count the number of palindromes of the given length (up to 10⁹) containing the given string (of length at most 200) as a subsequence (not necessarily as a substring - i.e. the characters don't have to be consecutive), modulo 10007.

You can see my slow progress towards a solution in the screencast: at about 37 minutes mark of the screencast, I've implemented a slow solution and automatic period detection, hoping that the answers for consecutive lengths would form a sequence with a short period - but they would not. Then, at about 50 minutes into the screencast, I came up with the idea that the slow solution can actually be improved by considering segments of palindrome before the next match of the subsequence at once, and thus separating the result into a large sum of products of powers of 24, 25 and 26 (more details probably in a later post), but after implementing this part around 1 hour 1 minute mark I've realized that I still have no idea how to quickly compute the sum I reduced the problem to. Around 1 hour 12 minute mark I've realized that this sum can be computed by taking 200 relatively small matrices to a large power modulo 10007, something we can do relatively quickly. I've finished the implementation and submitted around 1 hour 22 minute mark - only to learn that the solution is still too slow. Some more thinking led me to the idea of computing all 200 numbers I need using just one matrix power, but the matrix unfortunately became bigger, and thus the solution was still about 50% slower than needed. 1.5x was already in the 'non-asymptotic' speedup area, so I've switched to speeding up matrix multiplication, first by using the modulo operation less often, and then by taking advantage of the fact that the matrix had corners of zeroes that didn't need to be recomputed. That has finally enabled me to make a successful submission at 1 hour and 49 minutes into the contest, with too little time left to solve any other problem.

In the meantime, Ilya has solved the remaining four problems and claimed the victory - congratulations!

And finally, let me finish this post with something different: a chess puzzle! More specifically, I want to share a wonderful gem of a chess website, lichess, that provides a training area with puzzles like this one: http://en.lichess.org/training/23280.

Their idea is that since many people are playing chess against each other on their website, they can simply find "interesting" situations in those games automatically - probably when computer could see a unique sequence of good moves in a position that's losing otherwise - and present those situations as puzzles that make people learn real-world chess tactics, not just apply abstract backtracking skills. Quite fittingly, all puzzles are asking you to find the best move for Black/White, not to find a mate in three or something like that, since the former is what actually matters in real chess games. In particular, the puzzle referenced above was taken from this blitz game, where the real black player could not find the right sequence of moves and lost.

The puzzles also have the usual up/down voting buttons, so as hundreds and thousands of people are going through them, the system can become even more intelligent and suggest only quite interesting puzzles to most. The puzzle linked above and shown on the left was presented to me recently, and I've enjoyed solving it - did you?

Also, I can't help but wonder if we can come up with similar training approach for algorthmic programming based on the enourmous base of contest solutions that we've accumulated over the years.

Thanks for reading, and check back next week!