diss_quack and Array Game

Turning binary into a cost

For $x>0$, define

$F(x)=\operatorname{popcount}(x)+\lfloor\log_2 x\rfloor,$

and define $F(0)=0$.

This is exactly the number of operations needed to erase one isolated number:

• If $x$ is odd, subtracting $1$ clears its last binary 1. Thus $F(x)$ decreases by exactly $1$.
• If $x$ is even, dividing by $2$ right-shifts its binary representation. The popcount stays unchanged and $\lfloor\log_2 x\rfloor$ decreases by $1$, so again $F(x)$ decreases by exactly $1$.

For example, $6=110_2$ has

$F(6)=2+2=4,$

corresponding to

$6\to3\to2\to1\to0.$

Now use the potential

$P=\sum_i F(a_i).$

An odd subtraction decreases $P$ by $1$. If Alice divides an even prefix of length $r$, every affected number loses one unit of $F$, so $P$ decreases by exactly $r$.

Therefore, every Alice turn decreases $P$ by at least one. The only way Bob can attain the maximum possible number of turns is to make every divided prefix have length one.

Bob's odd stopper

Suppose the array currently contains an odd number.

Whenever at least two elements remain, Bob can arrange for position $2$ to contain an odd number using one swap:

• If position $2$ is already odd, he does nothing.
• Otherwise, he swaps position $2$ with any position containing an odd value. This also works when the only odd value is currently at position $1$.

Afterward:

• If $a_1$ is even, the odd value at position $2$ stops the even prefix immediately, so Alice divides only $a_1$.
• If $a_1$ is odd, Alice changes only $a_1$ anyway, while the odd stopper at position $2$ survives.

