Hints → https://atcoder.jp/contests/arc153/editorial/5524

For a sequence \(A\) of non-negative integers, let \(F(A)\) denote the minimum possible value of \(\sum_{i=1}^N f(A_i+x)\).

Additionally, let \(K\) be the maximum number of digits in \(A_i\).

[1] Computing \(F(A)\) recursively

For \(0\leq r\leq 9\), let \(F_r(A)\) denote the minimum of the above value for \(x\) such that \(x\equiv r \pmod{10}\). We have \(F(A) = \min_{r} F_r(A)\).

For instance, when \(r=1\), if we let \(x=10x'+1\), from \(f(123+x)=f(12+x')+4\), \(f(45+x)=f(4+x')+6\) and so on, we have:

\[F_1((123,45,678,90)) = 20 + F((12,4,67,9)).\]

Similarly, when \(r=5\), we have:

\[F_5((123,45,678,90)) = 16 + F((12,5,68,9)).\]

In this way, when \(\max(A)\geq 2\), one can compute \(F(A)\) using \(F(A')\) for a sequence \(A'\) with smaller values. When \(\max(A) = 1\), we clearly have \(F(A) = \text{sum}(A)\), so this method can compute \(F(A)\).

[2] Evaluating the number of states

For how many sequences \(A'\) do we have to compute \(F(A')\) when computing \(F(A')\) recursively by the above method?

It can be seen that the recursive calls at depth \(k\) only take the sequences \(A'\) that can be written as \(A'_i = \biggl\lfloor \dfrac{A_i + c}{10^k}\biggr\rfloor\) for some \(0\leq c < 10^k\).

Thus, if \(i_1, i_2, \ldots, i_N\) are the result of sorting \(i=1,2,\ldots,N\) in ascending order of \(A_i\bmod 10^k\), the recursive calls only take \(A'\) in the following form:

\[A'_i = \begin{cases}\biggl\lfloor \dfrac{A_i}{10^k}\biggr\rfloor & (i = i_1, \ldots, i_n) \\ \biggl\lfloor \dfrac{A_i}{10^k}\biggr\rfloor+1 & (i = i_{n+1}, \ldots, i_N)\end{cases}\]

Let \(A(k, n)\) denote the sequence \(A'\) determined in this way. One can see that there are at most \(K(N+1)\) such sequences.

[3] Summary

Therefore, the problem can be solved by dynamic programming where \(\text{dp}[k][n]\), defined by \(\text{dp}[k][n] = F(A(k,n))\) (\(0\leq k < K, 0\leq n\leq N\)), are computed in descending order of \(k\). The bottleneck is the sorting of \(A_i\bmod 10^k\) for each \(k\), and the total complexity is \(O(NK\log N)\). Or, in the manner of radix sort, one can use the result of sorting \(A_i\bmod 10^{k-1}\) in the sorting of \(A_i\bmod 10^k\) to make the complexity \(O(NK)\).

Note that the complexity would increase if you performed a computation taking \(\Omega(N)\) time for all sequences \(A(k,n)\), such as examining all terms. To perform the recursive computation stated in [1], you only need the frequency distribution of the ones digits of \(A(k,n)\), so the computation can be done faster by looking at the differences of \(A(k,n+1)\) and \(A(k,n)\), or using some cumulative sums.