This week in competitive programming

The final round of Russian Code Cup 2014 took place on Saturday (problems in Russian, results, top 5 on the left), but it went without the official onsite event like we had last year, as the organizers decided to cancel the onsite part and hold the final round online. The monetary prizes were still up for grabs, and Gennady has claimed the biggest one with just 2 minutes to go!

Problem C was the highlight of the competition for me. You were given a positive integer M, and were asked to come up with an instance of the knapsack problem which has exactly M solutions (well, to be precise, M had to divide the number of solutions, but all approaches I know yield exactly M). More precisely, M was up to 10¹⁸, and you had to find at most 200 positive integers a_i, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {a_i} sum to W. Some a_i might be equal, but they are still treated as different for the purpose of subsetting. I encourage you to try solving this problem, you can submit your solutions at the Codeforces gym!

TopCoder SRM 635 took place later in the evening (problems, results, top 5 on the left). This round had problem statements in English unlike the Russian Code Cup, but the top 3 were exactly the same, Gennady claiming the first place thanks to the ultra-fast solution for the hardest problem.

That problem went like this; how many sequences of integers between 1 and 4 exist such that adjacent numbers are different, and there are exactly n₁ ones, n₂ twos, n₃ threes and n₄ fours? n₁ and n₂ are up to 200, n₃ and n₄ are up to 50000. Similar problems appear in competitions time and time again, but every time they turn out surprisingly difficult to implement. Can you see an approach that leads to a simple implementation?

Bayan 2015 Contest Warm Up happened on Codeforces on Sunday (problems, results, top 5 on the left). Conratulations fotile96, hogloid and sankear on solving all problems!

Thanks for reading, and see you next week!