SRM 583: Last minute (and explanations)

So, I decided a new strategy. Not opening the 250-points (Easy) problem is surely going to be interesting. Today's match seemed intentionally directed towards making that strategy fail. Medium and Easy were both solved by plenty of coders and I lost rating even after solving the medium.

Delay

I had a delay, I was using the time between 11:00 AM and 11:10 AM to try to improve my solution for the Marathon Round 3 problem. Near 11:10, my most recent implementation wasn't working as intended. So I kept insisting even after 11:10 AM, I didn't want to start the SRM without removing this bug from my mind. I think I started the match seven minutes afterwards.

950 points

I opened the hard problem. Couldn't do much and gave up and moved to 500 I guess that's going to take me a while to solve for the editorial.

500 points - The one with trees

Lately TopCoder is taking ages before the results and problem statements are published.

In short, you have a tree of at most 50 vertices. You have to pick up the minimum number of simple paths between its vertices. Some edges can be picked any number of times, some edges must be picked an even number of times and some edges must be picked an odd number of times.

So, let us try to decide the number of times each edge will be used and then pick the minimum cost to do that...

The root of the tree has some children nodes, each connected with an edge. Let us decide to use its edge #0 in a total of i simple paths. Assume that this pick is valid (even or odd as needed). Interesting things happen afterwards:

• Assume that we then solved for child #0, we need to decide what to do with edges 1, 2, etc of the root. It is exactly a new version of the same problem, the only difference is that we have used i edges in "the past". i edges are [available].
• The children 0 of the root now has a parent edge that is used i times. We can consider this scenario a new version of the problem, the only difference is that the root has i [available] edges.
• We call these edges "available", because if we decide to use a later edge in a path, we can use the root to connect these two edges and take part in the same simple path (and save a cost unit).

So the problem is split in two sub-versions of the same problem.

Let us solve the general version: f(x, paths, e) returns the minimum cost to solve the sub-tree rooted at x. We are only allowed to use edges indexed greater than or equal to e. We know that the "past" edges (including the parent edge) were used a number of times and we have paths "available" egdes.

Let us pick the number of times i we will use edge e in a simple path (Has to have a valid parity). This could increase the cost, if i <= paths, it wouldn't, because we can just use the previous paths without increasing the cost. i > paths, then we have created (i - paths) new paths. The number of paths for the next edge changes. It is abs(i - paths).

• We need to solve the sub-problem for the child connected by edge e: f(child, i, 0) (Because its parent edge is used i times).
• We need to solve the sub-problem of the remaining edges of the root: f(x, new value of paths, e + 1 ).

The sum between the cost and the two new calls to f() is the result. We can implement this with memoization.

const int MAX_VERTICES = 50;
const int MAX_EDGES    = 49;

const int MAX_STEPS    = MAX_EDGES; //we can just pick each important edge once.

struct TurnOnLamps
{
    int degree[MAX_VERTICES];
    int g[MAX_VERTICES][MAX_EDGES];
    bool can[MAX_VERTICES][MAX_EDGES][2];
    
    int mem[MAX_VERTICES][ MAX_STEPS + 1][MAX_EDGES+1];
    
    int rec(int x, int paths, int e)
    {
        int & res = mem[x][paths][e];
        if (res == -1) {
            if (e == degree[x]) {
                //base case. All the sub-trees  were decided, well-done!
                // we can just decide not to use the available roads
                res = 0;
            } else {
                res = MAX_STEPS * 2; //Arbitrarily large value
                // how many paths use edge e?
                for (int i = 0; i <= MAX_STEPS; i++) {
                    // Use this edge in i paths:
                    if (can[x][e][ abs(i) % 2]) { //Valid parity for the number of paths
                        int npaths = abs( paths - i );
                        int cost = max( i - paths  , 0  );
                        int p = rec(g[x][e], i     , 0  );
                        int q = rec(x      , npaths, e+1);
                        res = std::min(res, cost + p + q );
                    }
                }
            }
        }
        return res;
    }
    
    int minimize(vector <int> roads, string initState, string isImportant)
    {
        memset(mem, -1, sizeof(mem));
        int n = roads.size() + 1;
        for (int i=0; i<n; i++) {
            degree[i] = 0;
        }
        for (int i=0; i<n-1; i++) {
            //between roads[i] and i+1
            int u = roads[i], v = i + 1;
            int x = degree[u]++;
            g[u][x] = v;
            can[u][x][0] = can[u][x][1] = true;
            if (isImportant[i] == '1') {
                can[u][x][ initState[i]- '0' ] = false;
            }
        }
        return rec(0, 0, 0);
    }
};

During the match, it took me a while to think of a dynamic programming approach. Then I started to code it, and it was already a bit late, I think only 15 minutes were left before the end of the match.

When I finished coding and debugging that approach, it turns out that it passed example tests, but it was too slow for larger test cases. I was unnecessarily nesting a second dynamic programming inside the main one. I noticed that I could merge the two ideas into a single dynamic programming. But there were very few minutes left, at most 8, if I remember correctly.

I rushed and did the best I could to implement the fix quickly. I was able to compile in the last second and submitted. I think that I literally did it at the last second.

The easy problem

I opened this later after the match. Turns out it was just a simple shortest paths problem! They are not even weighted edges!. If you use Floyd-Warshall this problem is ridiculously easy.

int minTimes(vector <int> range, int startCity, int endCity)
{
    int n = range.size();
    int dist[n][n];
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if ( std::min(abs(j - i), std::min( j+n - i, i+n - j) ) <= range[i] ) {
                dist[i][j] = 1;
            } else {
                dist[i][j] = 1000000000;
            }
        }
    }
    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] );
            }
        }
    }
    return dist[startCity][endCity];
}

Conclusion

I really think the easy problem was too easy this time. The other problems were fine. Although it seems that there was a greedy solution for the 500 points. I think it is still a interesting problem.

The strategy is doing fine. If I used my old strategy, I would have switched to the easy problem before the last 10 minutes. Bore myself trying to implement Floyd-Warshall as fast as possible and then miss the chance to prove that I could have solved the medium problem. It was a lot more exciting and fun to solve the medium this time.

Read More

Change of plans

If you remember the post: Topcoder SRM 560-562: You people have stood in my way long enough. I'm going to clown college!. You would know that's the moment in which I decided to start using a new contest strategy: To open the "Easy" problem only when there are 10 minutes left for the match.

As it was expected, that strategy is too risky. I had very bad matches afterwards. A good example is the last one: SRM 582.

In SRM 582, I opened the division 1 hard, it seemed a bit complicated. Then I opened the div1 medium. I spent the remaining tens of minutes trying to code an easy (but super slow) dynamic programming approach. In the hopes that maybe, once that approach is coded and understood, I can optimize it to O(N^2). (This is an approach that has worked for me in the past). But I kept having issues with the example cases, so something was probably wrong, either in the code or in my understanding of the problem.

I opened 250 points problem. I only had 10 minutes. I realized that it could be solved by a binary search. The matching afterwards could be done with some greedy strategy. But I had the *brilliant* idea to use min-cost-flow to solve this. Unfortunately, it seems I spent more time than I planned pasting and tweaking my min-cost-flow solver (It didn't help that KawigiEdit has the habit of turning slow when there is a lot of code).

At the end, this one last SRM has taught me. The strategy is too risky. I need a change.

This is the reason that , from now on, I will change my strategy: I will no longer open the easy problem during the coding phase. I will only open the medium and hard problems and dedicate all the coding time to attempt to solve at least one of them.

I bet this new strategy will be much less risky!
(Wikimedia Commons)

Read More

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);
}

Read More