Yet Another Blog

Problem:
This is a 500-points problem from TC SRM440 Div1. It can be summarized as follows:

We are given a matrix. Some cells are marked closed and others are marked open. We can only move from one open cell to an adjacent open cell. The matrix is defined such that there is one and only one way from one open cell to another.

Our target is to reach a specific open cell, let’s call it the target cell. Our starting point is uniformly random (can be the target cell itself). Moving from one cell to another takes one second. Our motion is also uniformly random; that is, whenever we are in an open cell, the probability to move from that cell to any of the adjacent open cells is the same for all adjacent open cells (but we must move, we can’t stand still).

It is required to calculate the expected time to reach the target cell.

Solution:
Since the starting cell is uniformly random, we will calculate the expected time to reach the target cell for each possible starting cell; then the required overall expected time is just the average of all those expected times.

Let the open cells be where is the target cell. For the special case where is the starting cell, the expected time equals . We need to calculate the expected time for the rest.

For any cell , where , let the expected time to reach be . If the degree (the number of adjacent cells) of is then the probability of going to any of the adjacent cells is . If we are in cell , and we chose to go to the adjacent cell then the expected time to reach will be one second (for moving from to ) plus (the expected time to reach from ). We end up with the following formula for :

This is a system of linear equations that can be solved with any appropriate method, for example Gauss-Jordan elimination.

Comments:
The interesting thing with this problem is that it is asking for an algorithm to analyze the performance of a heuristic! We can think of this matrix as an undirected graph, where open cells of the matrix are vertices of the graph, and adjacent open cells correspond to adjacent vertices. Since there is one and only one way between any two open cells then it is actually a tree, and the algorithm is just analyzing the performance of a random search in a tree.