[1] Winning condition in Step 3

Let us call the cell designated in Step 1 the start cell, and denote it by S.

Alice’s winning condition is as follows:

• For each row \(i\), a cell \((i,y_i)\) can be chosen so that:
  • \(y_{i+1}\in \lbrace y_i-1,y_i+1\rbrace\) (\(1\leq i\leq N-1\))
  • Of the cells adjacent to the left and right of cell \((i,y_i)\), any that exist are white.
  • The start cell \(S\) is a white cell adjacent to the left or right of some \((i,y_i)\).

If we call cells of the form \((i,y_i)\) type-A cells, and the cells adjacent to their left and right type-B cells, one example of the winning condition is illustrated as follows:

.BAB...
BAB....
AB.....
BAB....
.BAB...
..BAS..  the start cell S is also B
.BAB...
..BAB..

---

[2] Proof of sufficiency of the winning condition

First, consider the case where we can choose \((i,y_i)\) satisfying the conditions in [1]. In this case, we can observe the following:

• For every type-B cell, a type-A cell exists on at least one side (left or right).
• For every type-A cell, any adjacent cell (up, down, left, or right) that exists is a type-B cell.

The former is clear from the definition, and the latter follows from \(y_{i+1}\in \lbrace y_i\pm 1\rbrace\). From this, Alice can win with the following strategy:

• Alice’s strategy: always move toward a type-A cell.

Since the start cell is type-B, Alice can move toward a type-A cell. As long as Alice continues this strategy, Bob’s destination is always a type-B cell. Therefore, Alice can continue this strategy indefinitely.

At the end of the game, the last turn is Bob’s, and his destination is a type-B cell (hence a white cell). Therefore, Alice wins.

---

[3] Proof of necessity of the winning condition

Assume Alice has a winning strategy, and fix one.

Suppose the start cell is in row \(k\), and define type-A cells as follows:

• When Bob takes the strategy of moving upward for the first \(k-1\) turns, the cells to which Alice moves the piece are called type-A cells.
• When Bob takes the strategy of moving downward for the first \(N-k\) turns, the cells to which Alice moves the piece are called type-A cells.

This defines exactly one type-A cell from each row (a minor point: we use the fact that the number of turns \(10^{10}\) is larger than \(k-1\) and \(N-k\)). Denoting these positions as \((i,y_i)\), we verify the conditions stated in [1].

\(y_{i+1}\in \lbrace y_i-1,y_i+1\rbrace\) is clear from the definition. It remains to show that, if the cells adjacent to the left and right of a type-A cell are called type-B cells, those type-B cells are white.

By definition, a type-A cell is a cell that Alice moves the piece to under some strategy of Bob. Therefore, cells adjacent to a type-A cell are cells that Bob can potentially move the piece to on the next turn.

Once Bob can move the piece to a cell on some turn, Bob can always return to that cell on subsequent turns. Therefore, if we assume such a cell is black, Bob could win. Since we assumed Alice has a winning strategy, this cell must be white.

We have thus shown that the winning condition in [1] is necessary for Alice to win.

---

[4] Computing the answer

For each cell, we compute the minimum cost required to make that cell a type-A cell while satisfying the conditions in [1].

The way to determine the type-A cells above and below any given cell can be considered independently, and the minimum costs for all cells can be computed using a simple dynamic programming.