You are not logged in. Please login at www.codechef.com to post your questions!

×

CHN07 - Editorial

0
1

PROBLEM LINK:

Contest

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 $$2^k - 2^{k-1} - 2^{k-2} - 2^{k-3} - \ldots - 2^m$$ 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.

This question is marked "community wiki".

asked 26 Jan '16, 07:18

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 15 Feb '16, 20:38

admin's gravatar image

0★admin ♦♦
19.7k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,490
×308
×96
×3

question asked: 26 Jan '16, 07:18

question was seen: 1,371 times

last updated: 15 Feb '16, 20:38