PSHTBRTH - Editorial

PROBLEM LINK:

Practice
Contest

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.

3 Likes

In this task you can use BIT instead of a segment tree, it’s easier to implement and runs faster.

3 Likes

Can someone tell a good source for learning Sprague-Grundy Theorem , in general Grundy Numbers ?

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?

1 Like

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

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.

@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)

@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 ?

@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.

2 Likes

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.

1 Like

can any one explain what is happening in 6 loops to calculate grundy values

Hi Everyone!

I was finally able to make a video editorial on this problem. Here is the link:

Pishty and Birthday

Pishty Image

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!

11 Likes

The editorialist has mentioned that. BIT and Fenwick tree are the same.

3 Likes

Sure, TopCoder has a very nice tutorial. There’s another one on geeksforgeeks.

7 Likes

Thanks @meooow

thanks a lot meooow!! I was myself searching for one!!!

No problem :slight_smile:

1 Like

50000 bytes is the source code limit and not the memory limit

3 Likes

Thanks for the clarification. Can you tell me the memory limit?

See admin’s answer here.