Dice Roll Sequence

Research checked: the supplied statement, the official Codeforces problem page, and the Codeforces Round 1080 tutorial/code at https://codeforces.com/blog/entry/151174. The official code uses the same greedy idea below; the statement remains the source of truth.

The die is simpler than it looks. Opposite faces are $(1,6)$, $(2,5)$, and $(3,4)$, so two values $x,y$ are adjacent iff

$$x \ne y \quad\text{and}\quad x+y \ne 7.$$

So an adjacent pair is bad iff

$$x=y \quad\text{or}\quad x+y=7.$$

Now look at the operation. Changing $a_i$ can only affect the two neighboring pairs:

$$(a_{i-1},a_i) \quad\text{and}\quad (a_i,a_{i+1}).$$

So one operation can fix at most two bad adjacent pairs, and those two bad pairs must be consecutive. That already hints at the answer: scan bad edges and greedily cover them in chunks of size at most $2$.

The only non-obvious part is this: when we find a bad pair $(a_i,a_{i+1})$, can we always spend one operation on $a_{i+1}$ and safely ignore the next pair too?

Yes. Suppose $i+2$ exists. We want to replace $a_{i+1}$ with some value $v$ such that both pairs are valid:

$$(a_i,v) \quad\text{and}\quad (v,a_{i+2}).$$

For $(a_i,v)$ to be valid, $v$ must not be

$$a_i \quad\text{or}\quad 7-a_i.$$

For $(v,a_{i+2})$ to be valid, $v$ must not be

$$a_{i+2} \quad\text{or}\quad 7-a_{i+2}.$$

That bans at most $4$ values out of $6$, so at least $2$ valid choices remain. If $i+2$ does not exist, it is even easier: just choose anything adjacent to $a_i$.

So the greedy is:

• scan pairs from left to right;
• if pair $(i-1,i)$ is already valid, move on;
• if it is bad, answer increases by $1$, and we skip pair $(i,i+1)$ because the same operation can be chosen to make both pairs valid.

This is not just vibes, it is optimal.

For the lower bound, consider the first bad pair not yet handled. Any valid final sequence must change at least one of its two endpoints, so we need at least one operation. Also, that one operation cannot affect anything beyond the next pair. Therefore after paying one operation for this bad pair, the best possible situation is exactly that the current pair and the next pair are both handled. The greedy does that, so it never wastes an operation.

Equivalently, bad adjacent pairs form runs, and a single changed element can cover at most two consecutive bad pairs. A run of length $L$ therefore needs at least $\lceil L/2\rceil$ operations, and the greedy takes exactly every other bad pair, giving $\lceil L/2\rceil$ for each run. Clean, no dice gymnastics required.

Edge cases:

• For $n=1$, there are no adjacent pairs, so the answer is $0$.
• Equal values like $(2,2)$ are bad because a face is not adjacent to itself.
• Opposite values like $(3,4)$ are bad because $3+4=7$.
• The algorithm does not need to know the actual replacement value; existence is enough.

The scan is linear. Each test case runs in

$$O(n)$$

time and uses

$$O(1)$$

extra memory.