PROBLEM LINK:Author: Kaushik Iska DIFFICULTY:EASYMEDIUM PREREQUISITES:SpragueGrundy theorem, Dynamic programming PROBLEM:Two players are playing a game on a rectangular grid in which some point are "candidate locations". At any point the grid is splitted into several axisparallel rectangles. On each turn a player picks a rectangle having at least one candidate location, picks a candidate location from the rectangle, and splits the rectangle into four or fewer rectangles by removing the row and column having the picked candidate location. The player making the last move wins. The problem is to find if any of the two players have a winning strategy. QUICK EXPLANATION:This problem is a classical example of SparagueGrundy theorem. We have an impartial game, i.e., the set of allowable moves depend entirely on the current configuration of the grid rather than on the player who is going to make the next move. Hence, the game is equivalent to a nimber, and one needs to compute the spraguegrundy number of the original configuration, if it is nonzero, then the first player wins, otherwise the second player wins. The spraguegrundy number of the original rectangle can be computed using dynamic programming (more details in next section). EXPLANATION:Any two player game where the set of possible moves at any point depend only on the current configuration of the board (grid), and not on the player who is going to make the next move, is called an impartial game. According to SpragueGrundy theorem, any impartial game is equivalent to a standard nimber. This can be used to decide which of the two players have a winning strategy. Each configuration is assigned a nonnegative number called the spraguegrundy number (sg numbers for abbreviation) of the configuration. If the spraguegrundy number of a configuration is zero, then the configuration is a losing configuration, otherwise the configuration is a winning one. How to compute the Spraguegrundy numbers:Before describing the method of computing the sg numbers, let us first define nonoverlapping configurations: Two configurations C_{1} and C_{2} are called nonoverlapping configurations, if making a move on C_{1} does not affect the set of possible moves from C_{2} and viceversa. In our problem, if we had two nonoverlapping rectangles such that a player can pick any of the two rectangles to make a move, then the configurations of the two rectangles are nonoverlapping. Now, let us see how to compute the sg numbers. There are three rules which can be used to compute the sg numbers in a bottomup manner. 1) If there are no possible moves from a configuration, then the sg number of that configuration is 0. Dynamic programming to compute the Spraguegrundy numbers:Now, let us see how we can use the rules from the earlier section to compute the sg numbers in our problem. In our problem, we compute the sg numbers of all subrectangles of the original rectangle in increasing order of size. 1) The sg number of an empty subrectangle (with 0 number of rows and columns) is 0. Here is the snippet to compute the sg numbers of all subrectangles: // sg[xl][xr][yl][yr] represents the sg number of the subrectangle having // line segment joining (xl, yl) and (xr, yr) as its main diagonal. int sg[N][N][N][N]; for (w := 0; w < N; ++w) { for (xl := 0; (xl + w) < N; ++xl) { for (h := 0; h < N; ++h) { for (yl := 0; (yl + h) < N; ++yl) { // Considering the rectangle of width (w + 1) and height (h + 1) // having line segment joining (xl, yl) and (xl + w, yl + h) // as its main diagonal. // Stores the sg numbers of the configurations which result from // splitting this rectangle into 4 smaller ones. hash_map<int> seen_values; for (x := xl; x <= (xl + w); ++x) { for (y := yl; y <= (yl + h); ++y) { // Choosing the monster at location (x, y) and splitting the // rectangle into 4, by removing the row x and column y. if (monster[x][y]) { // If any of the rectangle is degenerate, then its sg number // is taken as 0, e.g., sg[xl][yl][xl  1][yl  1] = 0, which // may occur in the following recurrence if x = xl, y = yl. seen_values.insert(sg[xl][yl][x  1][y  1]^ sg[xl][y + 1][x  1][yl + w]^ sg[x + 1][yl][xl + w][y  1]^ sg[x + 1][y + 1][xl + w][yl + w]); } } } // Smallest nonnegative number not in the set S described above. s := 0; while (true) { if (!seen_values.find(s)) { sg[xl][yl][xl + w][yl + h] = s; break; } ++s; } } } } } Finally, if sg[0][0][M  1][N  1] is nonzero, then first player has a winning strategy, otherwise second player has a winning strategy. Time Complexity:O (N^{6}) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be put up soon.
This question is marked "community wiki".
asked 14 Oct '13, 16:05

The SpragueGrundy theorem says that any given rectangle in the grid is equivalent to a particular nimber. We can show that, for a given configuration C that can lead to the configurations {C_{1}, C_{2}, ..., C_{k}}, the exact nimber N ≥ 0 equivalent to C (denoted sg(C)) is the smallest nonnegative number not present in {sg(C_{1}), sg(C_{2}), ..., sg(C_{k})}. One of the requirements for being equivalent to the nimber N is that there should be configurations C_{i} that lead to each of the nimbers {0, 1, 2, ..., N1}, but there should not be one that leads to N. This is easily seen to be true because of our choice of N (as the smallest excluded element). Now consider what happens if a player moves to a configuration C_{i} having a nimber sg(C_{i})=S which is > N. Now, by definition, from the configuration C_{i} we can reach any of the nimbers {0, 1, 2, ..., S1}. This set includes N. This means that any move which moves a configuration C (with sg(C)=N) to another with higher nimber can easily be reverted! So, if you're in a losing position and you decide to move a configuration C_{i} to one with a higher nimber (sg(C_{i})=S), the other player can simply move that again to one with nimber N, so you're in a losing position again. And if you're in a winning position, there's no need for you to increase the nimber of any configuration, because you're already in a winning position! In other words, increasing the nimber is irrelevant to the winning criteriait just makes the game longer. More details here. answered 22 Oct '13, 08:02

Fun problem thanks  I enjoyed it even though I got WA  I feel I was very very close. Can anyone see the bug in my code? I got WA: http://www.codechef.com/OCT13/status/CAOS3,robertking answered 15 Oct '13, 02:56
I think this part of your code, game1 := win(i1, j1, i, j) game2 := win(i1, j + 1, i, j2) game3 := win(i + 1, j1, i2, j) game4 := win(i + 1, j + 1, i2, j2) is wrong. But i might be wrong
(16 Oct '13, 23:36)

I am having trouble understanding this part
Could someone please tell me why should we choose the smallest nonnegative number? answered 21 Oct '13, 14:31

Similar Question answered 16 Oct '13, 23:30

The editorial is quite confusing. At beginning of snippet it is written sg[xl][xr][yl][yr] represent rectangle with diagonal (xl,yl)>(xr, yr) but at the end it is written sg[0][0][M1][N1] will give result.
link
This answer is marked "community wiki".
answered 21 Nov '13, 02:17

Tester's solution uses topdown approach + memoization. Please include brief explanation in editorial :)
TC: O(N^6) :O
could you explain what axisparallel rectangle is ?