Sunday, January 26, 2014

This week in competitive programming

The week started with Codeforces Round 225 on Monday (problems, results, top 5 on the left). I didn't take part, so I can't tell much about the problems; SPb SU 4 have reminded everybody that they're the team to beat at this year's ICPC World Finals, taking the first and the third place in this contest.

On Tuesday, TopCoder SRM 605 took place (problems, results, top 5 on the left). I didn't take part as well; the winner, semiexp, is now seventh in the world; in another round of ICPC World Finals news, Lidia Perovskaya comments in my earlier post that very strong University of Tokyo team that includes the SRM winner semiexp and two-time TCO winner rng_58 is not going to the World Finals this year.

Finally, two rounds of SnarkNews Winter Series have ended this week. Round 3 (results, top 5 on the left) featured, among others, the following nice problem. You are given a string with 10000 characters. Consider all 210000 ways to pick a subset of its characters. Some of them result in different strings, some result in equal strings. For each distinct string that we can obtain that way, we count the number of ways to obtain it, and need to find the sum of squares of those counts modulo a large prime. The problem required a beautiful insight to solve, and the only contestant to get it was tourist.

Round 4 (results, top 5 on the left) reiterated on a somewhat well-known but still beautiful idea in the following knapsack problem: you are given 100 'small' numbers, each up to 105, and 1000 'large' numbers, each at least 1010 (and at most 1017). For each large number, you need to find the minimum amount of small numbers (each small number may be used more than once, each usage counts) that sums to this large number. I don't know how to solve this problem fast enough if large numbers were, say, around 108, but I've solved it when they're at least 1010 - can you?

Thanks for reading, and see you next week!

No comments:

Post a Comment