PSHTBRTH - Editorial

editorial
game-theory
march17
medium
pshtbrth
segment-tree
sprague-grundy

#2

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


#3

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


#4

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?


#5

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


#6

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.


#7

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


#8

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


#9

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


#10

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.


#11

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


#12

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!


#13

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


#14

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


#15

Thanks @meooow


#16

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


#17

No problem :slight_smile:


#18

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


#19

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


#20

See admin’s answer here.


#21

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