×

PSHTBRTH - Editorial

Author: Ivan Fekete
Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak

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:

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.

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.

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.

This question is marked "community wiki".

74484997
accept rate: 12%

19.7k350498541

 9 Hi Everyone! I was finally able to make a video editorial on this problem. Here is the link: Pishty and Birthday If you need some theory on Grundy Numbers or Sprague Grundy, you can check out the respective videos. If you have any doubts, please don't hesitate to get them clarified. Looking forward to your suggestions. Cheers! answered 22 Mar '17, 10:04 4★gkcs 2.6k●1●11●27 accept rate: 9% 2 Thanks dude!! I REALLY was carving for a video editorial for this one!! Made my day!! THANKS AGAIN!! :) (22 Mar '17, 10:14) 1 Thanks @vijju123 :-) (22 Mar '17, 10:18) gkcs4★
 3 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 4★linkret 236●5 accept rate: 25% 3 The editorialist has mentioned that. BIT and Fenwick tree are the same. (13 Mar '17, 16:36) meooow ♦6★
 2 @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 21●2 accept rate: 0% yeah, Got it (15 Mar '17, 12:03) sau19994★
 1 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 4★raja379 89●2 accept rate: 0% 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) raja3794★ See admin's answer here. (13 Mar '17, 21:27) meooow ♦6★
 1 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 11●1 accept rate: 0%
 0 Can someone tell a good source for learning Sprague-Grundy Theorem , in general Grundy Numbers ? answered 13 Mar '17, 17:09 497●1●8 accept rate: 15% 7 Sure, TopCoder has a very nice tutorial. There's another one on geeksforgeeks. (13 Mar '17, 17:11) meooow ♦6★ 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) meooow ♦6★
 0 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 Second move : Loshty and she will pick [ 1 ] submatrix third move : Now it's Pishty's chance and she can't make any move so Loshty Has won the game answered 14 Mar '17, 15:45 4★sau1999 65●1●4 accept rate: 0% 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)
 0 Sir please elaborate, how to solve the answer for 2^16 possiblities of a singl egame.I have read Sprague-Grundy 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 3★ryuzakil -3●1 accept rate: 0%
 0 @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 4★avi224 218●1●10 accept rate: 18% @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) sau19994★
 0 @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 ? answered 14 Mar '17, 20:12 4★sau1999 65●1●4 accept rate: 0%
 0 can any one explain what is happening in 6 loops to calculate grundy values answered 19 Mar '17, 19:15 1 accept rate: 0% 1 those 6 loops check all the possible state that can be visited from the current state. It checks whether a submatrix has all ones in it or not. if it is having all ones then we clear that submatrix and goes to a lower state otherwise we break the loop. Hope it helps :) (21 Mar '17, 11:44)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,497
×2,559
×1,727
×316
×124
×59
×4

question asked: 11 Mar '17, 08:56

question was seen: 3,256 times

last updated: 22 Mar '17, 10:18