Editorial : Flip the Bit (Easy Version)

Editorial (model solution)

This section matches the easy-version program in model_sol.cpp ($k = 1$).

Index the array from $0$ to $n - 1$ and let $p$ be the special index after converting the given $1$-based position. Along the prefix ending at $p$, count how many adjacent pairs differ:

$$ \texttt{nless} = \#\{\, i \mid 0 \le i,\; i + 1 \le p,\; a_i \ne a_{i + 1} \,\}. $$

Along the suffix starting at $p$, count

$$ \texttt{nmore} = \#\{\, i \mid p \le i,\; i + 1 < n,\; a_i \ne a_{i + 1} \,\}. $$

Set $\texttt{ans} = \max(\texttt{nless}, \texttt{nmore})$. If $\texttt{ans}$ is odd, replace it by $\texttt{ans} + 1$, then print $\texttt{ans}$. Each test case is handled in linear time in $n$.

Let $p$ be the unique special index, and let $x=a_p$.
Define:

$$ b_i = a_i \oplus x. $$

Now we need to turn all $b_i$ into $0$.

An operation toggles some segment $[l,r]$ with $l \le p \le r$, so it always contains $p$.

For the left side, add virtual values $b_0=0$ and $b_p=0$.
Whenever $b_{i-1} \ne b_i$ for $i \in [1,p]$, that boundary must be crossed an odd number of times by chosen left endpoints. Let:

$$ L = \#\{\, i \in [1,p] \mid b_i \ne b_{i-1} \,\}. $$

For the right side, add $b_{n+1}=0$ (and still $b_p=0$).
Whenever $b_i \ne b_{i+1}$ for $i \in [p,n]$, that boundary must be crossed an odd number of times by chosen right endpoints. Let:

$$ R = \#\{\, i \in [p,n] \mid b_i \ne b_{i+1} \,\}. $$

Each operation chooses exactly one left extension and one right extension, so it can satisfy one unit on each side. Therefore:

we need at least $L$ operations to satisfy all left requirements,
we need at least $R$ operations to satisfy all right requirements.

Hence answer $\ge \max(L,R)$.
Conversely, we can pair required left/right odd boundaries; any surplus on one side is handled in pairs on the other side, so $\max(L,R)$ operations are enough.

Therefore the minimum is:

$$ \boxed{\max(L,R)}. $$

The implementation runs in $O(n)$ per test case.