[Trees][Binary Lifting] 501 - D Misha And Permutations

Misha and Permutations

Problem statement:

The problem can be found here. The gist of the problem is:

You're given two permutations of $n$. Their order might be $a$, and $b$. By "order" I mean, the index of the permutation. That is, for $n=3$, $0,1,2$ is the first permutation, whereas, $2,1,0$ is the last (=6th). 

So, we have to find $(a+b)%(n!)$th permutation. 

This is it. Simple. Isn't is? 

No. Nope. Nada. Wtf is this question man?

Okay, rants apart.

Ideas:

The major point here is the conversion of order, and the permutation. We convert the initial permutations into the order. Add them. Mod by n!, and then find the resulting permutation.

There are many problems with this approach. You'll have to find ways to interconvert order and permutation, plus the mod by n!. Since $1 \leq n \leq 200000$, thus $n!$ can be a very large number. You don't want to solve, this way.

Enter the [Factorial Number System](https://en.wikipedia.org/wiki/Factorial_number_system).

As the name suggests, it's the factorial number system. Instead of bases, you have factorials! An example would be:

$$ 4\times 4! + 3\times 3!+2\times 2!+1\times 1!+0\times 0!$$.

This number in factorial representation (or factoradic) can be written as $43210_{!}$, which in decimal representation can be written as $119_{10}$. 

A good property is that, we can represent permutations using factoradics. This way, we can ignore the decimal representation altogether. But you'll say what about the n! mod? We'll come back to that later. I promise.

Pemutation to factoradic conversions:

Given a permuation $3,0,2,1$. It's factoradic representation is not simply $4132_{!}$. We have to put some mind to it. 

We have $n=4$. So we have $A\times 3! + B\times 2! + C\times 1! + D\times 0!$. We have to find the values of $A,B,C$ and $D$. 

A = We can simply do that by finding number of elements smaller than 3. That is 3. 

Now we remove 3 from consideration, and have $\{0,1,2\}$. 

B = Number of elements smaller than 0? None. So 0. Remove 0. We're left with $\{1,2\}$.

C = Number of elements smaller than 2? 1. So 1. We have $\{1\}$ left.

D = 0

So, we have $3010_{!}$, representing $3,0,2,1$. To double check, you can find the decimal value, which comes out to be: $3\times 3!+0\times 2!+1\times 1!+ 0 \times 0! = 18+0+1+0 = 19$

As you can see here, 3021, is indeed the 19th permutation for n=4. 

The basic inference you can get from here is that factoradic representation gives the rank of the number, for the remaining numbers. 

This can be done by fenwick trees / Binary indexed trees, easily.

Modulus n!: 

Thanks to Ecenerwala's solution.

So, until now, we have converted the permutations into their factoradic representations, and added them. How do we do the mod n!?

A factoradic representation is of the form (for n):

$$X_{(n-1)!}\times (n-1)!+X_{(n-2)!}\times(n-2)!+...+X_{2!}\times 2!+X_{1!}\times 1!$$.

Thus if $X_{(i-1)!}>=i$, then it can be written in the form: $X_{(i-1)!} = i+(X_{(i-1)!}-i)$. Thus, the term $$X_{(i-1)!}\times (i-1)! = i \times (i-1)! + (X_{(i-1)!}-i\times (i-1)!) \\= i!+(X_{(i-1)!}-i\times (i-1)!$$

This extra $i!$ can be added to the next greater element. So, if we percolate up to $(n-1)$, then we might get an extra $n!$ element. That's it!

Isn't that what we want? We know that there can be at most one n! extra. You can check that. (Kuchh to krlo khud se)

Code for that:

Good. Beautiful.

Factoradic to permutation conversion:

So, as I mentioned earlier, factoradic-> Rank (well actually, number of elements smaller). So you have ranks, and  you want the permutation now. Consider $3010_{!}$ again. You want the (3+1)th element, amongst $0,1,2,3$ = 3. Remove 3. $\{0,1,2\}$ left. You want the (0+1)st element. You get 0. Remaining $\{1,2\}$. You want the (1+1)nd element. You get 2. Remaining $\{1\}$. You want the (0+1)st element. You get 1. So $3,0,2,1$ formed.

This can be done by binary searching on he fenwick tree, or doing binary lifting on it. 

My submission can be found here.