Problem:
 Score : 700 points    Problem Statement We have N cards numbered 1, 2, ..., N .
Card i ( 1 \leq i \leq N ) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side.
Initially, these cards are arranged from left to right in the order from Card 1 to Card N , with the red numbers facing up.  Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i ( 1 \leq i \leq N - 1 ), the integer facing up on the (i+1) -th card from the left is not less than the integer facing up on the i -th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.   Choose an integer i ( 1 \leq i \leq N - 1 ).
Swap the i -th and (i+1) -th cards from the left, then flip these two cards.       Constraints  1 \leq N \leq 18  1 \leq A_i, B_i \leq 50 ( 1 \leq i \leq N )  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N  B_1  B_2  ...  B_N       Output If it is impossible to have a non-decreasing sequence, print -1 .
If it is possible, print the minimum number of operations required to achieve it.        Sample Input 1 3
3 4 3
3 2 3      Sample Output 1 1  By doing the operation once with i = 1 , we have a sequence [2, 3, 3] facing up, which is non-decreasing.       Sample Input 2 2
2 1
1 2      Sample Output 2 -1  After any number of operations, we have the sequence [2, 1] facing up, which is not non-decreasing.       Sample Input 3 4
1 2 3 4
5 6 7 8      Sample Output 3 0  No operation may be required.       Sample Input 4 5
28 15 22 43 31
20 22 43 33 32      Sample Output 4 -1       Sample Input 5 5
4 46 6 38 43
33 15 18 27 37      Sample Output 5 3

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL : https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d
解説AC

きもすぎBit全探索および転倒数
    （転倒数に結びついたら強い
    　隣通しを入れ替えてsortの操作数→バブルソートの操作数→転倒数
    　これの徹底）

AC例1: 最初に考え付いたのはこっち
    maskでどのindexが裏返しになっているかを保持。
    その状況下で生成される表面の数の配列を作成し(これをLとする)ソート。
    iを[0,n)で回して各A[i],B[i]に対して
    maskをもとにAかBが使用されているかを見る。
    Lにおけるその数のindexとiの差の偶奇は奇数B偶数ならA。
    defalutdictかなんかで各Lの数字とそのindexの偶奇の数とそのindexを保持
    indexとiの差の偶奇とdictからLの各indexが元どの番号にいたかを保持。
    あとは元の番号の配列の転倒数を求めればそのmaskにおける操作数が出る

AC例2: 解説はこっち
    maskではどのindexがすでに左側で固定化されたかを保持。
    巡回セールスマンのようにどこを決めて最後に決めたindexは何か
    というDPでいける。（は？）
    というのもmaskだけではそのマスク内の順番はわからないからね。
    欲しいのはその固定化された物の最大の値なので最悪なんかうまくできるかも
    すごすぎ
    こっちを実装します
    700点をACしたいね(2020/3/25/ 20:05)

    Reference: https://atcoder.jp/contests/keyence2020/submissions/9567775 By:yutaka1999
"""


def solve():
    n = II()
    A = LI()
    B = LI()
    bit_length = [0] 
    for i in range(n):
        bit_length += [x + 1 for x in bit_length]
    dp = [[-1] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0
    for mask in range(1 << n):
        dpm = dp[mask]
        c = bit_length[mask]
        for i in range(n):
            if not((1 << i) & mask) or dpm[i] == -1: continue
            w = B[i] if 1 & i == c & 1 else A[i]
            cost = c
            for j in range(n):
                if 1 & (mask >> j):
                    cost -= 1
                else:
                    v = B[j] if 1 & j != c & 1 else A[j]
                    if v >= w:
                        vl = dpm[i] + cost
                        if dp[mask | (1 << j)][j] == -1 or dp[mask | (1 << j)][j] > vl:
                            dp[mask | (1 << j)][j] = vl

    ans = -1
    for i in range(n):
        if dp[-1][i] != -1:
            if ans == -1 or ans > dp[-1][i]:
                ans = dp[-1][i]
    print(ans)

    return



if __name__ == '__main__':
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL : https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d
解説AC

きもすぎBit全探索および転倒数
    （転倒数に結びついたら強い
    　隣通しを入れ替えてsortの操作数→バブルソートの操作数→転倒数
    　これの徹底）

AC例1: 最初に考え付いたのはこっち
    maskでどのindexが裏返しになっているかを保持。
    その状況下で生成される表面の数の配列を作成し(これをLとする)ソート。
    iを[0,n)で回して各A[i],B[i]に対して
    maskをもとにAかBが使用されているかを見る。
    Lにおけるその数のindexとiの差の偶奇は奇数B偶数ならA。
    defalutdictかなんかで各Lの数字とそのindexの偶奇の数とそのindexを保持
    indexとiの差の偶奇とdictからLの各indexが元どの番号にいたかを保持。
    あとは元の番号の配列の転倒数を求めればそのmaskにおける操作数が出る

AC例2: 解説はこっち
    maskではどのindexがすでに左側で固定化されたかを保持。
    巡回セールスマンのようにどこを決めて最後に決めたindexは何か
    というDPでいける。（は？）
    というのもmaskだけではそのマスク内の順番はわからないからね。
    欲しいのはその固定化された物の最大の値なので最悪なんかうまくできるかも
    すごすぎ
    こっちを実装します
    700点をACしたいね(2020/3/25/ 20:05)

    Reference: https://atcoder.jp/contests/keyence2020/submissions/9567775 By:yutaka1999
"""


