PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
The strategy of the game revolves around “LOSS” positions and “WIN” positions.In a “LOSS” position ,the player whose turn it is to move will lose with best play,while in a “WIN” position ,the player whose turn it is to move will win with best play.The optimal strategy from a “WIN” position is to move to any reachable “Loss” psition.
The classification of positions into “WIN” and “LOSS” can be carried out recursively with the following 4 rules:
Rule-1:(0,0) is the “TARGET” position.
Rule-2:Any position from which the “TARGET” position can be reached in a single move is a “WIN” position.
Rule-3:If every move from a particular position leads to a “WIN” position ,then that position is a “LOSS” position.
Rule-4:Any position from which the “LOSS” position can be reached in a single move is a"WIN" position.
Pre-processing step:Now following the rules of the game along with the above 4 rules the cells in a 1000X1000 matrix can be filled up as either “WIN” or “LOSS” for the first player ,i.e ALICE.
Solving the Problem:
Step-1:The actual target position (p,q) is shifted to the origin.
Step-2:Now the initial position (m,n) has also been accordingly changed and comparing the new initial position with the corresponding cell in the pre-processed matrix the winner can be decided.
You can view solutions here:
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.