This week in competitive programming

On Tuesday, TopCoder SRM 629 has fulfilled two characteristic features of a good ICPC contest: nobody solved all problems, but each problem was solved by somebody (problems, results, top 5 on the left, my screencast). These properties are not as important for the TopCoder format, of course, since the score of a problem decreases with time, and thus even if several people solve all problems, they are still differentiated quite well.

Two things made this possible: the easy problem had a very subtle trick, while the hard problem was just hard.

The easy problem had a real-world statement: you have a rectangular hole in the ground, and want to cover it completely using several rectangular boards, placing each board in such a way that its sides are parallel to the sides of the hole. In order for the boards not to fall into the hole, you want to place the boards in such a way that all four corners of each board are not inside the hole and not on its boundary. Given the size of the hole and the sizes of the boards you have, what is the smallest number of boards you need to cover the entire hole?

When a problem has a statement that relies on common sense instead of formal maths, one needs to formalize the statement before solving the problem. In this case, we need to formalize the "all four corners are outside the hole" part and the "covers completely" part. And the main trick is that those two are formalized differently: for all corners to be outside the hole, we need the height of the board to be strictly greater than the height of the hole (or the same for width), while covering the hole completely requires that sum of the widths of the boards is greater than or equal to the width of the hole (or the same for height). It was very easy to miss the "or equal" in the second formalization, and many competitors including the match winner K.A.D.R made that mistake. And because the formalization step is usually quite simple and boring, we're simply not used to looking for mistakes in that step - so even re-checking the solution won't help since one would compare the program to the formalized version of the problem in one's head, and find no discrepancies.

The hard problem asked about a very simple thing: given N, K and MOD, calculate S(N,K) modulo MOD, where S(N,K) is the sum of all possible products of exactly K different integers, each between 1 and N. For example, S(3,2) = 1*2+1*3+2*3 = 11. It's not hard to come up with the following reccurrence relation: S(N,K) = S(N-1,K)+N*S(N-1,K-1) - it represents whether we take the number N into the product or not. However, N was up to 10⁹, and K was up to 2000, so simply using that formula would be too slow.

K.A.D.R has come up with a brilliant insight which I want to share with you. He has noticed that when we fix the value of K, S(N,K) is a polynomial in N. For example, S(N,1)=N*(N+1)/2=1/2*N²+1/2*N. It's not hard to prove by induction that S(N,K) is a polynomial of degree 2K. One might now start constructing this polynomial in order to find its value for the given N - but that is quite hard, too. What Iaroslav did instead was to simply compute the value of this polynomial in points 1, 2, ..., 2K: S(1,K), S(2,K), ..., S(2K,K) can be computed in O(K²) time using the above recurrence relation very easily. And computing the value of a polynomial of degree 2K in point N given its values in 2K points can be done using a standard interpolation algorithm in O(K²), too!

Congratulations Iaroslav on this amazing solution and on winning the match!

On Friday, the Google Code Jam became yet another major contest won by Gennady in 2014 (problems, results, top 5 on the left). The Code Jam's scoreboard has loosely followed the pattern of the recent Yandex contest: at the end of the competition, Gennady was in 3rd place behind Evgeny 'eatmore' and Ivan 'mystic'. However, as the system test results for the large inputs were announced, it turned out that they were both incorrect in their attempts at solving F-large, while all of Gennady's submissions stood and he won the contest. Once again, making sure that one's solution are correct paid off - congratulations!

Second-placing Evgeny was really close to winning - the code he used for F-small looks good in general and should be able to solve F-large just as well - but his submission failed, indicating that he probably has some very small bug somewhere.

Among the problems of the final round, I've enjoyed problem D the most. You have up to 100 different candies, and for each pair of candies you prefer one of them to the other. Your preferences are not necessarily transitive - you might prefer A to B, B to C, and C to A. You're trying to pick your most favorite candy by considering all candies one by one and comparing each candy with the "current best" candidate. It's not hard to see that the candy chosen to be the most favorite depends on the order you consider the candies in. For example, in the above triangle, processing the candies in order ABC will lead to candy C being declared the most favorite, while ACB will make B look like the best candy. Given the matrix of preferences, and one specific candy, can you make that candy your favorite by considering all candies in the right order? If yes, you also need to find the lexicographically smallest such order.

The picture of Gennady on the right is from this article (which does have a few inaccuracies - but good job on publishing the article so quickly!)

Thanks for reading, and see you next week!