Block3Checkers editorial preview

Remember when I didn't take more than a week to write an editorial? I miss those times too. I am very sorry about this. Here is the first preview:

http://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+3A#Block3Checkers will contain the updated version of this explanation. It might eventually be improved and corrected. The following is the initial version:

Block3Checkers

There are three checkers that belong to Alice in a n x n grid board. There may also be some neutral checkers in some of the cells. Bob must place some checkers on the board in such a way that it is impossible for Alice to make any pair of her checkers meet after a number of moves. A valid move involves Alice moving one of her checkers up, down, left or right to an empty cell. Bob cannot move his cells or add new ones after Alice starts moving. Return the minimum number of checkers Bob needs to place, or 100 if it is impossible no matter what Bob does. n <= 20. Alice's checkers will always be initially placed in the border rows/columns.

Cut the paths

The initial thing to notice is that all that we need to do is to put new checkers in a way that all paths between each pair of checkers are blocked. For now on, we will forget of the distinction of neutral ('N') checkers and Bob's checkers. We will instead consider 'N's in the board as obstacles that don't allow Alice's checkers to move to them. The objective is to find the minimum number of additional obstacles to add to the board so that the paths between Alice's checkers are blocked (Or return 100 in case it is not possible).

After some analysis we should conclude that although the constraints are small, it does not seem approachable to find a brute force method. Classical ways to cut paths like the min-cut algorithm don't seem to fit this three checkers scenario. There is only one interesting bit left: The constraints ensure us that Alice's checkers will be at the edge/border of the board. It is likely that the solution requires us to use this constraint.

Two checkers

In order to find a way to take advantage of the edges, let us first try to solve an easier version. Alice only has two checkers. How would you block them? Imagine various scenarios in which the checkers are blocked:

The key is to imagine that the two checkers divide the board's border cells in two groups, delimited by the checkers:

We can now see that the cells with obstacles form a sequence of cells that connects the two halves of the board's border:

These sequences of connected obstacles are curiously 8-connected (Two connected cells need to be adjacent or have a corner in common) as opposed to 4-connected as the actual paths that the checkers can take. As long as the sequence of cells connects the two partitions of the border there is otherwise no other requirement for the sequence of obstacles that block the checkers. This sequence of connected cells is, of course, a path of cells.

This knowledge is useful when solving the minimization problem:

We need to add obstacles to the minimum number of cells such that there is a path of cells with obstacles connecting the two parts of the board. We can approach this problem as just "find the path of cells with the minimum cost to fill with obstacles". Let us then find a shortest weighted path between the two edges. We can use any cell that does not contain Alice's checkers, the cost to include a cell is 0 if the cell already contains an obstacle (Neutral checker) or 1 otherwise (Place one of Bob's checkers). There can be plenty of paths and plenty of shortest paths, but we only need to find the minimum cost.

In the image you can see the shortest path between the two edges of the board and the two cells that were empty before. So the shortest path has cost 2, and we need to add two checkers to this board in order to block Alice's cells.

Three checkers

When we have three checkers there are many similarities. The board's border this time is divided in three parts. There are once again ways to connect these edges and block the paths between the checkers:

This times the pictures use black checkers for the neutral / Bob's checkers, just obstacles. The first observation is that we do not need all three of those paths connecting the edges. Only two of them are enough:

To further complicate things, the two paths are not necessarily disjoint - they may have cells in common:

The overlap - one cell

The trick to solve the overlap problem is to notice that in any case where there is an overlap:

We can pick any of the cells in the overlap as "the center":

This center cell has a interesting property: For each edge, there is one path of cells with obstacles that connects the center cell and the edge. If the minimum paths between this cell and two of the edges overlap, then there will be another cell for which those paths will not overlap.

Solution

All the knowledge we have found so far is actually enough to design a solution. Let us call the three edges that are separated by the checkers X-Y-Z. Then we need to add new obstacles such that one of the following statements is true:

• There is a 8-connected path of obstacle cells connecting X and Y, and also a path connecting X and Z.
• There is an 8-connected path of obstacle cells connecting X and Y, and also a path connecting Y and Z.
• There is an 8-connected path of obstacle cells connecting X and Z, and also a path connecting Y and Z.
• There is one cell Center that has 8-connected paths of obstacle cells that connect it to X, Y and Z.

We can try to calculate the minimum cost to have each of those options and then pick the one that costs the least. Each of the first two require us to do two instances of the shortest-path problem. The fourth one requires us to pick a cell (one of the n x n available) as the center cell, and find the shortest paths that connect it to each of the edges. It could be that in the first two cases, the paths that we find overlap, but if that is the case, then the cost to make the fourth case will be smaller and it will be correct.

Depending on the shortest paths algorithm we use, this approach can work even for N=50. Let us, however, take advantage that N is low and just use Floyd-Warshall.

