I am trying to solve spoj problem “Minimum Permutation” ,but i am not able to get any logic to solve this.If someone can give any approach or logic for this problem it will be a great help. Thanks.
problem link: http://www.spoj.com/problems/MMINPER/
Ok. So logic behind this problem. Implementation itself can be tricky and you should overthink it before programming, but the main idea is pretty simple.
First thing. If you have n numbers (from 1 to n) what it’s maximal possible number of inversions? Like is said in statement it’s n(n-1)/2 (common formula for sum of first n-1 numbers) - permutation (n, n-1, n-2 … 1). And also notice, that you can create permutation with arbitrary numbers of inversions between 0 and n(n-1)/2.
Second, what it’s maximal number of inversions if we have n numbers and number k must be first in our permutation? Well number k create k-1 inversions with numbers 1 to k-1 and from rest of numbers we can create (n-1)(n-2)/2 inversions so totaly it’s k-1 + (n-1)(n-2)/2 inversions.
Last thing. If we want to the smallest permutation we want to prefer smaller numbers on beginning. So when we can create correct permutation (with right numbers of inversions) starting with 1 and also with 2 we use that with 1 at beginning.
Now you just add these knowledge together. Just start picking numbers for first position. It’s possible to create correct permutation with number 1 at beginning? This is possible only if (n-1)(n-2)/2 >= m. So if this conditions is met, than you should use 1 as first element. Else try next number - 2. Again, if condition 1 + (n-1)(n-2)/2 is met, use number 2. And so on. For number k condition k-1 + (n-1)(n-2)/2 must be fulfill.
When you pick first number, you have n-1 numbers left and you create k-1 inversions if first number is k. So you have the same problem but smaller - only have n-1 numbers and looking for m-k+1 inversions. Nevermind, that you have different set of numbers, there can be converted to numbers 1 to n-1 without changing relative positions.
And that’s it. Again I highlight, that this is only main idea, in implementation you must face problems with converting numbers (not necessary) and fast picking of first element (binary search will work). But I believe, there is a nice solution, but you must think about it for a while 
1 Like
Thanx a lot.I will work on this.