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: Time Limit Exceeded

Solution code:
class Solver:

    def __init__(self):
        self.move_map = [{} for _ in range(51)]
        self.calc_one_step()
        self.compress()
        self.best_cost = float('inf')

    @staticmethod
    def cost(a):
        return sum(2 ** i for i in a)

    @staticmethod
    def prod(now, aa, bb):
        for a in aa:
            for b in bb:
                now.add(a + b)
        return now

    def calc_one_step(self):
        for i in range(51):
            for j in range(1, i + 1):
                m = i % j
                if m not in self.move_map[i]:
                    self.move_map[i][m] = {(j,)}
                else:
                    self.move_map[i][m].add((j,))

    def compress(self):
        for i in range(51):
            self.move_map[i] = self._comp(i)

    def _comp(self, n):
        new = self.move_map[n].copy()
        for m, a in self.move_map[n].items():
            for mm, aa in self.move_map[m].items():
                if mm not in new:
                    new[mm] = aa
                else:
                    self.prod(new[mm], a, aa)
        return new

    def solve(self, start, goal):
        path_list = []
        for s, g in zip(start, goal):
            if s == g:
                continue
            path = self.move_map[s].get(g)
            if path is None:
                self.best_cost = -1
                return
            path_list.append(path)
        self._solve(0, path_list, [])

    def _solve(self, cost, path_list, divs):
        if not path_list:
            if cost < self.best_cost:
                self.best_cost = cost
            return
        for one, new_list in self.iter_one(path_list):
            d = divs + [one]
            c = cost + 2 ** one
            if c >= self.best_cost:
                break
            elif not new_list and c < self.best_cost:
                self.best_cost = c
            else:
                self._solve(c, new_list, d)

    def iter_one(self, path_list):
        ones = set()
        for path_set in path_list:
            for path in path_set:
                ones.add(path[0])
        for one in sorted(ones):
            new_list = []
            for path_set in path_list:
                new_set = set()
                for path in path_set:
                    if path[0] == one:
                        path = path[1:]
                        if not path:
                            break
                    new_set.add(path)
                else:
                    new_list.append(new_set)
            yield one, new_list


