Dearrange sorting solution codechef

Dearrange sorting solution codechef

You are given a permutation PP of length NN. A permutation of length NN is an array where every element from 11 to NN occurs exactly once.

You must perform some operations on the array to make it sorted in increasing order. In one operation, you must:

  • Select two indices LL and RR (1L<RN)(1≤L<R≤N)
  • Completely dearrange the subarray PL,PL+1,PRPL,PL+1,…PR

A dearrangement of an array AA is any permutation BB of AA for which BiAiBi≠Ai for all ii.

For example, consider the array A=[2,1,3,4]A=[2,1,3,4]. Some examples of dearrangements of AA are [1,2,4,3][1,2,4,3][3,2,4,1][3,2,4,1] and [4,3,2,1][4,3,2,1][3,5,2,1][3,5,2,1] is not a valid dearrangement since it is not a permutation of AA[1,2,3,4][1,2,3,4] is not a valid dearrangement either since B3=A3B3=A3 and B4=A4B4=A4.

Find the minimum number of operations required to sort the array in increasing order. It is guaranteed that the given permutation can be sorted in atmost 10001000 operations.

Input Format

Dearrange sorting solution codechef

  • The first line contains a single integer TT — the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer NN — the size of the permutation PP.
  • The second line of each test case contains NN space-separated integers P1,P2,,PNP1,P2,…,PN denoting the permutation PP.

Output Format

  • On the first line of each test case output the minimum number of operations MM. The description of the MM operations must follow.
  • Each operation must be described in two lines
    • On the first line of each operation output two space separated integers LL and RR (1L<RN)(1≤L<R≤N) — the indices of the subarray chosen.
    • On the second line output NN space separated integers — the permutation PP after dearranging the subarray PL,PL+1,PRPL,PL+1,…PRNote that you have to output the whole permutation {P1,P2,PN}{P1,P2,…PN}

Dearrange sorting solution codechef


  • 1T2001≤T≤200
  • 3N10003≤N≤1000
  • PP is a permutation of length NN
  • The sum of NN over all test cases does not exceed 10001000
  • It is guaranteed that the given permutations can be sorted in atmost 10001000 operations.

Sample Input 1 

1 2 3 4 5
2 1 3 5 4

Sample Output 1

Dearrange sorting solution codechef

1 2
1 2 3 5 4
4 5
1 2 3 4 5


Test case 11: No operations are required since the permutation is already sorted.

Test case 22: Initially, P=[2,1,3,5,4]P=[2,1,3,5,4]. Consider the following sequence of operations.

  • Choose L=1L=1 and R=2R=2 and dearrange the subarray in the following manner [2,1––––,3,5,4][1,2,3,5,4][2,1_,3,5,4]→[1,2,3,5,4]
  • Choose L=4L=4 and R=5R=5 and dearrange the subarray in the following manner [1,2,3,5,4––––][1,2,3,4,5][1,2,3,5,4_]→[1,2,3,4,5]

It can be shown that it is not possible to sort the given permutation in less than 22 operations.


Click Here

Leave a Comment

Your email address will not be published.