Contest Duration: - (local time) (210 minutes) Back to Home

## B - Three Coins Editorial by rng58_admin

For a given sequence $$x_1, \cdots, x_k (x_1 < \cdots < x_k)$$, let’s check if it’s possible to reach a state where these $$k$$ cells contain coins, and no other cells contain coins.

First, notice that only the values of $$x_1 \mod 3, \cdots, x_k \mod 3$$ are important. This is because, by doing the following operations,

...# -> #### -> #...

all states can be converted to the “minimal” state that preserves the values of indexes modulo $$3$$.

Thus, we get the following problem:

• We start with an empty string. We are allowed to insert strings 012, 120, 201 in any position. Also, we are allowed to remove a substring from the string if the substring is one of 012, 120, 201. Is it possible to make a given srting?

We can prove that we never need to use the removal operation. If a removal operation comes right after an insertion operation,

• In case the two operations are performed on disjoint positions, we can swap the operations (and repeat swapping and moving the removal operation earlier while you can; you eventually have to stop at some point.)
• Otherwise, the two operations cancels out. For example, 01 -> 01201 -> 01 (inserted 201 and removed 012, but nothing changed.)

To summarize, a sequence $$x_1, \cdots, x_k$$ is valid if for some $$p, q, r (p < q < r)$$,

• $$x_q = x_p + 1, x_r = x_p + 2 \pmod 3$$
• $$x_1, \cdots, x_{p-1}$$ is a valid sequence.
• $$x_{p+1}, \cdots, x_{q-1}$$ is a valid sequence.
• $$x_{q+1}, \cdots, x_{r-1}$$ is a valid sequence.
• $$x_{r+1}, \cdots, x_{k}$$ is a valid sequence.

Now it’s easy to get an $$O(N^3)$$ DP to solve the problem.

posted:
last update: