CNTDIGIT - Editorial

general
, ,
1

Problem Link: contest, practice

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 ≤ L ≤ R ≤ N.

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.

Please, check out Setter’s and Tester’s solutions for your better understanding.

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

Setter’s Solution: link

Tester’s Solution: link

2 Likes
2

I have solved favnums as you suggested( Thanks , I have learned Aho Corasick and it was a fun problem) . But still can’t understand what you are telling to do in the dp F. I mean , I have the string. but what does it mean to be (size if prefix) . What is the current prefix. Can you explain the dp F a bit more with explanation of the transitions please? like what is the corresponding property for number of prefix ?

3

Let’s fix some F(6)(0)(1010111011). That means, that we have considered six first digits of B[], the current prefix is lexicographically less than the corresponding prefix of B(in case the second parameter equals to 1, the current prefix equals to the corresponding prefix of B) and we have faced the digits {0, 2, 4, 5, 6, 8, 9}. Is that clear?

4

yes , thank you ! but if that is so , then there is no need for some string matching algo.

5

Can somebody explain me the test case in the question ? Please…