def solve():
    n = II()
    A = LI()
    B = LI()
    bit_length = [0] 
    for i in range(n):
        bit_length += [x + 1 for x in bit_length]
    dp = [[-1] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0
    for mask in range(1 << n):
        dpm = dp[mask]
        c = bit_length[mask]
        for i in range(n):
            if not((1 << i) & mask) or dpm[i] == -1: continue
            w = B[i] if 1 & i == c & 1 else A[i]
            cost = c
            for j in range(n):
                if 1 & (mask >> j):
                    cost -= 1
                else:
                    v = B[j] if 1 & j != c & 1 else A[j]
                    if v >= w:
                        vl = dpm[i] + cost
                        if dp[mask | (1 << j)][j] == -1 or dp[mask | (1 << j)][j] > vl:
                            dp[mask | (1 << j)][j] = vl

    ans = -1
    for i in range(n):
        if dp[-1][i] != -1:
            if ans == -1 or ans > dp[-1][i]:
                ans = dp[-1][i]
    print(ans)

    return



if __name__ == '__main__':
    solve()

Solution (Python):
class BinaryIndexedTree():  
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


INF = 10**18

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

res = INF

for i in range(2**N):
    front = []
    back = []
    for j in range(N):
        if (i >> j) & 1:
            front.append((A[j], j))
        else:
            back.append((B[j], j))
    odd = []
    even = []
    for x, j in front:
        if j % 2 == 0:
            odd.append((x, j))
        else:
            even.append((x, j))
    for x, j in back:
        if j % 2 != 0:
            odd.append((x, j))
        else:
            even.append((x, j))
    if len(even) != N // 2:
        continue
    odd.sort()
    even.sort()
    seq = []
    for j in range(N):
        if j % 2 == 0:
            seq.append(odd[j // 2])
        else:
            seq.append(even[j // 2])
    for j in range(N - 1):
        if seq[j][0] > seq[j + 1][0]:
            break
    else:
        bit = BinaryIndexedTree(N)
        count = 0
        for j in range(N):
            bit.add(seq[j][1] + 1, 1)
            count += j + 1 - bit.sum(seq[j][1] + 1)
        res = min(res, count)

print(res if res != INF else -1)

Solution (Python):

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 2**19





dp = [[INF for _ in range(50 + 1)] for _ in range((1<<N))]

dp[0][0] = 0

for bit in range(1<<N):
  num_used = bin(bit).count("1") 
  idx = num_used
  remaining = [] 
  for i in range(N):
    if not (bit & (1 << i)):
      
      
      
      remaining.append((i, idx))
      idx += 1
  for s in range(51):
    
    if dp[bit][s] >= INF:
        continue
    for init_pos, current_pos in remaining:
      
      number = [A[init_pos], B[init_pos]][abs(init_pos-num_used)%2]
      if number >= s: 
        dp[bit | (1<<init_pos)][number] = min(
          dp[bit | (1<<init_pos)][number], dp[bit][s] + abs(num_used - current_pos)
        )



ans = min([dp[-1][s] for s in range(51)])

print(ans if ans < INF else -1)

Solution (Python):

from itertools import *









N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Zlst=set([i for i in range(N)])
if N==1:
    print(0)
    exit()
count=-1
for lst in combinations(range(N),N//2+N%2):
    odds=[[A[i],i] if i%2==0 else [B[i],i] for i in lst]
    even=[[B[i],i] if i%2==0 else [A[i],i] for i in list(Zlst-set(lst))]
    oddsst=sorted(odds,key=lambda  x:x[0])
    evenst=sorted(even,key=lambda  x:x[0])

    temp=oddsst[0][0]
    lst=[oddsst[0][1]]
    for i in range(1,N):
        if i%2==1:
            ntemp=evenst[i//2]
        else:
            ntemp=oddsst[i//2]
        if temp>ntemp[0]:
            flag=0
            break
        else:
            flag=1
            temp=ntemp[0]
            lst.append(ntemp[1])

    if flag:
        if count==-1:
            count=10**10
        tempcount=0
        while flag:
            flag=0
            for i in range(len(lst)-1):
                if lst[i]>lst[i+1]:
                    lst[i],lst[i+1]=lst[i+1],lst[i]
                    tempcount+=1
                    flag=1
        count=min(count,tempcount)


print(count)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append(b[j])
    else:
      x.append(a[j])
  sx = sorted(x)
  odd = [0] * 51
  even = [0] * 51
  for j in range(N):
    odd[sx[j]] += j % 2
    even[sx[j]] += (j % 2 == 0)
  for j in range(N):
    if i & (1 << j):
      if j % 2: even[x[j]] -= 1
      else: odd[x[j]] -= 1
    else:
      if j % 2: odd[x[j]] -= 1
      else: even[x[j]] -= 1
  return min(min(odd), min(even)) >= 0
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(N)
  t = 0
  odd = []
  even = []
  for j in range(N):
    if i & (1 << j):
      if j % 2: even.append((b[j], j))
      else: odd.append((b[j], j))
    else:
      if j % 2: odd.append((a[j], j))
      else: even.append((a[j], j))
  
  odd.sort(key = lambda x: x[0])
  even.sort(key = lambda x: x[0])
  ind = []
  
  for j in range(N):
    if j % 2: ind.append(odd[j // 2][1])
    else: ind.append(even[j // 2][1])
  
  for x in ind:
    t += fwk.get(x, N)
    fwk.add(x + 1, 1)
  res = min(res, t)
  
if res == float("inf"): print(-1)
else: print(res)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res


def inv_cnt(seq):
    n = len(seq)
    bit = BIT(n)
    cnt = 0
    for i in range(n - 1, -1, -1):
        cnt += bit.sum(seq[i] - 1)
        bit.add(seq[i], 1)
    return cnt


n = I()
A = LI()
B = LI()
ans = INF
for odd_ind in combinations(range(n), n // 2):
    even_ind = set(range(n)) - set(odd_ind)
    odd_list = []
    even_list = []
    whole_num_list = []
    whole_idx_list = []
    for i in odd_ind:
        if i % 2:
            odd_list += [(A[i], i)]
        else:
            odd_list += [(B[i], i)]
    for j in even_ind:
        if j % 2:
            even_list += [(B[j], j)]
        else:
            even_list += [(A[j], j)]
    even_list.sort(reverse=1)
    odd_list.sort(reverse=1)
    while even_list or odd_list:
        x, idx = even_list.pop()
        whole_num_list += [x]
        whole_idx_list += [idx]
        if odd_list:
            x, idx = odd_list.pop()
            whole_num_list += [x]
            whole_idx_list += [idx]
    if whole_num_list == sorted(whole_num_list):
        ans = min(ans, inv_cnt(whole_idx_list))

if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
B = LI()
ans = INF
for odd_ind in combinations(range(n), n // 2):
    even_ind = set(range(n)) - set(odd_ind)
    odd_list = []
    even_list = []
    whole_num_list = []
    whole_idx_list = []
    for i in odd_ind:
        if i % 2:
            odd_list += [(A[i], i)]
        else:
            odd_list += [(B[i], i)]
    for j in even_ind:
        if j % 2:
            even_list += [(B[j], j)]
        else:
            even_list += [(A[j], j)]
    even_list.sort(reverse=1)
    odd_list.sort(reverse=1)
    while even_list or odd_list:
        x, idx = even_list.pop()
        whole_num_list += [x]
        whole_idx_list += [idx]
        if odd_list:
            x, idx = odd_list.pop()
            whole_num_list += [x]
            whole_idx_list += [idx]
    if whole_num_list == sorted(whole_num_list):
        cnt = 0
        for i in range(n):
            for j in range(i + 1, n):
                if whole_idx_list[i] > whole_idx_list[j]:
                    cnt += 1
        ans = min(ans, cnt)


if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from itertools import combinations
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

def inversion(inds):
    bit = [0] * (N+1)
    def bit_add(x,w):
        while x <= N:
            bit[x] += w
            x += (x & -x)
    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret
    inv = 0
    for ind in reversed(inds):
        inv += bit_sum(ind + 1)
        bit_add(ind + 1, 1)
    return inv

INF = float('inf')
ans = INF
for odd_idxs in combinations(range(N), N//2):
    odd_idxset = set(odd_idxs)
    odds = []
    evens = []
    for i in range(N):
        if i in odd_idxset:
            odds.append((A[i] if i%2 else B[i], i))
        else:
            evens.append((B[i] if i%2 else A[i], i))
    odds.sort()
    evens.sort()
    vals = []
    inds = []
    for (e,ei),(o,oi) in zip(evens, odds):
        vals.append(e)
        vals.append(o)
        inds.append(ei)
        inds.append(oi)
    if len(evens) > len(odds):
        v,i = evens[-1]
        vals.append(v)
        inds.append(i)
    if any(a>b for a,b in zip(vals,vals[1:])): continue
    ans = min(ans, inversion(inds))

print(-1 if ans==INF else ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

@mt
def slv(N, A, B):
    AB = list(zip(A, B))


    ans = INF
    for f in product(range(2), repeat=N):
        o = []
        e = []
        for i, (c, ab) in enumerate(zip(f, AB)):
            v = ab[c]
            if i % 2 == 0:
                if c == 0:
                    e.append((v, i))
                else:
                    o.append((v, i))
            else:
                if f[i] == 0:
                    o.append((v, i))
                else:
                    e.append((v, i))
        if 0 <= len(e) - len(o) <= 1:
            bit = Bit(50)
            e.sort()
            o.sort()
            eo = [e, o]
            cand = 0
            p = -1
            for i in range(N):
                if p > eo[i%2][i//2][0]:
                    break
                p = eo[i % 2][i//2][0]
                bit.add(eo[i%2][i//2][1]+1, 1)
                cand += i + 1 - bit.sum(eo[i%2][i//2][1]+1)
            else:
                ans = min(ans, cand)
    if ans == INF:
        ans = -1
    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(slv(N, A, B))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    if i % 2:
        aa, bb = bb, aa
    all_cards.append([aa, bb, i])

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i][1] > l[j][1]:
                ret += 1
    return ret

ans = float('inf')
for cards in combinations(all_cards, (n + 1)// 2):
    acards = []
    for card in cards:
        acards.append([card[0],card[2]])
    bcards = []
    for card in all_cards:
        if [card[0],card[2]] not in acards:
            bcards.append([card[1],card[2]])

    acards.sort()
    bcards.sort()
    abcards = []
    
    for i in range(len(bcards)):
        abcards.extend([acards[i], bcards[i]])
    else:
        if n % 2:
            abcards.append(acards[-1])
    
    if abcards != sorted(abcards, key=lambda x: x[0]):
        continue
    ans = min(ans, cnt(abcards))

if ans == float('inf'):
    ans = -1
print(ans)

Solution (Python):



N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 1 << 20


dp = [[INF for _ in range(51)] for _ in range(1 << N)]
dp[0][0] = 0

for bit in range(1 << N):

    
    num_used = bin(bit).count("1")

    curr = num_used
    remaining = []
    for i in range(N):
        
        if not(bit & (1 << i)):
            remaining.append((i, curr))
            curr += 1

    for s in range(51):
        
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            
            num = A[ini] if abs(num_used - ini) % 2 == 0 else B[ini]

            
            if num >= s:
                
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))

ans = INF
for i in range(51):
    ans = min(ans, dp[-1][i])

print(ans if ans < INF else -1)

Solution (Python):
from itertools import combinations

def solve():
    INF = 10**5

    def getNumInversion(odrAs):
        def makeBIT(numEle):
            numPow2 = 2 ** (numEle-1).bit_length()
            data = [0] * (numPow2+1)
            return data, numPow2
        def addValue(iA, A):
            iB = iA + 1
            while iB <= numPow2:
                data[iB] += A
                iB += iB & -iB
        def getSum(iA):
            iB = iA + 1
            ans = 0
            while iB > 0:
                ans += data[iB]
                iB -= iB & -iB
            return ans
        lenA = len(odrAs)
        data, numPow2 = makeBIT(lenA)
        ans = 0
        for odrA in reversed(odrAs):
            ans += getSum(odrA)
            addValue(odrA, 1)
        return ans

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    ans = INF
    for iEvens in combinations(range(N), r=N//2):
        iEvens = set(iEvens)
        COdds, CEvens = [], []
        for i in range(N):
            if i in iEvens:
                if i % 2:
                    CEvens.append((As[i], i))
                else:
                    CEvens.append((Bs[i], i))
            else:
                if i % 2:
                    COdds.append((Bs[i], i))
                else:
                    COdds.append((As[i], i))
        COdds.sort()
        CEvens.sort()

        Cs = []
        for COdd, CEven in zip(COdds, CEvens):
            Cs += [COdd, CEven]
        if N % 2:
            Cs += [COdds[-1]]

        for i in range(N-1):
            if Cs[i][0] > Cs[i+1][0]:
                break
        else:
            odrAs = [i for C, i in Cs]
            num = getNumInversion(odrAs)
            ans = min(ans, num)
            if ans == 0:
                break

    if ans == INF:
        print(-1)
    else:
        print(ans)


solve()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()

ans = INF
for S in range(1<<N):
    
    if pop_count(S) % 2 != 0:
        continue
    
    A1 = [[] for i in range(2)]
    for i in range(N):
        
        if S & 1<<i:
            A1[(i&1)^1].append((cards[1][i], i))
        
        else:
            A1[i&1].append((cards[0][i], i))
    
    if len(A1[0]) != ceil(N, 2) or len(A1[1]) != N // 2:
        continue
    
    A1[0].sort(reverse=1)
    A1[1].sort(reverse=1)
    cnt = 0
    A2 = [0] * N
    idxs = [0] * N
    for i in range(N):
        
        A2[i], idxs[i] = A1[i&1].pop()
    
    if A2 == sorted(A2):
        
        cnt = 0
        for i, idx1 in enumerate(idxs):
            for j, idx2 in enumerate(idxs[i+1:], i+1):
                if idx1 > idx2:
                    cnt += 1
        ans = min(ans, cnt)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 1 << 19

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""

dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]

dp[0][0] = 0

for bit in range(1 << N):
    
    num_used = bin(bit).count("1")
    
    
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                
                
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))




ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)

Solution (Python):


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 1 << 29

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""

dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]

dp[0][0] = 0

for bit in range(1 << N):
    
    num_used = bin(bit).count("1")
    
    
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                
                
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))




ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()


dp = list2d(1<<N, N, INF)
for i in range(N):
    
    dp[1<<i][i] = 0
for S in range(1, 1<<N):
    popcnt = pop_count(S)
    
    acc = [0] * N
    for i in range(N):
        if S & 1<<i:
            acc[i] = 1
    
    acc = list(accumulate(acc[::-1]))[::-1]
    for i in range(N):
        if dp[S][i] == INF or not S & 1<<i:
            continue
        
        cur = cards[(i&1)^(1-(popcnt&1))][i]
        for j in range(N):
            if S & 1<<j:
                continue
            
            nxt = cards[(j&1)^(popcnt&1)][j]
            
            if cur <= nxt:
                
                dp[S|1<<j][j] = min(dp[S|1<<j][j], dp[S][i] + acc[j])
ans = INF
for i in range(N):
    ans = min(ans, dp[(1<<N)-1][i])
if ans == INF:
    print(-1)
else:
    print(ans)