[Solution] Dearrange sorting CodeChef Solution | CodeChef Problem Solution 2022

[Solution] Dearrange sorting Solution CodeChef Solution | CodeChef Problem Solution 2022

You are given a permutation P$P$ of length N$N$. A permutation of length N$N$ is an array where every element from 1$1$ to N$N$ 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 L$L$ and R$R$ (1≤L<R≤N)$(1\le L<R\le N)$
• Completely dearrange the subarray PL,PL+1,…PR$P_L,P_{L+1},\dots P_R$

A dearrangement of an array A$A$ is any permutation B$B$ of A$A$ for 

Solution Click Below:-  CLICK HERE

which Bi≠Ai$B_i\ne A_i$ for all i$i$.

For example, consider the array A=[2,1,3,4]$A=[2,1,3,4]$. Some examples of dearrangements of A$A$ 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 A$A$. [1,2,3,4]$[1,2,3,4]$ is not a valid dearrangement either since B3=A3$B_3=A_3$ and B4=A4$B_4=A_4$.

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

Input Format

• The first line contains a single integer T$T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ — the size of the permutation P$P$.

Chef and Brain Speed CodeChef Solution

Chef and Chocolates CodeChef Solution

Determine the Winner CodeChef Solution

Is this priority or parity!  CodeChef Solution

Path Parity CodeChef Solution

Dearrange sorting CodeChef Solution 

Equal Integers CodeChef Solution

Remove and Add CodeChef Solution

• The second line of each test case contains N$N$ space-separated integers P1,P2,…,PN$P_1,P_2,\dots ,P_N$ denoting the permutation P$P$.

Output Format

• On the first line of each test case output the minimum number of operations M$M$. The description of the M$M$ operations must follow.
• Each operation must be described in two lines
  • On the first line of each operation output two space separated integers L$L$ and R$R$ (1≤L<R≤N)$(1\le L<R\le N)$ — the indices of the subarray chosen.
  • On the second line output N$N$ space separated integers — the permutation P$P$ after dearranging the subarray PL,PL+1,…PR$P_L,P_{L+1},\dots P_R$. Note that you have to output the whole permutation {P1,P2,…PN}$\{P_1,P_2,\dots P_N\}$

Constraints

• 1≤T≤200$1\le T\le 200$
• 3≤N≤1000$3\le N\le 1000$
• P$P$ is a permutation of length N$N$
• The sum of N$N$ over all test cases does not exceed 1000$1000$
• It is guaranteed that the given permutations can be sorted in atmost 1000$1000$ operations.