5
$\begingroup$

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

| |
$\endgroup$
  • 1
    $\begingroup$ This looks like a problem from a programming competition. Do you have the source? $\endgroup$ – Dmitry Kamenetsky May 5 at 11:39
  • $\begingroup$ Since this is part of an ongoing competition, the question has been locked. $\endgroup$ – Deusovi May 12 at 22:30
1
$\begingroup$
  1. I agree with Dmitry Kamenetsky that this looks like a programming competition, so I won't at this time give algorithms, just results.

  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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ A basic sketch of an algorithm would be appreciated. $\endgroup$ – Jason Todd May 5 at 13:34
  • 1
    $\begingroup$ Specifically, right-shifting triplets is an even permutation, so only even permutations can be sorted. $\endgroup$ – AxiomaticSystem May 5 at 14:29
  • 3
    $\begingroup$ @JasonTodd But you need to tell us where this came from. We don't help in active competitions. That's the rule here. $\endgroup$ – David G. May 5 at 17:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.