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:
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())
if a==b:
	print 0
	quit()

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

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


	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
	cnt+=1
else:
	if len(S)==0:
		S.append(1)


ans=0
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())
if a==b:
	print 0
	quit()

a_max=max(a)

S=set()
i=a_max
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 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+1 in S:
				i=-100
				flag="Impossible"
			else:
				S.add(i+1)
				i+=1
				break
	i-=1
	cnt+=1
else:
	if flag=="Impossible":
		print -1
		quit()
	if len(S)==0:
		S.add(1)


ans=0
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())
if a==b:
	print 0
	quit()

a_max=max(a)

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

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


	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] , 2**y )

	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+1 in S:
				i=-100
				flag="Impossible"
			else:
				S.append(i+1)
				tmp.append((v1,v2))
				prev=i+1
				i+=1
				break
	i-=1
	cnt+=1
else:
	if flag=="Impossible":
		print -1
		quit()
	if len(S)==0:
		S.append(1)

ans=0
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())
if a==b:
	print 0
	quit()

a_max=max(a)

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

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

	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=min( dp[x][x%y] , 2**y )
	for m,n in tmp:
		dp[m][n]=0

	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 in S:
				i=-100
				flag="Impossible"
			else:
				S.append(i+1)
				tmp.append((v1,v2))
				prev=i+1
				i+=1
	i-=1
	cnt+=1
else:
	if flag=="Impossible":
		print -1
		quit()
	if len(S)==0:
		S.append(1)

ans=0
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())
if a==b:
	print 0
	quit()

a_max=max(a)

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

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

	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=min( dp[x][x%y] , 2**y )
	for m,n in tmp:
		dp[m][n]=0

	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):
		if dp[v1][v2]==float("inf"):
			if i in S:
				i=-100
				flag="Impossible"
			else:
				S.append(i+1)
				tmp.append((v1,v2))
				prev=i+1
				i+=1
	i-=1
	cnt+=1
else:
	if flag=="Impossible":
		print -1
		quit()
	if len(S)==0:
		S.append(1)


ans=0
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())
if a==b:
	print 0
	quit()

a_max=max(a)

S=[]
i=a_max
cnt=0
flag=""

while i>0:
	n=i
	# Warshall-Floyd
	dp=[ [float("inf") for y in range(51)] for x in range(51)]
	for x in range(1,51):
		for y in range(1,n+1):
			dp[x][x%y]=min( dp[x][x%y] , 2**y )
	for x in range(1,51):
		for y in S:
			dp[x][x%y]=min( dp[x][x%y] , 2**y )

	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):
		if dp[v1][v2]==float("inf"):
			if i in S:
				i=-100
				flag="Impossible"
			else:
				S.append(i+1)
				prev=i+1
				i+=1
	i-=1
	cnt+=1
else:
	if flag=="Impossible":
		print -1
		quit()
	if len(S)==0:
		S.append(1)


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

Submission status: Wrong Answer

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**15
mod = 10**9+7

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():
    n = I()
    aa = LI()
    a = [set([_]) for _ in aa]
    b = LI()
    c = [None] * n

    e = [[None]*51 for _ in range(51)]
    for i in range(51):
        for j in range(i+1):
            if i == j:
                e[i][j] = 0
                continue
            for k in range(1,i,1):
                ik = i % k
                if ik == j or ik > j*2:
                    e[i][j] = k
                    break

    for i in range(n):
        if e[aa[i]][b[i]] is None:
            return -1

    def f():
        r = -1
        for i in range(n):
            tr = inf
            for d in a[i]:
                if e[d][b[i]] < tr:
                    tr = e[d][b[i]]
            if r < tr:
                r = tr

        return r

    rr = 0

    while 1:
        k = f()
        if k == 0:
            break
        for i in range(n):
            for c in list(a[i]):
                at = c % k
                if e[at][b[i]] is not None:
                    a[i].add(at)
        rr |= 2**k


    return rr


print(main())

Submission status: Wrong Answer

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**15
mod = 10**9+7

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():
    n = I()
    aa = LI()
    a = [set([_]) for _ in aa]
    b = LI()
    c = [None] * n

    e = [[None]*51 for _ in range(51)]
    for i in range(51):
        for j in range(i+1):
            if i == j:
                e[i][j] = 0
                continue
            for k in range(1,i,1):
                ik = i % k
                if ik == j or ik > j*2:
                    e[i][j] = k
                    break

    for i in range(n):
        if e[aa[i]][b[i]] is None:
            return -1

    def f():
        r = -1
        for i in range(n):
            tr = inf
            for d in a[i]:
                if e[d][b[i]] is None:
                    continue
                if e[d][b[i]] < tr:
                    tr = e[d][b[i]]
            if tr == inf:
                continue
            if r < tr:
                r = tr

        return r

    rr = 0

    while 1:
        k = f()
        if k == 0:
            break
        for i in range(n):
            for c in list(a[i]):
                at = c % k
                if e[at][b[i]] is not None:
                    a[i].add(at)
        rr += 2**k


    return rr


print(main())

Submission status: Wrong Answer

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

candidate = [(a, 0, 0)]
best_score = (False, 2**(max(a)))

while candidate != []:
    c = candidate.pop(0)
    print(c)
    A, prev_k, score = c
    if score >= best_score[1]:
        continue
    index = [i for i in range(len(A)) if A[i] != b[i]]
    if index == []:
        best_score = (True, min(score, best_score[1]))
        continue
    K = [ (i, [k for k in range(b[i] + 1, A[i] + 1) if A[i] % k >= b[i]])  for i in index]
    is_valid = True
    for (i, ks) in K:
        if ks == []:
            is_valid = False
            break
    if not is_valid:
        continue

    for (i, ks) in K:
        for k in ks:
            A2 = A.copy()
            A2[i] %= k
            if k == prev_k:
                candidate.append((A2, k, score))
            else:
                candidate.append((A2, k, score + 2**k))
    candidate.sort(key = lambda c:c[2])
                
