Hello.
I'm stuck in this problem for a while now.(It reminded me with the "Berzerk" problem here)
To be honest; I never really understood this kind of problems nor did I ever understand why a solution is always possible(When the author says so).
When I think of it(or any similar problem) I always believe that it will go on forever..
Specially when the statement says; "If both the players play clever and cautious(or optimally)..
When I read the examples, an idea crossed my mind; the player will win if and only if he can get to the north-east,north-west,south-east,south-west cell of his opponent's.
However, I don't know whether that is the only possibility.
Please note that I don't need help with the first two subtasks which are: R=2 & C=2 and R <= 100 & C=1.
The real problem is with the other two subtasks: R,C <= 100 and R,C <= 1e9 ...
Any hints?
Thanks!
Its Just a problem on the invariant of the position wrt to the winning or losing player. Here notice that |x1-x2|+|y1-y2| is an invariant for the losing state. That is, when |x1-x2|+|y1-y2| is even, the player whose move it is loses. whenever he moves, the other can compel the invariant to be even and its magnitude to be either same or less than the previous value. Eventually the magnitude will decrease and come to zero. So the game must terminate. You can decide the winner directly from the invariant initially.
Understood.
What about the case when the game keeps on going forever?
as vivekgupta said, if the distance between the two players is initially even, the first player loses. based on this, if the distance is odd the first player has to move to an adjacent cell and make the distance even which results in the second player's loss. after every 2 moves the distance can get smaller but always remains even/odd until it reaches 1 or 0 (when the losing player reaches a corner on the grid he has to go back and the distance gets smaller by 2, "par recurrence" it will reach 1 and the game will end) and the game can never end in a draw (sa77a laz :p)
Yes Absolutely, It has to terminate with only one result, If both play optimally