PROBLEM LINK:
Author:
Tester:
Editorialist: Jingbo Shang, Suhash
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Dynamic Programming, Fast Power Method, A little Math
PROBLEM:
Given a number N, find the sum of f(x) for all x such that 1 <= x <= N. f(x) is defined as the sum of all digits in base 10 representation of the number x.
The special condition is that the total number of different consecutive digits are limit to M–1. That is, in the base 10 representation of N, there are only M blocks and each block contains the same digits.
EXPLANATION:
Simpler Version 1
Before we begin solving the actual problem, let’s try to solve the following problem:
Given an integer x, let g(x) denote the sum of the digits of all integers from 1 to (10^x)-1.
It can be proved very easily that g(x) = 45 * x * 10^(x-1). Because for each digit 0…9 (0+1+2…+9 = 45), it could occurs in x different positions and there are 10^(x-1) different combinations for other positions. By this formula and fast power method, for a given x, g(x) can be calculated in O(log x).
Simpler Version 2
Now, coming to the actual problem, let’s again first try and solve a simpler version of the problem: Given an integer N, find h(N) = sum{f(i), i=1 to N}, where length(N) <= 10^6.
First, let N = (n1 n2 n3 … nk) in base 10 representation. Here, k = length(N), and the digits 0 <= ni <= 9.
Then, define dp[i] as sum of all numbers <= N, such that the first i-1 digits of N remain unchanged, and remaining digits can be filled in anyway, such the integer formed is <= N. This can be done as follows.
At position i,
-
if we put any digit from 0 to ni–1, then the resulting number is always < N. In this scenario, we can fill the remaining k-i positions with any digits. This value is exactly g(k-i), which we have discussed in simpler version 1. The number of ways of filling is 10^(k-i). Summing the above cases, we get
(0 + 1 + 2 + ... + (ni-1)) * 10^(k-i) + ni * g(k-i) -
If we put a digit = ni at position i, problem reduces to dp[i+1].
Therefore, we can write it as follows:
dp[i] = (0 + 1 + 2 + ... + (ni-1)) * 10^(k-i) + ni * g(k-i) + dp[i+1].
With a little simplification, it can be seen that this can be done in O(k * log k), while dp[1] is the required answer.
If k <= 10^6, then this can be easily solved. But in our case, k <= 10^18. We need to do something smarter.
Final Version
The trick is that a contiguous block of digits have the same value. In the above dynamic programming, instead of going from dp[i] to dp[i+1], we can go from dp[i] to dp[i+L], where a contiguous block of L digits have the same value.
It can basically be reduced to the following form:
dp[i] = sum(j=i to i+L) (k1 * 10^(k-j) + k2 * (k-j) * 10^(k-j)) + dp[i+L].
where, k1 and k2 are two constants depend on ni could be derived from previous discussion. The sum part above can be found in O(log L) using the similar idea to the fast power method. And we only need to calculate the value of dp at most M points, where M is the number of blocks of digits given. Thus, the problem can be solved in O(M log L).
AUTHOR’S AND TESTER’S SOLUTIONS:
The links will be fixed soon.
Author’s solution can be found here.
Tester’s solution can be found here.