# Shift and Sort the Sequence [closed]

Given a permutation of integers 1 through N, we need to determine whether it is possible to sort this list in an increasing order by following certain conditions.

The conditions imposed are :
We are allowed to perform the following type of operation upto K times :

• Choose three pairwise distinct indices i1, i2, i3 in any order. Note that these indices need not necessarily be chosen in increasing order.
• Perform a cyclic right shift on the elements at these indices i. e.
if we denote the values of pi1, pi2 and pi3 before this operation by v1, v2 and v3 respectively, we should change pi2 to v1, pi3 to v2 and pi1 to v3

For example, the permutation (1,4,3,2,5) can be changed to the permutation (1,5,3,4,2) in one operation by choosing i1 = 2, i2 = 4 and i3 = 5

If it is possible to sort the given permutation we should also display the number of operations along with the indices i1, i2, i3 at which the operation is performed

For example
N = 4
K = 2
Sequence : 3 2 4 1

Output
No. of operations performed = 1
Sequence of indices for each operation:
1 3 4

Explanation
We can sort the permutation by performing one cyclic right shift operation on the indices 1, 3 and 4

• This looks like a problem from a programming competition. Do you have the source? May 5, 2020 at 11:39
• Since this is part of an ongoing competition, the question has been locked.
– Deusovi
May 12, 2020 at 22:30

2. Fully $$\frac{1}{2}$$ of the possible input have no solution.
3. The longest optimal solution for $$N$$ integers is of length $$\big\lfloor{\frac{N}{2}}\big\rfloor$$.
4. The bit about a cyclic right shift is deceptive. You can do both directions just by swapping $$i_2$$ and $$i_3$$.