This week in competitive programming

Tourist has started the week in his usual fashion by winning Codeforces Round 260 on Friday (problems, results, top 5 on the left). He has participated in just 4 regular Codeforces rounds in 2014 - and he has won them all. Amazing consistency!

TopCoder Open Algorithm Round 3B, like most TCO rounds, took place on Saturday (problems, results, top 12 on the left, my screencast of the parallel round). Twelve more spots in one of the most prestigious tournaments in competitive programming were given out. The problemset was destined to make the contestants very nervous :) The 500 problem did not require any sophisticated algorithms or ideas, but required a small insight and a lot of attention to detail. Most contestants tried to solve it - but just 4 contestants managed to solve it correctly (3 out of those 4 are in the top 12 to the left), while many top rated favorites had a bug in their solutions and failed. This problem also played a very important part for some people who didn't solve it, as they were able to challenge a lot of incorrect solutions and gain a spot in top 12 that way.

The 1000 problem, on the other hand, had a really simple problem statement but required great combinatorial prowess. 4 out of 5 people who submitted it got it right, so it was a safe ticket to the TopCoder Open - provided you could actually get a solution that passes the example cases. Congratulations to wata on solving it very quickly and winning the round with a commanding margin!

The problem asked to count the number of trees on the given vertices (at most 50) that share at least the given number of edges with one specific given tree. Can you do it?

Finally, MemSQL Start[c]UP 2014 Final Round was held on Sunday (problems, onsite results, online results, top 5s on the left). The onsite round was for those willing to travel to the MemSQL office in San Francisco, and the online round was for the rest of us, using the same problemset. This time the problemsetters didn't worry that much about having easy problems in the set, so the first three problems all had a hundred thousand numbers in the input and required O(n) or at least O(nlogn) solutions. This has unexpectedly bitten the contestants using Java since two out of those three problems involved sorting hundred thousand integers - and it turned out that using Arrays.sort is not good enough, since it uses a deterministic quicksort algorithm and thus can be made to work in O(n²) by a specially crafted testcase. Sure enough, some contestants did come up with such testcase. Lessons learned: either shuffle the array before sorting using time-based randomness, or use Arrays.sort on arrays of objects, not primitives, since that version is not quicksort.

The hardest problem was not solved, is still not solved by anybody in the problem archive, and I still have no clue how to solve it. You are given a rooted tree of at most 250 vertices, and each node of the tree is either a leaf or has exactly two children. Each leaf has a number associated with it. Two players, maximizer and minimizer, are playing a game by making turns in order. At each turn, a player must pick a node with two children that are both leaves, erase those leaves, and pick one of their two numbers as the number for the node. The game ends when just the root is left in the tree, and the score of the game is the number picked for it. Maximizer wants to maximize the score, while minimizer moves in the other direction. What will be the score if both players do their best?

Thanks for reading, and see you next week!

Tweet