Monday, October 6, 2014

This week in competitive programming

The final round of Russian Code Cup 2014 took place on Saturday (problems in Russianresults, 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 1018, and you had to find at most 200 positive integers ai, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {ai} sum to W. Some ai 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 n1 ones, n2 twos, n3 threes and n4 fours? n1 and nare up to 200, n3 and nare 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!

No comments:

Post a Comment