Reverse Game#12836

Reverse Game (Editorial)

Author: Anton Trygub

Solved by:

First to solve: Echipa Dulce

Let's consider the number of inversions in the string (defined as the number of pairs such that 1 \leq i < j \leq n, s_i = 1, s_j = 0). Suppose that currently it's .

Note that reversing 10 decreases by , and reversing any of 110, 100, 1010 decreases by . Let's show, that if I\ge 1, it's possible to decrease it by in 1 turn, and if I\ge 2, it's possible to decrease it by in one turn.

Proof:

  • Suppose that I\ge 1, there has to be a substring 10 in it, otherwise all zeros would go before all ones and there would have been no inversions. Then we can just reverse this 10.

  • Suppose that I\ge 2. We want to show that must contain at least one of 110, 100, 1010. Suppose that it doesn't. Then, if there is block of at least consecutive zeros, it has to be in the beginning, and if there is a block of at least consecutive ones, it has to be in the end. So, the string looks like: 00\ldots0101\ldots0101111\ldots11.

    Suppose that the string has zeros in the beginning, ones in the end and repetitions of 10 between them. If c=0, there would be no inversions at all, if c=1, there would be exactly inversion, so c\ge 2, and we can choose substring 1010, which finishes the proof.

This shows that the game is equivalent to following:

Two players can substract or from in their turns, the one who can't make a move loses. Who wins?

In this well-known game the first player wins iff is not divisible by . So, to solve the problem, it's enough to find in and to determine if it's divisible by .