### PROBLEM LINK:

**Author:** ???

**Tester:** Kevin Atienza, Jingbo Shang

**Editorialist:** Kevin Atienza

### PREREQUISITES:

Game theory

### PROBLEM:

A game is played on a string of length n consisting of `R`

s and `B`

s. In a turn, an `R`

is selected, along with zero or more consecutive `B`

s immediately to the right of it. Then all these letters are flipped. A player loses if there are no more valid moves (i.e. no more `R`

s). Which player wins?

### QUICK EXPLANATION:

Replace all `B`

s with 0 s and `R`

s with 1 s, and interpret the string as a binary number. If this number is divisible by 3, then the second player wins. Otherwise, the first player wins.

### EXPLANATION:

If you didn’t catch the simple solution, you might have instead tried to brute-force all instances of the problem for small n, and found that *there is always a winning move flipping just the leftmost R, the letter immediately right of it, or both*. With this observation, you might be able to find an O(n) dynamic programming solution, and it passes the time limit. However, there is in fact a nicer solution than this.

First, replace all `B`

s with 0 s and `R`

s with 1 s, and interpret the string as a binary number, X.

An example of a valid move is to replace a 1 with a 0, and then replacing some number of zeroes to the right of it with a 1. Since this is a binary number, the place value of the 1 is 2^k for some k, and the 0 s to the right of it have place values 2^{k-1}, 2^{k-2}, \ldots, 2^m for some m. A move in effect decreases the value of our number by

which is just equal to 2^m. (Why?) Thus, a valid move consists of subtracting a number 2^m \le X. It can also be seen that subtracting *any* power of two \le X constitutes a valid move. The question is now: which numbers X are winning positions for the first player?

A *losing position* is a position such that every move results in a winning position. A *winning position* is a position such that there is a move resulting in a losing position. We must find a property that all winning positions, and only winning positions, have. Such a property must satisfy the following:

- X = 0 doesn’t have the property.
- If X doesn’t have the property, then subtracting any power of two \le X results in a number with the property.
- If X has the property, then there is a power of two \le X you can subtract that results in a number without the property.

It can be seen that the following property satisfies both requirements:

**X is not a multiple of 3**

Obviously X = 0 doesn’t have this property (because it is a multiple of 3). Now, if X is a multiple of 3, then subtracting a power of two from it results in a number that is not a multiple by 3, because no power of two is a multiple of 3. But if X is not a multiple of 3, then there are two cases:

- If X \bmod 3 = 1, then we can subtract 2^0 = 1 from X.
- If X \bmod 3 = 2, then we can subtract 2^1 = 2 from X.

In both cases, the resulting number is a multiple of 3. Thus, the property satisfies all requirements! So the solution is simply:

**If X is divisible by 3, then the second player wins. Otherwise, the first player wins.**

Finally, checking whether X is a multiple of 3 can be done with the *Horner method* modulo 3: (here we write `X[i]`

as the i th bit of X *from the left*):

```
def is_multiple_of_3(X):
r = 0
for i in 1..n:
r = (2*r + X[i]) % 3
return r == 0
```

### Time Complexity:

O(n)

### AUTHOR’S AND TESTER’S SOLUTIONS:

[setter][333]

[tester][444]

[editorialist][555]

[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.

[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.

[555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.