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];

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)

{

int res = dpRabbit[y][x][x0][x1];

if (res == -1) {

if ( !(x0 <= x && x < x1) ) {

res = (costs[y+1][x] - '0') + playEel(y+1,x, x,x);

} else {

res = INF;

if (x0 > 0) {

res = sum(y, x0-1, x) + playEel(y,x0-1, x0,x1);

}

if (x1 < w) {

int tem = sum(y, x+1, x1+1) + playEel(y,x1, x0,x1 );

res = std::min(res, tem);

}

}

dpRabbit[y][x][x0][x1] = res;

}

return res;

}

int playEel(int y, int x, int x0, int x1)

{

int res = dpEel[y][x][x0][x1];

if (res == -1) {

if (y == h - 1) {

res = 0;

} else {

res = playRabbit(y,x, x0,x1);

if( x1 - x0 < w - 1) {

int tem = playRabbit(y,x, std::min(x0,x), std::max(x1,x+1) );

res = std::max(res, tem);

}

}

dpEel[y][x][x0][x1] = res;

}

return res;

}

int play(vector <string> costs)

{

this->costs = costs;

h = costs.size(), w = costs[0].size();

memset(dpRabbit, -1, sizeof(dpRabbit));

memset(dpEel , -1, sizeof(dpEel));

int best = INF;

for (int i=0; i<w; i++) {

best = std::min(best, (costs[0][i]-'0') + playEel(0,i, i,i) );

}

return best;

}