[Solution] Different Subarrays Rearrange solution codechef

by

Different Subarrays Rearrange solution codechef – You are given an array AA of NN integers A1,A2,…,ANA1,A2,…,AN. Determine if there are two permutations BB and CC of this array, for which the following condition is satisfied:

[Solution] Different Subarrays Rearrange solution codechef

  • There doesn’t exist a pair of integers (i,j)(i,j) such that 1≤i≤j≤N1≤i≤j≤N and (i,j)≠(1,N)(i,j)≠(1,N), for which the subarray B[i:j]B[i:j] is a permutation of subarray C[i:j]C[i:j].

If there exist such permutations, find any of them.

As a reminder, B[i:j]B[i:j] refers to the subarray [Bi,Bi+1,…,Bj][Bi,Bi+1,…,Bj]

Input Format

  • The first line of the input contains a single integer TT, the number of test cases. The description of the test cases follows.
  • The first line of each test case contains a single integer NN — the number of integers.
  • The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output Format

For each test case, if there are no such permutations BB and CC, output NO.

Otherwise, on the first line output YES. In the next line, output NN integers B1,B2,…,BNB1,B2,…,BN. In the next line, output NN integers C1,C2,…,CNC1,C2,…,CN.

You may print each character of YES/NO in either uppercase or lowercase (for example, the strings YES, yeS, YeS, and yEs will all be treated as identical).

[Solution] Different Subarrays Rearrange solution codechef

  • 1≤T≤1001≤T≤100
  • 3≤N≤10003≤N≤1000
  • 0≤Ai≤1090≤Ai≤109
  • The sum of NN over all test cases doesn’t exceed 20002000.

Sample Input 1 

3
3
1 1 2
4
19 39 19 84
6
1 2 3 1 2 3

Sample Output 1 

NO
YES
19 19 39 84 
39 84 19 19 
YES
1 1 2 2 3 3 
2 3 3 1 1 2

Different Subarrays Rearrange solution Explanation

Test case 11: There are 3×3=93×3=9 pairs of permutations of the given array. Here’s why they’re all bad:

  • If B=[1,1,2]B=[1,1,2] and C=[1,1,2]C=[1,1,2], B[1:1]=C[1:1]B[1:1]=C[1:1]
  • If B=[1,1,2]B=[1,1,2] and C=[1,2,1]C=[1,2,1], B[1:1]=C[1:1]B[1:1]=C[1:1]
  • If B=[1,1,2]B=[1,1,2] and C=[2,1,1]C=[2,1,1], B[2:2]=C[2:2]B[2:2]=C[2:2]
  • If B=[1,2,1]B=[1,2,1] and C=[1,1,2]C=[1,1,2], B[1:1]=C[1:1]B[1:1]=C[1:1]
  • If B=[1,2,1]B=[1,2,1] and C=[1,2,1]C=[1,2,1], B[1:1]=C[1:1]B[1:1]=C[1:1]
  • If B=[1,2,1]B=[1,2,1] and C=[2,1,1]C=[2,1,1], B[3:3]=C[3:3]B[3:3]=C[3:3]
  • If B=[2,1,1]B=[2,1,1] and C=[1,1,2]C=[1,1,2], B[2:2]=C[2:2]B[2:2]=C[2:2]
  • If B=[2,1,1]B=[2,1,1] and C=[1,2,1]C=[1,2,1], B[3:3]=C[3:3]B[3:3]=C[3:3]
  • If B=[2,1,1]B=[2,1,1] and C=[2,1,1]C=[2,1,1], B[1:1]=C[1:1]

For Solution

“Click here“

Leave a Comment