PROBLEM LINK
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(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 set-bit 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 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.