I took a bit longer to write this than planned. I really wanted to do it before the 48 hours limit this time. Oh well.

The following is the WIP editorial. The official link (http://apps.topcoder.com/wiki/display/tc/SRM+581 will be updated eventually with corrections and fixes.

## YetAnotherBoardGame

## Bits and Xors

Let us begin by turning the board into a matrix of 1s and 0s. Black cells are represented by 0s and
White cells by 1s. The objective is to make all cells into 0s. The two operations *toggle* some
of the cells, the 0s become 1s and the 1s become 0s. We can see it as performing the xor
operation between some part of the matrix and the two following shapes:

010 010 101 111 010 010

## A single row changes everything

The problem is all about picking the number of times (0 or 1) we apply one of the two moves on a single cell, and of course the types of cells you we use. The order in which the moves are done doesn't really matter. Let us do it from top to bottom.

Let us decide what moves to do in the first row. A subset of the cells will be used in moves. The type of move to use in this row is also a variable. We are free to choose any subset and any type of move. The moves we perform will only affect the first and second row, because for a cell (0,i), the affected cells wold be: (0,i-1), (0,i+1) and (1,i) (Depending if they exist or not) and (0,i) in case a type 2 move was used. Cell (-1,i) does not exist. The crux of the matter is that after we decide which cells to use and the kind of move, the first two rows will contain some 1s and 0s:

1001010101 0101101010 0001010101 ... 010 Use 101 (type 1) centered at cells (0,2), (0, 5) and (0,6): 010 1100101001 0111110010 0001010101 ...

We should then progress to decide what moves to use for the second row. The key observation is
that this is our last opportunity to alter the contents of the first row. A move of any type in cell (1,**i**)
will forcefully toggle the contents
of cell (0,**i**). This means that for every cell (0,**i**) that is 1, we *must* make a move
using cell (1,**i**) (So that (0,**i**) becomes 0) and if (0,**i**) is 0, we *cannot* make
a move using cell (1,**i**). In the example above, we are forced to make moves using cells
(1,0),(1,1),(1,4),(1,6) and (1,9). It appears the only decision we can afford to make is the type of move for this row. Should we
use a type 1 move or a type 2 move? In reality, remember that we are making a move at (1,6) and that previusly, we did a move at (0,6), so the type of move
in both cells (they share a column) must be the same. Just like that, we are forced to make type 1 moves at specific cells of row 1.

000000000010101101001101111100...

We should proceed to the third row. This is our last chance to set the contents of the first row to 0. Which means that we need moves at (2,0), (2,2), (2,4), (2,5) and (2,7). In addition, the move type for (0,2) is already known. We can use this logic on each row, using the previous rows to select the moves. Until we decide the moves for the last row, if after these moves, the last row is full of zeros (and since the previous moves were made so that each of the previous rows ended full of zeros too) then we reached the objective in a specific number of moves.

Information from previous rows *may* also allow us to know
the move type for the current row. Although there can be a case in which there is not a specific requirement. Consider this new example:

0111000010 0010000101 0000000010

For the first row, we use only a type 2 move at cell (0,2):

0000000010 0000000101 0000000010

In order to set the first row to 0, we need a move at (1,8), but this time we can choose any type of moves. It is incidentally best to pick a type 2 move.

There is also a corner case. What if we need to set some cells in a row, but two of those cells have columns that have already-chosen move types that contradict each other, then it is not possible to make any progress in the given situation.

This logic that picks one of 2^{n} subsets of cells and the type
for the moves in the top row and then fills the remaining rows from top to bottom, deciding the movement type
if possible and cropping the invalid cases can be implemented using a recursive
backtracking. It is possible
to implement the recursion in a way that we only need one binary operation to update the rows
according to the application of a move to a subset of cells in a row. If such an optimization
is used, this recursive approach will actually pass in time. The next section will develop an
iterative solution that also demonstrates that the time complexity of the
recursive solution is fast enough.

## Row and columns

In the previous section, the moves of the top row and their type are decided. Then, for each row, the moves are deduced from the previous row and their type may be decided. At the end, a sequence of moves that reaches the objective can be represented solely by the subset of cells from the first row that participate in moves and the movement types decided for each row.

Turns out it is also possible to represent a valid sequence of moves by the cells chosen for the first
row and the types chosen *for the columns*. Let us assume the types to be used in each column were already chosen and that we
choose the initial sets to be used in moves in the top row:

211112112 (Move types decided for each column) --------- 010101010 Apply 111 centered at cell (0, 5): 111001111 1 000111100 110101010 -> 010110110 111000111 000111100 110101010

(0,5) was the only move in row 0, we proceed to row 1, and once again, the only way to set the 1s in row 0 to 0s is to use specific row 1 cells in moves: (1,1), (1,3), (1,4), (1,6) and (1,7). This time, the move types of the columns are already decided. We just need to make sure they are all the same for each of the chosen cells (so that the row only uses one move type). If they are not, the initial combination of moves and column types was invalid. We can once again, use this logic for each of the rows.

Let us say the cells in a row i that are used in moves are: (i,c1), (i,c2), ... (i,ct). Because row
i must use moves of only one type, the columns c1,c2,...,ct must be
of either type 1 or type 2, but not both. (The exception is when the set of used columns is empty). This is true
even for row 0 and limits the number of possible combinations of column types and cells used in row i. We pick
one of 2^{m} subsets of columns, name the subset **colType**. The cells used in
moves in row 0 will also be part of a set, **u0**. **u0** must either be a subset of **colType** or
a subset of the complement of **colType**.

There are O(3^{m) ways to pick two subsets A and B of a set X of m elements such that A c B. As a quick
proof: It is like for each of the m elements of X, we decide one of three choices: 0,1 and 2. 0 means
that the element does not belong to A and does not belong to B. 1 means that the element
belongs to A but does not belong to B and 2 means the element belongs to B (and therefore A). We can use
this fact to show that there are 2*3m pairs (colType, u0). There are 3m pairs
in which (u0 c colType) and 3m other pairs in which (u0 c ~colType) (Where ~ is the complement operator). }

## Implementation details

The first step is to pick each of the pairs (**colType**, **u0**). **u0** must be subset of
**colType** or ~**colType**. We should make sure to pick the pairs in O(3^{m}) time. We can
use a backtracking, but a nicer approach is to represent the sets by bitmasks and use the trick explained
in this tutorial: A bit of fun: fun with bits. We first use
it to iterate the subsets of **colType** and then we use it again to iterate the subsets of ~**colType**.

For a given pair of sets (**colType**, **u0**) we need to evaluate if it is a
valid starting move and count the number of moves used. We can trivially simulate all the moves for each row in O(**n*****m**), but
it is possible to do it in **n** steps (and possibly the only way to pass this problem within the time limit). To
accomplish this, we will once again use bitmasks.

Let us apply a set **ui** of moves of type 1 in row **i**:

- This means that some cells in
row (
**i**-1) (If it exists) will be toggled. Specifically, those cells (**i**-1,**k**) such that**k**belongs to**ui**. This is the same as doing:**row**[i-1] =**row**[i-1]*xor***ui**. - Some cells in row 1 will be toggled, some cells may be toggled more than once (by multiple moves). For
each
**k**that belongs to**ui**, the toggled cells will be (**i**,**k**-1) and (**i**,**k**+1). Let us do the moves in order:**row**[i] =**row**[i]*xor*(**ui**>>1); //(**ui**>>1) will shift each bit in ui to the right, if the k-th bit // is on in**ui**, the (k-1)-th bit will be on in (**ui**>>1).**row**[i] =**row**[i]*xor*(**ui**<<1); // This is the same but shifting left.**row**[i] =**row**[i] & ( (1<<**m**) -1); // ( (1<<**m**) -1) returns a integer with m 1 bits. // Since the previous step could have left bit**m**as 1, we should clean // this extra bit by making sure to include only the first**m**bit positions. - The cells in row (
**i**+1) (If it exists) will be toggled in the same way the cells in row**i**were toggled.

