Yet another algorithmic problem

[Nineshadow]

A safe has a very special kind of "lock". It displays a "public key", made out of two parts : a vector of integers v={v₀,v₁,...,v₉} and an integer k. To gain access to the safe, you must calculate the k-th integer (in ascending order) which can be formed with v₀ digits of 0, v₁ digits of 1, v₂ digits of 2 and so on, modulo 10⁹+7.

Examples :

v={1,1,0,0,0,0,0,0,0,0}:
	for k=1, the answer is 1
	for k=2, the answer is 10

v={1,1,1,0,0,0,0,0,0,0}:
	for k=1, the answer is 12
	for k=2, the answer is 21
	for k=5, the answer is 201

v={1,2,0,0,0,0,0,0,0,0}:
	for k=2, the answer is 101

Note that the number you are asked for can start with 0. If it starts with 0-s, the 0-s simply get discarded, meaning that 012=12, and 000012=12.

Restrictions

• you are given <=5.000 queries.
• the number you need to form will have at most 70.000 digits (v₀+v₁+v₂+...+v₉<=70.000)
• k <= 10¹²
• a solution is guaranteed
• time : 2sec
• memory : 65536 kbytes

___________________________________________________________________________________________________

 

I think it is clear that the problem asks what's the k-th lexicographic permutation of a certain set.

For example, if v={1,1,1,0,0,0,0,0,0,0}, then the first permutation will look like this : {0,1,2}. If v={1,2,0,0,0,0,0,0,0,0}, the first permutation will look like this : {0,1,1}.

It should also be noted that k is pretty small compared to the number, considering the amount of digits it can have.

However, the interesting part comes when we take into consideration the modulo. Calculating the modulo for a number with 70.000 digits is not at all convenient. So there's definitely something else in play here.

@fizzlesticks

[Sauron]

I haven't done the math on it but it seems to me that if you place all digits in ascending order, then scale the most significant figure to the right k-1 times, you'll find the solution (ignoring the modulo). This seems pretty efficient to me.

 

I'm confused when it comes to the modulo, 10⁹+7 is a prime number...  NVM, I'll have to think about it

 

By the way, what sort of safe gives you a hint on how to open it?

[Nineshadow]

1 hour ago, Sauron said:

By the way, what sort of safe gives you a hint on how to open it?

The one that gives you problems to solve I guess.

Finding just the k-th permutation isn't that hard. You can do it pretty easily with the factorial number system, at least theoretically. But additionally, you need to find the number made from that permutation, modulo 10⁹+7. Yes, 10⁹+7 is a prime number, which will make calculations easier if modular arithmetic arises later on. But so far...eh? I don't have too many useful ideas.

I thought about writing the permutation as a number in base 10⁹+7. That should be pretty cool. In that situation, the modulo will be just the least significant digit of the permutation. However, the issue is actually calculating the permutation in base 10⁹+7, without having to do it in base 10 and then converting it.

[Nineshadow]

@Sauron

More specifically, to generate the k-th permutation given the frequency of digits:

Consider the number x with n digits, d₀,d₁,...,d_n-1.

Order the digits such that d₁<=d₂<=...<=d_n.

Let the frequencies with which the digits appear in the number x be f₀,f₁,...,f₉.

Then the number of distinct permutations of the digits of x will be nr=n!/(f₀!*f₁!*...*f₉!). We are basically eliminating all the permutations in which only identical digits are permuted.

We don't need to generate all the permutations to reach the k-th permutation. So we do this:

1.Calculate the number of distinct permutations which begin with the smallest digit d₀:

p=(n-1)!/((f₀-1)!*f₁!*...*f₉!)=nr*f₀/n

2.If p>n, then the permutation we're looking for begins with the digit d₀. We continue searching for the second digit, eliminating the digit d₀ from x, equivalent to decrementing f₀, in a recursive manner.

3.If p<n, then the permutation begins with a larger digit, and we go back to step 1, while keeping our results included into p.

4.If p=n, then we've used all the digits of x, and we've calculated the permutation.

You can also think about it using the factorial number system.

 

This works fine, except it's not fast enough for this problem. Or at least the  next step isn't, the step in which you turn the permutation into the required number.