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.