PROBLEM LINKDIFFICULTYSIMPLE PREREQUISITESBrute Force, Simple Math PROBLEMA Delicious number is a number which contains digits uniquely. You have to find the number of Delicious numbers between a given range. QUICK EXPLANATIONThe 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(R)  numBelow(L1). EXPLANATIONMETHOD 1  Generate all Delicious NumbersYou 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.
Initialize delicious and used as follows for i = 1 to 9 delicious.enque(i) used.enque(2^{i}) 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 setbit i in _u (in increasing order from 0 to 9) new_d = d*10 + i new_u = u  2^{i} 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 NThis calculation would require some precalculations to be performed. Let alldelicious(k) be the number of delicious numbers with at most k digits. alldelicious(0) = 0 alldelicious(1) = 9 alldelicious(2) = 9 * 9 + alldelicious(1) alldelicious(3) = 9 * 9 * 8 + alldelicious(2) ... alldelicious(10) = 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 + alldelicious(9) alldelicious(k) = alldelicious(k1), for k > 10 (since a delicious number will never have more than 10 digits!) Let forceddelicious(k,n) be the number of delicious numbers of n digits that can be constructed using k unique digits. forceddelicious(k,n) = k! / (nk)! Let delicious(T) be the number of delicious numbers less than or equal to T. The intricasies of delicious(T) are best explained in pseudocode 1 procedure:delicious(T) 2 let k be the number of digits in T 3 result = alldelicious(k1) 4 if(k > 10) return result 5 // since we have already counted all the delicious numbers 6 Let b be a bitmask of digits seen till now 7 b = 0 8 for digit d in T from left to right, at position p (1based) 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 + forceddelicious(10p,kp) 14 b.set(d) 15 result = result + 1 16 // since the number must itself be a delicious number 17 return result The above pseudocode is not entirely correct. In line11, 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(R)  delicious(L1). SETTERS SOLUTIONCan be found here. TESTERS SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Nov '12, 18:28

can anyone breakdown this tutorial into a simpler version? not able to get it! answered 13 Nov '12, 15:09

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:
Store them in an array as :
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
2.Now consider the numbers greater than 23 not included in the first case: These numbers can be of the form:
3.Now consider numbers less than 267 not included the first case:
(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
Design your code according to every test case possible and not limited to a particular test case. answered 14 Nov '12, 01:26

Thank you for your reply @jigsaw004 :) 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! answered 14 Nov '12, 15:19

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? answered 26 Dec '14, 12:29

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 answered 09 Feb '15, 22:41

+1 for brute force
Is
forceddelicious(k,n) = k! / (nk)!
correct? If k > n then(nk)!
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 bek!
but that doesn't correspond with the real answer. Am I missing out something?