Whats the approach in this question?

#1

I dont think that I’m able to figure out the correct approach. I felt I could bottom up the grundy number of each cell in 1000 X 1000 matrix and answer each query in constant time, since test cases are 10^5. But I’m unable to compute the grundy number of entire matrix. Can you help me out in this?

#2

Hey @ayushjain.iitg
Don’t think about grundy numbers. They are just a tool to game theory questions. There is a logical answer here. You can divide the 1000*1000 region into 3 regions. 2 regions have win and 1 has lose. This about it once.

#3

https://drive.google.com/open?id=1-GWl2478LNM3XoPZkgftRc81Ug3nc4_r

I tried to think and I saw the pattern that the upper triangular points are symettric with lower triangular points and if I talk about points in upper triangular where it is a loss, the points follow a common pattern : first increment is of 1,2 then 2,3 then again 1,2 and then again 2,3 … so basically I got this, but this gives me wrong answer :frowning:

#4

The points of loss is:
(1,2)
(3,5)
(4,7)
(6,10)
in the upper triangular region

#5

The 3 regions are as follows -

  1. If you are on final point row, col or diagonal you win
  2. If by making a move in any direction you end up at (1) only then you lose
  3. Otherwise you win
1 Like
#6

Ya, I understood your point!
I solved it now, thanks!
Also, my formula was valid!! (with some tweaks about base cases) - it needs no preprocessing!
I thought preprocessing might get TLE!
But it also passed!

1 Like