PROBLEM LINK:Author: Ivan Fekete 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 nonzero 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 SpragueGrundy 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 1In 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 2In 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 3In this subtask, we have $N, M \leq 10^5$. The intended solution is to use SpragueGrundy theorem to decompose the game on matrices in a range $[L, R]$ into $RL+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 nonzero 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 nonnegative 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 nonnegative 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 SpragueGrundy 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 nonzero. 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:
This question is marked "community wiki".
asked 11 Mar '17, 08:56

Hi Everyone! I was finally able to make a video editorial on this problem. Here is the link:
Cheers! answered 22 Mar '17, 10:04
2
Thanks dude!! I REALLY was carving for a video editorial for this one!! Made my day!! THANKS AGAIN!! :)
(22 Mar '17, 10:14)

In this task you can use BIT instead of a segment tree, it's easier to implement and runs faster. answered 13 Mar '17, 16:10

@sau1999 playing optimally doesn't mean that they choose only maximum possible rectangle,they play for winning the game so if pishty select the submatrix [1 1] ,then neverthless he will lose the game.therefore he will select the submatrix [1] in submatrix [1 1],and finally pishty will win the game.If you will go through deep,then u will find that position of 1's in matrix decide whether pishty or lotsy win the game .And it is already fixed for every matrix that who will win the game,and playing optimally means if pishty have any chance to win the game,then he will absolutely win the game otherwise lotsy win. answered 14 Mar '17, 21:24

int bit[(1<<16)]; I guess 2^16 * 4 bytes are used to store bit array. That is 65536*4 = 262144 bytes. We are provided with 50000 bytes. Shouldn't the solution go out of memory? answered 13 Mar '17, 19:06
3
50000 bytes is the source code limit and not the memory limit
(13 Mar '17, 19:18)
Thanks for the clarification. Can you tell me the memory limit?
(13 Mar '17, 20:47)
See admin's answer here.
(13 Mar '17, 21:27)

Can someone explain how the sparse grundy number is calculated for the matrix above in detail. I don't understand the way to find the grundy value for all the possible position from the first position ans so on. answered 15 Mar '17, 20:58

Can someone tell a good source for learning SpragueGrundy Theorem , in general Grundy Numbers ? answered 13 Mar '17, 17:09
7
Sure, TopCoder has a very nice tutorial. There's another one on geeksforgeeks.
(13 Mar '17, 17:11)
Thanks @meooow
(13 Mar '17, 17:14)
thanks a lot meooow!! I was myself searching for one!!!
(13 Mar '17, 17:30)
1
No problem :)
(13 Mar '17, 17:37)

Can somebody explain me the first test case of problem Pishty and birthday because i think that answer should be Losty as First move : Pishty and she will pick [1 1] submatrix
answered 14 Mar '17, 15:45
1
optimally means that Phishty won't pick that move. Instead, she will pick [1] only out of the two consecutive ones. Then , Lotsy will have to pick only a [1] and then phishty will do so again and since then Lotsy won't have any moves, the former wins.
(14 Mar '17, 21:19)

Sir please elaborate, how to solve the answer for 2^16 possiblities of a singl egame.I have read SpragueGrundy Theorem but i dont understand how the game is solved.Please as i was stuck on this question for far too long. answered 14 Mar '17, 16:12

@sau1999 Firstly, Pishty can pick any single 1 from [1 1]. Now Lotsy will have to pick any of the two remaining single 1s and Pishty will pick up the last 1 and win. (Note that both are playing optimally) answered 14 Mar '17, 17:00
@avi224 i can't understand why Pishty will choose single 1 from [1 1] as they are playing optimally Pishty will choose max rectangle size. Can you clarify that ?
(14 Mar '17, 20:33)
