 # CNTDIGIT - Editorial

Difficulty: Medium-Hard

Pre-requisites: DP

Problem:

Given an integer N. You are to calculate the sum of distinct digits that appear in the decimal representation of at least one of the numbers L, L+1 … R for each pair (L, R), where 1 ≤ LRN.

Explanation:

The first observation is that all ranges that contain 10 or more integers will have the answer 10. So, we can calculate the answer for them separately. Otherwise, the answer will be between 1 and 10 and the size of the range will be less than 10. The most hard part of the problem is to handle that kind of ranges.

I strongly recommend you to read the following editorials before this one and understand it: Round Numbers (USACO), FAVNUM (CodeChef). Otherwise, it’s gonna be super-hard to understand this editorial.

Let’s make an array B[], which contains the digits of N(from the most to the least significant bits). For example, if N = 1240941, then B[] = [1, 2, 4, 0, 9, 4, 1]. After that, we should precaculate the following dynamic programming: F( the size of the prefix of B )( boolean flag, that indicates if the current prefix is equal to the corresponding one in B )( bitmask of different digits, that we have faced so far ). F equals to the number of different prefixes with the corresponding properties. If you understand the editorials, that I have suggested above, then you should be able to calculate that DP in O( 2 * 210 len( N ) ) time.

OK, now let’s discuss the hardest part.

Let’s represent L(the left bound of some range) like “…x9999…999y”, where x and y are digits. More than this, x is not greater than 8. Now we are working only with ranges that contain less than 10 elements, so the part of L, which lays before x, will stay the same for any possible R. Also, let’s fix D = R - L(0 ≤ D ≤ 8). Then, we can easily say, how does the part of R, that corresponds to the “x9999…999y” part of L after adding D, look like. To calculate the answer for all variants with fixed x, the number of 9’s after x, y and D we can use the precaculated DP F. It’s kind of meet-in-the-middle approach: the first half of the numbers we treat with DP, the second half of the numbers has a pattern “x9999…999y” and it’s also fixed.

You should be really careful to consider all the possible cases and calculate the answer correctly. I suggest you to think about the solution for a while. If you still don’t understand the conception - feel free to ask a question.

Total complexity is O( 2 * 210 len( N ) + 9 * 10 * len( N ) * 8 * len( N ) ).