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 Rs and Bs. In a turn, an R is selected, along with zero or more consecutive Bs 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 Rs). Which player wins?
QUICK EXPLANATION:
Replace all Bs with 0 s and Rs 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 Bs with 0 s and Rs 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.