if not best_score[0]:
    print(-1)
else:
    print(best_score[1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import copy

huge = 100

def get_k(a, b):
    assert b >= 0 and a >= 0
    if b == a:
        return 0
    if b == 0:
        return 1
    if 2 * b >= a:
        return huge
    for k in range(b + 1, a):
        if a % k == b:
            return k
    return huge

n = int(input())
ai = list(map(int, input().split()))
bi = list(map(int, input().split()))
assert len(ai) == len(bi) == n

achievable = [{ai[i]} for i in range(n)]

res = 0
for roop in range(49):
    max_k = 0
    for i in range(n):
        min_k = huge
        for a in achievable[i]:
            k = get_k(a, bi[i])
            min_k = min(min_k, k)
        max_k = max(max_k, min_k)
    if max_k == huge:
        res = -1
        break
    if max_k == 0:
        break
    for i in range(n):
        ach_pre = copy.deepcopy(achievable[i])
        for a in ach_pre:
            achievable[i].add(a % max_k)
    res += 2 ** max_k

print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

huge = 100

def get_k(a, b):
    assert b >= 0 and a >= 0
    if b == a:
        return 0
    if b == 0:
        return 1
    if 2 * b >= a:
        return huge
    for k in range(b + 1, a):
        if a % k == b:
            return k
    return huge

n = int(input())
ai = list(map(int, input().split()))
bi = list(map(int, input().split()))
assert len(ai) == len(bi) == n

achievable = [{ai[i]} for i in range(n)]

res = 0
for roop in range(49):
    max_k = 0
    print(achievable)
    for i in range(n):
        min_k = huge
        for a in achievable[i]:
            k = get_k(a, bi[i])
            min_k = min(min_k, k)
        max_k = max(max_k, min_k)
    if max_k == huge:
        res = -1
        break
    if max_k == 0:
        break
    for i in range(n):
        achievable[i].add(a % max_k)
    res += 2 ** max_k

print(res)

Submission status: Wrong Answer

Solution code:
def pos(a, b, seq):
	st = set([a])
	for k in seq:
		new_st = set(st)
		for v in st:
			new_st.add(v%k)
		st = new_st
	return b in st
	
def main():
	n = input()
	aa = map(int, raw_input().split())
	bb = map(int, raw_input().split())
	def ok(seq):
		for a,b in zip(aa,bb):
			if not pos(a,b,seq):
				return False
		return True
	u = []
	for j in xrange(60,0,-1):
		if not ok(u + range(1,j)):
			u.append(j)
	#print u
	if 59 in u:
		print -1
		return
	else:
		print sum(2**k for k in u)

main()

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()]
flag=0
for i in range(N):
    if (a[i]-1)//2<b[i]:
        flag=1
        break
if flag==1:
    print(-1)
else:
    k=[0 for i in range(N)]
    #それぞれに１回ずつやった場合
    for i in range(N):
        for j in range(1,a[i]+1):
            if a[i]%j==b[i]:
                k[i]=j
                break
    S=set(k)
    T=0
    for n in S:
        T+=2**n
    print(T)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from collections import defaultdict
from collections import Counter

hoge = {}
for a in range(1, 51):
    hoge[a] = defaultdict(list)
    for b in range(1, 51):
        hoge[a][a % b].append(b)


def main():
    N = int(input().strip())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    ans = 0

    while True:
        k = []
        for i in range(N):
            if A[i] != 0 and A[i] != B[i]:
                if not hoge[A[i]][B[i]]:
                    return -1
                k.append(hoge[A[i]][B[i]])
        if not k:
            break
        # k = min(map(lambda a: min(a), k))
        ks = Counter()
        for x in k:
            for y in x:
                ks[y] += 1
        k = ks.most_common(1)[0][0]

        ans += 2**k
        for i in range(N):
            if A[i] % k == B[i]:
                A[i] = B[i]
    return ans


if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from collections import defaultdict

hoge = {}
for a in range(1, 51):
    hoge[a] = defaultdict(list)
    for b in range(1, 51):
        hoge[a][a % b].append(b)


def main():
    N = int(input().strip())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    ans = 0

    while True:
        k = []
        for i in range(N):
            if A[i] != 0 and A[i] != B[i]:
                if not hoge[A[i]][B[i]]:
                    return -1
                k.append(hoge[A[i]][B[i]])
        if not k:
            break
        k = min(map(lambda a: min(a), k))
        ans += 2**k
        for i in range(N):
            if A[i] % k == B[i]:
                A[i] = B[i]
    return ans


if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

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

candidate = [(a, b, 0, 0)]
best_score = (False, 2**(max(a)))

while candidate != []:
    c = candidate.pop(0)
    A, B, prev_k, score = c
    if score >= best_score[1]:
        continue
    index = [i for i in range(len(A)) if A[i] != B[i]]
    if index == []:
        best_score = (True, min(score, best_score[1]))
        continue
    K = [ (i, [k for k in range(B[i] + 1, A[i] + 1) if A[i] % k >= B[i]])  for i in index]
    is_valid = True
    for (i, ks) in K:
        if ks == []:
            is_valid = False
            break
    if not is_valid:
        continue

    for (i, ks) in K:
        for k in ks:
            A2 = A.copy()
            A2[i] %= k
            if k == prev_k:
                candidate.append((A2, B, k, score))
            else:
                candidate.append((A2, B, k, score + 2**k))
                
if not best_score[0]:
    print(-1)
else:
    print(best_score[1])