Reputation: 205
I am not able to get the logic behind the solution to the problem . I will be very thankful if someone can explain me the working of it.
Solution:
#include <bits/stdc++.h>
using namespace std;
const int N=1509;
int n;
int a[N];
void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
}
void sol(){
int K=1;
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
K^=(a[i]>a[j]);
if (K) printf("YES\n");
else printf("NO\n");
}
int main() {
int test;
scanf("%d",&test);
while (test--){
input();
sol();
}
return 0;
}
I am not able to get how after xoring each permutation, value of 'k' in the end is determining the answer(ie whether it can be arranged in sorting order) ?
Upvotes: 1
Views: 190
Reputation: 11968
When you rotate a block you change the number of inversions by +/- 2 or 0 (work it out on paper, if you don't trust me). So if the number of inversions in the array is odd you will not be able make it sorted with the given operation. You'll end up with the array almost sorted with all but 2 elements in place (1 inversion) and you can't fix that with the given operation.
What the code does is check if the number of inversions is odd by xoring with itself every time it sees an inversion. You can get the same result if you count the inversions up and check inversions % 2 == 0
.
Upvotes: 2