This week in competitive programming

This week had two TopCoder SRMs which brought very good but still very disappointing results for me - two second places :) But I enjoyed solving the problems anyway, and want to share the most interesting ones.

The week started with TopCoder SRM 619 on Monday (problems, results, top 5 on the left, my screencast). Nobody managed to solve the hard problem during the SRM, but it has a very simple and nice problem statement and thus is interesting to solve: consider two sequences of N (up to 100) integers, each integer between 1 and M. We call them similar if it's possible to remove at most two elements from each sequence so that they become equal. How many pairs of similar sequences are there for the given N and M (modulo 10⁹+7)? How would you approach such problem?

TopCoder SRM 620 happened on Saturday (problems, results, top 5 on the left, my screencast). The medium problem turned out to be the most interesting, and produced the most challenges. You were given at most 50 strings with at most 50 characters each, and could sort the strings by any character (keeping the current order when the corresponding character is the same). You needed to come up with a way to obtain the given ordering of the strings from the initial one by zero or more such sort operations. The problem is actually quite simple, but there are many ways to make a wrong step.

Google Code Jam 2014 Round 1C was the last chance to advance to Round 2, and took place on Sunday (problems, results, top 5 on the left). Congratulations to all who advanced - you have just two more rounds before the onsite in Los Angeles!

Any finally, Codeforces Round 245 wrapped up the week (problems, results, top 5 on the left). I did not take part, but have noticed the heated and extensive discussion on the forums - it's always nice to see people take an interest in the problems and their tests beyond simply participating in the contest :)

Thanks for reading, and see you next week!