Problem:


Reverse Sort

1 &sim; NまでのN個の数字の順列A1, A2, ……, ANが与えられる。
この順列に対して区間[i, j](1 ≤ i ≤ j ≤ N)の数字の順序を逆順にする操作reverse(i, j)を行うことが出来る。
例えば、[1, 2, 3, 4, 5]に対してreverse(2, 4)を適用すると[1, 4, 3, 2, 5]となる。
最小で何回の操作を行えば順列を昇順にソートされた状態にすることが出来るか計算せよ。

Input

入力は以下の形式で与えられる。

N
A1 A2 …… AN

Constraints

Nは整数である

2 ≤ N ≤ 10

Output

問題の解を1行に出力せよ。

Sample Input 1

5
1 4 3 5 2

Output for the Sample Input 1

2

reverse(4,5):1 4 3 2 5

reverse(2,4):1 2 3 4 5

のようにすればよい。

Sample Input 2

5
3 1 5 2 4

Output for the Sample Input 2

4

例えば

reverse(1,2):1 3 5 2 4

reverse(3,5):1 3 4 2 5

reverse(2,4):1 2 4 3 5

reverse(3,4):1 2 3 4 5

のようにすればよい。

Sample Input 3

3
1 2 3

Output for the Sample Input 3

0

Sample Input 4

10
3 1 5 2 7 4 9 6 10 8

Output for the Sample Input 4

9



Sample input:
5
1 4 3 5 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
from collections import deque
sys.setrecursionlimit(1000000)
	
sorted_a = ""
m = dict({})

def dist_a(a):
	res = 0
	for i, x in enumerate(a):
		res += abs(i - int(x))
	return res

N = int(input())
A = ''.join(list(map(lambda x: str(int(x)-1), input().split())))
sorted_a = ''.join(list(sorted(A)))
#i = 1
#j = 4
#x = "03214"
#print(A[:i:])
#print(A[::-1][len(A)-j:len(A)-i:])
#print(A[j::])
#print(x[:i:] + x[::-1][len(x)-j:len(x)-i:] + x[j::])
q = deque()
q.append((A, 0))
m[A] = 0
while True:
	a, x = q.popleft()
	if a in m and m[a] < x:
		continue
	#if x == 4:
	#	break;
	#print(len(m))
	if a == sorted_a:
		print(x)
		break
	d_a = dist_a(a)
	for i in range(len(a)):
		for j in range(i+2, len(a)+1):
			next_a = a[:i:] + a[::-1][len(a)-j:len(a)-i:] + a[j::]
			if next_a in m:
				continue
			if d_a < dist_a(next_a):
				continue
			q.append((next_a, x+1))
			m[next_a] = x+1
			
	
#print(reverse_a(A, 0))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
from collections import deque
sys.setrecursionlimit(1000000)
	
sorted_a = ""
m = dict({})

N = int(input())
A = ''.join(list(map(lambda x: str(int(x)-1), input().split())))
sorted_a = ''.join(list(sorted(A)))

q = deque()
q.append((A, 0))
m[A] = 0
while True:
	a, x = q.popleft()
	if a in m and m[a] < x:
		continue
	if x == (len(a)-1) // 2:
		break;

	for i in range(len(a)):
		for j in range(i+2, len(a)+1):
			next_a = a[:i:] + a[::-1][len(a)-j:len(a)-i:] + a[j::]
			if next_a in m:
				continue

			q.append((next_a, x+1))
			m[next_a] = x+1
			
m2 = dict({})
q = deque()
q.append((sorted_a, 0))
m2[sorted_a] = 0
while True:
	a, x = q.popleft()
	if a in m2 and m2[a] < x:
		continue
	if x == (len(a)-1) // 2:
		break;

	for i in range(len(a)):
		for j in range(i+2, len(a)+1):
			next_a = a[:i:] + a[::-1][len(a)-j:len(a)-i:] + a[j::]
			if next_a in m2:
				continue
			q.append((next_a, x+1))
			m2[next_a] = x+1

ret = sys.maxsize
for a, x in m.items():
	if a in m2:
		ret = min(ret, x + m2[a])
	
if ret == sys.maxsize:
	print(len(A) - 1)
else:
	print(ret)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N = int(readline())
    INF = 10**9
    A = tuple(map(int, readline().split()))
    B = tuple(range(1, N+1))
    def check(N, A, N1):
        que = [(0, A)]
        dist = {A: 0}
        S = [A]
        B = list(A)
        for cost in range(N1):
            T = []
            for v in S:
                if dist[v] < cost:
                    continue
                for i in range(N):
                    B[:] = v
                    for j in range(i+1, N):
                        B[i:j+1] = reversed(v[i:j+1])
                        key = tuple(B)
                        if cost+1 < dist.get(key, N1+1):
                            dist[key] = cost+1
                            T.append(key)
            S = T
        return dist
    D0 = check(N, A, (N-1)//2)
    D1 = check(N, B, (N-1)//2)
    ans = N-1
    for state, v in D0.items():
        if state in D1:
            ans = min(ans, v + D1[state])
    write("%d\n" % ans)
solve()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()

        def search(s,t):
            n2 = 4
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True
                if u == t:
                    return k

                vd = k + 1
                for i in range(n):
                    for j in range(i+1,n):
                        uv = tuple(u[:i] + u[i:j+1][::-1] + u[j+1:])
                        if v[uv]:
                            continue
                        if d[uv] > vd:
                            d[uv] = vd
                            if vd < 4:
                                heapq.heappush(q, (vd, uv))

            return d

        r1 = search(tuple(a), tuple(range(1,n+1)))
        if isinstance(r1, int):
            return r1
        r2 = search(tuple(range(1,n+1)), tuple(a))
        r = n - 1
        for k,v in r1.items():
            t = v + r2[k]
            if r > t:
                r = t

        return r


    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))
        # print('rr', rr[-1])
        break

    return '\n'.join(map(str,rr))


print(main())