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 2¹⁰⁰⁰⁰ 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⁵, and 1000 'large' numbers, each at least 10¹⁰ (and at most 10¹⁷). 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⁸, but I've solved it when they're at least 10¹⁰ - can you?

Thanks for reading, and see you next week!

This week in competitive programming

There were no Codeforces or TopCoder rounds this week. However, SnarkNews Winter Series 2014 Round 2 has finished on Wendesday (top 5 on the left, full results), so let me share a nice problem from that round. We want to assign integers starting from 2 to (an infinite amount of) users and groups of users of our service in such a way that:

• each user is assigned a different positive integer number.
• each group (set) of at least two users is assigned a positive integer number that is different for all groups and is different from all user's numbers.
• each integer more than one is assigned to either a user or a group.
• the number for each group is the product of the numbers of the users in that group.

The problem then asked to find the users belonging to the group with the given number. It did not claim this explicitly, but it implicitly relied on the fact that there's exactly one way to choose which numbers belong to users and which belong to groups so that all above conditions are satisfied. Can you figure it out?

Thanks for reading, and see you next week!

This week in competitive programming

This week TopCoder came back from holidays with two SRMs. SRM 603 (problems, results, top 5 on the left), on Monday, featured a problem requiring a Fast Fourier Transformation implementation. It's funny that searching for [topcoder fast fourier transformation] brings up an old post from this very blog. A problem requiring FFT appeared on TopCoder almost 5 years ago, and I was regretting that I don't have a library of prewritten algorithms that has FFT in it. Fast forward 5 years, and the feeling is exactly the same :) Given that TopCoder Open now allows libraries of prewritten algorithms, it makes more sense to start assembling one.

SRM 604 (problems, results, my screencast, top 5 on the left), on Saturday, featured a nice dynamic programming on trees problem: you are given a tree with some vertices having a token in them, and some not. You need to move the tokens in such a way that they occupy a connected set of (different) vertices, and the total distance travelled by tokens is as small as possible (full problem statement). The solution to this problem can be very tedious, but it can also be simple if you make an important observation.

Moreover, intuitively it feels that this problem should be solvable greedily. Any ideas?

On Friday, the first round of SnarkNews Winter Series 2014 has ended (see my old post for details about this contest) (results, my screencast, top 5 on the left). The rules have changed since that post, though - the current rules are available under TCM/Time heading at the Yandex.Algorithm page. Short version is: when you submit a problem, you can choose whether you want instant feedback or not, and you get a penatly time bonus if you don't require instant feedback (but of course your solution can fail in the end and then you'll get nothing for this problem). For example, in the top 5 shown on the left, tourist sent all 6 problems without feedback, Egor sent three problems with feedback (all were accepted on the first attempt, so he could've send all six without feedback and get a better result) and three without, and so on.

Such rules add an extra dimension to the competition, increasing randomness, but not in a bad way, as it's still rewarding good strategies.

Finally, on Sunday, Codeforces Round 223 took place (problems, results, my screencast, top 5 on the left). Problem C was nice because it asked a very simple-looking question, yet answering it required some creative thinking. Here's how it went: for a string consisting of opening and closing parentheses, we can find the smallest number of characters to be removed from the string such that the remains are a correct parentheses sequence. Now you're given a string with a million parentheses, and need to find the above number for hundred thousand given substrings of that string.

Thanks for reading, and see you next week!

P.S. Comments and suggestions on improving the weekly digest are welcome.

This week in competitive programming

Happy New Year!

Last week was mostly holidays, but it still featured a programming competition. Codeforces ran its last round of 2013 on Monday (problems, results, my screencast, top 5 on the left). The problems were not bad but not too exciting in my opinion, but in the aftermath of the round a nice formula for creating nasty problems was born :)

Some more exciting problems are still open to be solved at New Year's Prime Contest (see my last year's description for details). Here's this year's link (Russian), PDF with problems, and the current standings. Problem 5 is still not solved by anybody, although its problem statement is not very clear, which might explain why nobody tries to solve it. I've particularly enjoyed problem 2, which goes as follows: you are given a 2000x2000 matrix of zeroes and ones, and need to find the number of permutations of its columns that result in a matrix where ones in each row are consecutive (see the PDF for details). Squeezing it into the time limit might not be too exciting, but coming up with any polynomial solution certainly is. I'm also the author of problem 31.

And finally, I want to share a picture of a New Year's gift from my dear wife Irina: it's a bed cover made from old T-shirts, mostly from programming contests. This might be a bit too personal for this blog, but I hope it's enough of a programming contest artifact :)

Thanks for reading, and see you next week!