def main():
    solver = Solver()
    int(input())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    solver.solve(start, goal)
    print(solver.best_cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
G=[]
def g(x):
  global G
  G=[]
  for i in range(51):
    G.append([])
    for j in range(1,i+1):
      if x&(1<<j):
        G[i].append((i%j,0))

from heapq import *
D=[0]*51
INF=1000
def ijk(s):
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
def j(x):
  g(x)
  for i in range(N):
    ijk(A[i])
    if D[B[i]]>=INF:
      return 0
  return 1

X=-1
for i in range(1,52):
  if j((1<<i)-1):
    X=(1<<i)-1
    break
if X==-1:
  print(-1)
  exit()
for i in range(51,-1,-1):
  if X&(1<<i):
    if j(X^(1<<i)):
      X^=(1<<i)
print(X)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# a->b, possible with using at most c as max
T = [[[None] * 51 for _ in range(51)] for _ in range(51)]

def dp(a, b, c):
  if T[a][b][c] is not None:
    return T[a][b][c]
  if a == b:
    T[a][b][c] = True
    return T[a][b][c] 
 # if c == 0:
 #   T[a][b][c] = b == 0
 #   return T[a][b][c] 
  if b >= c or a < b:
    T[a][b][c] = False
    return T[a][b][c] 
  if dp(a, b, c-1):
    T[a][b][c] = True
    return T[a][b][c] 
  else:
    T[a][b][c] = dp(a % c, b, c-1)
    return T[a][b][c]

T2 = [[None] * 51 for _ in range(51)]
def min_c(a, b):
  if T2[a][b] is not None:
    return T2[a][b]
  for c in range(51):
    if dp(a,b,c):
      T2[a][b] = c
      return T2[a][b]
  T2[a][b] = 51
  return T2[a][b]

#print(min_c(14,0))
#print(min_c(14,4))
  
def solve():
  count = 0
  for a, b in zip(A,B):
    if a < b:
      print(-1)
      return
    if a > b:
      count += 1
#  print(count)
#  print(list(zip(A, B)))
 # return
  
  cost = 0
  ABs = [{(a, b)} if a > b else set() for a, b in zip(A,B)]
  while count:
    # min->max
    mm = [min(min_c(a, b) for a, b in s) if s else 0 for s in ABs]
    m = max(mm)
    if m > 50:
      print(-1)
      return
    
    cost += 2 ** m
    for i in range(len(ABs)):
      if mm[i] == m:
        new_s = set()
        done = False
        for a, b in ABs[i]:
          if min_c(a % m, b) == 0:
            done = True
            break
          elif min_c(a, b) == m:
            new_s.add((a % m, b))
        if done:
          count -= 1
          ABs[i] = set()
        else:
          ABs[i] = new_s
      else:  # optional
        new_s = set()
        done = False
        for a, b in ABs[i]:
          if min_c(a % m, b) == 0:
            done = True
            break
          elif min_c(a % m, b) < m:
            new_s.add((a % m, b))
        if done:
          count -= 1
          ABs[i] = set()
        else:
          ABs[i].update(new_s)
        
  print(cost)
    
    
    

solve()

Submission status: Accepted

Solution code:
cost={(i,j):[] for i in range(51) for j in range(51)}
def dfs(nf,c,fr,to):
    if nf==to:
        cost[(fr,to)].append(c)
        return 0

    if to*2+1>nf:
        return 0

    for i in range(1,nf+1):
        dfs(nf%i,c+2**i,fr,to)


for i in range(1,51):
    for j in range(51):
        dfs(i,0,i,j)
        cost[(i,j)].sort()

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

for i in range(51):
    cost[(i,i)].append(0)

for i in range(N):
    if not cost[(a[i],b[i])]:
        print(-1)
        exit()

ans=0
k=50
while k>0:
    check=False
    for i in range(N):
        test=cost[(a[i],b[i])][0]
        if test>>k &1==1:
            check=True

    if check:
        ans+=2**k
        for i in range(N):
            for j in range(len(cost[(a[i],b[i])])):
                c=cost[(a[i],b[i])][j]
                if c>>k &1==1:
                    cost[(a[i],b[i])][j]-=2**k
            cost[(a[i],b[i])].sort()
    k-=1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    d = [[None]*51 for _ in [0]*51]  # 目的のあまり、現在の数値
    for i in range(51):
        d[i][i] = [[]]
    for i in range(51):  # あまり
        for j in range(i+1, 51):  # 現在の数値
            temp = []
            for kk in range(1, j+1):  # 割る数
                k = j % kk
                if d[i][k] is None:
                    continue
                for l in d[i][k]:
                    temp += [l+[kk]]
            if temp == []:
                temp = None
            d[i][j] = temp
    c = [d[bb][aa] for aa, bb in zip(a, b)]
    if None in c:
        print(-1)
        return
    ans = 0
    while True:
        M = -1
        for i in range(n):
            if [] in c[i]:
                c[i] = [[]]
            else:
                m = min([j[-1] for j in c[i]])
                M = max(M, m)
        if M == -1:
            break
        ans += 2**M
        for i in range(n):
            temp = []
            if c[i] == [[]]:
                continue
            for j in c[i]:
                if j[-1] == M:
                    temp.append(j[:-1])
                elif j[-1] < M:
                    temp.append(j)
            c[i] = temp
    print(ans)


main()

Submission status: Accepted

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

    canReach = [[[False for _ in range(51)] for _ in range(N)] for _ in range(50)]  # k, n, a

    for k in range(50):
        for n in range(N):
            canReach[k][n][B[n]] = True

    for k in range(1, 50):
        for n in range(N):
            for a in range(51):
                if canReach[k - 1][n][a] or canReach[k - 1][n][a % k]:
                    canReach[k][n][a] = True

    aList = [[[False for _ in range(51)] for _ in range(N)] for _ in range(50)]  # k, n, a
    for n in range(N):
        aList[49][n][A[n]] = True

    ans = 0
    for k in reversed(range(1, 50)):
        # 到達可能かどうかチェック
        for n in range(N):
            judge = False
            for a in range(51):
                if aList[k][n][a] and canReach[k][n][a]:
                    judge = True
                    break
            if not judge:
                print(-1)
                exit()
        # kを使わないで行けるかどうかチェック
        shouldUseK = False
        for n in range(N):
            judge = False
            for a in range(51):
                if aList[k][n][a] and canReach[k - 1][n][a]:
                    judge = True
                    break
            if not judge:
                shouldUseK = True
                break

        if shouldUseK:
            ans += 2 ** k
            for n in range(N):
                for a in range(51):
                    if aList[k][n][a]:
                        aList[k - 1][n][a] = True
                        aList[k - 1][n][a % k] = True
        else:
            for n in range(N):
                for a in range(51):
                    if aList[k][n][a]:
                        aList[k - 1][n][a] = True

    print(ans)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc022/tasks/agc022_c


ある　t 以下のkで全て終わらせる < t+1を使う
なので、まず答えを満たすのに必要な最小の最大値を求める必要がある
大きい奴は使わない方がよい
→これを使わなくても答えが成立しうるか？を上から決めてく

計算量不安だけど平気そう
"""

def able(na,nb,lis):

    if na < nb:
        return False
    elif na == nb:
        return True
    
    q = {}
    q[na] = 1
    for i in range(50,0,-1):

        temp = []
        if not lis[i]:
            continue
        
        for j in q:

            if j % i == nb:
                return True
            elif j % i > nb:
                temp.append(j % i)

        for j in temp:
            q[j] = 1

    return False
            

N = int(input())

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

lis = [True] * 51

import sys

for j in range(N):
    if not able(a[j],b[j],lis):
        print (-1)
        sys.exit()

for i in range(50,0,-1):

    lis[i] = False
    for j in range(N):

        ret = able(a[j],b[j],lis)

        if not ret:
            lis[i] = True
            break

ans = 0
for i in range(1,51):
    if lis[i]:
        ans += 2**i
print (ans)

Submission status: Accepted

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
  else:
    return ret
    
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: Accepted

Solution code:
def solve(bit_state, num, mod):
    for div in range(1, num + 1):
        if num % div == mod:
            cand[i].append(bit_state | (1 << div))
        if num % div > mod:
            solve(bit_state | (1 << div), num % div, mod)


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

cand = [[] for i in range(n)]
for i in range(n):
    solve(0, a[i], b[i])
    if a[i] == b[i]:
        cand[i].append(0)

ans = 0
while True:
    max_ = 0
    for j in range(n):
        min_ = 10 ** 5
        for num in cand[j]:
            min_ = min(min_, num.bit_length() - 1)
        max_ = max(max_, min_)

    if max_ == 0:
        print(ans)
        break
    if max_ == 10 ** 5:
        print(-1)
        break
    ans += 2 ** max_
    
    tmp = [[] for i in range(n)]
    for j in range(n):
        for num in cand[j]:
            if num & (1 << max_):
                tmp[j].append(num - (1 << max_))
            else:
                tmp[j].append(num)
    cand = tmp[0:]

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))

graph = [[] for _ in range(51)]
for i in range(51):
    for k in range(1, i + 1):
        # i から i%k に k を使って行ける
        graph[i].append((i % k, k))

memo = [[None] * 51 for _ in range(51)]


def can_go(s, t, graph):
    if s == t:
        return True
    if memo[s][t] is not None:
        return memo[s][t]
    ret = False
    for u, _ in graph[s]:
        if can_go(u, t, graph):
            ret = True
            break
    memo[s][t] = ret
    return ret


ok = True
for a, b in zip(A, B):
    ok &= can_go(a, b, graph)
# 同頑張っても無理
if not ok:
    print(-1)
    exit()

ans = 0
# ある k を使うだけで、0 から k-1 までのすべてを使うよりもコストが大きくなる
# →k の大きい順に使うか使わないかを決められる。
for k in reversed(range(51)):
    # k を使わないグラフを構築
    next_graph = [[] for _ in range(51)]
    for v in range(len(graph)):
        for u, w in graph[v]:
            if w != k:
                next_graph[v].append((u, w))
    memo = [[None] * 51 for _ in range(51)]
    ok = True
    for a, b in zip(A, B):
        ok &= can_go(a, b, next_graph)
    if ok:
        # この k は使わなくていい
        graph = next_graph
    else:
        # この k は必要
        ans += 1 << k
print(ans)
# print(bin(ans))

Submission status: Accepted

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():

    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

    use = 0
    for l in reversed(range(1, 52)):
        for a, b in zip(A, B):
            ok = False
            q = [b]
            checked = [False]*51
            checked[b] = True
            while q:
                qq = []
                for p in q:
                    if p == a:
                        ok = True
                        break
                    for cost, np in graph[p]:
                        if not checked[np] and (cost < l or use&(1<<cost)):
                            checked[np] = True
                            qq.append(np)
                if ok: break
                q = qq
            if not ok:
                if l == 51:
                    return -1
                use |= (1<<l)
                break
    return use

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    b = LI()
    ans = 0
    l = []
    m = 51
    for num in range(1,m+1)[::-1]:
        res = list(range(1,num))+l
        d = [[0 if i == j else float("inf") for j in range(m)] for i in range(m)]
        for k in res:
            for i in range(m):
                d[i][i%k] = 0
        for k in range(m):
            for i in range(m):
                for j in range(m):
                    nd = d[i][k]+d[k][j]
                    if nd < d[i][j]:
                        d[i][j] = nd

        for i in range(n):
            if d[a[i]][b[i]] == float("inf"):
                break
        else:
            continue
        if num == m:
            print(-1)
            return
        else:
            ans += 1<<num
            l.append(num)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(adj, s, t, use):
    if s == t:
        return 1
    que = deque()
    seen = [0] * len(adj)
    que.append(s)
    seen[s] = 1
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == 0 and use[cost] == 1:
                if u == t:
                    return 1
                seen[u] = 1
                que.append(u)
    return 0


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

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

use = [1] * 51
use[0] = 0
for i in range(50, 0, -1):
    use[i] = 0
    for ai, bi in zip(a, b):
        if not bfs(adj, ai, bi, use):
            use[i] = 1
            break

if sum(use) == 50:
    print(-1)
    exit()

print(sum([(2**i) * use[i] for i in range(51)]))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n,*a=map(int,open(0).read().split())
a,b=a[:n],a[n:]
d=[]
M=max(a)
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(-(len(d)==M)or sum(2**k for k in d))

Submission status: Accepted

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

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

Solution code:
from collections import deque
def BFS_dist(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

M = 51
X = [[] for _ in range(M)]
for i in range(1, M):
    for j in range(1, i+1):
        X[i].append([i%j, 2**j])

def chk(S):
    M = 51
    X = [[] for _ in range(M)]
    for j in S:
        for i in range(j, M):
            X[i].append(i%j)
    DI = []
    for i in range(M):
        DI.append(BFS_dist(M, X, i))
    for i in range(N):
        if DI[A[i]][B[i]] < 0:
            return 0
    return 1

L1 = [i for i in range(1, 51)]
L2 = []
if chk(L1) == 0:
    print(-1)
else:
    while L1:
        while True:
            if chk(L1 + L2):
                if len(L1) == 0:
                    break
                L1.pop()
            else:
                L2.append(L1[-1]+1 if L1 else 1)
                L1 = [i for i in range(1, L2[-1])]
                break
        if len(L1) == 0:
            break

    print(sum([1<<l for l in L2]))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush as hpush, heappop as hpop
def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

M = 51
X = [[] for _ in range(M)]
for i in range(1, M):
    for j in range(1, i+1):
        X[i].append([i%j, 2**j])

def chk(S):
    M = 51
    X = [[] for _ in range(M)]
    for j in S:
        for i in range(j, M):
            X[i].append([i%j, 2**j])
    DI = []
    for i in range(M):
        DI.append(dijkstra(M, X, i))
    for i in range(N):
        if DI[A[i]][B[i]] < 0:
            return 0
    return 1

L1 = [i for i in range(1, 51)]
L2 = []
if chk(L1) == 0:
    print(-1)
else:
    while L1:
        while True:
            if chk(L1 + L2):
                if len(L1) == 0:
                    break
                L1.pop()
            else:
                L2.append(L1[-1]+1 if L1 else 1)
                L1 = [i for i in range(1, L2[-1])]
                break
        if len(L1) == 0:
            break

    print(sum([1<<l for l in L2]))

Submission status: Accepted

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

import numpy as np

N = int(input())
A = np.array(input().split(), dtype=np.int8)
B = np.array(input().split(), dtype=np.int8)

def test(li):
    # xをyにできる
    can_make = np.eye(51,dtype=np.bool)
    for k in li:
        can_make |= can_make[np.arange(51)[:,None]%k,np.arange(51)[None,:]]
    return can_make[A,B].all()

if not test(list(range(1,51))):
    print(-1)
    exit()

use = []
x = 50
while x:
    if test(use):
        break
    for y in range(1,x+1):
        if test(list(range(1,y+1)) + use):
            use = [y] + use
            x = y-1
            break

answer = sum(1<<x for x in use)
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

isEssentials = [False] * 51
for k in reversed(range(1, 52)):
    adjL = [set() for _ in range(51)]
    for v in range(1, 51):
        for t in range(1, v+1):
            if t < k or isEssentials[t]:
                adjL[v].add(v%t)
        adjL[v] = list(adjL[v])

    for A, B in zip(As, Bs):
        isOK = False
        useds = [False] * 51
        Q = deque([A])
        while Q:
            vNow = Q.popleft()
            if vNow == B:
                isOK = True
                break
            useds[vNow] = True
            for v2 in adjL[vNow]:
                if not useds[v2]:
                    Q.append(v2)
        if not isOK:
            if k == 51:
                print(-1)
                sys.exit()
            isEssentials[k] = True
            break

ans = sum([2**k for k in range(1, 51) if isEssentials[k]])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
D = [[False] * 51 for i in range(51)]
use = []


def calc(a, b, D):
    if a == b:
        return True
    d = {}
    stack = [a]
    while stack:
        u = stack.pop()
        if u == b:
            return True
        d[u] = 1
        for w in range(1, 51):
            if (u % w) in d:
                continue
            if D[u][u % w]:
                stack.append(u % w)

    return False


def check(n):
    D = [[False] * 51 for i in range(51)]
    for i in range(51):
        for k in range(1, n):
            D[i][i % k] = True
        D[i][i] = True

    for i in range(51):
        for j in use:
            D[i][i % j] = True

    for a, b in zip(A, B):
        if not calc(a, b, D):
            return True
    return False


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

ans = 0
for j in range(50, 0, -1):
    if check(j):
        use.append(j)
        ans += 2 ** j

print(ans)

Submission status: Accepted

Solution code:
INF = 1<<60
d = [[INF]*51 for _ in range(51)]
for i in range(51):
    for j in range(i):
        for m in range(1, i+1):
            if i%m==j:
                d[i][j] = 1<<m
                break
    d[i][i] = 0
for k in range(51):
    for i in range(51):
        for j in range(51):
            if d[i][j] > d[i][k] | d[k][j]:
                d[i][j] = d[i][k] | d[k][j]
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A = list(map(lambda x: {x}, A))
ans = 0
for i in range(N):
    #print(i, A)
    ma = -1
    ama = -1
    for j, (a, b) in enumerate(zip(A, B)):
        d_ = INF
        for a_ in a:
            d_ = min(d_, d[a_][b])
        if d_ > ma:
            ma = d_
            ama = j
    del A[ama], B[ama]
    M = [m for m in range(1, 51) if ma>>m & 1]
    for j in range(len(A)):
        for a_ in list(A[j]):
            for m in M:
                A[j].add(a_%m)
    #print(ma)
    ans |= ma
print(ans if ans < INF else -1)

Submission status: Accepted

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 a[i] == b[i]:
		same += 1
	elif b[i]*2 >= a[i]:
		print(-1)
		sys.exit()

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

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
stack=[[a[i]] for i in range(N)]
def dfs(x):
  if x==0:
    return 
  global ans
  ans+=2**x
  for i in range(N):
    visited=[False]*51
    for j in stack[i]:
      visited[j]=True
      if not visited[j%x]:
        stack[i].append(j%x)
        visited[j%x]=True
  k=0
  for i in range(N):
    k=max(k,min([dp[j][b[i]] for j in stack[i]]))
  if k==0:
    return 
  return dfs(k)
M=max([dp[a[i]][b[i]] for i in range(N)])
if M>50:
  print(-1)
  exit()
dfs(M)
print(ans)