Minimum Good Permutation
The questions states that we have to print the lexicographically smallest good permutation p.
A permutation p is of length n and is made up of numbers from 1 to n.
To keep the permutation smallest , we should print the smallest numbers first. But in the most basic case of arranging the numbers in ascending order , is not possible according to the definition of “good permutation” .
One simple greedy approach that comes to our mind is why not we make an ascending order sequence and swap each successive pair of elements where no two pairs overlap .
For ex if n=4
Initial sequence 1 2 3 4 <–invalid
After swapping (i) 1 and 2 and (ii) 3 and 4
Final sequence 2 1 4 3
So we have found out the greedy approach for this problem .
But there may be two cases of n :
(1) n is even
(2) n is odd
If n is even we don’t have to do anything extra
We go from i=1 i<=n incrementing i by 2 at each step and print out the (i+1)th number first follwed by the (i)th number.
If n is odd one thing we observe is that the (n-2)th number comes at the end . Before it comes the (n)th number and before this comes the (n-1)th number .
Here we do the same thing until i==n-2 . At this point we print the (i+1)th number i.e (n-1)th number and break from the loop. Then outside the loop we print out the (n)th and the (n-2)th number .
And this becomes our solution to the problem.
Although yhis thing could have been done after storing all the numbers in the array but it wil be wastage of both memory and time and the base on which competitve stands is the efficiency .
Link to my solution : Solution: 15226639 | CodeChef