NEXTNUM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vineet Paliwal
Tester: Roman Rubanenko
Editorialist: Jingbo Shang

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Factorial, Enumeration, Bruteforce

PROBLEM:

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 alt text

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.

2 Likes

Plz tell me where my code is wrong…i have checked for many cases and it’s giving correct answer…http://www.codechef.com/viewsolution/2998892

1 Like

Big Integer? Don’t need it. Answer always fits in long long (it’s quite obviuos, because 2^63>18!).

2 Likes

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 saw that some solutions calculated answers by moving from last digit to first. Can anyone explain that to me

Can someone please tell what is the meaning of this - \frac{(\sum_{i = 0} ^ {9} N[i]) !}{\Pi_{i = 0}^{9}(N[i])!} ?

Let’s consider a simpler problem: how many different numbers (leading 0s are fine) can we get by permuting its digits?

In the formula for this, there should be multiplication of frequencies instead of numbers in denominator itself.

Yeah… In this problem BigInteger just slows down the coding time…

http://www.codechef.com/viewsolution/2998578

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.

This is cakewalk?!