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



Sample input:
3
3 4 3
3 2 3


Sample output:
1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
print(-1)import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = float("inf")
for i in range(pow(2, N)):
  x = []
  l = []
  c = 0
  for j in range(N):
    if i & (1 << j):
      c += 1
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  if c % 2: continue
  y = sorted(x, key = lambda x: x[0])
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  if z == -1: continue
  z = 0
  for j in range(N):
    for k in range(j, len(x)):
      if x[k][0] == y[j][0]:
        x.pop(k)
        x.insert(0, (0, 0))
        z += k - j
        break
  res = min(res, z)

  
if res != float("inf"): print(res)
else: print(-1)

Submission status: Runtime Error

Solution code:
from itertools import combinations

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

odd = a[::2] + b[1::2]
even = a[1::2] + b[::2]

#print(odd)
#print(even)

odd.sort()
even.sort()

i = 0
nums = [0]
while odd and even:
    if i % 2:
        while even:
            num = even.pop(0)
            if num >= nums[-1]:
                nums.append(num)
                break

    else:
        while odd:
            num = odd.pop(0)
            if num >= nums[-1]:
                nums.append(num)
                break

    i += 1

nums.pop(0)

if len(nums) < n:
    print(-1)
    exit()

choose = n // 2 + n % 2
for odds in combinations(range(n), choose):
    front = []
    for i in range(n):
        if i in odds:
            if i % 2:
                front.append(b[i])
            else:
                front.append(a[i])
        else:
            if i % 2:
                front.append(a[i])
            else:
                front.append(b[i])

    front.sort()
    #print(front)
    i = 0
    for e in nums:
        if e == front[i]:
            i += 1

        if i == n:
            break

    if i == n:
        raise Exception

Submission status: Runtime Error

Solution code:
from itertools import combinations

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a2=list()
b2=list()

for i in range(n):
    if i%2:
        b2.append(a[i])
        a2.append(b[i])
    else:
        a2.append(a[i])
        b2.append(b[i])

