Codeforces Round #721 Palindrome Game (easy/hard) Solution (Java/C++)

Solution:

1: Consider the simplest case: the string is palindrome, and the length of string is even. For example, 000000. For this case, Bob must win. See operations below:
A:100000; B:100001; A:110001; B:110011; A:111011; B: reverse; A: 111111.
So that: Every time, after Alice changed 0 to 1. Bob also changes the corresponding 0 to 1 to keep the string palindrome. Until last two 0, at that time, Bob do one reverse operation.

But there is one exception: if the string is palindrome, and the length is even, but it is all 1s. Then the result is draw.

2: Now consider the case that: the string is palindrome, but the length is odd. Based on case 1, we find that the second player will win, and will win 2 points. So, if the center is 0, then Alice will change on this firstly, and get win.

3: Then consider the case that string is not palindrome. For this case Alice will be happy. Let us consider there are more than 2 pairs not palindrome. For example, 00000111.
A:reverse; B:10000111; A:reverse...
Based one first cases, the winner at most win 2 points. So, before the string become palindrome, Alice continually reverses the string, and get an advantage of at least 2 points. So, Alice will win.

4: Then let us consider the case that have 1 pair not palindrome. For this case, it same to the case 2. Alice will take this firstly and get win.
But one exception: if there is only one 0 exclude this no palindrome pos. For example, 001, and exclude no palindrome pos: 0. For this case, If the first step of Alice is reverse, then Bob will change to 101. Then Alice must change to 111. If the first step of Alice is 011 or 101, then Bob will change to 111. So, draw.

5: Now the last case is: there are exactly 2 pairs not palindrome. For example, 000011. For this case:
A:reverse; B:100011;
Now, A:110011. And Alice is second player, will win.

Code:

Java

C++