[Solution] Triple Inversions solution codechef

Triple Inversions solution codechef – For a permutation PP of the integers 11 to NN, we define a new array APAP of length N2N−2 as follows:

[Solution] Triple Inversions solution codechef

  • For 1iN21≤i≤N−2(AP)i(AP)i denotes the number of inversions in the subarray P[i:i+2]P[i:i+2], i.e, the number of inversions in the array [Pi,Pi+1,Pi+2][Pi,Pi+1,Pi+2].

You are given an array AA of length NN, all of whose elements lie between 00 and 33. Does there exist a permutation PP of length N+2N+2 such that AP=AAP=A?

Input Format

  • The first line of input will contain one integer TT, the number of test cases. The description of TT test cases follows.
  • Each test case consists of two lines of input.
  • The first line of each test case contains a single integer NN, the size of AA.
  • The second line of each test case contains NN space-separated integers — the values of A1,A2,,ANA1,A2,…,AN.

[Solution] Triple Inversions solution codechef

For each test case, output in a single line the answer — 𝚈𝙴𝚂YES if a permutation that satisfies the given conditions exists, and 𝙽𝙾NO otherwise.

The output is not case sensitive, so for example the strings 𝚈𝙴𝚂, 𝚈𝚎𝚜, 𝚢𝙴𝚂YES, Yes, yES, etc. will all be treated as correct.

Constraints

  • 1T1051≤T≤105
  • 1N1051≤N≤105
  • 0Ai30≤Ai≤3
  • The sum of NN over all test cases doesn’t exceed 105105

Sample Input 1 

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

Sample Output 1 

YES
NO
YES
NO

Triple Inversions solution Explanation

Test case 11: Consider P=[1,2,6,5,3,4]P=[1,2,6,5,3,4]. It can be verified that AP=[0,1,3,2]AP=[0,1,3,2]. There are other permutations which give the same array — for example [2,3,6,5,1,4][2,3,6,5,1,4] and [3,4,6,5,1,2][3,4,6,5,1,2].

Test case 22: It can be verified that no permutation PP of length 66 has AP=[0,1,2,3]AP=[0,1,2,3].

Test case 33: The only permutation that satisfies the condition is P=[1,2,3,4,5,6]P=[1,2,3,4,5,6].

Test case 44: It can be verified that no permutation PP of length 77 has AP=[0,1,2,1,0]

For Solution

Click here

Leave a Comment