PROBLEM LINK:Practice Setter: Praveen Dhinwa 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
EXPLANATIONThis 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 nonzero 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 nonzero 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 xorsum. Let us see the final state. In this state, none of the pile has any stones left. In terms of xorsum, the xorsum 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 xorsum 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 xorsum). The reasoning is simplified in terms of xorsum of piles. See, All losing states have xorsum of stones count in piles 0. The reasoning is, that If some piles have xorsum 0, then in next turn, it will definitely change into some nonzero value. And, If the piles have xorsum nonzero, it is always possible to remove stones so as to make xorsum 0. This way, a parallel is drawn between Nim's game and xorsum, 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 ComplexityTime 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 19 Nov '18, 12:53

For those who are clueless. https://discuss.codechef.com/questions/135756/fctreditorial/135773 Looks like someone went through a change of mind @taran_1407 ? :p answered 19 Nov '18, 13:51
1
.......XDD
(19 Nov '18, 14:48)
I certainly remember what i said at that time. And, it was true :P This one went long because of additional explanation of nim's game i provided.
(19 Nov '18, 18:30)
Congrats, its true in this case as well now :)
Mine went long because I wanted a nice formatting to explain maths :)
(19 Nov '18, 18:50)

Video solution with explanation: https://youtu.be/Gp90sUHZ6Y0 answered 20 Nov '18, 11:51

i did the same but it gave WA: https://ideone.com/k6pI0F answered 19 Nov '18, 17:43

@vipin1407 please check this: https://ideone.com/k6pI0F answered 21 Nov '18, 09:41

@saurav0001 what you are doing in your submission is wrong. You need to study more about nim games and how to determine the winner in case of nim games (xor of the piles' sizes etc.). answered 22 Nov '18, 19:33
