This week in competitive programming

Tuesday and Wednesday were the days of TopCoder Open semifinals and finals. The final results are on the left, here's a link to problems. I had a very nervous wait for the final results because peter50216's successful challenge (on tourist's hard) meant he would be first if my hard failed as well. Luckily, it didn't fail, although it was very close - it took 1.5s out of 2s to run on some testcases.

Here's what the decisive hard problem from the finals boiled down to (link to full problem statement): you are given a NxN (N<=50) grid with some cells black and some cells white. How many ways are there to place non-intersecting T-tetraminoes onto the grid such that each "central" cell of a tetramino falls onto a white cell, and each white cell is the central cell of some tetramino? You need to find this number in O(N^2). I will try to write about the solution later this week, so that you have some time to try solving it yourself.

I've been thinking what was different this year that has allowed me to win. Obviously, this could be completely random, but that's not too interesting to think about :) One difference is Gennady's presence in the finals, that did certainly add motivation. Another possibly important thing is: Egor has convinced me to go and watch an ice hockey game, Capitals vs Blue Jackets, on the night between the semifinal and the final. Looking at my 1st place and his 3rd place, such a distraction might actually be a positive thing.

On Sunday, the fourth Open Cup stage took place, top 5 on the left, here's a link to full results. As far as I know, the problems for this stage were taken from the Polish ICPC quarterfinal, so we can compare the Russian teams with the Polish teams - Polish results are here. Judging from this contest only, it looks like SPb SU 4 is still the best contender for this year's World Finals among the teams I know.

Speaking of Polish teams, the Central European Regional Contest of ACM ICPC took place on Sunday, too (here's a link to final results, top 5 are on the picture). The top 3 are quite similar to last year's with the Warsaw team suprisingly losing 1 problem to Comenius and Jagiellonian. However this didn't stop the Warsaw team from becoming the best team from Central Europe at the World Finals, and I would still expect them to be an important player in the World Finals this year.

Most other regionals have already happened during the first two weeks of November, you can find their results on the official ICPC website: link. I don't want to paste all those results here, but please tell if there's something particularly interesting in there that I should discuss here! The regional which gave us the last two world champions, NEERC, is going to happen on December 1st in St Petersburg.