So this problem I thought was pretty straight forward once you figure out the game theory, maybe someone can point out what I missed.
As the cells alternate directions, we can process in pairs
There are three types of pairs
a) A…A
b) B…B
c) A…B or B…A
If it is a) += number of ‘.’ to moves for player A
If it is b) += number of ‘.’ to moves for player B
If it is c) += 1 to AB [THIS IS THE PART THAT WAS WRONG - SEE BELOW]
(Almost forgot), if there is an odd number of A/Bs, make sure to add number of ‘.’ between the last A/B and the end of the string
Then if A + (AB % 2) > B, A wins
The reason a/b we do += # of ‘.’ is because we want to maximize moves, and the opponent can’t take any moves away, so we can take the maximum steps. The reason for c we do += 1 is because we remove a potential move from our opponent. We do AB % 2 because AB’s cancel each other out unless if it is odd, in which case player can take advantage of the extra move.
The 2 corner cases I came up with were when our string has ALL or NO ‘.’, in which case B will win.
However, I still had WA. Anyone know why?
[THIS IS WHAT WAS WRONG]
The processing of A…B was incorrect. As fruwajacybyk pointed out, there is a hidden game of Nim here, so we need to keep track of the odd vs even A…B pairs.
Taking the zones starting at the left-moving tokens:
A…A is an exclusive A zone of 4 moves; B…B is an exclusive B zone of 3 moves. (in either case the final character could also be the end of input string; count the dots).
A…B is a contested zone of 5 moves.
If one or the other player have an advantage in the total exclusive moves, they win, because the contested zones get played out and a “spare” exclusive move is enough to win.
The contested zones are effectively a game of nim; assuming the exclusive moves are equal, you can calculate the winner, given optimum play, from the XOR rule.
If you find a seq like A…B, then xor it with nim variable, as it is same as having fixed value from which any player can remove a certain amount of value. And if nim = 0, implies last move was made by B, else last move was made by A
If you find seq which starts and ends with same value like A…A or B…B, then add it to excess steps the certain player has. Not to forget the last trailing sequence, like A…B…A…, then the trailing “.” will be added to A
Then, we can assume that the players first play the nim game and then use the excess values for the rest of the game.