ans=10**9
for idx in combinations(range(0,n), (n+1)//2):
    a3=list()
    b3=list()
    flag=True
    for i in range(n):
        if i in idx:
            a3.append([a2[i], i])
        else:
            b3.append([b2[i], i])
    a3.sort(key=lambda x:x[0])
    b3.sort(key=lambda x:x[0])

    for i in range(len(b3)-1):
        if a3[i][0]>b3[i][0] or a3[i+1][0]<b3[i][0]:
            flag=False
    if len(a3)>len(b3):
        if a3[-1][0]<b3[-1][0] or a3[-2][0]>b3[-1][0]:
            flag=False
    elif a3[-1][0]>b3[-1][0]:
        flag=False

    if flag:
        ansidx = list()
        for i in range(len(b3)):
            ansidx.append(a3[i][1])
            ansidx.append(b3[i][1])
        if len(a3)>len(b3):
            ansidx.append(a3[-1][1])

        swap=0
        for i in range(n):
            for j in range(i,n):
                if ansidx[i]>ansidx[j]:
                    swap+=1
        ans= min(ans, swap)

if ans==10**9:
    print('-1')
else:
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from itertools import combinations
    input = sys.stdin.readline

    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

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

    even = []
    odd = []
    for i in range(N):
        if i%2:
            odd.append(A[i])
            even.append(B[i])
        else:
            even.append(A[i])
            odd.append(B[i])

    L = list(range(N))
    ans = 10**9
    for v in combinations(L, N//2):
        ok = 1
        tmp = []
        tmp_odd = []
        tmp_even = []
        for i in range(N):
            if i in v:
                tmp.append(odd[i] * 100 + (v.index(i) * 2+1))
                tmp_odd.append(odd[i])
            else:
                cnt = 0
                for j in range(N):
                    if j == i:
                        break
                    if j not in v:
                        cnt += 1
                tmp.append(even[i] * 100 + cnt * 2)
                tmp_even.append(even[i])

        tmp_odd.sort()
        tmp_even.sort()
        tmp_check = []
        for i in range(N):
            if i%2:
                tmp_check.append(tmp_odd[i//2])
            else:
                tmp_check.append(tmp_even[i // 2])
        for i in range(N-1):
            if tmp_check[i] > tmp_check[i+1]:
                ok = 0
                # print(v, tmp_check, odd, even)
                break
        if not ok:
            continue

        bit = Bit(5100)
        ans_new = 0
        for i in range(N-1, -1, -1):
            ans_new += bit.sum(tmp[i]-1)
            bit.add(tmp[i], 1)
        # print(v, tmp, ans_new, odd, even)
        ans = min(ans, ans_new)

    if ans == 10**9:
        assert False
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import combinations
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
minc = 19
num = [i for i in range(N-1)]
for i in range(N-1):
    for j in combinations(num,i):
        now = 0
        flag = True
        count = len(j)
        A2 =  A.copy()
        B2 =  B.copy()
        per = list(j)
        while True:
            A2[k],A2[k+1],B2[k],B2[k+1] = B2[k+1],B2[k],A2[k+1],A2[k]

        for j in A2:
            if now <= j:
                now = j
            else:
                flag = False
                break
        if flag:
            minc = min(minc,count)
if minc != 19:
    print(minc)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys

def swap(i,P,Q):
    Q[i+1],Q[i],P[i+1],P[i]=P[i],P[i+1],Q[i],Q[i+1]
    return P,Q

def judge(P):
    for i in range(len(P)-1):
        if P[i]>P[i+1]:
            return False
    else:
        return True

N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
flag=False
if judge(A):
    print(0)
    sys.exit()
for l in itertools.permutations(range(0,N-1)):
    if flag:
        break
    T=copy(A)
    Y=copy(B)
    count = 0
    for i in l:
        T,Y=swap(i,T,Y)
        count += 1
        if judge(T):
            ans = l
            flag=True
            print(count)
            break
else:
    print(-1)
    sys.exit()
#T=copy(A)
#Y=copy(B)
#print(T,Y)
#for i in ans:
#    T,Y=swap(i,T,Y)
#    print(T,Y)

Submission status: Runtime Error

Solution code:
n = int(input())
red = list(map(int,input().split()))
blue = list(map(int,input().split()))
ans = 10 ** 5
for i in range(2 ** n):
    s = format(i,"b").zfill(n)
    num = {(red[j],j) if s[j] == "0" else (blue[j],j+1) for j in range(n)}
    num.sort()
    nu = 0
    for h in range(n):
        nu += abs(num[h][-1]-h)
        if ((num[h][1]) % 101-h) % 2 != 0:
            break
        if h == n-1:
            ans = min(ans,nu//2)
if ans == 10 ** 5:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 10**9+7
for i in range(2**N):
    card = [[],[]]
    num = []
    x = i
    for j in range(N):
        if i&1:
            num.append(B[j])
            card[(j+1)%2].append(j)
        else:
            num.append(A[j])
            card[(j)%2].append(j)
        i >>= 1
    if len(card[1]) != N//2:
        continue
    card[0].sort(key=lambda x:[num[x],x]);card[1].sort(key=lambda x:[num[x],x])
    hoge = []
    for i in range(N):
        hoge.append(card[i%2][i//2])
    flag = True
    for i in range(N-1):
        if num[hoge[i]] > num[hoge[i+1]]:
            flag = False
    if flag:
        huga = sum(abs(hoge[i]-i)for i in range(N))
        if huga % 2:
            print(1/0)
        else:
            huge //= 2
        if huga < ans:
            ans = huga
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
n = int(input())
a_lis = list(map(int, input().split()))
b_lis = list(map(int, input().split()))
used = []
res = []
def rec(a_lis, b_lis, l):
    found = True
    pre = -1
    for a in a_lis:
        if a < pre:
            found = False
            break
        pre = a
    if found:
        res.append(l)
        return
    used.append((a_lis, b_lis))
    for i in range(len(a_lis) - 1):
        na_lis = a_lis[:i] + [b_lis[i + 1]] + [b_lis[i]] + a_lis[i + 2:]
        nb_lis = b_lis[:i] + [a_lis[i + 1]] + [a_lis[i]] + b_lis[i + 2:]
        if (na_lis, nb_lis) not in used:
            rec(na_lis, nb_lis, l + 1)
rec(a_lis, b_lis, 0)
if res:
    print(min(res))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

odd = a[::2] + b[1::2]
even = a[1::2] + b[::2]

#print(odd)
#print(even)

odd.sort()
even.sort()

i = 0
nums = [0]
while odd and even:
    if i % 2:
        while even:
            num = even.pop(0)
            if num >= nums[-1]:
                nums.append(num)
                break

    else:
        while odd:
            num = odd.pop(0)
            if num >= nums[-1]:
                nums.append(num)
                break

    i += 1

nums.pop(0)

if len(nums) < n:
    print(-1)

else:
    raise Exception

Submission status: Runtime Error

Solution code:
n = int(input())
a_lis = list(map(int, input().split()))
b_lis = list(map(int, input().split()))
used = []
res = []
def rec(a_lis, b_lis, l):
    found = True
    pre = -1
    for a in a_lis:
        if a < pre:
            found = False
            break
        pre = a
    if found:
        res.append(l)
        return
    used.append((a_lis, b_lis))
    for i in range(len(a_lis) - 1):
        na_lis = a_lis[:i] + [b_lis[i + 1]] + [b_lis[i]] + a_lis[i + 2:]
        nb_lis = b_lis[:i] + [a_lis[i + 1]] + [a_lis[i]] + b_lis[i + 2:]
        if (na_lis, nb_lis) not in used:
            rec(na_lis, nb_lis, l + 1)
rec(a_lis, b_lis, 0)
if res:
    print(min(res))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            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
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())
m=10**18
for i in range(2**n):
    t,u=[],[]
    x=y=0
    for j in range(n):
        f=1if 2**j&i>0else 0
        if f:
            if j%2:
                t+=b[j],
            else:
                u+=b[j],
        else:
            if j%2:
                u+=a[j],
            else:
                t+=a[j],
        if j%2:
            x+=f
        else:
            y+=f
    if x!=y:
        continue
    l=[]
    for p,q in zip(sorted(t),sorted(u)):
        l+=p,
        l+=q,
    if len(t)>len(u):
        l+=max(t),
    if l!=sorted(l):
        continue
    bit=BIT(64)
    v=0
    for j,p in enumerate(t):
        bit.add(p,1)
        v+=j+1-bit.sum(p)
    bit=BIT(64)
    w=0
    for j,p in enumerate(u):
        bit.add(p,1)
        w+=j+1-bit.sum(p)
    m=min(m,v+w+x)
if m==10**18:
    print(-1)
else:
    1/0

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)


def check(array):
    return array == sorted(array)


N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
n = set(range(N - 1))


def dfs(c, i, a, b):
    if c > 10:
        return float("inf")
    if c > 0 and a == A:
        return float("inf")
    if check(a):
        return c
    a[i], a[i+1], b[i], b[i+1] = b[i+1], b[i], a[i+1], a[i]
    ret = float("inf")
    for j in n.difference({i}):
        ret = min(ret, dfs(c+1, j, a, b))
    b[i + 1], b[i], a[i + 1], a[i] = a[i], a[i + 1], b[i], b[i + 1]
    return ret


ans = dfs(0, 0, A.copy(), B.copy())
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
def isValid(seq):
  return sorted(seq) == seq
N = int(input())
As_fixed = map(int, input().split(' '))
Bs_fixed = map(int, input().split(' '))

fact = 1
for i in range(1, N+1):
  fact *= N
  

if isValid(As_fixed):
  print(0)
else:

  odd = []
  even = []
  for i in range(N):
    if i%2==0:
      odd.append(As_fixed[i])
      even.append(Bs_fixed[i])
    else:
      even.append(As_fixed[i])
      odd.append(Bs_fixed[i])
      
min_trial = -1

As_tmp = [0 for _ in range(N)]
Bs_tmp = [0 for _ in range(N)]

for i in range(fact):
  tmp_
  As_tmp[i]

Submission status: Runtime Error

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())

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

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

if A==sorted(A):
	print("0")

def flip(i):
	k=A[i]
	A[i]=B[i+1]
	B[i+1]=k
	l=B[i]
	B[i]=A[i+1]
	A[i+1]=B[i]




else:
	print("-1")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

sys.setrecursionlimit(10000)


def main():
    n = int(input())
    a = [int(ai) for ai in input().split()]
    b = [int(bi) for bi in input().split()]

    seen = set()
    mapper = dict()

    def solve(idxs):
        t = tuple(idxs)
        if t in mapper:
            return mapper[t]
        if t in seen:
            return 10**9
        seen.add(t)

        prev = 1
        for idx in idxs:
            if idx > 0:
                if prev > a[idx - 1]:
                    break
                else:
                    prev = a[idx - 1]
            else:
                if prev > b[-idx - 1]:
                    break
                else:
                    prev = b[-idx - 1]
        else:
            mapper[t] = 0
            return 0

        res = 10**9
        for i in range(n - 1):
            new_idxs = idxs[:]
            new_idxs[i], new_idxs[i + 1] = -new_idxs[i + 1], -new_idxs[i]
            res = min(res, solve(new_idxs) + 1)

        mapper[t] = res
        return res

    r = solve(list(range(1, n + 1)))
    print(-1 if r == 10**9 else r)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def solve(n, cards):
    dp = {(1 << n) - 1: {0: 0}}
    for d in range(n):
        ndp = defaultdict(lambda: defaultdict(lambda: 1000000))
        for state, scores in dp.items():
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                curr_dp = ndp[state ^ b]
                for score, left_num in scores.items():
                    if left_num > num:
                        continue
                    curr_dp[score + curr] = min(curr_dp[score + curr], num)
                k ^= b
                curr += 1
        if len(ndp) == 0:
            return -1
        dp = ndp
    return min(dp[0].keys())


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
f = 0
for i in range(1000):
    if A == sorted(A):
        print(ans)
        quit()
    for i in range(N-1):
        a = A[i]
        ai = A[i+1]
        b = B[i]
        bi = B[i+1]
        if b > bi:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
        elif a > ai:
            A[i] = bi
            A[i+1] = b
            B[i] = ai
            B[i+1] = a
            ans += 1
print(-1)

Submission status: Runtime Error

Solution code:
N,K,S = map(int,input().split())

ans = [S]*K+[S-1]*(N-K)
for a in ans:
    print(a,end=' ')
print()