C - 1, 2, 3 - Decomposition Editorial by evima
Let us call a positive integer good whose every digit is \(1\), \(2\), or \(3\).
For \(N\geqq 0\), let \(f(N)\) be the minimum number of good integers when representing \(N\) as the sum of good integers. We have \(f(0) = 0\). Additionally, for convenience, we let \(f(N) = \infty\) for \(N < 0\).
◆ The structure of the sum of good numbers
Let us first understand what kind of numbers can be represented as the sum of \(K\) good numbers.
Let us represent each \(A_i\) as \(A_i = 10a_i + b_i\) using the quotient and remainder when dividing it by \(10\). Then, \(A_i\) is good if and only if:
- \(b_i\) is \(1\), \(2\), or \(3\); and
- \(a_i\) is a good number or \(0\).
Thus, a number can be written as the sum of \(K\) good numbers if and only if it can be written as the sum of the following:
- an integer between \(K\) and \(3K\);
- the sum of at most \(K\) good numbers, multiplied by \(10\).
Using this fact, let us recursively compute \(f(N)\).
◆Computing \(f(N)\)
Assume \(N\geqq 1\). Also, let us assume that \(f(N')\) is known for every \(N' < N\) to come up with a way to compute \(f(N)\).
From the above statement, for each \(K = 1, 2, 3, \ldots\) in this order, we can determine whether \(N\) can be written as the sum of \(K\) good numbers in \(O(K)\) time. For example, we can:
- try all integers \(r\) between \(K\) and \(3K\);
- if there exists an integer \(n\) such that \(N = 10n + r\) and it satisfies \(f(n) \leqq K\), \(N\) can be written as the sum of \(K\) good numbers.
We can do this check for each \(K\) in order and let \(f(N) = K\) when it first succeeds.
◆ The upper bound of the answer and analysis of complexity
It turns out that \(f(N) \leqq 5\) for any \(N\geqq 0\). We can easily prove this by induction from the fact that we can always choose \(n\) and \(r\) such that \(N = 10n + r\) and \(5\leqq r\leqq 15\) when \(N\geqq 5\).
We can find \(f(N)\) by doing the above check for \(K = 1, 2, 3, 4\), which can be done in \(O(1)\) time under the assumption that \(f(N')\) is known for every \(N' < N\).
Additionally, we can see that \(f(N)\) is determined by two values \(f(n)\) and \(f(n-1)\), where \(n = \lfloor N/10\rfloor\). Thus, we only need to compute \(f(n)\) sequentially for values that can be written as \(n = \lfloor N/10^k\rfloor\) or \(n = \lfloor N/10^k\rfloor - 1\). There are \(\Theta(\log N)\) such numbers \(n\), so we can solve the problem in \(\Theta(\log N)\) time per test case.
◆ Sample Implementation
posted:
last update: