Editorial

One Two Three 2

Editorial

Subtract $1$ from every value, so the initial values are $0,1,2$ . If $A<C$ , apply the reflection $x\mapsto 2-x$ ; hence assume $A\ge C$ .

Let $N=A+B+C$ , $S=B+2C$ , $g = \gcd (N, S$ , , and . The final value must be the global average . After any number of operations, every reduced denominator is a power of two, so the task is impossible if is not a power of two.

Assume that $p$ is a power of two. Since $A\ge C$ , we have $q\le p$ . Let $\lambda=\max\left(0,C-g\left\lfloor\dfrac q2\right\rfloor\right)$ . The minimum number of operations is .

Construction

If $p>1$ , then $q$ is odd. Make $\lambda$ groups of size $2p$ , each containing $2p-q,0,q$ copies of , respectively. Split the remaining elements into groups of size .

Bound

Build a graph $G$ by joining two indices if they are ever used together, and let $k$ be its number of connected components. If a component has size $s$ , its final sum $sq/p$ must be an integer, so $s$ is divisible by . Write the component sizes as ; then .

The total time complexity is $O(N)$ .

Solution written by GPT5.6

g = g cd (N, S)

p=\dfrac Ng

q=\dfrac Sg

q/p

p

=

max(0,C−g⌊2q⌋)

N-g+\lambda

2

p

−

q,0,q

0,1,2

g-2\lambda

p

If a size- $p$ group contains $c$ copies of $2$ , then its numbers of $0,1,2$ must be $p-q+c$ , $q-2c$ , $c$ . Thus $0\le c\le\lfloor q/2\rfloor$ , and the sum of $c$ over all size- $p$ groups must be $C-\lambda q$ . The definition of $\lambda$ guarantees that this is possible.

Every group can be averaged in exactly its size minus one operations. A size- $p$ group consists of $0,1,2$ and has odd sum. Dividing every value of a size- $2p$ group by $2$ gives a $0,1$ group with odd sum.

Consider a group of size $D=2^k$ with values in $\{0,1,2\}$ and odd sum $q$ . Construct the operations backwards. Initially imagine $D$ copies of the final average $q/D$ . From two equal current values $x$ , fix one position to an original integer $a\in\{0,1,2\}$ and change the other backwards to $2x-a$ . This reverses one averaging operation.

When there are $D$ active positions, let $r=q\bmod D$ . Every active value has fractional part $r/D$ , so only $r/D$ and $1+r/D$ can occur. Let $H$ be the number of high values and pair equal values.

If $r<D/2$ , a low pair restores a $0$ and leaves one low value. A high pair may restore a $1$ and stay high, or restore a $2$ and become low.
If $r>D/2$ , a high pair restores a $2$ and leaves one high value. A low pair may restore a $1$ and stay low, or restore a $0$ and become high.

The next level has $D/2$ active positions. For each state $(D,H)$ , the possible numbers of still-unrestored $2$ 's form one integer interval. At $D=2$ , the states are $(H,c)=(0,0)$ and $(2,1)$ . The transitions above compute the intervals from small $D$ upward. Prefix and suffix minima and maxima process one level in $O(D)$ time, and the sum of all level sizes is $O(D)$ . During reconstruction, choose any transition whose next state remains feasible. Reversing the recorded backward operations gives exactly $D-1$ forward operations.

p

ps_1,ps_2,\ldots,ps_k

s_1+s_2+\cdots+s_k=g

Let $c_i$ be the initial number of $2$ 's in component $i$ . Its sum is $qs_i$ , so $c_i\le\left\lfloor\dfrac{qs_i}{2}\right\rfloor$ . Since $q$ is odd,

\begin{align*} C &\le \sum_{i=1}^k \left\lfloor \frac{qs_i}{2}\right\rfloor \\ &= \sum_{i=1}^k \left(s_i\left\lfloor\frac q2\right\rfloor+\left\lfloor\frac{s_i}{2}\right\rfloor\right) \\ &\le g\left\lfloor\frac q2\right\rfloor+\sum_{i=1}^k(s_i-1) \\ &= g\left\lfloor\frac q2\right\rfloor+g-k. \end{align*}

Hence $k\le g-\lambda$ . A connected component of size $s$ requires at least $s-1$ operations, so the total number of operations is at least

N-k\ge N-g+\lambda.

⌋

2

qsi

⌋

=i=1∑k(si⌊2q⌋+⌊2si⌋)

≤g⌊2q⌋+i=1∑k(si−1)

=g⌊2q⌋+g−k.