CAOS3-Editorial

PROBLEM LINK:

Practice
Contest

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.

  1. If there are no possible moves from a configuration, then the sg number of that configuration is 0.
  2. 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.
  3. 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.

  1. The sg number of an empty subrectangle (with 0 number of rows and columns) is 0.
  2. 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.
  3. 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.

7 Likes

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

1 Like

Tester’s solution uses top-down approach + memoization. Please include brief explanation in editorial :slight_smile:

TC: O(N^6) :open_mouth:

could you explain what axis-parallel rectangle is ?

Similar Question

www.spoj.pl/problems/BOMBER

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

I am having trouble understanding this part

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)

Could someone please tell me why should we choose the smallest non-negative number?

1 Like

@deepai_dutta

The Sprague-Grundy 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 {C1, C2, …, Ck}, the exact nimber N ≥ 0 equivalent to C (denoted sg©) is the smallest non-negative number not present in {sg(C1), sg(C2), …, sg(Ck)}.

One of the requirements for being equivalent to the nimber N is that there should be configurations Ci that lead to each of the nimbers {0, 1, 2, …, N-1}, 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 Ci having a nimber sg(Ci)=S which is > N. Now, by definition, from the configuration Ci we can reach any of the nimbers {0, 1, 2, …, S-1}. This set includes N.

This means that any move which moves a configuration C (with sg©=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 Ci to one with a higher nimber (sg(Ci)=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 criteria–it just makes the game longer.

More details here.

2 Likes

got it thanks :slight_smile:

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][M-1][N-1] will give result.

Yes because [0][0][M-1][N-1] represent the original starting biggest rectangle