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.
0000000000 1010110100 1101111100 ...
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 2n 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 2m 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(3m) 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(3m) 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(3m) 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