An easier memory efficient approach for MINPERM for beginners

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 : CodeChef: Practical coding for everyone

another simple approach to this question need brute force and some manipulation of output in the end. MY SOLUTION :
https://www.codechef.com/viewsolution/15192514

Great !

You are doing the same thing but the thing I did here is to do it without using any array for storage.