Cyclic Shifts Sorting (Codeforces 1374F)
Tags: Implement, sortings

You are given an array $$$a$$$ consisting of $$$n$$$ integers.In one move, you can choose some index $$$i$$$ ($$$1 \le i \le n - 2$$$) and shift the segment $$$[a_i, a_{i + 1}, a_{i + 2}]$$$ cyclically to the right (i.e. replace the segment $$$[a_i, a_{i + 1}, a_{i + 2}]$$$ with $$$[a_{i + 2}, a_i, a_{i + 1}]$$$). Your task is to sort the initial array by no more than $$$n^2$$$ such operations or say that it is impossible to do that.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains one integer $$$n$$$ ($$$3 \le n \le 500$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 500$$$), where $$$a_i$$$ is the $$$i$$$-th element $$$a$$$.It is guaranteed that the sum of $$$n$$$ does not exceed $$$500$$$.

Output: For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations $$$ans$$$ on the first line and $$$ans$$$ integers $$$idx_1, idx_2, \dots, idx_{ans}$$$ ($$$1 \le idx_i \le n - 2$$$), where $$$idx_i$$$ is the index of left border of the segment for the $$$i$$$-th operation. You should print indices in order of performing operations.


Sample Inputs:
5
5
1 2 3 4 5
5
5 4 3 2 1
8
8 4 5 2 3 6 7 3
7
5 2 1 6 4 7 3
6
1 2 3 3 6 4

Sample Outputs:
0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4

Solution (Python):
import sys

def rotate(s, i, ans):
    (s[i], s[i + 1], s[i + 2]) = (s[i + 2], s[i], s[i + 1])
    ans.append(str(i + 1))
    return (s, ans)
t = int(input())
while t:
    ans = []
    n = int(input())
    s = list(map(int, sys.stdin.readline().split()))
    ss = s.copy()
    ss.sort()
    l = len(ss)
    if l == 3:
        t -= 1
        i = 0
        while True:
            if s == ss:
                print(len(ans))
                print(' '.join(ans))
                break
            (s, ans) = rotate(s, i, ans)
            if len(ans) == 3:
                print(-1)
                break
        continue
    j = 0
    c = 0
    while j < l:
        k = ss[j]
        i = j + s[j:].index(k)
        while i - 2 >= j:
            i = i - 2
            (s, ans) = rotate(s, i, ans)
        if i != j:
            if j + 2 == l:
                if s[j] == s[j + 1]:
                    break
                elif s[j - 1] == s[j + 1] and j != 0:
                    ans.append(str(j))
                    break
                elif l > len(set(ss)):
                    for i in range(-2, -l - 1, -1):
                        if s[i] == s[i + 1]:
                            break
                    if -i % 2 == 1:
                        k = -3
                        while k >= i:
                            ans.append(str(l + k + 1))
                            k -= 2
                        ans.append(str(l + i + 1))
                        k = 1
                        while i + k < -2:
                            ans.append(str(l + i + k + 1))
                            ans.append(str(l + i + k + 1))
                            k += 2
                    else:
                        k = -3
                        while k >= i + 1:
                            ans.append(str(l + k + 1))
                            k -= 2
                        ans.append(str(l + i + 1))
                        k = 2
                        while i + k < -2:
                            ans.append(str(l + i + k + 1))
                            ans.append(str(l + i + k + 1))
                            k += 2
                    break
                else:
                    c = 1
                    print(-1)
                    break
            (s, ans) = rotate(s, j, ans)
            (s, ans) = rotate(s, j, ans)
            i -= 1
        j += 1
    if c == 0:
        print(len(ans))
        print(' '.join(ans))
    t -= 1

Solution (Python):
import sys

def rotate(s, i, ans):
    (s[i], s[i + 1], s[i + 2]) = (s[i + 2], s[i], s[i + 1])
    ans.append(str(i + 1))
    return (s, ans)
t = int(input())
while t:
    ans = []
    n = int(input())
    s = list(map(int, sys.stdin.readline().split()))
    ss = s.copy()
    ss.sort()
    if len(s) == 3:
        t -= 1
        i = 0
        while True:
            if s == ss:
                print(len(ans))
                print(' '.join(ans))
                break
            (s, ans) = rotate(s, i, ans)
            if len(ans) == 3:
                print(-1)
                break
        continue
    j = 0
    c = 0
    l = len(ss)
    while j < l:
        k = ss[j]
        i = j + s[j:].index(k)
        while i - 2 >= j:
            i = i - 2
            (s, ans) = rotate(s, i, ans)
        if i != j:
            if j + 2 == l:
                if s[j] == s[j + 1]:
                    break
                elif s[j - 1] == s[j + 1] and j != 0:
                    ans.append(str(j))
                    break
                elif len(ss) > len(set(ss)):
                    for i in range(-2, -len(ss) - 1, -1):
                        if s[i] == s[i + 1]:
                            break
                    if -i % 2 == 1:
                        k = -3
                        while k >= i:
                            ans.append(str(l + k + 1))
                            k -= 2
                        ans.append(str(l + i + 1))
                        k = 1
                        while i + k < -2:
                            ans.append(str(l + i + k + 1))
                            ans.append(str(l + i + k + 1))
                            k += 2
                    else:
                        k = -3
                        while k >= i + 1:
                            ans.append(str(l + k + 1))
                            k -= 2
                        ans.append(str(l + i + 1))
                        k = 2
                        while i + k < -2:
                            ans.append(str(l + i + k + 1))
                            ans.append(str(l + i + k + 1))
                            k += 2
                    break
                else:
                    c = 1
                    print(-1)
                    break
            (s, ans) = rotate(s, j, ans)
            (s, ans) = rotate(s, j, ans)
            i -= 1
        j += 1
    if c == 0:
        print(len(ans))
        print(' '.join(ans))
    t -= 1

Solution (Python):
for _ in range(int(input())):
    (n, l, out) = (int(input()), list(map(lambda x: int(x) - 1, input().split())), [])
    ll = sorted([(l[i], i) for i in range(n)])
    swap = (-1, -1)
    newl = [0] * n
    for i in range(n - 1):
        if ll[i][0] == ll[i + 1][0]:
            swap = (ll[i][1], ll[i + 1][1])
    for i in range(n):
        newl[ll[i][1]] = i
    (l, swapN) = (newl, 0)
    (works, done) = (True, False)
    for i in range(n):
        for j in range(i + 1, n):
            if l[i] > l[j]:
                swapN += 1
    if swapN & 1:
        (l[swap[0]], l[swap[1]]) = (l[swap[1]], l[swap[0]])

    def shift(i):
        out.append(i + 1)
        (l[i], l[i + 1], l[i + 2]) = (l[i + 2], l[i], l[i + 1])
    while not done:
        for i in range(n):
            if l[i] != i:
                break
        else:
            done = True
        if done:
            break
        for find in range(i + 1, n):
            if l[find] == i:
                break
        while find - i >= 2:
            find -= 2
            shift(find)
        if find - i == 1:
            if find <= n - 2:
                shift(find - 1)
                shift(find - 1)
            else:
                works = False
                break
    if works:
        print(len(out))
        print(' '.join(map(str, out)))
    else:
        print(-1)