SRM 580 recap and WallGameDiv1 editorial preview

I intended to make a recap post of SRM 580 on Saturday. Then I got a blog writer's block.

This was a interesting match. I started with my risky strategy as usual, but this time, I opened the hard problem first. I liked it and it seemed like I could solve it. There was a time in which I doubted it and opened the medium problem... But I came back to the hard problem.

Eventually, I thought of a solution. I had plenty of doubts about it being correct. But I decided to give it a try. With a bit more than 10 minutes left for the match, I finished the code. But it was failing all example cases. I was supposed to open the easy problem when there were 10 minutes left, but I decided to gamble and use 2 more minutes trying to fix the bug. It turned out to be a simple bug - I forgot that the Rabbit has to pay the cost for the initial cell. Passed examples and rushed to open the easy problem.

The easy problem seemed approachable, but I had little time to do it. I quickly noticed that you only needed to worry about the end points. But for some reason I thought of a very wrong dynamic programming approach. I kept failing examples, and when there was little time left, I decided to submit a wrong solution for fun. felix-halim turned out to be the one to take advantage of this easy challenge.

I spent the intermission and challenge phase nervous and unconvinced I actually solved a hard problem. Then it turned out I passed system tests. That's about the time an actual formal proof for my approach appeared in my head. Great, I guess.

WallGameDiv1 editorial

Problem statement.

As usual, this is just the editorial preview. The official page will be updated better and have more fixes when it is finished.

From Eel's perspective

Let us see the game from Eel's perspective. Eel must decide both the time and location to place the walls.

Not giving away too much information

Consider an extreme case, Eel decides to place all the walls that it can just before the first turn. This sub-problem is basically the same as the division 2 version. After Eel places all the walls in this manner, there will still be a path that Rabbit can take. Since Rabbit already knows all the positions of the walls, Rabbit can take the direct, simplest path possible.

What happens is that when Eel places more walls than it needs to place in a step, it gives Rabbit more information than necessary. At any time, Eel should place only enough walls to force Rabbit into the worst path possible, but not more walls than that.

To place or not a wall directly bellow the Rabbit

Assume there is already a wall bellow the Token, Eel does not need to place any additional wall until the Rabbit moves the Token to a cell that has no walls bellow it. If Eel placed any wall before the Rabbit moves to one of those cells, Eel would be handling Rabbit information for free. Consider the following example, which is an extreme case:

If Eel places the remaining wall of the row too soon, Rabbit would know which side of the row is better to move to and will move directly to it. It is better for Eel to wait until the Rabbit takes the token to either extreme, making the Rabbit revisit many cells:

Eel should always wait until the token is placed on a cell that does not have a wall directly bellow it. Then Eel should decide between placing the wall in that location or not. In case all of the other cells in the row already have walls, Eel is unable to place a wall in that location (Because Eel cannot make the game completely impossible). The decision that Eel makes (place or not a wall bellow the current cell) will be the one that will require the largest cost.

From Rabbit's perspective

Rabbit wants to minimize the cost. Assume Rabbit placed the Token above a cell that does not have a wall directly bellow to it. There are two possibilities: a) Eel will place a wall bellow that cell or b) Eel will not place a wall bellow the cell.

In case the Eel didn't place the wall. The rabbit has the option to move to the row bellow it. This decision seems like a very good choice - The lower we move the closer we are to the bottom-most row. It is actually possible to show that this is always the optimal move.

Proof: The current cell position is (x, y). After the Rabbit placed the token on this cell, Eel didn't put a wall bellow it, allowing Rabbit to move to cell (x, y+1). By contradiction: Assume there is a cell (x2, y+1) better than (x, y+1) as a starting point in row y+1. If there is no wall above (x2, y+1), then the Rabbit might try to move to (x2, y). Eel will now have a choice to place a wall bellow (x2, y+1), because we know that the wall space between (x,y) and (x,y+1) is empty, thus it will be a valid move to place a wall between (x2, y) and (x2, y+1). If Eel places this wall, then Rabbit will be forced to move back to (x,y), this time forced to move to (x,y+1), the path cost starting at (x,y+1) is still the same, but Rabbit spent cost units by unnecessarily attempting to move to (x2,y).

Whenever the path to the cell bellow the token is empty, Rabbit must always move down.

The other case is when the Token is already above a wall. Eel will wait until the Rabbit moves above an empty wall space. It makes sense to make the Rabbit take the straight path, either to the left space or the right space. Rabbit must pick the choice that minimizes the overall result (including the cost to move to the empty space).

Dynamic programming

Once the token is in row y, we can ignore any walls in previous rows. The only walls that matter are those that were placed between row y and y+1.

When the token enters the row for the first time, the walls between y and y+1.

form an empty set. If Eel decides to place a wall bellow (x, y) the set of walls will contain only x. Rabbit can choose to move to x+1 or x-1, where Eel will once again have the choice to add a new wall. The new set of walls will be {x-1,x} or {x,x+1}. Let us assume Rabbit move to x-1, Rabbit once again has the choice to move to another cell that is not above a wall. The choices are x-2 or x+1. Note how the set of walls is always an interval of positions.. This is great because there are only O(w*w) possible intervals which we can represent by two variables, x0,x1 such that the interval is [x0,x1). There are only four choices for x, because x will either be outside the interval and be equal to x0-1 or x1 or it can also be at either of the extremes of the interval (equal to x0 or x1-1). The values for y are O(h). All in all, the state of the game can be described by tuple (y, x, x0,x1) and there are O(h*w*w) such tuples.

