Larry's Array

locked

by nikasvanidze

• Problem
• Submissions
• Leaderboard
• Discussions
• Editorial

Larry has a permutation of N$N$ numbers, A$A$, whose unique elements range from 1$1$ to N$N$ (i.e.: A={a1,a2,…,aN−1,aN}$A=\{a_1,a_2,\dots ,a_{N-1},a_N\}$). He wants A$A$ to be sorted, so he delegates the task of doing so to his robot. The robot can perform the following operation as many times as it wants:

• Choose any 3$3$ consecutive indices and rotate their elements in such a way that ABC$ABC$rotates to BCA$BCA$, which rotates to CAB$CAB$, which rotates back to ABC$ABC$.

For example: if A={1,6,5,2,4,3}$A=\{1,6,5,2,4,3\}$ and the robot rotates (6,5,2)$(6,5,2)$, A$A$ becomes {1,5, 2, 6,4,3}$\{1,\mathbf{\text{5, 2, 6}},4,3\}$.

On a new line for each test case, print YES$\mathtt{\text{YES}}$ if the robot can fully sort A$A$; otherwise, print NO$\mathtt{\text{NO}}$.

Input Format

The first line contains an integer, T$T$, the number of test cases. 
The 2T$2T$ subsequent lines each describe a test case over 2$2$ lines:

1. An integer, N$N$, denoting the size of A$A$.
2. N$N$ space-separated integers describing A$A$, where the ith$i^{th}$ value describes element ai$a_i$.

Constraints

• 1≤T≤10$1\le T\le 10$
• 3≤N≤1000$3\le N\le 1000$
• 1≤ai≤N, where every element ai is unique.$1\le a_i\le N\text{, where every element }{a}_i\text{ is unique.}$

Output Format

On a new line for each test case, print YES$\mathtt{\text{YES}}$ if the robot can fully sort A$A$; otherwise, print NO$\mathtt{\text{NO}}$.

Sample Input

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

Sample Output

YES
YES
NO

Let's call inversion in sequence A$A$ (size of N$N$) number of pairs(x,y)$(x,y)$,
where 1≤x<y≤N$1\le x<y\le N$ and Ax>Ay$A_x>A_y$.


Let's prove that parity of inversions will not change:
A,B,C$A,B,C$ -> B,C,A$B,C,A$.
Order of A,C$A,C$ changed thats ±1$\pm 1$.
Order of A,B$A,B$ changed thats ±1$\pm 1$.
So change is −2$-2$ or 0$0$ or 2$2$.

Prove that we can always get permutation:
[1,2,3,...,n−2,n−1,n]$[1,2,3,...,n-2,n-1,n]$ or [1,2,3,...,n−2,n,n−1]$[1,2,3,...,n-2,n,n-1]$. (n$n$ and n−1$n-1$ are swapped). using out operation we are moving B$B$ and C$C$ left by one, in this way we can move 1$1$ in first place, then move 2$2$ to second place and so on including n−2$n-2$.
So, number of inversions will be 0([1,2,3,...,n−2,n−1,n])$0([1,2,3,...,n-2,n-1,n])$ or 1([1,2,3,...,n−2,n,n−1])$1([1,2,3,...,n-2,n,n-1])$.
If it is 1$1$ then it's impossible to sort, and if it's 0 that means it's sorted.


Calculate parity using any BST, solution will be O(T∗Nlog2N)$O(T\ast Nlo{g}_{2}N)$.

In this problem you can calculate answer by compairing each pair. O(T∗N2)













#include<bits/stdc++.h>

using namespace std;

int a[1010];

int main()

{

    int n;

    int t;

    cin>>t;

    while(t--)

    {

        

         cin>>n;

         for(int i=1;i<=n;i++)

         cin>>a[i];

         int in=0;

         for(int i=1;i<=n;i++)

         {

            for(int j=i+1;j<=n;j++)

      {

           if(a[j]<a[i])

        in++; 

      } 

   }

   if(in&1)

   cout<<"NO"<<endl;

   else cout<<"YES"<<endl;

    }

    return 0;



}