PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Game Theory, Nim’s Game and Observations.
PROBLEM:
Two players A and B plays a game on a string consisting of characters ‘.’, ‘A’ and ‘B’. Each occurrence of character ‘A’ and ‘B’ is assigned direction from left to right alternatively, starting from the right direction. ‘.’ represent empty spot.
Player A can move any character marked ‘A’ in the predetermined direction any number of steps as long as not jumping over any of character ‘A’ and ‘B’, while player B can move any character marked ‘B’ in the predetermined direction in the same manner.
Players make move alternatively, with player A playing first. Determine who will win, if both of them play optimally and the player making the last move wins.
For this problem, I am counting only A and B as characters, for a simpler explanation.
QUICK EXPLANATION
- Except for the last character if the number of characters present is odd, all characters are assigned directions such that in pairs of two, Characters are moving toward each other. ie. First and second are moving toward each other, Third and Fourth characters are moving toward each other and so on. If there are an odd number of characters, the last character is moving toward the right end.
- Let reserve moves represent the number of moves a player can perform independently of other moves. More the reserve moves, better for that person. Since he wants to play the last move.
- If any pair of adjacent characters moving toward each other belongs to the same player, that player can move either of his characters toward the other in maximum d moves, if d is the number of empty cells between both characters. So, That player’s reserve moves increases by d. In case of the last character where the last character is moving toward the right border, that player has an additional d reserve moves, if there are d empty cells between last character and right border.
- If the pair of adjacent characters are different and there are d empty cells between both characters, It can be reduced to the game of Nim, with sizes of piles being the number of cells between every pair of adjacent numbers, where the losing player has to use its reserve moves first.
- The final game is the game of Nim with a finite number of pass moves for both players.
- If Number of pass moves differ, The player having the higher number of pass moves will always win. Otherwise, It is simply a Game of Nim, with the winner of Nim game being the winner of the Game.
EXPLANATION
This is not a single game, but a combination of Nim’s game combined with a simple turn game.
Let us see how the directions first. Consider example A…A…A…B…B…B. The first character is assigned direction right, second is assigned left, third is assigned right and so on. This way. Directions are assigned as R…L…R…L…R…L.
It is easy to notice that the first and second characters are moving together, third and fourth character are moving toward each other and so on. So, Every pair of characters can be treated separately.
Let us define the concept of reserve moves for a player as the number of moves a player can perform independently of the moves performed by the opponent.
Playing a simple game for understanding
Player A can perform X moves, while player B can perform Y moves, independent of each others’ moves. If player A is first to move, player A wins if X > Y. But if player B is second to move, player A wins if X \geq Y. It is not easy to prove how.
The first move matters.
Coming back to original problem
When both characters of the pair are same, both characters are controlled by the same player, and cannot be affected by opponent’s moves. This player can make minimum 1 and maximum d moves using these pair of characters only. Since a player wants to play as many moves as possible, it is optimal to spend d moves on this pairs. This will add to reserve moves available to the player.
Similarly, If there are an odd number of characters available, the last character is assigned right direction and it will move toward the right border. This will add d moves to reserve moves of player, to whom the last character belongs.
Now comes the tricky part.
When both characters of the pair are different. Either of the players can move any number of steps at a time, moving only one character in one move until there is no empty cell left in between. Notice that Either player will run out of moves if and only if there are no such pairs, with empty cells in between. Hence, in the final state, all such pairs will compress, removing all empty cells between the characters.
Let us consider an example A…B.A…B
Winning player is A with the strategy to move his character at position 6 to position 7, and then in subsequent moves, moving his character in the same way as B moves.
Let’s try to reframe the problem as Number of empty cells between first such pair is 2, while the number of empty cells between the second pair is 3. Playing in turns with A moving first, Each player at a move is allowed to reduce exactly one of the numbers by any non-zero number. The player unable to make a move loses. Find the winner if both players play optimally.
Does the above rings a bell?
Give it a try!!
The above statement is exactly the Nim’s game. 
(Explaining Nim’s Game later).
Hence, the problem is just the Nim’s game, with both players having a given number of pass moves (possibly different number of moves). In case initially the Nim’s game is in a winning position, A will Make move so as to give B a losing position in Nim’s game. In case the given game was already in a losing position, A will use a reserve move. In either way, Now player B and A, in turns, use their pass moves till pass moves are exhausted for a player, and is forced to make a move in losing position in Nim, thus losing the game.
Another way of writing the winning idea is, If both players have an unequal number of reserve moves, the player with more reserve moves wins, otherwise the winner of Nim’s game wins. It is not hard to follow, once you get the idea of the above solution.
About Nim’s Game
I had seen a post asking details on Game Theory but couldn’t reply, so, here we go!
I will not be going in too much detail, will be using informal language, just explaining the ideas with brief proof. Details you can find on various blogs, for example, here and here.
The Nim’s game at the core is the problem with N piles of stones containing a non-zero number of stones. Both players, in their turns, are allowed to remove any positive number of stones from exactly one pile. The player unable to make a move loses.
The solution is based on the idea of xor-sum.
Let us see the final state. In this state, none of the pile has any stones left. In terms of xor-sum, the xor-sum of the number of stones in each pile is 0. The previous state must have included one pile containing say x stones, having x as xor-sum and is a winning state.
We know, that in game theory, The states visited from last to first is something like losing state, winning state, losing state alternatively and so on. So, the second last state visited must be losing state for the player to move.
If it was like, that before second last move, there was only one pile having more than x stones and losing player removed stones to leave x stones, Then this is not an optimal strategy as the losing player could have removed the whole pile, winning the game.
So, in second last move, there should be exactly two piles. Suppose there were y stones in that pile. Suppose x \neq y. Even now, the player making the current move can win, by removing stones in such a way to get the same number of stones in both piles, thus again winning the game.
Thus, for second last state to be losing, the required condition becomes x == y.
Similar reasoning escalates to more piles. (Equality changes into zero xor-sum).
The reasoning is simplified in terms of xor-sum of piles. See, All losing states have xor-sum of stones count in piles 0. The reasoning is, that If some piles have xor-sum 0, then in next turn, it will definitely change into some non-zero value.
And, If the piles have xor-sum non-zero, it is always possible to remove stones so as to make xor-sum 0.
This way, a parallel is drawn between Nim’s game and xor-sum, and we get the result as we know today.
That’s all for today. Feel free to share anything useful related to Game theory.
Time Complexity
Time complexity is O(|S|) where |S| is the length of string and we need to iterate over it only once.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed.
