Sunday, September 29, 2013

This week in competitive programming

A quite eventful week in competitive programming comes to an end.

On Monday, the onsite round of Russian Code Cup took place. If you haven't heard about it - it's a very well organized international competition, with a great onsite part, but with problem statements in Russian. Final results: (top 5: myself, Gennady Korotkevich, Dmytro Dzhulgakov, Vladislav Isenbaev, Pavel Kunyavsky), problems: The final round lasted 3 hours, and there was online commentary during the entire competition. You can view the recording at, plus pictures at They had personal cameras for some competitors, several other cameras on the floor, interviews, problem discussions and so on.

I had a very lucky day, solving the first five problems without mistakes quickly. I think the most important moment was the fourth problem. Here's the approximate statement in English: you are given a 1000x1000 grid of black and white cells, with top-left and bottom-right cells being black. You need to get from top-left cell to bottom-right cell. At every move, you go to an adjacent cell (sharing a side). If that cell is white, you're then teleported to a random white cell. What is the lowest expected number of moves you can achieve, assuming you follow the best possible strategy?

This is a nice problem that doesn't require complicated textbook algorithms, but rather concise thinking and implementation. I won't write the solution here so you can enjoy solving it :) In the contest, it was very important to get it right from the first attempt, it gave me a lot of breathing room.

In addition to the above commentary, here's my much less exciting screencast (still processing, hopefully will be up soon):

On Friday, TopCoder Single Round Match 592 took place. Results, problems. Top five on the picture. The round consisted of two reasonably "mainstream" problems (one on ad-hoc case study, and one on dynamic programming in combinatorics), plus one quite unusual problem. It went like this: there are N hidden non-negative integers Pi, arranged in a circle and  symmetric around zero: Pi=PN-i for 1 <= i <= N-1. Now we calculate Qi=sum(Pj*Pk), over all j and k such that j+k=i (modulo N). Given N non-negative integers Qi, calculate the lexicographically smallest Pthat would give this result. N is up to 25. Again, won't spoil the problem in this post - try solving it if you haven't yet! Will describe the solution later. I was very close during the round - got the correct idea but had two bugs in my solution. You can follow my failed attempt in the screencast:

Also on Friday, Codeforces Round 202 took place, which I skipped, so I can only show you the results. Final results:, problems:

And finally, on Sunday, the second son of my friend, teammate and competitor Egor Kulikov and Kate was born - Petr Kulikov! Congratulations Egor and Kate!

No comments:

Post a Comment