For type 2 moves, the logic is the same, but we do an extra operation: **row**[i] = **row**[i] *xor* **ui**.

We can also do other steps, like verifying if **ui** is a subset of **colType** or ~**colType** in a single step. The rest
is to implement the following solution. It is evident that the following c++ solution does **n** operations for each
of the O(3**m**) pairs (**colType**, **u0**). It needs 0.8 seconds in its worst case, and there is
room for more optimization.

`int rowCopy[1<<13];`

int row[1<<13];

int toggle1[1<<13];

int toggle2[1<<13];

int minimumMoves(vector <string> board)

{

int n = board.size(), m = board[0].size();

// Represent each row as a binary number:

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

rowCopy[i] = 0;

for (int j=0; j<m; j++) {

rowCopy[i] |= ( (board[i][j] == 'W') << j );

}

}

// We will precalculate the operations needed to toggle

// row i when using a type 1 (or type 2) move in a given

// set of cells in that row. (mask is the set).

for (int mask = 0; mask < (1<<m); mask++) {

// *

// * * <- This part:

// *

toggle1[mask] = ( (mask << 1) & ((1<<m)-1) );

toggle1[mask] ^= (mask >> 1);

// *

// *** <- This part:

// *

toggle2[mask] = toggle1[mask] ^ mask;

}

