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: http://russiancodecup.ru/round/15/results (top 5: myself, Gennady Korotkevich, Dmytro Dzhulgakov, Vladislav Isenbaev, Pavel Kunyavsky), problems: http://russiancodecup.ru/round/15/tasks. The final round lasted 3 hours, and there was online commentary during the entire competition. You can view the recording at http://russiancodecup.ru/, plus pictures at http://t.co/PxwO5lPfqF. 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 Pi that 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: http://codeforces.com/contest/348/standings, problems: http://codeforces.com/contest/348.
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!
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):
No comments:
Post a Comment