PROBLEM LINKDIFFICULTYmedium PREREQUISITESinclusionexclusion principle, dp  bitmask and digit dp. PROBLEMYou 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 subtaskFirst 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 subtaskIn 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) $\times$ $10$ (the number of transitions), i.e. $\mathcal{O}(2^{10} * 20 * \log{n})$ Solution using inclusionexclusion principleLet $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 inclusionexclusion 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) \times 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 inclusionexclusion 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 $l1$ 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.
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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 16 Apr '17, 05:10

Can someone explain the combinatorics part for finding the number of ways of filling the remaining numbers for a given prefix via inclusionexclusion? answered 18 Apr '17, 00:50

The gist of the inclusionexclusion 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[i] 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[i] times (our original problem). You can view my solution here: https://www.codechef.com/viewsolution/13353292 The important functions are go() which implements the inclusionexclusion part, and all_with() which implements the combinatorics part. Let me know if you didn't get something. :) answered 18 Apr '17, 03:22

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. answered 18 Apr '17, 21:48

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!! answered 18 Apr '17, 06:35

@acyume I also have used same approach as mentioned in the editorial using INCLUSIONEXCLUSION technique, but my solution is failing for some testfiles . I tried a lot to debug it by generating lots of testfiles but i couldn't figure out where it is failing. So, can you please tell me after looking at the testresults where it is failing? Thanks in advance. link to my solution : https://www.codechef.com/viewsolution/13330723 answered 18 Apr '17, 15:25

I am unable to view the testers and setters solutions due to an 'access denied' error. answered 18 Apr '17, 02:19

i used inclusionexclusion,concept of digit dp and simple Reasoning https://www.codechef.com/viewsolution/15951934 answered 25 Oct '17, 00:44

User InclusionExclusion Principle I have a few questions
answered 04 Feb, 16:29
