Problem:


Score : 700 points

Problem Statement

Aoki is playing with a sequence of numbers a_{1}, a_{2}, ..., a_{N}. Every second, he performs the following operation :

Choose a positive integer k. For each element of the sequence v, Aoki may choose to replace v with its remainder when divided by k, or do nothing with v. The cost of this operation is 2^{k} (regardless of how many elements he changes).

Aoki wants to turn the sequence into b_{1}, b_{2}, ..., b_{N} (the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.

Constraints

1 \leq N \leq 50

0 \leq a_{i}, b_{i} \leq 50

All values in the 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

Print the minimum cost required to turn the original sequence into b_{1}, b_{2}, ..., b_{N}. If the task is impossible, output -1 instead.

Sample Input 1

3
19 10 14
0 3 4

Sample Output 1

160

Here's a possible sequence of operations :

Choose k = 7. Replace 19 with 5, 10 with 3 and do nothing to 14. The sequence is now 5, 3, 14.

Choose k = 5. Replace 5 with 0, do nothing to 3 and replace 14 with 4. The sequence is now 0, 3, 4.

The total cost is 2^{7} + 2^{5} = 160.

Sample Input 2

3
19 15 14
0 0 0

Sample Output 2

2

Aoki can just choose k = 1 and turn everything into 0. The cost is 2^{1} = 2.

Sample Input 3

2
8 13
5 13

Sample Output 3

-1

The task is impossible because we can never turn 8 into 5 using the given operation.

Sample Input 4

4
2 0 1 8
2 0 1 8

Sample Output 4

0

Aoki doesn't need to do anything here. The cost is 0.

Sample Input 5

1
50
13

Sample Output 5

137438953472

Beware of overflow issues.



Sample input:
3
19 10 14
0 3 4


Sample output:
160

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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


def main():
    border = 12

    graph = [[] for _ in range(51)]
    for start in range(51):
        for cost in range(1,51):
            if start%cost == 0:
                graph[0].append((cost, start))
    for end in range(1, 51):
        for cost in range(end+1, 51):
            start = end + cost
            while start <= 50:
                graph[end].append((cost, start))
                start += cost

    mustconsider = [True]*N
    basebit = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if b >= border:
            mustconsider[i] = False
            if a >= 2*b+1:
                basebit |= 1<<(a-b)
            else:
                return -1
    
    # 立ってるbitのcostを使う
    ans = 10**60
    for bit in range(1<<(border-1)):
        bit <<= 1
        ok = True
        using = [0 for _ in range(N)]
        lowest = []
        for i, (a, b) in enumerate(zip(A, B)):
            if mustconsider[i]:
                canreach = False
                q = [b]
                checked = [False]*51
                checked[b] = True
                while q:
                    qq = []
                    for p in q:
                        if p == a:
                            canreach = True
                            break
                        if 2*p+1 <= a:
                            using[i] |= 1<<(a-p)
                        for cost, np in graph[p]:
                            if (1<<cost)&bit and not checked[np]:
                                checked[np] = True
                                qq.append(np)
                    if canreach: break
                    q = qq
                if not canreach:
                    if using[i] == 0:
                        ok = False
                        break
                    l = using[i] & -using[i]
                    lowest.append((l, i))
        if ok:
            now = bit|basebit
            lowest.sort(reverse=True)
            for l, i in lowest:
                if using[i]&now: continue
                now |= l
            ans = min(ans, now)

    if ans == 10**60:
        return -1
    return ans



if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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


def main():
    border = 13

    graph = [[] for _ in range(51)]
    for start in range(51):
        for cost in range(1,51):
            if start%cost == 0:
                graph[start].append((cost, 0))
    for end in range(1, 51):
        for cost in range(end+1, 51):
            start = end + cost
            while start <= 50:
                graph[start].append((cost, end))
                start += cost

    mustconsider = [True]*N
    basebit = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if b >= border:
            mustconsider[i] = False
            if a >= 2*b+1:
                basebit |= 1<<(a-b)
            else:
                return -1
    
    # 立ってるbitのcostを使う
    ans = 10**60
    for bit in range(1<<border):
        ok = True
        for i, (a, b) in enumerate(zip(A, B)):
            if mustconsider[i]:
                okcost = False
                q = [a]
                checked = [False]*51
                checked[a] = True
                while q:
                    qq = []
                    for p in q:
                        if p == b:
                            okcost = True
                            break
                        for cost, np in graph[p]:
                            if (1<<cost)&bit and not checked[np]:
                                checked[np] = True
                                qq.append(np)
                    if okcost: break
                    q = qq
                if not okcost:
                    ok = False
                    break
        if ok:
            ans = bit|basebit
            break
    if ans == 10**60:
        return -1
    return ans



if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

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

def check():
    return all(i == j for i, j in zip(a, b))

res = 0
while not check():
    mx = max(a)
    for i in range(mx, -1, -1):
        # i以下を全て使う
        ok = True
        for p, q in zip(a, b):
            for j in range(i, 0, -1):
                r = p % j
                if q == r or r > 2 * q:
                    p = r
            else:
                if p != q:
                    ok = False
                    break
        if not ok:
            break
    for j in range(n):
        r = a[j] % (i + 1)
        if b[j] == r or r > 2 * b[j]:
            a[j] = r
    if a == c:
        print(-1)
        exit()
    res += 2 ** (i + 1)
print(res)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
    r=range(M+1)
    for k in r:
        for i in r:
            for j in r:
                t=d[i][k]+d[k][j]
                if t<d[i][j]:
                    d[i][j]=t
    return d
n,*a=map(int,open(0).read().split())
a,b=a[:n],a[n:]
for x,y in zip(a,b):
    if x==y:continue
    if y>x:
        print(-1)
        exit()
    if x-y<y:
        print(-1)
        exit()
M=max(a)
d=[]
for k in range(M-1,-1,-1):
    s=set(a)
    e=[[10**18]*(M+1)for _ in range(M+1)]
    for i in range(M+1):e[i][i]=1
    for i in d+list(range(k,0,-1)):
        t=s.copy()
        for x in s:
            e[x][x%i]=1
            t|={x%i}
        s=t
    c=warshall_floyd(e)
    for x,y in zip(a,b):
        if c[x][y]>=10**18:
            d+=k+1,
            break
print(sum(2**k for k in d))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n,*a=map(int,open(0).read().split())
a,b=a[:n],a[n:]
for x,y in zip(a,b):
    if x==y:continue
    if y>x:
        print(-1)
        exit()
    if x-y<y:
        print(-1)
        exit()
M=max(a)
d=[]
for k in range(M,-1,-1):
    s=set(a)
    e=[[0]*(M+1)for _ in range(M+1)]
    for i in range(M+1):e[i][i]=1
    for i in d+list(range(k,0,-1)):
        t=s.copy()
        for x in s:
            e[x][x%i]=1
            t|={x%i}
        s=t
    c=floyd_warshall(e)
    for x,y in zip(a,b):
        if c[x,y]==float('inf'):
            d+=k+1,
            break
print(sum(2**k for k in d))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n,*a=map(int,open(0).read().split())
a,b=a[:n],a[n:]
for x,y in zip(a,b):
    if x==y:continue
    if y>x:
        print(-1)
        exit()
    if x-y<y:
        print(-1)
        exit()
M=max(a)
d=[]
for k in range(M-1,-1,-1):
    s=set(a)
    e=[[0]*(M+1)for _ in range(M+1)]
    for i in range(M+1):e[i][i]=1
    for i in d+list(range(k,0,-1)):
        t=s.copy()
        for x in s:
            e[x][x%i]=1
            t|={x%i}
        s=t
    c=floyd_warshall(e)
    for x,y in zip(a,b):
        if c[x,y]==float('inf'):
            d+=k+1,
            break
print(sum(2**k for k in d))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n,*a=map(int,open(0).read().split())
a,b=a[:n],a[n:]
for x,y in zip(a,b):
    if x==y:continue
    if y>x:
        print(-1)
        exit()
    if x-y<y:
        print(-1)
        exit()
M=max(a)
d=[]
while 1:
    e=[[0]*(M+1)for _ in range(M+1)]
    for i in range(M+1):
        e[i][i]=1
    s=set(a)
    t=s.copy()
    for k in d:
        for x in s:
            e[x][x%k]=1
            t|={x%k}
        s=t
        t=s.copy()
    f=0
    for k in range(M+1):
        if k:
            for x in s:
                e[x][x%k]=1
                t|={x%k}
            s=t
            t=s.copy()
        c=floyd_warshall(e)
        for x,y in zip(a,b):
            if c[x,y]==float('inf'):
                f=1
                break
        else:
            if f:
                d+=k,
                break
            else:
                print(sum(2**k for k in d))
                exit()

Submission status: Wrong Answer

Solution code:
import sys

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

same = 0
for i in range(n):
	if b[i]*2 >= a[i]:
		print(-1)
		sys.exit()
	elif a[i] == b[i]:
		same += 1
if same == n:
	print(0)
	sys.exit()

edges = [[] for _ in range(51)]
for i in range(1, 51):
	for j in range(1, i+1):
		edges[i].append([i%j, j])

available = [True for _ in range(51)]
visited = [False for _ in range(51)]

def dfs(start, goal, cur):
	global visited
	if cur == goal:
		return True
	for e, k in edges[cur]:
		if visited[e] == False and available[k] == True:
			visited[e] = True
			if dfs(start, goal, e) == True:
				return True
	return False

ans = 0
for k in range(50, 0, -1):
	available[k] = False
	ok = True
	for i in range(n):
		visited = [False for _ in range(51)]
		visited[a[i]] = True
		if dfs(a[i], b[i], a[i]) == False:
			ok = False
			break
	if not ok:
		ans += 2**k
		available[k] = True

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

minimum = [[51 for _ in range(51)] for _ in range(51)]
for i in range(50, 0, -1):
	minimum[i][i] = 50
	for j in range(1, 51):
		for k in range(51):
			if minimum[i][k] <= 50:
				minimum[i][k%j] = min(j, minimum[i][k%j])

ans = 0
for k in range(51, 0, -1):
	needed = False
	for i in range(n):
		if a[i] == b[i]:
			continue
		elif b[i]*2 >= a[i]:
			print(-1)
			sys.exit()
		else:
			if minimum[a[i]][b[i]] == k:
				needed = True
	if needed:
		ans += 2**k
		for i in range(n):
			if a[i]%k == b[i]:
				a[i] %= k
			elif minimum[a[i]][b[i]] == k:
				a[i] %= k
			elif minimum[a[i]][b[i]] >= minimum[a[i]%k][b[i]]:
				a[i] %= k
		#print(k, a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

minimum = [[51 for _ in range(51)] for _ in range(51)]
for i in range(50, 0, -1):
	minimum[i][i] = 50
	for j in range(1, 51):
		for k in range(51):
			if minimum[i][k] <= 50:
				minimum[i][k%j] = min(j, minimum[i][k%j])

ans = 0
for k in range(51, 0, -1):
	needed = False
	for i in range(n):
		if a[i] == b[i]:
			continue
		elif b[i] >= (a[i]+1)//2:
			print(-1)
			sys.exit()
		else:
			if minimum[a[i]][b[i]] == k:
				needed = True
	if needed:
		ans += 2**k
		for i in range(n):
			if a[i]%k == b[i]:
				a[i] %= k
			elif minimum[a[i]][b[i]] >= minimum[a[i]%k][b[i]]:
				a[i] %= k
		#print(k, a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

minimum = [[51 for _ in range(51)] for _ in range(51)]
for i in range(50, 0, -1):
	minimum[i][i] = 50
	for j in range(1, 51):
		for k in range(51):
			if minimum[i][k] <= 50:
				minimum[i][k%j] = min(j, minimum[i][k%j])

ans = 0
for k in range(51, 0, -1):
	needed = False
	for i in range(n):
		if a[i] == b[i]:
			continue
		elif b[i] >= (a[i]+1)//2:
			print(-1)
			sys.exit()
		else:
			if minimum[a[i]][b[i]] == k:
				needed = True
	if needed:
		ans += 2**k
		for i in range(n):
			if a[i]%k == b[i] or a[i]%k > 2*b[i]:
				a[i] %= k
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

Cost = 0
Sub = [0] * N

def divisor(i, b): #iの約数でbより大きく最小のもの
    for n in range(b+1, i):
        if i % n == 0:
            return n
    return i

def operate(A, B):
    Div = 0
    for i in range(N):
        if A[i] == B[i] or B[i] == 0: continue
        elif A[i] - B[i] < B[i]:return -1
        else:Div = max(divisor(A[i] - B[i], B[i]), Div)
    return Div

for i in range(N):
    div = operate(A, B)
    if div == -1:
        print(-1)
        break
    elif div == 0: continue
    else:
        for i in range(N):
            if A[i] == B[i]: continue
            elif A[i] % div >= B[i]:
                A[i] %= div
        Cost += 2 ** div
else: 
    for i in range(N):
        if B[i] == 0 and A[i] > 0:
            Cost += 1
            break
    print(Cost)

Submission status: Wrong Answer

Solution code:
N=int(input())
inf=float("inf")
dp=[[inf]*51 for i in range(51)]
for b in range(51):
  for a in range(51):
    if b==0:
      if a==0:
        dp[a][b]=0
      else:
        dp[a][b]=1
    else:
      for i in range(1,a+1):
        if a==b:
          dp[a][b]=0
        elif dp[a%i][b]<=50 or a%i==b:
          dp[a][b]=i
          break
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
ans=0
while max(a)>0:
  k=max([dp[a[i]][b[i]] for i in range(N)])
  if k==0:
    break
  if k>50:
    print(-1)
    exit()
  ans+=2**k
  for i in range(N):
    if dp[a[i]%k][b[i]]<=dp[a[i]][b[i]]:
      a[i]%=k
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
inf=float("inf")
dp=[[inf]*51 for i in range(51)]
for b in range(51):
  for a in range(51):
    if b==0:
      if a==0:
        dp[a][b]=0
      else:
        dp[a][b]=1
    else:
      for i in range(1,a+1):
        if a==b:
          dp[a][b]=0
        elif dp[a%i][b]<=50 or a%i==b:
          dp[a][b]=i
          break
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
ans=0
while max(a)>0:
  k=max([dp[a[i]][b[i]] for i in range(N)])
  if k==0:
    break
  if k>50:
    print(-1)
    exit()
  ans+=2**k
  for i in range(N):
    if dp[a[i]%k][b[i]]<=50:
      a[i]%=k
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
inf=float("inf")
dp=[[inf]*51 for i in range(51)]
for b in range(51):
  for a in range(51):
    if b==0:
      if a==0:
        dp[a][b]=0
      else:
        dp[a][b]=1
    else:
      for i in range(1,a+1):
        if a==b:
          dp[a][b]=0
        elif dp[a%i][b]<=50 or a%i==b:
          dp[a][b]=i
          break
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
ans=0
while max(a)>0:
  k=max([dp[a[i]][b[i]] for i in range(N)])
  if k==0:
    break
  if k>50:
    print(-1)
    exit()
  ans+=2**k
  for i in range(N):
    if dp[a[i]%k][b[i]]<=50:
      a[i]%=k
print(ans)

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
import sys
def edge(S):
    e = defaultdict(lambda: set())
    for i in range(N+1):
        for j in S:
            e[i].add(i%j)
        e[i] = e[i] | {i}
    return e
def path(edge):
    p = defaultdict(lambda: set())
    for st in range(N+1):
        Q, p[st], new = [edge[st]]*3
        while Q:
            for j in Q:
                new = new | edge[j]
            Q = new - p[st]
            p[st] = p[st] | new
    return p

K = int(input())
A = inpl()
B = inpl()
for i in range(K):
    if A[i] < B[i]:
        print(-1)
        sys.exit()
if A == B:
    print(0)
    sys.exit()
N = max(A) 
T = []
for l in range(N,0,-1):
    S = T + list(range(1,1+l))
    Pa = path(edge(S))
    for i in range(K):
        if B[i] not in Pa[A[i]]:
            break
    else:
        continue
    T.append(l+1)
if not T:
    print(2)
    sys.exit()
if N+1 in T:
    print(-1)
    sys.exit()
print(sum([2**i for i in T]))

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
import sys
def edge(S):
    e = defaultdict(lambda: set())
    for i in range(N+1):
        for j in S:
            e[i].add(i%j)
        e[i] = e[i] | {i}
    return e
def path(edge):
    p = defaultdict(lambda: set())
    for st in range(N+1):
        Q, p[st], new = [edge[st]]*3
        while Q:
            for j in Q:
                new = new | edge[j]
            Q = new - p[st]
            p[st] = p[st] | new
    return p

K = int(input())
A = inpl()
B = inpl()
for i in range(K):
    if not A[i]:
        if B[i]:
            print(-1)
            sys.exit()
if A == B:
    print(0)
    sys.exit()
N = max(A) 
T = []
for l in range(N,0,-1):
    S = T + list(range(1,1+l))
    Pa = path(edge(S))
    for i in range(K):
        if B[i] not in Pa[A[i]]:
            break
    else:
        continue
    T.append(l+1)
if not T:
    print(2)
    sys.exit()
if N+1 in T:
    print(-1)
    sys.exit()
print(sum([2**i for i in T]))

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
import sys
def edge(S):
    e = defaultdict(lambda: set())
    for i in range(N+1):
        for j in S:
            e[i].add(i%j)
        e[i] = e[i] | {i}
    return e
def path(edge):
    p = defaultdict(lambda: set())
    for st in range(N+1):
        Q = edge[st]
        p[st] = edge[st]
        new = edge[st]
        while Q:
            for j in Q:
                new = new | edge[j]
            Q = new - p[st]
            p[st] = p[st] | new
    return p

K = int(input())
A = inpl()
B = inpl()
if A == B:
    print(0)
    sys.exit()
N = max(A)
ctr = N 
T = []
S = list(range(1,N+1))
Pa = path(edge(S))
for i in range(K):
    if B[i] not in Pa[A[i]]:
        print(-1)
        sys.exit()
for l in range(N,0,-1):
    S = T + list(range(1,1+l))
    Pa = path(edge(S))
    for i in range(K):
        if B[i] not in Pa[A[i]]:
            break
    else:
        continue
    T.append(l+1)
if not T:
    print(2)
    sys.exit()
print(sum([2**i for i in T]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
x,ans = [],0
def f(m):
	q = [i+1 for i in range(m)]+x
	c = [[True]*51 for i in range(51)]
	for i in q:
		for j in range(i,51): c[j][j%i] = False
	for k in range(51):
		for i in range(51):
			for j in range(51): c[i][j]*=bool(c[i][k]+c[k][j])
	return any(c[a[i]][b[i]] for i in range(n))
if f(50): print(-1)
else:
	for i in range(49,-1,-1):
		if f(i): x.append(i+1)
	for i in x: ans+=2**i
	print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
kai = set()
ans = 0
for m in range(N):
  for i in range(50,0,-1):
    kai.add(i)
  amari = [] 
  for i in kai:
    are = a[m] % i
    amari.append(are)
  for k in range(len(amari)):
    for i in kai:
      are = amari[k] % i
      amari.append(are)
  if b[m] in amari:
    ann = 0
  else:
    ans = -1

for p in range(50,0,-1):
  kai.remove(p)
  for j in range(N):
    amari = [] 
    for i in kai:
      are = a[j] % i
      amari.append(are)
    for k in range(len(amari)):
      for i in kai:
        are = amari[k] % i
        amari.append(are)
    if b[j] in amari:
      ann = 0
    else:
      kai.add(p)
if ans == -1:
   print(-1)
else:
  ans = 0
  for i in kai:
    ans += 2 ** i
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=[]
def bfs(n,start,end):
	c=[set() for i in range(51)]

	for i in range(51):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(51):
	 	c[i].add(i)

	for i in range(51):
		for j in S:
			c[i].add(i%j)

	V=[ None for i in range(51) ]

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False



for i in range(50,0,-1):
	#print i
	for x,y in zip(a,b):
		#print i,x,y,bfs(i,x,y)
		if not bfs(i,x,y):
			if i==50:
				print -1
				quit()
			else:
				S.append(i+1)


ans=0
for i in S:
	ans+=2**i
print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=[]
def bfs(n,start,end):
	c=[set() for i in range(51)]

	for i in range(51):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(51):
	 	c[i].add(i)

	for i in range(51):
		for j in S:
			c[i].add(i%j)

	V=[ None for i in range(51) ]

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False



for i in range(50,0,-1):
	#print i
	for x,y in zip(a,b):
		#print i,x,y,bfs(i,x,y)
		if not bfs(i,x,y):
			if i==50:
				print -1
				quit()
			else:
				S.append(i+1)


ans=0
for i in S:
	ans+=2**i
print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=set()
def bfs(n,start,end):
	if start==end:	return True

	c=[set() for i in range(51)]

	for i in range(1,51):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(1,51):
		for j in S:
	 		c[i].add(i%j)

	V=[ None for i in range(51) ]

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False



for x,y in zip(a,b):
	if not bfs(50,x,y):
		print -1
		quit()


k=50
while k>0:
	#print "=="+str(k)+"=="
	for x,y in zip(a,b):
		#print x,y,bfs(k,x,y)
		if not bfs(k,x,y):
			if k==50:
				print -1
				quit()
			else:
				S.add(k+1)
				k+=1
	k-=1



ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=set()
def bfs(n,start,end):
	if start==end:	return True

	c=[set() for i in range(51)]

	for i in range(1,51):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(1,51):
		for j in S:
	 		c[i].add(i%j)

	V=[ None for i in range(51) ]
	#print V

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False



for x,y in zip(a,b):
	if not bfs(50,x,y):
		print -1
		quit()


k=max(max(a),max(b))
while k>0:
	#print "=="+str(k)+"=="
	for x,y in zip(a,b):
		#print x,y,bfs(k,x,y)
		if not bfs(k,x,y):
			S.add(k+1)
			k+=1
	k-=1



ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=set()
def bfs(n,start,end):
	if start==end:	return True

	c=[set() for i in range(51)]

	for i in range(1,start+1):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(1,start+1):
		for j in S:
	 		c[i].add(i%j)

	V=[ None for i in range(51) ]
	#print V

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False



for x,y in zip(a,b):
	if not bfs(50,x,y):
		print -1
		quit()


k=max(max(a),max(b))
while k>0:
	#print "=="+str(k)+"=="
	for x,y in zip(a,b):
		#print x,y,bfs(k,x,y)
		if not bfs(k,x,y):
			S.add(k+1)
			k+=1
	k-=1



ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=set()
def bfs(n,start,end):
	if start==end:	return True

	c=[set() for i in range(51)]

	for i in range(1,start+1):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(1,start+1):
		c[i].add(i)

	for i in range(1,start+1):
		for j in S:
	 		c[i].add(i%j)

	V=[ None for i in range(51) ]
	#print V

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False





for x,y in zip(a,b):
	if not bfs(50,x,y):
		print -1
		quit()


k=max(a)
while k>0:
	#print "=="+str(k)+"=="
	for x,y in zip(a,b):
		#print x,y,bfs(k,x,y)
		if not bfs(k,x,y):
			S.add(k+1)
			k+=1
	k-=1



ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=set()
def bfs(n,start,end):
	if start==end:	return True

	c=[set() for i in range(51)]

	for i in range(1,start+1):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(1,start+1):
		for j in S:
	 		c[i].add(i%j)

	V=[ None for i in range(51) ]
	#print V

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False


max_a=max(a)


for x,y in zip(a,b):
	if not bfs(50,x,y):
		print -1
		quit()


k=max_a
while k>0:
	#print "=="+str(k)+"=="
	for x,y in zip(a,b):
		#print x,y,bfs(k,x,y)
		if not bfs(k,x,y):
			S.add(k+1)
			k+=1
	k-=1



ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())


S=set()
i=50
cnt=0
flag=""
tmp=[]

while i>0:
	#print "=="
	#print i
	n=i
	# Warshall-Floyd
	dp=[ [ False for y in range(51)] for x in range(51)]
	for j in range(51): dp[j][j]=True

	#print S

	for x in range(1,51):
		for y in S:
			dp[x][x%y]=True 

	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=True

	for k in range(1,51):
		for x in range(1,51):
			for y in range(1,51):
				dp[x][y]=dp[x][y] | (dp[x][k] & dp[k][y])

	for v1,v2 in zip(a,b):
		#print v1,v2,dp[v1][v2]
		if dp[v1][v2] is False:
			if i==50:
				print -1
				quit()
			else:
				S.add(i+1)
				i+=1
				break
	i-=1


ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())


S=set()
i=50
cnt=0
flag=""
tmp=[]

while i>0:
	#print "=="
	#print i
	n=i
	# Warshall-Floyd
	dp=[ [ False for y in range(51)] for x in range(51)]
	for j in range(51): dp[j][j]=True

	#print S

	for x in range(1,51):
		for y in S:
			dp[x][x%y]=True 

	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=True

	for k in range(1,n+1):
		for x in range(1,n+1):
			for y in range(1,n+1):
				dp[x][y]=dp[x][y] | (dp[x][k] & dp[k][y])

	for v1,v2 in zip(a,b):
		#print v1,v2,dp[v1][v2]
		if dp[v1][v2] is False:
			if i==50:
				print -1
				quit()
			else:
				S.add(i+1)
				i+=1
				break
	i-=1


ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())


