Yet Another Sorting Problem (Codeforces 1591D)
Tags: Math, sortings

Petya has an array of integers $$$a_1, a_2, \ldots, a_n$$$. He only likes sorted arrays. Unfortunately, the given array could be arbitrary, so Petya wants to sort it.Petya likes to challenge himself, so he wants to sort array using only $$$3$$$-cycles. More formally, in one operation he can pick $$$3$$$ pairwise distinct indices $$$i$$$, $$$j$$$, and $$$k$$$ ($$$1 \leq i, j, k \leq n$$$) and apply $$$i \to j \to k \to i$$$ cycle to the array $$$a$$$. It simultaneously places $$$a_i$$$ on position $$$j$$$, $$$a_j$$$ on position $$$k$$$, and $$$a_k$$$ on position $$$i$$$, without changing any other element.For example, if $$$a$$$ is $$$[10, 50, 20, 30, 40, 60]$$$ and he chooses $$$i = 2$$$, $$$j = 1$$$, $$$k = 5$$$, then the array becomes $$$[\underline{50}, \underline{40}, 20, 30, \underline{10}, 60]$$$.Petya can apply arbitrary number of $$$3$$$-cycles (possibly, zero). You are to determine if Petya can sort his array $$$a$$$, i. e. make it non-decreasing.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^5$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output: For each test case, print "YES" (without quotes) if Petya can sort the array $$$a$$$ using $$$3$$$-cycles, and "NO" (without quotes) otherwise. You can print each letter in any case (upper or lower).

Note: In the $$$6$$$-th test case Petya can use the $$$3$$$-cycle $$$1 \to 3 \to 2 \to 1$$$ to sort the array.In the $$$7$$$-th test case Petya can apply $$$1 \to 3 \to 2 \to 1$$$ and make $$$a = [1, 4, 2, 3]$$$. Then he can apply $$$2 \to 4 \to 3 \to 2$$$ and finally sort the array.

Sample Inputs:
7
1
1
2
2 2
2
2 1
3
1 2 3
3
2 1 3
3
3 1 2
4
2 1 4 3

Sample Outputs:
YES
YES
NO
YES
NO
YES
YES

Solution (Python):
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math, random
Z = stdin.readline

def inp(force_list=False):
    re = list(map(int, Z().split()))
    if len(re) == 1 and (not force_list):
        return re[0]
    return re

def inst():
    return Z().strip()

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x
mod = 1000000007

class RMQ(object):

    def __init__(self, da, func):
        self.func = func
        n = len(da)
        sp = [[0 for i in range(25)] for i in range(n)]
        for i in range(n):
            sp[i][0] = da[i]
        for i in range(1, 25):
            for j in range(n):
                if j + (1 << i) >= n:
                    break
                sp[j][i] = func(sp[j][i - 1], sp[j + (1 << i)][i - 1])
        self.sp = sp
        self.log = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log[i] = self.log[i // 2] + 1
        print(self.log)

    def query(self, l, r):
        j = self.log[r - l + 1]
        return self.func(self.sp[l][j], self.sp[r - (1 << j)][j])

def my_main():
    kase = inp()
    pans = []
    for _ in range(kase):
        n = inp()
        da = inp(True)
        if len(set(da)) != len(da):
            pans.append('YES')
            continue
        cycle = 0
        vi = [0] * n
        for i in range(n):
            if vi[i]:
                continue
            vi[i] = 1
            i = da[i] - 1
            while vi[i] == 0:
                vi[i] = 1
                i = da[i] - 1
                cycle += 1
        pans.append('YES' if cycle % 2 == 0 else 'NO')
    print('\n'.join(pans))
my_main()

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if len(set(a)) < n:
        print('YES')
        continue
    swaps = 0
    for i in range(n):
        while a[i] != i + 1:
            (j, k) = (i, a[i] - 1)
            (a[j], a[k]) = (a[k], a[j])
            swaps += 1
    if swaps % 2 == 0:
        print('YES')
    else:
        print('NO')

Solution (Python):
for _ in range(int(input())):
    (n, a) = (int(input()), list(map(int, input().split())))
    if len(set(a)) < n:
        print('YES')
        continue
    sorted_a = sorted(a)
    num2i = {num: i for (i, num) in enumerate(sorted_a)}
    vis = [0] * n
    ans = 0
    for i in range(n):
        if vis[i]:
            continue
        (size, cur) = (0, i)
        while not vis[cur]:
            vis[cur] = 1
            (size, cur) = (size + 1, num2i[a[cur]])
        ans += size % 2 == 0
    print('YES') if ans == 0 or ans % 2 == 0 else print('NO')