A problem that requires being careful and determined

In my earlier post I've told you about a problem that almost guaranteed me a win in the Russian Code Cup. Here's how I solved it.

Problem statement: you are given a rectangular grid of white and black cells, N rows of M columns each. Top-left and bottom-right corner cells are black. You start at the top-left cell. Every second you move to an adjacent cell (sharing a side). You're not allowed to stay in the same cell. If you move to a white cell, then you're instantly teleported to a random white cell that is picked uniformly and independently. Note that it's possible that you're teleported to the cell you're already in. Your goal is to reach the bottom-right corner as fast as possible. Of course, random teleportations mean you can't guarantee how long it will take, so you need to minimize the expected (average) time to reach the bottom-right corner.

The first step is standard for this kind of problem: we treat it as a dynamic programming problem. We have N*M states, one per cell of the grid, and we should calculate the expected time to reach the bottom right-corner starting from each of those cells. Let's denote this expected time for cell X as T_X. Suppose the possible moves from cell X lead to cells Y₁, Y₂, ... If all of those cells are black, then it's not hard to see that T_X=1+min(T_Y1, T_Y2, ...). This equation simply says: we will spend one second and end up in one of those cells - so it's obvious we should pick the cell with the smallest expected time. If at least one of those cells is white, then T_X=1+min (W, T_Y1 if Y₁ is black, T_Y2 if Y₂ is black, ...), where W is the average value of T_Z over all white cells Z. This equation says: we can either go to a black cell, in which case we know the expected time, or to a white cell, in which case the expected time is the average expected time over all cells we could be teleported to.

It might seem that we already have a working dynamic programming solution - but we don't. The equations we've written down have cycles. Adjacent cells depend on one another, and many cells, including some white cells, depend on all white cells. So we can't just compute the values of T.

Here's the problem-specific part: we will now simplify the equations so that it becomes clear how to find T. First, suppose we stand on some cell. It's not hard to see that there are only two feasible strategies: either we go to the bottom-right cell using only black cells, and using the shortest possible path over black cells, or we go to the closest white cell in order to teleport. Indeed, if we ever go to a white cell, then our state is completely reset - we can end up in any white cell. So there's no need to pick a particular white cell to jump to, and it's fastest to go to the nearest one.

Now, let's consider the value of T_Z for a cell Z. Let A_Z be the length of the shortest path over black cells from Z to the bottom-right corner, and B_Z be the length of the fastest way to get to a white cell starting from this white cell. Then T_Z=min(A_Z,B_Z+W). Now remember that W is the average value of T_Z over all white cells Z: W=sum(T_Z)/NW, where NW is the number of white cells. So W=sum(min(A_Z,B_Z+W))/NW. We have an equation over W, but we can't solve it immediately because it has 'min's in it.

Since A and B are integers, we could tell which part of each 'min' is smaller if we know the integer part of W: K<=W<K+1. Indeed, we can just compare A_Z with B_Z+K. If A_Z is smaller or equal, then it will be the value of the corresponding 'min'. If A_Z is greater, then the corresponding 'min' is simply B_Z+W. After we know what each 'min' turns out to be, we're left with a simple linear equation on W that we can easily solve. The only remaining thing is indeed to check that K<=W<K+1. Of course, we also need to find the proper K. We can just check all values starting from 0, and exactly one will yield the answer. Alternatively, it's not hard to see that if the value of W that we obtain from the above equation ends up being larger than K, then the value of K is too small, and if it's smaller than K, then K is too big - that allows us to do a binary search on K.

Having found W, we can solve the rest of the problem easily. Remember that the answer for each cell, black or white, is just T_Z=min(A_Z,B_Z+W). One further observation that doesn't help much in this problem: B_Z for white cells is either 1 or 2. If there's another white cell next to Z, we can just jump there, and if not, we can go to any neighboring black cell and back.

What do you feel when looking at the above solution? Well, for one, it's rather long. But at the same time, it didn't require any out-of-nowhere tricks or fancy algorithms (well, it did require breadth-first search for shortest paths over black cells). The only real requirement is the ability to carefully simplify the problem step by step until it becomes solveable. Note that we could make many wrong assumptions that would lead us to an incorrect answer - the main difficulty is to be careful and determined enough to avoid that. Many programming contets problems are like that, and I think this problem is an excellent example that you can train on to improve this skill. I think this skill is also extremely useful in software engineering and helps me a lot in my daily work.

Do you have a favorite problem of this kind? Please answer in comments!