DDISH - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Brute Force, Simple Math

PROBLEM

A Delicious number is a number which contains digits uniquely. You have to find the number of Delicious numbers between a given range.

QUICK EXPLANATION

The number of Delicious numbers in a given range can be found in many ways. We have to ensure that we select a manner which is fast enough. Since, there are as many as 200,000 queries per input file, and only a second to spare on it.

You can brute force to generate all the Delicious numbers. There are only 8,877,690 of them. We will cover the details of this generation in the detailed explanation section.

Once this is complete, the answer can be found by performing a binary search on the list of Delicious numbers to find how many of them fall within the range.

Alternately, you can find the number of Delicious numbers below a number through some simple math. This too is covered in the detailed explanation section below.

If we have the number of Delicious numbers that are below a given number, then the answer can be calculated as

numBelowÂŽ - numBelow(L-1).

EXPLANATION

METHOD 1 - Generate all Delicious Numbers

You will not be able to generate Delicious Numbers in any order and then sort them. This turns out to be too slow for the problem. Sorting the numbers takes almost as much time as generating them, and hence by eliminating the need for the sorting step, we can generate the numbers fast enough.

Let us see how we can generate them, in sorted order.

  • D is an array of delicious numbers.
  • delicious is a queue to store delicious numbers.
  • used is a queue that stores masks which represent the digits that are present in the respective delicious number (in the delicious queue).

Initialize delicious and used as follows

for i = 1 to 9
    delicious.enque(i)
    used.enque(2i)

The following procedure will pick the smallest delicious number from the queue and ensure that the next batch of delicious numbers are generated. Since delicious numbers are being picked in increasing order, we are assured that when the next delicious number if picked (that is, when the procedure is called again); the delicious numbers which are generated will be larger than the ones that were generated in the previous invocation!

procedure
    d = delicious.dequeue()
    u = used.dequeue()
    D.push(d)
    _u = invert(u)
    for each set-bit i in _u (in increasing order from 0 to 9)
        new_d = d*10 + i
        new_u = u | 2i
        delicious.enqueue(new_d)
        used.enqueue(new_u)

You can see the setter’s or the tester’s solution for an implementation of this approach.

Once the list of numbers have been generated, we can binary search for the position of L and R in the list, and calculate the answer.

METHOD 2 - Calculate the number of Delicious Numbers less than N

This calculation would require some pre-calculations to be performed.

Let all-delicious(k) be the number of delicious numbers with at most k digits.

all-delicious(0) = 0
all-delicious(1) = 9
all-delicious(2) = 9 * 9 + all-delicious(1)
all-delicious(3) = 9 * 9 * 8 + all-delicious(2)
...
all-delicious(10) = 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 + all-delicious(9)
all-delicious(k) = all-delicious(k-1), for k > 10
(since a delicious number will never have more than 10 digits!)

Let forced-delicious(k,n) be the number of delicious numbers of n digits that can be constructed using k unique digits.

forced-delicious(k,n) = k! / (n-k)!

Let delicious(T) be the number of delicious numbers less than or equal to T.

The intricasies of delicious(T) are best explained in pseudo-code

1   procedure:delicious(T)
2       let k be the number of digits in T
3       result = all-delicious(k-1)
4       if(k > 10) return result
5       // since we have already counted all the delicious numbers
6       Let b be a bit-mask of digits seen till now
7       b = 0
8       for digit d in T from left to right, at position p (1-based)
9           if b.isset(d) then return result
10          // since we have already counted the delicious numbers which are less
11          for digit i = 0 to 9
12              if b.isunset(i) and i < d
13                  result = result + forced-delicious(10-p,k-p)
14          b.set(d)
15      result = result + 1
16      // since the number must itself be a delicious number
17      return result

The above pseudo-code is not entirely correct. In line-11, we seem to always consider all the digits from 0 to 9. But, if k = 0, then we cannot consider 0 as a choice of digit to start the number. Fixing that bug makes delicious(T) complete.

The answer can be found as deliciousÂŽ - delicious(L-1).

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

6 Likes
2

+1 for brute force

3

can anyone breakdown this tutorial into a simpler version?
not able to get it!

4 Likes
4

I didn’t understand the above solution either. If it helps, I can tell you the way I went about doing this problem: I used the concept of a problem that appeared in the June Long contest. This is the link to the problem and this is the link to its editorial. It involved examining all numbers between the limit by processing the digits of L & R. First of all, count the numbers totally between L & R, i.e. the numbers that have their first digit lying between that of L & R. This counting can be done easily by simple combination formula. Then count the numbers which are greater than L & less than R which were not covered for in the previous case. For example if input is:

L = 23
R = 267

Store them in an array as :

  | 0 | 1 | 2 |
----------------
L:| 0 | 2 | 3 |
R:| 2 | 6 | 7 |
----------------

Go on to the digit (starting from the most significant digit) where the first difference occurs:
i.e. the index 0 in this case.

1.Now find all the numbers starting with digits greater than L[0] + 1 & R[0] - 1 i.e. 1 in this case

Total such numbers: 1 * 9 * 8 = 72 (see for yourself)

2.Now consider the numbers greater than 23 not included in the first case:

These numbers can be of the form:

2X or XX (where X is an arbitrary digit).

for 2X: X can be  4, 5, 6, 7, 8, 9 (all digits greater than 3).

for XX: the first X can be 3, 4, 5, 6, 7, 8, 9. (all digits greater than 2).
        the second X can be any digit from 0 to 9 except the one used in the first X.

Total such numbers will be 1 * 6(for 2X) + 7 * 9(for XX) = 69

3.Now consider numbers less than 267 not included the first case:

These numbers can be of the form 26X or 2XX.

(Numbers of the form XXX have already been discussed  in first case.)

Total such numbers are: 1 * 1 * 5 (for 26X) + 1 * 5 * 8  (for 2XX) = 45.

(try to examine on your own the possible values of X)

4.Now we consider L & R themselves. Add 1 to the sum if either L or R satisfy the delicious criteria. Add 2 if both satisfy the delicious criteria else add 0.

Therefore, the answer for the above case is: 72(first case) + 69(second case) + 45(third case) + 2(last case) = 188.

I used a temporary array of size 10 with a[i] = 0 or 1 with a[i] = 0 signifying that digit ‘i’ has already been used once and a[i] = 1 signifying that digit ‘i’ is available for use.

The above example may be sufficient to sum up the whole process. However, do take care of cases like

L = 144569
R = 144789

Design your code according to every test case possible and not limited to a particular test case.

2 Likes
5

Is forced-delicious(k,n) = k! / (n-k)! correct? If k > n then (n-k)! would be a factorial of a negative number, if k < n then the answer would be 0 since we need at least n unique digits, finally if k = n the answer would be k! but that doesn’t correspond with the real answer. Am I missing out something?

6

Thank you for your reply @jigsaw004 :slight_smile:
Along with your solution I even found the second solution in the above editorial pretty good and easy!
@anton_lunyov 's solution follows that concept
link:http://www.codechef.com/viewsolution/1507602
Thank you again for taking your time and posting a reply!

7

I am unable to understand method 1 which involves the generation of delicious numbers. Could anyone please explain the pseudocode in simple terms or provide a more detailed pseudocode?

8

My code is working fine on my complier (DevC++)
Here is the link: http://www.codechef.com/viewsolution/6187493
But, I am getting a “wrong answer” when I submitted my code