Six Seven

I used the official Codeforces statement at 2200H - Six Seven and the official Round 1084 tutorial as research references. Public accepted-submission mirrors did not surface quickly, so the proof here is derived from the statement and the official recursive idea.

Let $v_p(x)$ be the exponent of prime $p$ in $x$. Then

$f_6(x)=\min(v_2(x),v_3(x)),\qquad f_7(x)=v_7(x).$

So $x$ is special iff

$\min(v_2(x),v_3(x)) > v_7(x).$

First, every special number is divisible by $6$, because the left side must be at least $1$. That immediately gives a hard impossibility check: after adding the same number of operations $d$, all values must become multiples of $6$, so all original $a_i$ must have the same residue modulo $6$. If not, answer is $-1$. No amount of cleverness fixes modular arithmetic being pissed at you.

Now classify special numbers by modulo $42$.

If $42 \nmid x$, then $x$ is special exactly when $6 \mid x$. Indeed, if $6 \mid x$ but $42 \nmid x$, then $7 \nmid x$, so $f_7(x)=0$ and $f_6(x)\ge 1$. If $6 \nmid x$, then $f_6(x)=0$, impossible.

If $42 \mid x$, write $x=42y$. Then

$f_6(42y)=1+f_6(y),\qquad f_7(42y)=1+f_7(y),$

so

$42y \text{ is special} \iff y \text{ is special}.$

That is the whole trick: numbers divisible by $42$ recurse after division by $42$; nonzero multiples of $6$ modulo $42$ are already done.

Define $F(A)$ as the minimum shared increment needed for all numbers in a multiset $A$. If $A$ is empty, $F(A)=0$. If every element is $1$, then $F(A)=5$, because $1+5=6$ is the first special number.

Assume all elements have the same residue $c$ modulo $6$. Any valid increment $d$ must satisfy

$d \equiv -c \pmod 6.$

Write

$d=k+42q,\qquad 0\le k<42.$

There are only seven possible values of $k$. For each $r\in\{0,1,\dots,6\}$, let

$k_r \equiv -c-6r \pmod{42},\qquad 0\le k_r<42.$

This is the choice where exactly the elements with

$x\equiv c+6r \pmod{42}$

land on $0$ modulo $42$ after adding $k_r$.

For all other residue classes, $x+k_r+42q$ is a nonzero multiple of $6$ modulo $42$, so it is automatically special. The only elements still requiring work are the ones landing on $0$ modulo $42$:

$x+k_r+42q = 42\left(\frac{x+k_r}{42}+q\right).$

By the recursive property, those are special iff the transformed numbers

$T_r=\left\{\frac{x+k_r}{42}: x\in A,\ x\equiv c+6r \pmod{42}\right\}$

become special after $q$ more operations. Therefore

$F(A)=\min_{r=0}^{6}\left(k_r+42F(T_r)\right).$

If a recursive branch is impossible, treat it as infinity.

Why this is correct:

For the lower bound, take any valid increment $d$. Let $k=d\bmod 42$ and $q=(d-k)/42$. The chosen $k$ corresponds to one residue class modulo $42$ landing on zero. Every element in that class must still be special after dividing by $42$, so $q$ must be a feasible answer for the transformed set. Hence $d\ge k+42F(T)$.

For the upper bound, choose some residue class $r$ and let $q=F(T_r)$. Add $d=k_r+42q$. Elements outside $T_r$ become nonzero multiples of $6$ modulo $42$, hence special. Elements inside $T_r$ become $42$ times recursively special numbers, hence also special. So the recurrence constructs a valid increment.

The recursion terminates because transformed values are roughly divided by $42$. The only self-loop case is all ones, handled by the base case $5$.

Implementation details:

Scan the current vector. If residues modulo $6$ differ, return infinity. Otherwise bucket numbers by ((x-c)/6) mod 7, which is their residue class among the seven possible multiples of $6$ modulo $42$. For each bucket, compute the corresponding $k_r$, transform only that bucket by dividing (x+k_r)/42, recurse, and minimize.

Complexity: each recursion level partitions the elements, and values shrink by a factor of about $42$. The time is $O(n\log A)$ over a test case, with $A=\max a_i$; here the depth is tiny for $A\le 10^9$. Memory is $O(n\log A)$ with these simple vectors, still easily inside limits.