This week in competitive programming

TopCoder SRM 614 took place on Saturday (problems, results, top 5 on the left). The most interesting things happened with the hard problem. It went like this: you are given a NxM rectangular field wrapped like a torus - to the right of the last column is the first column and to the top of the last row is the first row. You start in cell (0, 0) and do one random step per second - you go one step to the right or one step to the top, each with probability 50%. What is the expected number of steps before reaching the given cell (X, Y) the first time? N and M are up to 100.

If you're logged into TopCoder, you can view the fastest solution for this problem, which required just 9 minutes to write (and could've probably been done even faster). It solves a natural system of equations: if we introduce a variable for the expected number of steps to reach the goal from each cell, we get a very simple set of equations: for each non-final cell, its variable is one plus half of sum of the variables of the two cells we can move to. This system has 10000 equations and 10000 variables, but each equation has just 3 variables in it. The code in question solves the system iteratively: start with all zeroes, then 7000 times update the value of each variable according to the corresponding equation using the current value of the other two variables.

There are different ways to organize such iteration. One way is to use "generations": we produce NxM new values based on NxM current values. Such approach is essentially equivalent to a DP which computes the expected value assuming we'll need at most 1, 2, ... steps to reach the goal. And that's why such approach doesn't work here - we'd need much more than 7000 steps to get a good approximation of the answer.

But the solution in question does something more tricky: it has just one set of NxM values, and updates them in-place, going in the decreasing-row then decreasing-column order. Such order means that when processing subsequent values, we'll be more likely to use the values that were already updated during the current iteration, and thus potentially "consider" more than 7000 steps: instead of processing just one step per one NxM iteration, we're processing something like O(M) horizontal steps and O(N) vertical steps, since we're tracing an entire part of the path that does not wrap around the torus. This part is a bit hand-wavy, but I hope it makes some sense (alternatively, please explain why it doesn't!). This speeds up the convergence about 50-100 times, and several hundred thousand steps  is already enough to get a good enough approximation.

During the round, the admins have apologized that such simple iterative solution worked, saying it was unintentional. But I think there's nothing to apologize for - this is actually a clever solution that relies on a tricky insight about the right order of processing of the cells, so kudos to everyone who came up with it!

Codeforces Round 239 took place on Sunday (problems, results, top 5 on the left). My solution for problem C relied on the fact that falling factorials, or falling factorial powers, adhere to the same binomial law as normal powers. More precisely, let xⁿ = x*(x-1)*...*(x-n+1). Then (x+y)ⁿ = sum(C(n, k)*x^k*y^n-k). See this Wikipedia article and its outgoing links for more details. This and related identities allow to operate on polynomials expressed as a sum of falling factorial powers instead of the usual sum of powers in exactly the same way, and in this problem using such polynomials allowed to speed up the computations 100 times!

Thanks for reading, and see you next week!

P.S. I'd like my posts to be written in good English. But I'm afraid people with really good English don't think they are - please don't hesitate to point out grammar and other errors! I want to improve :)