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.