Define two functions: playEel(y, x, x0,x1) and playRabbit(y, x, x0,x1), that represent the decisions taken by each animal. playEel() returns the maximum possible cost Eel can accomplish after Rabbit moved the Token to a cell that does not have a wall directly bellow it. playRabbit() finds the minimum possible cost assuming that Eel has already decided whether or not to place a wall bellow (x,y).

• playEel(h-1, x, empty interval) is a base case, the Rabbit has managed to move the token to the last row. The Eel knows that the remaining cost is 0.
• playEel(y, x, x0,x1), as a precondition we know that (x,y) is not above a wall. The interval of walls [x0,x1) is either to the left or right of (x). Eel must decide between placing a wall or not. If Eel does not place a wall, it is Rabbit's turn without a wall bellow the token: ( playRabbit(y, x, x0,x1) ). If Eel places a wall, the interval [x0,x1) must be extended to include x, the result is equal to playRabbit(y,x, extended interval). If all the cells of the row (other than x) already contain walls, it is not possible for Eel to place a wall.
• playRabbit(y, x, interval that does not contain x), is the case where Eel decided not to place a wall bellow (y,x), Rabbit must move to the bellow row. After this move, Eel has a chance to decide for the new position. The result is: cost(y+1, x) + playEel(y+1,x, empty interval).
• playRabbit(y, x, interval that contains x), gives the rabbit two choices: Move to the empty cell to the right or left of the interval. This move involves visiting (and paying costs) for a wide number of cells. For example, if Rabbit moves the token to x0-1 , the total cost is: (Cost to move from (x,y) to (x0-1,y) ) + playEel(y,x, x0-1,x1).

These mutually recursive recurrence relations are still acyclic and we should be able to implement them with dynamic programming or memoization.

Code

int w, h;
vector <string> costs;
int dpRabbit[50][50][51][51];
int dpEel   [50][50][51][51];

// Sum of costs between (y,x0) and (y,x1-1):
int sum(int y, int x0, int x1)
{
    int s = 0;
    for (int i=x0; i<x1; i++) {
        s += costs[y][i] - '0';
    }
    return s;
}

int playRabbit(int y, int x,  int x0, int x1)
{
    // Token is currently at point (x,y). There are walls between each
    // (y, i) and (y+1,i) for each x0 <= i < x1 :
    // What should Rabbit do?

    int res = dpRabbit[y][x][x0][x1]; //O(n^3) states because x = x0-1, x0, x1-1 or x1
    if (res == -1) {
        if ( !(x0 <= x && x < x1) ) {
            // no wall bellow the Token. Best to move bellow:
            // It is convenient to use [x,x) as the empty interval. This way the
            // Eel function can easily extend it to include x:
            res = (costs[y+1][x] - '0') + playEel(y+1,x, x,x);
        } else {

            res = INF;
            // Rabbit decides to move to x0 - 1
            if (x0 > 0) {
                // sum(y,x0-1,x) = Cost to move from (x,y) to (x0-1,y).
                // playEel(y,x0-1, x0,x1) = Cost after Eel decides to place
                //                            a wall or not.
                //
                res = sum(y, x0-1, x) + playEel(y,x0-1, x0,x1);
            }
            
            // Rabbit decides to move to x1:
            if (x1 < w) {
                // sum(y, x+1, x1+1) = Cost to move from (x,y) to (x1,y).
                // playEel(y,x1, x0,x1 ) = Cost after Eel decides to place
                //                         a wall or not.
                //
                int tem = sum(y, x+1, x1+1) + playEel(y,x1, x0,x1 );

                // Rabbit wants the smaller cost:
                res = std::min(res, tem);
            }
        }
        dpRabbit[y][x][x0][x1] = res; // memoize the case.
    }
    return res;
}

int playEel(int y, int x,  int x0, int x1)
{
    // Token is currently at point (x,y). There are walls between each
    // (y, i) and (y+1,i) for each x0 <= i < x1 :
    // What should Eel do?
    
    int res = dpEel[y][x][x0][x1]; //Also O(n^3) because x = x0-1 or x1
    if (res == -1) {
        if (y == h - 1) {
            //The token is in the last row. Eel cannot do much about it.
            res = 0;
        } else {
            //What if Eel decides not to place a wall?
            res = playRabbit(y,x, x0,x1); //let the Rabbit do its move
            
            //What if Eel decides to place a wall?
            if( x1 - x0 < w - 1) { //Cannot fill the whole row with walls
                int tem = playRabbit(y,x, std::min(x0,x), std::max(x1,x+1) );
                // extend the interval that contains the wall
                
                // Eel wants the maximum cost:
                res = std::max(res, tem); 
            }
        }
        dpEel[y][x][x0][x1] = res; // memoize the case.
    }
    return res;
}



int play(vector <string> costs)
{
    // Save some variables for use by the functions:
    this->costs = costs;
    h = costs.size(), w = costs[0].size();
    // Initialize dpRabbit and dpEel with -1s.
    memset(dpRabbit, -1, sizeof(dpRabbit));
    memset(dpEel   , -1, sizeof(dpEel));

    // Rabbit picks a starting cell in the top row:
    int best = INF;
    for (int i=0; i<w; i++) {
        // Rabbit wants the choice that costs the least:
        best = std::min(best, (costs[0][i]-'0') + playEel(0,i, i,i) );
    }
    return best;

}