PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Alei Reyes
Tester: Aleksa Plavsic
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Greedy, Nim’s Misere Game.
PROBLEM:
Given N piles containing 0-s and 1-s only, Tweedle-Dee and Tweedle-Dum play a game. Tweedle-Dum may remove any number of elements from the top of the pile which currently have topmost element 0 and Tweedle-Dee may remove any number of elements from the top of the pile which currently have topmost element 1. They play alternating, with the player first to move given. Predict the outcome of the game, assuming optimal play from both players.
Player last to move loses the game.
SUPER QUICK EXPLANATION
- If there are consecutive occurrences of the same element in any pile, we can simply replace them with one copy of the same element, since it is optimal to remove all occurrences of the element present at the top. So, we can compress all piles to get the pile of form 010101 or 101010.
- Now, suppose there’s a pile, which have topmost element differing from its bottom-most element, we can prove that answer remains same even without this pile, because if one player makes a move on this pile, other player makes the next move by removing element from the same pile, resulting in exactly same position for the first player.
- If a pile has both top and bottom-most element as same, It requires one or the player to make one extra move. So, just count the number of extra move each player has to make. The player which runs of out extra moves first wins the game.
EXPLANATION
The game theory problems, where the player who makes the last move lose the game, are called Misere Nim’s Game. Strategies get reversed. In normal Nim’s game, we try to make sure that we play the last move, but in Misere Nim’s game, we want our opponent to play the last move.
For our discussion, I am calling 0 as Tweedle-Dee’s element and 1 as Tweedle-Dum element.
I am going to define Pending moves for this editorial.
Pending moves for a player is the minimum number of moves, which the player has to make, assuming optimal play from his opponent. Since in this game, we want our opponent to play the last move, both players aim to minimize the number of their own pending moves as well as maximizing the number of pending moves of their opponent.
First of all, let us analyze what is the optimal strategy in this problem.
First observation: Any player making a move, shall never leave his element at top of a pile. Each player will remove elements so that the new topmost element belong to their opponent.
The reason is simple, If the player leaves his element at top of a pile, He will have to make at least one more move to do the same thing (remove his element from top) which he could have done in one move, thus, not reducing his pending number of moves at all, leading to non-optimal play.
For example, If Dee makes a move on pile 000110101, the optimal moves are 000, 000110, 00011010. In the case where the last element belongs to the current player, it is also optimal to remove the whole pile, as for removing the last element, the current player will have to eventually make a move.
This observation implies, that all consecutive same elements in all piles can be replaced by a single copy of that element without affecting the answer.
Second Observation: Number of pending moves of each player is just the number of 0s and 1s present in all piles together, after compressing piles using observation 1.
This one is a crucial observation, so I am giving examples first.
Suppose we have a pile 0101010 and Tweedle Dee makes first move.
Here, Dee has 4 pending moves while Dum has 3 pending moves. Since both of them make moves alternatingly, First Dee makes a move, then Dum makes a move and so on. We can see that since Dum has less number of pending moves than Dee. So, Dum will win this game.
Above may be verified by analyzing the example manually. Dee may remove any number of elements from the top. Suppose he removes 010. In next move, Dum will remove 101, so that Dee is forced to remove 0 at the end. In fact, no matter what move Dee make, since the last element in pile is Dee’s element, Dum will always remove all but the last element from the pile, winning the game if this was the last pile left.
Another example: 10101010
Both players have 4 pending moves. The player making the first move lose the game. If Dee has first move, He cannot make a move on this pile at all, thus win the game. If Dum has moved first, he can simply remove all but the last element, which Dee will have to remove in next move. This way, Dum wins the game.
Now, stating the final restatement of our strategy, If both players have the same number of pending moves (after compressing piles by observation 1), the player first to move wins, otherwise no matter who plays first, the player having less number of pending moves win the game.
This much is sufficient to solve the problem, but I am presenting another observation which three of us (setter, tester, and editorialist) ended up using without each other’s knowledge. 
The thing is that after first observation, plies look like 010101 or 101010. If the first element of a pile is same as the last element, increase pending move of player to whom the first element belongs. Otherwise, ignore the pile and print answer depending upon pending number of moves.
The proof for using only first and last element is simple, and thus, is left as an exercise for readers.
Related Problem
I am giving you people to solve the same problem, except the fact that the player last to move wins the game, which can be found by name Binary Nim, set by the same author six months ago. 
Also, a problem on Misere nim can be found here.
Time Complexity
Time complexity is O(N). Memory complexity is O(1) (We can just make two counter variables counting pending moves for both the players.)
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. 