This week in competitive programming

The week started with Codeforces Round 215 on Tuesday (problems, results, top 5 on the left, my screencast). The round was unusually easy, with many competitors solving all five problems around the 1 hour mark, and the round was decided on challenges. There were two main strategies that could give one hundreds of challenge points. First, there was a nasty integer overflow possible in problem B, so a carefully constructed testcase could either make many solutions time out or make them produce a wrong answer. Then, problem C was to be essentially solved on paper, and asked to find some simple function f(n), so it was very easy to check this function in other solutions to see if it's any different from the correct one. Egor employed both strategies and achieved a commanding win, over 200 points above the second place.

On Friday, TopCoder Single Round Match 598 took place (problems, results, top 5 on the left). I didn't take part, so I can only admire Egor's second victory of the week. Another interesting fact is that the SRM took place at 6am Russian time, but the 4th and 5th place were taken by members of SPb SU 4 and SPb ITMO 1, two teams due to compete in NEERC just two days later - apparently they thought that additional preparation is worth more than not waking up early.

Did that work out? You can see the NEERC top 5 on the left (problems, results). SPb SU 4 won as expected, although they couldn't solve any of the 3 difficult problems, so they could easily lose the first place to another team. SPb ITMO 1 didn't do as good, but still qualified for the World Finals. Speaking of World Finals qualifications, in case NEERC competitors read my blog, it has just been announced that the ACM ICPC headquarters have agreed to give 17th slot to NEERC teams, so the Moscow Institute of Steel and Alloys is also going to the World Finals (all finalists from NEERC)!

As I mentioned before, I've test-solved this contest, my result was 9 problems. Out of the three difficult problems I've solved problem D, and I find it very beautiful. The author of this problem is Egor, so this seems to be his good week :)

Here's how it goes: you are given 50 strings of length at most 10. You need to construct a rooted tree and write exactly one character on each edge of the tree, in such a way that one can find each of those 50 strings in this tree. We say that we can find a string in such tree if we obtain this string using the following process. Start at some vertex, and repeat the following: pick one of the children of the current vertex (remember, the tree is rooted), write down the character from that child's edge, and make that child the new current vertex. In other words, there needs to be a path from some vertex in the tree to another vertex in the tree that always goes away from the root and has the string written along it (see the PDF for the complete statement, look for problem D "Dictionary"). What is the minimum possible size of such tree?