Given a number with D digits, find the its rank in the ascendingly sorted list of all numbers that can be generated by permuting its digits.
EXPLANATION:
Using the brute force enumeration, we can simply try all D! permutations and get the order. But it takes too much time.
Let’s consider a simpler problem: how many different numbers (leading 0s are fine) can we get by permuting its digits? Suppose the number of digit i (0 <= i <= 9) is N[i]. Then, the answer is
In another word, the target of the original problem is to find how many numbers generated by permuting the input number’s digits are smaller than it.
The smaller numbers can be grouped by how long the common prefix with the input number they have. Considering the smaller numbers with L digits same prefix, enumerate the next digit (must be smaller than the input number’s next digit) and sum the number of “how many different numbers can we get by permuting the remaining digits” which is solved previously.
The final algorithm is as follow:
For L = D - 1 downto 0
For nextDigit = 0 to inputNumer[L + 1]
Answer += “how many different numbers can we get by permuting the remaining digits”
64-bit integers are enough for answers. Thus, the time complexity is about O(D).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
I would also like to know where @hatim009 solution fails. I ran it against my own AC solution several times with sets of 10000 numbers and one time with 1000000 numbers and couldn’t find a mistake.
i changed my input used scanf() instead of getchar() and it got AC…don’t know why. i use Dev++ and i had also checked my program in GCC compiler and it is running fine. AC solution… http://www.codechef.com/viewsolution/2999341
Probably the input data contains extra whitespaces and such. I suspect the same situation can also be found in problem AMIFIB, where I get WA for using gets(), but using scanf() gives me AC.
I have updated the editorial.I think it represents the (summation of all N[i] from i=0 to i=9) factorial divided by product of all factorials of N[i] with i ranging from 0 to 9.Correct me if I am wrong.
