How to solve the Binary String Game problem?

https://www.codechef.com/COOK136B/problems/BINSTRGAME
Any hints plz …
thx :slight_smile:

reviewed tourist’s solution Solution: 55137999 | CodeChef, he calculates the number of consecutives “00” and “11”, if is the multiple of 3 then Uttu wins.

seems is greedy approach. I am also not quite understand this tricks lol.

In any position, any move either results in an increment of f(S) by 2 (as 11"1001010"01) or 1 (as 10"00101"), where the portion in quotes is flipped. In essence, if the portion you flip includes one of the corners, f(S)+=1, otherwise f(S)+=2, in a legal move. It’s easy to prove that both kinds of moves are possible before the game has ended, and that these are the only kinds of moves allowed. Finally, the number of flips must be N-1 at the end, hence f(S) must be incremented by p=N-1-original_flips. If p is divisible by 3, player 2 can force a win by adding (3-player_one’s_move) to f(S) at his turn. Otherwise, player 1 wins by incrementing f(S) by p%3 and following the strategy described above.
@ below fair enough

1 Like

I think the given examples need to be corrected.
11"1001010"01 will increase f(s) by 2 and 0"00101" will increase it by 1

can you please explain this a little bit more?

Can someone please explain the dynamic programming approach that some people have used?