DGTCNT - Editorial

april17
dgtcnt
editorial

#1

PROBLEM LINK

Practice
Contest

DIFFICULTY

medium

PREREQUISITES

inclusion-exclusion principle, dp - bitmask and digit dp.

PROBLEM

You are given 10 integers a_0, a_1, \dots, a_9. An integer x is said to be bad if it has number of i's in its decimal representation equal to a_i for some i in the range [0, 9].

Find the number of good integers in the range [L, R], where L, R can potentially go up to 10^{18}.

Solving first subtask

First subtask is very easy to solve. The L, R values can go maximum up to 10^5. We itearte over each x in the range [L, R], and check whether x is good or not by writing its decimal representation. Time complexity of this algorithm will be \mathcal{O}(|R - L + 1| * \log{R}), which will be \mathcal{O}(|R - L + 1| * \log{R}) in the worst case, i.e. around 10^6 operations.

Solving second subtask

In the second subtask a_i = 0 for each i. It means that an integer will be bad if there is some number i that does not appear in it, i.e. the good numbers should contain each number from 0 to 9. Let solve(n) denote the the number of integers from 0 to n that are good for a given n, then we can easily find the number of good numbers in the range [L, R] by solve(R) - solve(L - 1). From now on, we will focus on finding number of good numbers in the range 0 to n.

You can use a simple digit dp for it, the state of the dp will be dp(i, tight, mask) meaning that we are currently processing i-th digit and tight will denote the current prefix of number being generated is equal to prefix of n or not, mask will denote the digits that have appeared till now. We can process the current index by trying all possible digits at the i-th place and making transitions. Time complexity of this approach will be \log{n} \cdot 2 \cdot 2^{10} (number of states) imes 10 (the number of transitions), i.e. \mathcal{O}(2^{10} * 20 * \log{n})

Solution using inclusion-exclusion principle

Let A_i denote the set of numbers in the range [0, n] that consist A_i number of i's. We want to find the cardinality of union of A_0 \cup A_1 \dots \cup A_9. We can use the inclusion-exclusion principle for this. Let mask be an integer whether if the i-th bit of mask is set, then it will mean that number of i's in the decimal representation of the number is a_i. Note that this doesn’t put any condition on the bits of mask that are not set, their count could potentially be equal to corresponding a_i too. The set of masks that have odd number of set bits in it should be added into the answer, and those of even set bits should be subtracted from the answer.

Now, our problem turns into finding count of numbers in the [0, n] where you are also provided an integer mask denoting where the corresponding set bits put condition on the count of corresponding set bits.

A number in the range [0, n] will follow this kind of structure. It will have some prefix common with n, then the following digit being strictly less than corresponding digit of n, and then the remaining digits could be anything. So, we iterate over each possible length of largest common prefix from 1 to 18 (as n can be at most 10^{18}), then we iterate over the next digit from 0 to the corresponding digit of n. We can check the count of digits that have appeared till now. For the set bits, we can find the number of their occurrences which should be a part of upcoming part of the number being constructed. Obviously, it might happen that the count of some number i with i-th bit set of mask might have its number of occurrences greater than a_i, which will mean that the constructed number is already invalid and we should not proceed with it further. We can use simple combinatorics to find the number of ways of filling the remaining numbers.

One possible issue that might come in implementation is to take care of leading zeros properly. Assume that length of common prefix of the number being generated is zero, i.e. the first digit is 0. You should count such cases carefully.

Time complexity of the solution will be 2^{10} (maximum possible number of masks) imes 18 (number of possible values of largest common prefix) * 10 (number of ways of deciding the digit after the longest common prefix) * 18 (number of ways of filling the remaining digits using combinatorics)).

Overall time complexity will be \mathcal{O}(2^{10} \cdot 18 \cdot 10 \cdot 18) = 3 * 10^6 per test case. There are 20 test cases, which will have a total number of operations around 10^8 which will pass comfortably under 1 sec.

A polynomial time solution.

The main idea of the solution is very similar to previous solution, except that we won’t be using inclusion-exclusion principle this time. We fix a prefix of digits of n, and the next digit and find the number of ways of filling the remaining suffix using a dynamic programming solution.

