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: Accepted

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

if any([a < b for a,b in zip(A,B)]):
    print(-1)
    exit()
if A == B:
    print(0)
    exit()


def reachable(a,b,gr):
    if a == b: return True
    assert a > b
    visited = [0] * (a+1)
    stack = [a]
    while stack:
        v = stack.pop()
        if v == b: return True
        visited[v] = 1
        for to in gr[v]:
            if visited[to]: continue
            stack.append(to)
    return False

permanent_use = []

def need(n):
    gr = [set() for i in range(51)]
    for i in range(51):
        for p in permanent_use:
            gr[i].add(i%p)
        for j in range(1,n):
            gr[i].add(i%j)
    for a,b in zip(A,B):
        if not reachable(a,b,gr):
            return True
    return False

if need(51):
    print(-1)
    exit()

for i in range(50,0,-1):
    if need(i):
        permanent_use.append(i)

ans = 0
for p in permanent_use:
    ans += 2**p
print(ans)

Submission status: Accepted

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,-1,-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: Accepted

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 range(51): c[i][i] = False
	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: Accepted

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)
elif a == b:
  print(0)
else:
  ans = 0
  for i in kai:
    ans += 2 ** i
  print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xs = [int(c) for c in input().split()]
ys = [int(c) for c in input().split()]

def dp(x, y, mods):
  if y > x:
    return False
  table = [False] * (x + 1)
  table[x] = True
  mods.sort(reverse=True)
  for mod in mods:
    for i in range(x + 1):
      table[i % mod] = table[i % mod] or table[i]
  return table[y]

def ok(mods):
  return all(dp(x, y, list(mods)) for x, y in zip(xs, ys))

if not ok(range(1, 51)):
  print(-1)
  quit(0)

mods = []
for mod in range(50, 0, -1):
  if not ok(mods + list(range(1, mod))):
    mods.append(mod)

print(sum(2 ** mod for mod in mods))

Submission status: Accepted

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,-1,-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: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def make_graph(m):
    matrix = np.zeros([m + 1, m + 1, m + 1])
    for k in range(1, m + 1):
        for s in range(k, m + 1):
            matrix[k, s, s % k] = 1
    return matrix


def is_disable(matrix, subset, aaa, bbb):
    if subset:
        sub_matrix = matrix[list(subset)].max(axis=0)
    else:
        sub_matrix = matrix[0]
    sp = floyd_warshall(sub_matrix)
    return any(sp[a, b] > 50 for a, b in zip(aaa, bbb))


def solve(aaa, bbb):
    for a, b in zip(aaa, bbb):
        if a < b:
            return -1
    m = max(aaa)
    matrix = make_graph(m)
    subset = set(range(1, m + 1))
    if is_disable(matrix, subset, aaa, bbb):
        return -1

    for k in range(m, 0, -1):
        subset.remove(k)
        if is_disable(matrix, subset, aaa, bbb):
            subset.add(k)
    return sum(1 << k for k in subset)


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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra


def make_graph(m, subset):
    matrix = [[0] * (m + 1) for _ in range(m + 1)]
    for k in subset:
        for s in range(k, m + 1):
            matrix[s][s % k] = 1
    return dijkstra(matrix)


def solve(n, aaa, bbb):
    for a, b in zip(aaa, bbb):
        if a < b:
            return -1
    m = max(aaa)
    subset = set(range(1, m + 1))
    sp = make_graph(m, subset)
    if any(sp[a, b] > 50 for a, b in zip(aaa, bbb)):
        return -1

    for k in range(m, 0, -1):
        subset.remove(k)
        sp = make_graph(m, subset)
        if any(sp[a, b] > 50 for a, b in zip(aaa, bbb)):
            subset.add(k)
    return sum(1 << k for k in subset)


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

Submission status: Accepted

Solution code:
def solve(a, b):
    if a == b:
        yield []
    if a > b:
        for i in range(1, a+1):
            for x in solve(a % i, b):
                yield [i] + x

def subseq(a, b):
    if len(b) == 0: return True
    x = 0
    for t in a:
        if t == b[x]:
            x += 1
            if x == len(b):
                return True
    return False

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

R = []

for i in range(n):
    R.append(list(solve(A[i], B[i])))
    if len(R[-1]) == 0:
        print(-1)
        exit(0)

L = []
answer = 0

for i in range(50, 0, -1):
    T = L + list(range(i - 1, 0, -1))

    ok = True

    for j in range(n):
        cur = False

        for seq in R[j]:
            if subseq(T, seq):
                cur = True
                break

        if not cur:
            ok = False
            break

    if not ok:
        L.append(i)
        answer += 2**i

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N = int(input())
A = inpl()
B = inpl()
for a, b in zip(A, B):
    if a < b:
        print(-1)
        exit()
        
