You are not logged in. Please login at www.codechef.com to post your questions!

×

DGTCNT - Editorial

3
7

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) $\times$ $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) \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 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.

This question is marked "community wiki".

asked 16 Apr '17, 05:10

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136169
accept rate: 20%

edited 19 Apr '17, 22:31


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

link

answered 18 Apr '17, 00:50

sachinsahoo11's gravatar image

5★sachinsahoo11
353
accept rate: 0%

@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[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 inclusion-exclusion part, and all_with() which implements the combinatorics part. Let me know if you didn't get something. :)

link

answered 18 Apr '17, 03:22

drajingo's gravatar image

4★drajingo
1645
accept rate: 37%

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.

link

answered 18 Apr '17, 21:48

tommy_trash's gravatar image

4★tommy_trash
41
accept rate: 0%

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!!

link

answered 18 Apr '17, 06:35

boovi's gravatar image

3★boovi
211
accept rate: 0%

@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

link

answered 18 Apr '17, 15:25

divakar_tomar's gravatar image

5★divakar_tomar
111
accept rate: 0%

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?

link

answered 18 Apr '17, 02:19

vicennial's gravatar image

6★vicennial
2595
accept rate: 0%

@drajingo

Thanks, nice explanation. Got it now.

link

answered 18 Apr '17, 17:49

sachinsahoo11's gravatar image

5★sachinsahoo11
353
accept rate: 0%

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

link

answered 25 Oct '17, 00:44

chemtham's gravatar image

2★chemtham
203
accept rate: 0%

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

link

answered 26 Oct '17, 01:31

sonu_628's gravatar image

4★sonu_628
3468
accept rate: 8%

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 ?

link

answered 04 Feb, 16:29

dollarakshay's gravatar image

4★dollarakshay
17617
accept rate: 4%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,130
×122
×7

question asked: 16 Apr '17, 05:10

question was seen: 3,030 times

last updated: 04 Feb, 16:29