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
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.
I will post a full video solution here soon: https://www.youtube.com/c/codereport
Also, link to my WA solution.