Does The Last Problem from the recent Cook-Off have wrong test data?
The constraints clearly mention that all coordinates are <= 1000 so I precomputed a grid of size 1004 * 1004:
That got WA for a very long time. I tried increasing my grid size and it passed…
The value at cell (1000, 1000) is impacted by cell (2000, 0) as well.
So test data is correct.
Ah okay, my bad. Didn’t realise this at all
You can also precompute the grid without the (1000,1000) cell being affected by other cells more than it.
The idea is that the first number at ith row is s=(i*(i+1))/2. (sum of first i numbers) and all the consecutive numbers in that row’s columns are in AP s,s+i,s+i+(i+1) and so on
Same problem also happened with me. Now I realized the problem.
I tried this problem literally for the whole two and half hours of the contest time.
I thought the matrix in the question follows the Cartesian coordinate system, like x represents horizontal index and y represents vertical.
But to my surprise, after the contest has ended, I got to know from other solutions that my assumption was wrong and the x in the question meant to represent the vertical index and y for horizontal.
So, I just want to know if there is any convention that I am missing that would clear this out for me in future? or is the question flawed?