PROBLEM LINK:
Author: Kaushik Iska
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Sprague-Grundy 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 axis-parallel 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 Sparague-Grundy 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 sprague-grundy number of the original configuration, if it is non-zero, then the first player wins, otherwise the second player wins.
The sprague-grundy 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 Sprague-Grundy 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 non-negative number called the sprague-grundy number (sg numbers for abbreviation) of the configuration. If the sprague-grundy number of a configuration is zero, then the configuration is a losing configuration, otherwise the configuration is a winning one.
How to compute the Sprague-grundy numbers:
Before describing the method of computing the sg numbers, let us first define non-overlapping configurations: Two configurations C1 and C2 are called non-overlapping configurations, if making a move on C1 does not affect the set of possible moves from C2 and viceversa. In our problem, if we had two non-overlapping rectangles such that a player can pick any of the two rectangles to make a move, then the configurations of the two rectangles are non-overlapping.
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 bottom-up manner.
- If there are no possible moves from a configuration, then the sg number of that configuration is 0.
- If a configuration can be seen as the union of two or more non-overlapping configurations, then sg number number of this configuration is the same as the XOR of the non-overlapping configurations.
- If there are several moves possible from a configuration leading to configurations C1, C2, …, Ck, then the sg number of this configuration is the smallest non-negative number not present in the set S = {sg (C1), sg(C2), …, sg(Ck)}.
Dynamic programming to compute the Sprague-grundy 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.
- The sg number of an empty subrectangle (with 0 number of rows and columns) is 0.
- If a subrectangle has no monster location inside it, then there are no possible moves to split this subrectangle, hence sg number of this subrectangle is 0.
- If there are k monster location inside a subrectangle, that means there are k possible moves from this configuration by picking any of the monster location and splitting this subrectangle into four smaller subrectangles by removing the row and column of the monster. In order to compute the sg number of this subrectangle we should compute the sg numbers of all k resulting configuration, and then pick the smallest non-negative number which was not present in the set S = {sg (C1), sg(C2), …, sg(Ck)}. Note that each of the resuling configuration Ci is the union of four non-overlapping subrectangles, hence sg(Ci) is the XOR of the sg numbers of the 4 smaller subrectangles.
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 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 non-negative 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 non-zero, then first player has a winning strategy, otherwise second player has a winning strategy.
Time Complexity:
O (N6)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution can be found here.
