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.
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.
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
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!
The editorialist has mentioned that. BIT and Fenwick tree are the same.
thanks a lot meooow!! I was myself searching for one!!!
No problem 
50000 bytes is the source code limit and not the memory limit
Thanks for the clarification. Can you tell me the memory limit?
@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 ?
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.
yeah, Got it
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