PROBLEM LINK:
Author: Ivan Fekete
Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak
DIFFICULTY:
Medium
PREREQUISITES:
Game theory, Sprague–Grundy theorem, Segment tree
PROBLEM:
Two players play a game with N binary matrices of size 4 \times 4 arranged in a row and numbered from 1 to N. They play optimally and make moves in turns. In one move, the current player can select any non-zero matrix, then select any its submatrix containing only 1's and replace all of these 1's with 0's. The player who cannot make a move is declared the loser and the other player is declared the winner. The goal of the problem is to handle M queries. Each query either changes one of the matrices or asks who is the winner if the game is played on the matrices in a range [L, R].
QUICK EXPLANATION:
Use Sprague-Grundy theorem to decompose the game into separated games, each played with a single matrix. Then, for each of 2^{16} possible matrices compute the Grundy value of a single game played with that matrix. Finally, handle the queries with a segment tree using the fact that the Grundy value of a game played on matrices in a range [L, R] is a XOR of Grundy values of games played with single matrices in that range.
EXPLANATION:
Subtask 1
In the first subtask, both N and M are at most 10, so the constraints are quite low. This allows, for example, a solution similar to the one used for the third subtask, but with computing the Grundy values using a plain recursion with any memoization or dynamic programming.
Subtask 2
In the second subtask, we have N, M \leq 1000. The solution for these constraints is a slow implementation of the solution for the third subtask. For example, one can use a linear scan in order to handle each of M queries in O(N). Please refer to the next section for more details.
Subtask 3
In this subtask, we have N, M \leq 10^5. The intended solution is to use Sprague-Grundy theorem to decompose the game on matrices in a range [L, R] into R-L+1 games played with a single matrix, solve each of these games fast, and then compute the winner of the original game using the theorem and results of these smaller games.
Let’s consider a game played on a single matrix. We are going to assign every position in such a game a Grundy value, also denoted as mex. The idea is that a terminal position gets value 0. In our case, the zero matrix, i.e. the matrix containing only zeros, is the terminal position of the game, so it gets value 0. Then, let’s consider any non-zero matrix A. Let also P be a set of matrices reachable from A in a single move (remember that in a single move the current player selects a submatrix of A containing all 1's and changes all these 1's to 0's). Then, the Grundy value of matrix A is defined as the smallest non-negative integer which is not a Grundy value of any matrix in P. For example, if A have only one cell with value 1, then P contains only the zero matrix, so the Grundy value of A is 1 because the Grundy value of zero matrix is 0. Notice that we can use memoization or dynamic programming in order to compute these Grundy values fast and avoid solving multiple subproblems many times.
Moreover, the position of a game with Grundy value G is a winning position if and only if G \neq 0.
There are 2^{16} possible matrices to consider, and we are going to compute Grundy values for all of them. For a fixed matrix A, this can be done by computing the set P of matrices reachable from A in a single move, computing their Grundy values recursively and then assigning the smallest non-negative integer not present in the set of Grundy values of matrices in P as the Grundy value for A. For implementation details please refer to multiple solutions attached below.
Now, we have computed a Grundy value for every possible game played with a single matrix and the next step is to use the Sprague-Grundy theorem in order to get the value of a game played with matrices in a range [L, R]. The theorem states that the Grundy value of a game being a composition of K games is the XOR of Grundy values of these games. Thus, if we want to compute the Grundy value of a game played on matrices in a range [L, R], we just XOR Grundy values of games on a single matrix played with matrices in that range. It follows that the first player has a winning position if and only if the Grundy value of the game played with matrices in a range [L, R] is non-zero.
Finally, to handle all the M queries fast enough, we can use a segment tree or a Fenwick tree, in order to support both computing XOR of a range of values and updating a single value in that range. Segment tree supports these operations in O(\log N) time, so after the precomputation of Grundy values is done, the complexity of handling all the queries is O(M \cdot \log N). For implementation details please refer to multiple solutions liked below.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.
Editorialist’s solution can be found here.