If $a_1=1$ gets erased, the stopper merely shifts to position $1`; Bob can reposition it on his next turn. Once only one element remains, every operation obviously affects one element.

Thus, from any state containing an odd value, Bob can force every turn to decrease $P$ by exactly one. The remaining number of Alice turns is consequently exactly $P$.

That odd number is basically Bob's traffic cone: stupidly simple, annoyingly effective.

The value of a fixed array

Let

$q=\min_i v_2(a_i),$

where $v_2(x)$ is the number of trailing zero bits of $x$.

Every number is divisible by $2^q$. Hence, during the first $q$ Alice turns, the entire array is even and Bob cannot prevent Alice from dividing every element. After those $q$ global divisions, at least one number is odd, so Bob's stopper strategy becomes available.

Because

$F(2^q x)=F(x)+q,$

the potential remaining after those divisions is

$\sum_i(F(a_i)-q)=\sum_iF(a_i)-nq.$

The total number of game turns is therefore

=\sum_iF(a_i)-(n-1)q.$$ Equivalently, the $q$ common divisions save $(n-1)q$ turns compared with processing every number independently. ## Adding Alice's initial increments Suppose Alice changes the original values $a_i$ into final values $b_i\ge a_i$. She spends $$\sum_i(b_i-a_i)$$ initial moves. Applying the fixed-array formula afterward gives the total $$\sum_i\bigl(b_i-a_i+F(b_i)\bigr) -(n-1)\min_i v_2(b_i).$$ Directly optimizing this expression looks coupled because of the minimum trailing-zero count. We remove that coupling by fixing a candidate number $m$ of common divisions. For one original value $a$, define $$G_m(a)=\min_{\substack{x\ge a\\2^m\mid x}} \bigl(x-a+F(x)\bigr).$$ All elements can now choose their targets independently, giving $$C_m=\sum_iG_m(a_i)-(n-1)m.$$ The answer is $$\min_m C_m.$$ There is a small subtlety: all independently selected targets might actually be divisible by $2^{m+1}$, so their minimum trailing-zero count could exceed $m$. That causes no problem. - For any particular final array, choose $m$ equal to its true minimum trailing-zero count. The independent minima in $C_m$ can only be cheaper, so $\min_m C_m$ is no larger than the optimum. - Conversely, take the targets selected for some $C_m$. If their true minimum trailing-zero count is $q\ge m$, their real game cost subtracts $(n-1)q$, which is no larger than the value calculated in $C_m$. Thus the actual optimum is no larger than every $C_m$. Both inequalities hold, so the formula is exact. ## Finding $G_m(a)$ without a fake magic bound Let $s=2^m$, and let $$p=\left\lceil\frac{a}{s}\right\rceil s$$ be the smallest legal target. Choosing $p$ costs $$p-a+F(p).$$ For any legal target $x\ge p+F(p)$, since $F(x)\ge1$, $$x-a+F(x) \ge p+F(p)-a+1,$$ which is already strictly worse than choosing $p$. Therefore, an optimal target must belong to the tiny list $$p,p+s,p+2s,\ldots <p+F(p).$$ This detail matters: always selecting the first multiple is wrong. Crossing a binary boundary can sharply reduce popcount; for instance, incrementing $15$ to $16$ can be worthwhile. The short search catches those cases exactly. ## Why only $m=0,1,\ldots,17$ At $m=0$, choosing every target unchanged gives an answer at most $$\sum_iF(a_i)\le33n,$$ because $a_i\le10^5<2^{17}$. For $m\ge18$, every positive multiple of $2^m$ is at least $2^m$, and its $F$ value is at least $m+1$. Therefore, $$C_m\ge n2^m-\sum_i a_i+n+m \ge n(2^m-100000+1)+m,$$ which is already vastly larger than $33n$ at $m=18$ and only increases afterward. Such an $m$ cannot be optimal. ## Algorithm For every $m$ from $0$ through $17$: 1. Set $s=2^m$ and initialize the total with $-(n-1)m$. 2. For every $a_i$: - Find the first multiple $p$ of $s$ with $p\ge a_i$. - Enumerate the multiples of $s$ in $[p,p+F(p))$. - Add the minimum value of $x-a_i+F(x)$. 3. Minimize the answer with this total. For `[2,2,2,2]`, leaving the values unchanged gives $q=1$. Their individual costs sum to $8$, while the common division saves $3$, producing $5$. For `[6,8,2,4,1]`, Alice can increment the last value to $2$. The increment costs one move, and the resulting array has one common division. Its game lasts $11$ turns, giving $12$ moves total. ## Correctness proof **Lemma 1.** Processing an isolated positive value $x$ takes exactly $F(x)$ turns. Every legal operation on an isolated value decreases $F$ by exactly one, and the process ends precisely when $F=0$. **Lemma 2.** If an array contains an odd value, Bob can force the remaining game to last exactly $\sum_iF(a_i)$ turns. Every Alice turn decreases this potential by at least one, giving an upper bound. Bob can keep an odd stopper at position $2$, forcing every division to affect only position $1`; odd operations already affect only position $1$. Thus every turn decreases the potential by exactly one, attaining the bound. **Lemma 3.** For a fixed array, its game value is $$\sum_iF(a_i)-(n-1)\min_i v_2(a_i).$$ The first $q=\min_i v_2(a_i)$ turns divide all $n$ elements. Afterward an odd value exists, and Lemma 2 applies. Combining the $q$ global turns with the remaining potential gives the stated expression. **Lemma 4.** For fixed $m$, checking only multiples $x$ in $[p,p+F(p))$ finds $G_m(a)$. The target $p$ is legal. Every $x\ge p+F(p)$ has cost at least one greater than the cost of $p$, so no excluded target can be optimal. **Theorem.** The algorithm outputs the minimum number of moves under optimal play. By Lemma 3, every choice of final values has the derived increment-plus-game cost. Fixing $m$ makes all element choices independent and produces $C_m`. The two-direction argument above proves that minimizing these relaxed values over $m$ equals the optimum over all final arrays. Lemma 4 computes every per-element minimum exactly, and no $m\ge18$ can be optimal. Therefore, the algorithm checks every potentially optimal strategy and returns the required answer. ## Complexity Across all $m$, only $O(\log A)$ tiny candidate targets are examined per element; a looser bound of $O(\log^2 A)$ also easily passes. The total time is $O(n\log A)$ with these constraints, and the memory usage is $O(n)$.