This week in competitive programming

This week was relatively calm, with just one contest: TopCoder SRM 639 (problems, results, top 5 on the left, my screencast). The screencast is quite evenful in its second part: at 57:30 in the screencast, I was at the top of the standings with all problems solved and 1304 points, and was about to relax until the end of the contest. But then I've decided to quickly write a stress test comparing the output of my solution for the 1100 problem with the output of a simple-but-slow solution, and that changed everything. I've found that my solution had a bug, had to diagnose and fix it quickly (it turned out to be very very stupid, of course), and then had to go all-in at the beginning of the challenge phase with blind challenges.

All challenges were on the easy problem, which went like this: two players are playing a game with several rounds. The winner of the first round gets 1 point, the winner of the second round gets 3 points, then 5 points, and so on. Given two numbers x and y, is it possible that after some number of rounds the first player has x points and the second player has y points? If yes, then what is the smallest number of rounds the first player could've won?

If the scores for the rounds were 1, 2, 3... instead of 1, 3, 5, ..., then there would really be no corner cases and no challenge opportunities. However, the use of odd numbers resulted in a few tricky situations, in particular no player can score exactly 2 points now, and thus many greedy algorithms failed. In fact, just 138 out of 496 submitted solutions turned out to be correct. Can you see how to overcome this difficulty?

In addition to hosting the SRM, TopCoder has uploaded the TCO 2014 "Epilogue" video this week — check it out!

The ACM ICPC North-Western European Regional Contest happens today, most other European ACM ICPC regionals happened earlier, with the sole exception of the Russian and ex-USSR regional NEERC which takes place next Sunday. I will try to summarize the results of all European regionals in the next week's summary, so check back in 7 days!

Tweet