// e.g: We apply a set mask of type 2 moves in row i, then

// the operation to perform is row[i] = row[i] ^ toggle2[mask].

const int INF = n*m+1;

int best = INF;

// Iterate all the subsets colType of the columns:

for (int colType = 0; colType < (1<<m); colType++) {

int negaColType = colType ^ ( (1<<m) - 1); //The complement of colType

// The sets from which we will extract (u0) as subsets:

int maskarr[2] = { colType, negaColType };

// The used cells in row0 must be a subset of colType OR negaColType

// This means the number of pairs (colType, u0) is O(3^n):

for (int k=0; k<2; k++) {

int mask = maskarr[k];

// Iterate through the subsets of mask:

// Nice trick? It is thanks to this tutorial:

// http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation

for (int u0 = mask; u0 >= 0; u0 = (u0? ((u0 - 1)&mask) : -1) ) {

// load a copy of the rows

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

row[i] = rowCopy[i];

}

if (u0 & colType) {

//type 2

row[0] ^= toggle2[u0];

} else {

//type 1

row[0] ^= toggle1[u0];

}

if (n > 1) {

row[1] ^= u0;

}

int flips = __builtin_popcount(u0);

// __builtin_popcount(u0) returns the number of 1 bits in u0

// flips will hold the total number of moves we used.

bool good = true;

// For the remaining rows:

for (int i=1; i<n; i++) {

//we want row[i-1] to become 0.

//thus the mask must be equal to row[i-1]

int ui = row[i-1];

flips += __builtin_popcount(ui);

// ui must be a subset of colType or negaColType

// The superset determines the kind of move to use in row i:

// How the moves in ui affect row[i-1]:

row[i-1] = 0; //same as row[i-1] ^= ui (not actually needed)

// How the moves in ui affect row[i]:

// ui should be a subset of type2 or type1.

bool type2 = ( (colType & ui) == ui );

bool type1 = ( (negaColType & ui) == ui );

if (type2) {

row[i] ^= toggle2[ui];

} else if (type1) {

row[i] ^= toggle1[ui];

} else {

// Not a subset of either of them, we cannot use

// a valid sequence of moves to set row[i-1] to 0.

good = false;

}

// note that for ui==0, type2 and type1 are true, it does not

// matter because toggle2[0] = toggle1[0] = 0 and no moves are done

// The moves also affect row[i+1]:

if (i+1 < n) {

row[i+1] ^= ui;

}

}

// The final row must be full of zeros:

good = good && (row[n-1] == 0);

if ( good ) {

// If it is valid, remember the minimum number of moves:

best = std::min(best, flips);

}

}

}

}

return (best < INF) ? best : -1;

}

## Conclusion

This was a nice problem and it is surprising that the easiest solution works in time. It was a bit complicated to explain though. I wonder if it would have been better with images?

## No comments :

Post a Comment