M = max(max(A), max(B))

S = [i for i in range(1, M+1)]
T = len(S)

def dfs(a, b, G):
    visited = [False]*(M+1)
    Q = [a]
    while Q:
        p = Q.pop()
        if visited[p]:
            continue
        else:
            visited[p] = True
            for q in G[p]:
                if q == b:
                    return True
                if not visited[q]:
                    Q.append(q)
    else:
        return False

found = False
for i in range(M, 0, -1):
    del S[S.index(i)]
    G = [set() for _ in range(M+1)]
    for j in range(1, M+1):
        for s in S:
            G[j].add(j%s)
    
    for a, b in zip(A, B):
        if a==b:
            continue
        if not dfs(a, b, G):
            S.append(i)
            break
    else:
        found = True

ans = 0
for s in S:
    ans += 2**s

if found:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**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()

    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
            if j == 0:
                e[i][0] = 1
                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: Accepted

Solution code:
from itertools import chain

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

IMP = 100

dp = [[IMP for _ in range(51)] for _ in range(51)]

for i in range(51):
  dp[i][i] = 0
  for j in range(i):
    for m in range(1,51):
      if dp[i%m][j] != IMP:
        dp[i][j] = m
        break


if max(dp[x][y] for x,y in zip(A,B)) == IMP:
  print(-1)
else:
  cost = 0
  m = max(dp[x][y] for x,y in zip(A,B))
  AL = [{a} for a in A]

  def candmin(al,b):
    m = min(dp[a][b] for a in al)
    al.discard(a for a in al if dp[a][b] > m)
    return m

  while m != 0:
    for i,(al,b) in enumerate(zip(AL,B)):
      AL[i] |= set(a%m for a in al)
    cost += 2**m

    m = max(candmin(al,b) for al,b in zip(AL,B))

  print(cost)

Submission status: Accepted

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(j-1,0,-1)):
			u.append(j)
	#print u
	if 59 in u:
		print -1
		return
	else:
		print sum(2**k for k in u)

main()

Submission status: Runtime Error

Solution code:
def rem(x,r):
  if (x,r) == (1,0):
    return [[1]]
  if x <= 2*r:
    return -1
  ret = []
  for i in range(1,x+1):
    if x%i == r:
      ret.append([i])
    else:
      s = rem(x%i,r)
      if s == -1:
        continue
      else:
        for j in s:
          if j == -1:
            continue
          elif j[-1] < i:
            ret.append([i]+j)
          else:
            ret.append([i]+j)
  return ret
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
for xx,yy in zip(x,y):
  if xx != yy and rem(xx,yy) == -1:
    print(-1)
    exit()
ls = [rem(xx,yy) if xx != yy else 0 for xx,yy in zip(x,y)]
flg = [0]*n
def findmx(lsi,ansst,mx):
  ret = 100
  if lsi == 0:
    return 0
  for lsls in lsi:
    for j in lsls:
      if j > mx:
        return min(j,ret)
      elif j in ansst:
        continue
      else:
        ret = min(j,ret)
        break
    else:
      return 0
mxls = [ls[i][0][0] if type(ls[i]) == list else 0 for i in range(n)]
mx = max(mxls)
ansst = set((mx,))
mxcand = mx
while mxcand:
  for i in range(n):
    t = findmx(ls[i],ansst,mx)
    mxls[i] = t
    if t == 0:
      flg[i] = 1
  mxcand = max(mxls)
  ansst.add(mxcand)
  if flg.count(1) == n:
    break
ans = 0
for b in ansst:
  if b:
    ans += 2**b
print(ans)

Submission status: Runtime Error

Solution code:
def rem(x,r):
  if x <= 2*r:
    return -1
  ret = []
  for i in range(1,x):
    if x%i == r:
      ret.append([i])
    else:
      s = rem(x%i,r)
      if s == -1:
        continue
      else:
        for j in s:
          if j == -1:
            continue
          elif j[-1] < i:
            ret.append([i]+j)
          else:
            ret.append([i]+j)
  return ret
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
for xx,yy in zip(x,y):
  if xx != yy and rem(xx,yy) == -1:
    print(-1)
    exit()
ls = [rem(xx,yy) if xx != yy else 0 for xx,yy in zip(x,y)]
mxls = [ls[i][0][0] if type(ls[i]) == list else 0 for i in range(n)]
mx = max(mxls)
ansst = set()
ansst.add(mx)
flg = [0]*n
while mx:
  for i in range(n):
    if x[i]%mx == y[i]:
      flg[i] = 1
      mxls[i] = 0
      continue
    r = rem(x[i]%mx,y[i])
    if r != -1 and r[0][0] <= mxls[i]:
      mxls[i] = r[0][0]
      x[i] %= mx
  mx = max(mxls)
  ansst.add(mx)
  if flg.count(1) == n:
    break
