## 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: