King's Task (Codeforces 1510K)
Tags: Implement, graphs

The brave Knight came to the King and asked permission to marry the princess. The King knew that the Knight was brave, but he also wanted to know if he was smart enough. So he asked him to solve the following task.There is a permutation $$$p_i$$$ of numbers from 1 to $$$2n$$$. You can make two types of operations.   Swap $$$p_1$$$ and $$$p_2$$$, $$$p_3$$$ and $$$p_4$$$, ..., $$$p_{2n-1}$$$ and $$$p_{2n}$$$.  Swap $$$p_1$$$ and $$$p_{n+1}$$$, $$$p_2$$$ and $$$p_{n+2}$$$, ..., $$$p_{n}$$$ and $$$p_{2n}$$$. The task is to find the minimal number of operations required to sort the given permutation.The Knight was not that smart actually, but quite charming, so the princess asks you to help him to solve the King's task.

Input: The first line contains the integer $$$n$$$ ($$$1\le n\le 1000$$$). The second line contains $$$2n$$$ integers $$$p_i$$$ — the permutation of numbers from 1 to $$$2n$$$.

Output: Print one integer — the minimal number of operations required to sort the permutation. If it is impossible to sort the permutation using these operations, print $$$-1$$$.

Note: In the first example, you can sort the permutation in three operations:   Make operation 1: $$$3, 6, 5, 2, 1, 4$$$.  Make operation 2: $$$2, 1, 4, 3, 6, 5$$$.  Make operation 1: $$$1, 2, 3, 4, 5, 6$$$. 

Sample Inputs:
3
6 3 2 5 4 1

2
3 4 2 1

4
1 2 3 4 5 6 7 8

Sample Outputs:
3

-1

0

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List, Mapping
sys.setrecursionlimit(999999)
n = int(input())
arr = list(map(int, input().split()))
s = set()
q = collections.deque()
q.append([arr, 0])
while q:
    (aas, cnt) = q.popleft()
    if aas[0] == 1:
        if aas == list(range(1, 2 * n + 1)):
            print(cnt)
        else:
            print(-1)
        break
    if aas[0] in s:
        continue
    s.add(aas[0])
    at1 = aas[n:] + aas[:n]
    q.append([at1, cnt + 1])
    at2 = [0] * (2 * n)
    (at2[0::2], at2[1::2]) = (aas[1::2], aas[0::2])
    q.append([at2, cnt + 1])
else:
    print(-1)

Solution (Python):
n = int(input())
a = input().split()
c = d = 0
li = [i + 1 for i in range(2 * n)]
for i in range(2 * n):
    a[i] = int(a[i])
e = a.copy()

def op1(b):
    global n
    x = b[0:n]
    y = b[n:2 * n]
    return y + x

def op2(c):
    global n
    for i in range(0, 2 * n, 2):
        (c[i], c[i + 1]) = (c[i + 1], c[i])
    return c
while a != li:
    a = op1(a)
    c += 1
    if a == li:
        pass
    elif c > 2 * n:
        print(-1)
        exit()
    else:
        a = op2(a)
        c += 1
while e != li:
    e = op2(e)
    d += 1
    if e == li:
        pass
    elif d > 2 * n:
        print(-1)
        exit()
    else:
        e = op1(e)
        d += 1
print(min(c, d))
''

Solution (Python):
def jum(x, n):
    for i in range(0, n, 2):
        p = x[i]
        x[i] = x[i + 1]
        x[i + 1] = p
    return x

def shift(x, n):
    x = x[n // 2:] + x[:n // 2]
    return x
n = int(input())
a = list(map(int, input().split()))
req = list(range(1, 2 * n + 1))
if n % 2 == 0:
    k = 4
else:
    k = 2 * n
i = 0
while i < k and a != req:
    if i & 1 == 1:
        a = shift(a, 2 * n)
    else:
        a = jum(a, 2 * n)
    i = i + 1
if a == req:
    print(min(i, k - i))
else:
    print(-1)