ans = -1
for b in ansst:
  ans += 2**b
print(ans)

Submission status: Runtime Error

Solution code:
def rem(x,r):
  if x <= 2*r:
    return -1
  ret = []
  for i in range(1,x):
    if x%i == r:
      ret.append([i])
    else:
      s = rem(x%i,r)
      if s == -1:
        continue
      else:
        for j in s:
          if j == -1:
            continue
          elif j[-1] < i:
            ret.append([i]+j)
          else:
            ret.append([i]+j)
  return ret
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
for xx,yy in zip(x,y):
  if xx != yy and rem(xx,yy) == -1:
    print(-1)
    exit()
ls = [rem(xx,yy) if xx != yy else 0 for xx,yy in zip(x,y)]
mxls = [ls[i][0][0] if type(ls[i]) == list else 0 for i in range(n)]
mx = max(mxls)
ansst = set()
ansst.add(mx)
flg = [0]*n
while True:
  for i in range(n):
    if x[i]%mx == y[i]:
      flg[i] = 1
      mxls[i] = 0
      continue
    r = rem(x[i]%mx,y[i])
    if r != -1 and r[0][0] <= mxls[i]:
      mxls[i] = r[0][0]
      x[i] %= mx
  mx = max(mxls)
  ansst.add(mx)
  if flg.count(1) == n:
    break
ans = -1
for b in ansst:
  ans += 2**b
print(ans)

Submission status: Runtime Error

Solution code:
def rem(x,r):
  if x <= 2*r:
    return -1
  ret = []
  for i in range(1,x):
    if x%i == r:
      ret.append([i])
    else:
      s = rem(x%i,r)
      if s == -1:
        continue
      else:
        for j in s:
          if j == -1:
            continue
          elif j[-1] < i:
            ret.append([i]+j)
          else:
            ret.append([i]+j)
  return ret
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
for xx,yy in zip(x,y):
  if xx != yy and rem(xx,yy) == -1:
    print(-1)
    exit()
ls = [rem(xx,yy) if xx != yy else 0 for xx,yy in zip(x,y)]
mxls = [ls[i][0][0] if type(ls[i]) == list else 0 for i in range(n)]
mx = max(mxls)
ansst = set()
ansst.add(mx)
flg = [0]*n
while True:
  for i in range(n):
    if mxls[i] == mx or x[i]%mx == y[i]:
      flg[i] = 1
      mxls[i] = 0
      continue
    r = rem(x[i]%mx,y[i])
    if r != -1 and r[0][0] <= mxls[i]:
      mxls[i] = r[0][0]
      x[i] %= mx
  mx = max(mxls)
  ansst.add(mx)
  if flg.count(1) == n:
    break
ans = -1
for b in ansst:
  ans += 2**b
print(ans)

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
a,b=a[:n],a[n:]
for a,b in zip(a,b):
    if a==b:continue
    if b>a:
        print(-1)
        exit()
    if a-b<b:
        print(-1)
        exit()
1/0

Submission status: Runtime Error

Solution code:
n = int(input())
xs = [int(c) for c in input().split()]
ys = [int(c) for c in input().split()]

def dp(x, y, mods):
  table = [False] * (x + 1)
  table[x] = True
  mods.sort(reverse=True)
  for mod in mods:
    for i in range(x + 1):
      table[i % mod] = table[i % mod] or table[i]
  return table[y]

def ok(mods):
  return all(dp(x, y, list(mods)) for x, y in zip(xs, ys))

if not ok(range(1, 51)):
  print(-1)
  quit(0)

mods = []
for mod in range(50, 0, -1):
  if not ok(mods + list(range(1, mod))):
    mods.append(mod)

print(sum(2 ** mod for mod in mods))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def make_graph(m):
    matrix = np.zeros([m + 1, m + 1, m + 1])
    for k in range(1, m + 1):
        for s in range(k, m + 1):
            matrix[k, s, s % k] = 1
    return matrix


def is_disable(matrix, subset, aaa, bbb):
    sub_matrix = matrix[list(subset)].max(axis=0)
    sp = floyd_warshall(sub_matrix)
    return any(sp[a, b] > 50 for a, b in zip(aaa, bbb))


def solve(aaa, bbb):
    for a, b in zip(aaa, bbb):
        if a < b:
            return -1
    m = max(aaa)
    matrix = make_graph(m)
    subset = set(range(1, m + 1))
    if is_disable(matrix, subset, aaa, bbb):
        return -1

    for k in range(m, 0, -1):
        subset.remove(k)
        if is_disable(matrix, subset, aaa, bbb):
            subset.add(k)
    return sum(1 << k for k in subset)


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