Triple Inversions solution codechef – For a permutation PP of the integers 11 to NN, we define a new array APAP of length N−2N−2 as follows:
[Solution] Triple Inversions solution codechef
- For 1≤i≤N−21≤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
- 1≤T≤1051≤T≤105
- 1≤N≤1051≤N≤105
- 0≤Ai≤30≤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]