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 2

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 10

Thanks for reading, and see you next week!

^{10000}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 10

^{5}, and 1000 'large' numbers, each at least 10^{10}(and at most 10^{17}). 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 10^{8}, but I've solved it when they're at least 10^{10}- can you?Thanks for reading, and see you next week!

## No comments:

## Post a Comment