PROBLEM LINK:
Author: Aleksa Plavsic
Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah
PROBLEM
Vanja and Miksi are playing a game on N integer numbers. There is a counter S which is equal to 0 at the beginning. At each turn, each player picks a number from the array and either subtract it or add it to S. You are given also 2 numbers Z1, Z2. Whenever the counter is equal to one of them the player who played the last move wins. At least one turn should be played.
Assuming both players are playing optimally you have to determine the winner. In some cases, none of the players can win the game and if they are playing optimally it may last for more than 1010 turns. In such case, you need to tell that the game ends in a tie. Vanja starts the game.
DIFFICULTY
EASY
EXPLANATION
If our array contains any of these values {Z1, Z2, -Z1, -Z2}, then the first player can win by 1 move.
Let’s introduce the term dead end. Whenever a player has his turn and he is not able to win in 1 move and no matter what number he chooses the other player can pick a number and make S equal to Z1 or Z2, then our player is in a dead end.
We need to check if Vanja’s first move is a dead end. In case it’s, then Miksi is the winner. Otherwise, we are sure that the game will last for more than 2 turns.
In such case (more than 2 rounds), we can prove that the game ends in a tie. No matter which player is taking the turn (since each player knows the numbers given and Z1, Z2), he can determine whether he is in a dead end or not. In case he is, he can just play exactly the opposite of the move the last player did and avoid losing the game (and since the previous player couldn’t win at his previous turn, the game lasts forever).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s/Editorialist’s solution can be found here.