Assume zero based indexing. Let D denote the number of digits in decimal representation of n, and d_i denote the i-th digit in the decimal representation of n (remember we are going from most significant bit to least significant bit, in other words from left to right). Suppose we fixed a prefix of length l (i.e. the digits from 0 to l-1 are decided, these digits will be prefix of digits of n of length l). Now the digit at position l could go from 0 to d_i - 1. Let us find the number of ways of filling the remaining suffix of length D - l - 1. We know the number of occurrences of digits already encountered in the first l+1 digits. We need to count the number of ways of filling the remaining digits in such a way that number of occurrences of all digits i (from 0 to 9) is not equal to a_i.

We will first fill 0’s in the suffix, then 1’s, 2’s and so on till we fill the digit 9. So, we start with filling 0’s in the suffix, we can decide the number of zeros that we want to fill (ensuring the number of already filled zeros and these zeros is not equal to a_0). If the length of suffix is L, then number of ways of filling cnt_0 zeros will be \binom{L}{cnt_0}. Afterwards, we will go for filling 1’s in the remaining unfilled positions of the suffix. So, our dp state will be dp(curDigit, rem), denoting that are are currently trying to fill the suffix by curDigit, and rem will denote how many digits in the suffix are yet to be filled.

Time complexity of the approach can be determined as follows.

  • We iterate over each prefix of digits of n : D \leq 18.
  • We iterate over the next digit : d_i \leq 10
  • We find the number of ways using the dp solution:
    • states of dp(curDigit, n) \leq 10 \cdot 18
    • transitions of the dp: we try all possible counts of the curDigit \leq 10

The time complexity will be product of these, i.e. \mathcal{O}(D \cdot 10 \cdot 10 \cdot 18 \cdot 10) = 18 \cdot 10 \cdot 10 \cdot 18 \cdot 10 = 18^2 \cdot 10^3 = 324000 = 3 \cdot 10^5 operations. Note that you will also have to account for the constant factors involved too for estimating total number of operations.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.


#2

Can someone explain the combinatorics part for finding the number of ways of filling the remaining numbers for a given prefix via inclusion-exclusion?


#3

I am unable to view the testers and setters solutions due to an ‘access denied’ error.
Could you please fix it and/or upload it elsewhere?


#4

@sachinsahoo11

The gist of the inclusion-exclusion part is this: We add to our answer all numbers having 0 exactly a[0] times, or 1 exactly a[1] times, etc. But in this way we have counted some numbers multiple times. So we remove from our answer those numbers where 0 appears a[0] times AND 1 appears a[1] times, or 0 appears a[0] times AND 2 appears a[2] times, etc. Then we add those where 0 appears a[0] times AND 1 appears a[1] times AND 2 appears a[2] times, and so on. This can be efficiently done using a bitmask.

The problem of finding the count of numbers where selected digits appear x* times can be solved by simple combinatorics: Place these selected digits in any positions, and fill the remaining places with any other digits. Now if we have selected a specific prefix, say 1123, then we can simply subtract 2 from a[1], and 1 each from a[2] and a[3], and count all numbers where any number has a digit i appearing a* times (our original problem).

You can view my solution here: https://www.codechef.com/viewsolution/13353292

The important functions are go() which implements the inclusion-exclusion part, and all_with() which implements the combinatorics part. Let me know if you didn’t get something. :slight_smile:


#5

Can someone explain the digit dp with bit masking in elaborate way? I’m a newbie to digit dp. I find really difficult to get hold of the concept from this editorial. Please!!


#6

@acyume I also have used same approach as mentioned in the editorial using INCLUSION-EXCLUSION technique, but my solution is failing for some test-files . I tried a lot to debug it by generating lots of test-files but i couldn’t figure out where it is failing. So, can you please tell me after looking at the test-results where it is failing?
Thanks in advance.
link to my solution : https://www.codechef.com/viewsolution/13330723


#7

@drajingo

Thanks, nice explanation. Got it now.


#8

From my point of view Editorials are not well defined. It’s really hard to understand the Inclusion exclusion method, specially for people like us who’re in the stage of improving themselves… Such things end up making me feel depressed.


#9

i used inclusion-exclusion,concept of digit dp and simple Reasoning
https://www.codechef.com/viewsolution/15951934


#10

Setter’s and Tester’s Solution are visible. Can someone put their solution if it had some comments?
@admin please fix it


#11

User Inclusion-Exclusion Principle I have a few questions

  • The set of masks that have odd number of set bits in it should be added into the answer, and those of even set bits should be subtracted from the answer” Why is this so ?

  • …where you are also provided an integer mask denoting where the corresponding set bits put condition on the count of corresponding set bits”. What does this sentence even mean ?