Sum of Digits (and Again)

Research note: I checked the official Codeforces editorial/model solution, CF Step’s hints/code page, and the contest discussion comments. The common intended idea is to enumerate the second number in the chain, not the original huge number.

Let $D(v)$ be the sum of decimal digits of $v$.

For a number $A>9$, the string has the form

$$S(A)=\text{repr}(A)\;\text{repr}(D(A))\;\text{repr}(D(D(A)))\;\cdots$$

The annoying part is that $A$ may have up to $10^5$ digits, so directly trying values of $A$ is obviously cooked. The useful trick is to name the second number:

$$y = D(A).$$

Once $y$ is fixed, everything after $A$ is forced. Define

$$T(y)=\text{repr}(y)\;\text{repr}(D(y))\;\text{repr}(D(D(y)))\;\cdots$$

ending when the current value is one digit. Then any valid answer with $|s|>1$ must be

$$\text{repr}(A) + T(y)$$

where the digits of $A$ are exactly the leftover digits after removing the digits of $T(y)$ from the input multiset.

So we enumerate $y$.

Why is that small? Let

$$\text{SUM}=\sum_{c\in s}(c-\texttt{'0'}).$$

Since $A$ uses some of the digits of $s$,

$$y=D(A) \le \text{SUM} \le 9|s|.$$

Across all test cases, $\sum |s|\le 10^5$, so scanning all $y=1\ldots \text{SUM}$ is easily fine.

For a candidate $y$:

1. Build the digit counts of $T(y)$.
2. Check that these counts are available in $s$.
3. Let the remaining counts be the supposed digits of $A$.
4. Check that their digit sum is exactly $y$.
5. For non-singleton inputs, also require at least two leftover digits, because otherwise $A\le 9$ and the chain would stop immediately. This mostly protects against invalid junk like 11; the official constraints promise valid input, but the check costs nothing.

If all checks pass, construct the answer:

• print the leftover digits in descending order to form $A$;
• then print $T(y)$.

Descending order is not about greed. It just guarantees no leading zero because the leftover digit sum is $y>0$, so some nonzero digit exists. Any order with a nonzero first digit would work.

Correctness proof:

Assume the algorithm outputs a string for some candidate $y$. The suffix printed is exactly $T(y)$ by construction. The prefix consists of the leftover digits, call that number $A$. The leftover digit sum check gives

$$D(A)=y.$$

Because the prefix has at least two digits, $A>9$, so after appending $A$, the process continues with $D(A)=y$. From that point onward, the process appends exactly $T(y)$. Therefore the output is $S(A)$. Also, every printed digit comes from the input multiset exactly once, so it is a valid rearrangement.

Now assume a valid rearrangement exists. If $|s|=1$, the string itself is already $S(x)$ for the one-digit number $x$. Otherwise, let the valid original number be $A>9$ and let $y=D(A)$. The algorithm will eventually test this exact $y$. The digits of $T(y)$ are present as the suffix of $S(A)$, so the availability check passes. The remaining digits are precisely the digits of $A$, whose digit sum is $y$, so the leftover-sum check passes too. Thus the algorithm finds a valid candidate and prints a correct answer.

For implementation, precompute for all $v\le 900000$:

• $D(v)$;
• need[v][d], the number of times digit $d$ appears in $T(v)$.

For $v<10$, need[v] is just the digit count of $v$. For $v\ge 10$:

$$\text{need}[v] = \text{digits}(v) + \text{need}[D(v)].$$

Since $D(v)<v$ for $v\ge 10$, computing in increasing order works.

Complexity:

Precomputation is $O(900000\cdot 10)$, tiny. For each test case, scanning candidates costs $O(10\cdot \text{SUM})$, and

$$\sum \text{SUM} \le 9\sum |s| \le 900000.$$

So the total runtime is effectively linear in the input size, with a small constant. Memory is $O(900000\cdot 10)$.