Monday, August 4, 2014

This week in competitive programming

This week had two rounds, both on Friday. Yandex.Algorithm 2014 Final round (results, top 5 on the left) took place in Berlin, where 22 best contestants competed for the grand prize. I was competing there as well, and could have placed above tourist - had all of my blind submissions passed. Unfortunately, my solution for problem C turned out to have a very simple bug which I've missed in the end-of-contest rush, so I fell to the 7th place. It's probably even more disappointing for s-quark, who submitted problem C in the open and thus had several attempts to fix his bugs and claim the first place.

Anyway, congratulations to Gennady! He has won all 2014 tournament onsites he has participated in: Facebook Hacker Cup, Kotlin Challenge, Yandex.Algorithm. Three more to go - Google Code Jam in August, Russian Code Cup in October, and finally the TopCoder Open in November. The picture on the left is from the official news feed.

Amazingly, the problems were not too difficult. They don't seem to be public online. The four problems that were enough to win the competition were about sorting, backtracking, simple maths and quite standard Dynamic Programming. They did require a great deal of accuracy to get right, which was especially challenging given the open/blind format of the competition.
Codeforces Round 259 (problems, results, top 5 on the left) thus became a bit of a consolutation round to me. Problem D which decided the round boiled down to the following nice Dynamic Programming subproblem: you are given 220 numbers. For each position i between 0 and 220-1, and for each distance j between 0 and 20, what is the sum of the numbers with such indexes k that k and i differ in exactly j bits? The time limit is 6 seconds.

Thanks for reading, and see you next week! Last week, I've promised a detailed post on TopCoder Open Round 3A hard problem which had failed to materialize so far - but I still hope to publish it soon.

No comments:

Post a Comment