S=[]
i=50
cnt=0
flag=""
tmp=[]

while i>0:
	#print "=="
	#print i
	n=i
	# Warshall-Floyd
	dp=[ [ False for y in range(51)] for x in range(51)]
	for j in range(51): dp[j][j]=True

	#print S
	for x in range(1,51):
		for y in S:
			dp[x][x%y]=True 

	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=True

	for k in range(1,n+1):
		for x in range(1,n+1):
			for y in range(1,n+1):
				dp[x][y]=dp[x][y] | (dp[x][k] & dp[k][y])

	for v1,v2 in zip(a,b):
		#print v1,v2,dp[v1][v2]
		if dp[v1][v2] is False:
			if i==50:
				print -1
				quit()
			else:
				S.append(i+1)
				i+=1
				break
	i-=1


ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())


S=[]
i=50
cnt=0
flag=""
tmp=[]

while i>0:
	#print "=="
	#print i
	n=i
	# Warshall-Floyd
	dp=[ [float("inf") for y in range(51)] for x in range(51)]
	for j in range(51): dp[j][j]=0

	#print S
	for x in range(1,51):
		for y in S:
			dp[x][x%y]=min( dp[x][x%y] , 0 )

	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=min( dp[x][x%y] , 1)

	for k in range(1,n+1):
		for x in range(1,n+1):
			for y in range(1,n+1):
				dp[x][y]=min( dp[x][y], dp[x][k]+dp[k][y] )

	for v1,v2 in zip(a,b):
		#print v1,v2,dp[v1][v2]
		if dp[v1][v2]==float("inf"):
			if i==50:
				print -1
				quit()
			else:
				S.append(i+1)
				i+=1
				break
	i-=1


ans=0
if len(S)==0:
	if a==b:
		print 0
	else:
		print 2**1
else:
	for i in S:
		ans+=2**i
	print ans

Submission status: Wrong Answer

Solution code:
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())


S=[]
i=50
cnt=0
flag=""
tmp=[]

while i>0:
	#print "=="
	#print i
	n=i
	# Warshall-Floyd
	dp=[ [float("inf") for y in range(51)] for x in range(51)]
	for j in range(51): dp[j][j]=0

	for x in range(1,51):
		for y in S:
			dp[x][x%y]=min( dp[x][x%y] , 0 )

	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=min( dp[x][x%y] , 1)

	for k in range(1,n+1):
		for x in range(1,n+1):
			for y in range(1,n+1):
				dp[x][y]=min( dp[x][y], dp[x][k]+dp[k][y] )

	for v1,v2 in zip(a,b):
		#print v1,v2,dp[v1][v2]
		if dp[v1][v2]==float("inf"):
			if i==50:
				print -1
				quit()
			else:
				S.append(i+1)
				i+=1
				break
	i-=1


ans=0
if len(S)==0:
	print 0
else:
	for i in S:
		ans+=2**i
	print ans