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
N = 4
K = 2
Sequence : 3 2 4 1
No. of operations performed = 1
Sequence of indices for each operation:
1 3 4
We can sort the permutation by performing one cyclic right shift operation on the indices 1, 3 and 4