Problem link : Order Of Pheonix
Author : Ritesh Gupta
Tester : Romit Kumar
Editorialist : Abhishek Kumar
Pre-Requisite : Mahonian Numbers, Range update, Prefix sum
Problem : You are given an integer n. For every k [0<=k<=(n*(n-1)/2)+1] , you need to print the inversion count of permutation of numbers 1-n.
Explanation : First, let’s suppose we know the answer for a value ‘n’. To find the answer for ‘n+1’:
- For a given value ‘n’ the total number of distinct inversion count will be (n*(n-1)/2 +1) . For (n+1), it would be ((n+1)*n/2) +1 (Which is ‘n’ greater than the inversion count for n). Thus we create an array of length (((n+1)*n/2) +1) +1 and initialize all the elements with 0.
- Now for every i_{th} element in our known answer for n elements, we perform a update in the new array made for (n+1) elements. That is, for every a_i in the answer of ‘n’ , we add a_i at the i_{th} position of the new array, and -a_i at (i+n)_{th}.
- After performing update in the new array for every a_i in the old array, we apply a prefix sum on the new array, which gives us the answer.
Let us see by example why this algorithm works
Let us take n=3, Our numbers are {1,2,3}
All the permutation of these three numbers and their respective inversion counts are :
(1) 1 2 3 : 0
(2) 1 3 2 : 1
(3) 2 1 3 : 1
(4) 2 3 1 : 2
(5) 3 1 2 : 2
(6) 3 2 1 : 3
We know the answer for 3, now we will see how to find the solution for n=4 from the known answer.
Let us take the 1st permutation from above and introduce 4 into it and find the inversion count. We can do that in 4 positions.
4 1 2 3 : 3(due to 4) + 0(previous count) = 3
1 4 2 3 : 2(due to 4) + 0(previous count) = 2
1 2 4 3 : 1(due to 4) + 0(previous count) = 1
1 2 3 4 : 0(due to 4) + 0(previous count) = 0
4 1 3 2 : 3(due to 4) + 1(previous count) = 4
1 4 3 2 : 2(due to 4) + 1(previous count) = 3
1 3 4 2 : 1(due to 4) + 1(previous count) = 2
1 3 2 4 : 0(due to 4) + 1(previous count) = 1
Similarly for 6 such permutation , there will be 24(6 * 4) such new permutation after introducing ‘4’. By finding each of these permutation as shown above, we can notice that the value of inversion count changes linearly for each 4(value of n) new permutation. Thus from here we can infer the idea of range update from 1 to n for each a_i in the answer for previous value of n.
The complexity for this solution will be O(n*k) .