{html}{code}
vector<string> board;

int n;
int dist[20*20 + 3][20*20 + 3];
int segments;
int segmentId[20][20];

// This Depth-first-search is just a convenience to find the border cells and
// to which of the three segments each belongs:
void borderDFS(int x, int y, int s)
{
    bool a = ( (0 <= x && x < n) && (0 <= y && y < n) );    //cell belongs to board
    bool b = ( (1 <= x && x < n-1) && (1 <= y && y < n-1) ); //cell belongs to inner square 
                                                             //(board minus border)
    
    if ( a && !b  && (board[x][y] != 'A') && (segmentId[x][y] == -1) ) {
        //Save the segment of this border cell:
        segmentId[x][y] = s;
        dist[x*n + y][n*n + s] = 0;
        // try adjacent cells:
        borderDFS(x,y+1, s);
        borderDFS(x,y-1, s);
        borderDFS(x+1,y, s);
        borderDFS(x-1,y, s);
    }
}

void checkBorder(int x , int y)
{
    if (board[x][y] != 'A') {
        if (segmentId[x][y] == -1) {
            borderDFS(x,y, segments++);
        }
    }
}


int blockThem(vector <string> board)
{
    this->board = board;
    n = board.size();
    int N = n*n + 3; //total number of vertices in our graph.
                     // n x n cells + the three edges.
    
    // initialize distance array with INF
    const int INF = n*n*n;
    for (int i=0; i < N; i++) {
        for (int j=0; j < N; j++) {
            dist[i][j] = dist[j][i] = INF;
        }
    }

    // Find the border cells, count the number of segments:
    segments = 0;
    memset(segmentId, -1, sizeof(segmentId));

    for (int i=0; i<n; i++) {
        checkBorder(i,0);
        checkBorder(i,n-1);
        checkBorder(0, i);
        checkBorder(n-1, i);
    }
    if (segments != 3) {
        // If there are less than three segments, the only explanation is that 
        // two 'A' checkers are adjacent, that means it is impossible to block them:
        return 100;
    }
    // Vertices 0 to n*n-1 are cells, n*n, n*n+1 and n*n+2 are the edges:
    
    // Make the cells 8-connected:
    for (int i=0; i<n*n; i++) {
        int x0 = i / n, y0 = i % n;
        int dx[8] = { 1,1,1, 0,0,-1,-1,-1};
        int dy[8] = {-1,0,1,-1,1,-1, 0, 1};
        for (int k=0; k<8; k++) {
            int x1 = x0 + dx[k];
            int y1 = y0 + dy[k];
            if ( (0<=x1 && x1<n) && (0<=y1 && y1<n) && (board[x1][y1]!='A') ) {
                dist[i][x1*n + y1] = ( (board[x1][y1] == 'N') ? 0 : 1);
            }
        }
    }
    // Floyd-Warshall:
    for (int k=0; k<N; k++) {
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    
    int withMiddle = INF;
    // Case 4: A center cell connected to each of the three edges:
    for (int i=0; i<n*n; i++) { 
        // Pick cell i-th as the center.
        int c = ( (board[i/n][i%n] == 'N')? 0 : 1); //Cost to have an obstacle on i:
        // Minimum paths between i and each of the edges.
        int total = c + dist[i][n*n] + dist[i][n*n+1] + dist[i][n*n+2] ;
        // Remember the cell that yields the minimum cost:
        withMiddle = std::min(withMiddle, total);
    }
    // Cases 1-3, there is no overlap, try pairs of edges.
    // Find the minimum cost to connect each pair of eges:
    int segDist[3][3];
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            segDist[i][j] = INF;
        }
    }
    // For each border cell:
    for (int i=0; i<n; i++) {
        int bx[4] = {0, n-1, i,   i};
        int by[4] = {i,   i, 0, n-1};
        for (int k=0; k<4; k++) {
            int p = bx[k] * n + by[k];
            // The border cell that we picked is p, with coordinates bx[k], by[k]
            if (board[bx[k]][by[k]] != 'A') {
                // Find the minimum distance between this cell and the other edges
                // Remember the minimum for each pair of edges:
                // (This cell belongs to edge s:) 
                int s = segmentId[bx[k]][by[k]];
                for (int j=0; j<3; j++) {
                    int c = ( (board[bx[k]][by[k]] == 'N') ? 0 : 1 );
                    segDist[s][j] = std::min(segDist[s][j], c + dist[p][n*n + j] );
                }
            }
        }
    }
    // Pick the most expensive pair of edges and ignore it:
    int choices[3] = { segDist[0][1], segDist[0][2], segDist[1][2] };
    int noMiddle = choices[0] + choices[1] + choices[2] - *max_element(choices,choices+3);
    
    // Minimum possible:
    return std::min(withMiddle, noMiddle);
}