Problem:


Score : 500 points

Problem Statement

Snuke has a string s.
From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with ?s.

For example, if s is mississippi, we can choose the substring ssissip and replace its 1-st and 3-rd characters with ? to obtain ?s?ssip.

You are given the strings a, b, and c.
Find the minimum possible length of s.

Constraints

1 \leq |a|, |b|, |c| \leq 2000

a, b, and c consists of lowercase English letters and ?s.

Input

Input is given from Standard Input in the following format:

a
b
c

Output

Print the minimum possible length of s.

Sample Input 1

a?c
der
cod

Sample Output 1

7

For example, s could be atcoder.

Sample Input 2

atcoder
atcoder
???????

Sample Output 2

7

a, b, and c may not be distinct.



Sample input:
a?c
der
cod


Sample output:
7

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *

def comp(a,b,c=repeat("?")):
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a, b, c))

def comp_dup(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return comp(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

def _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

def _merge_right(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b, a[-lb+i:]):
      yield la-lb+i
  yield la

def merge_right(a,b):
  return list(_merge_right(a,b))

def iter_range(it, it_min, it_max=None):
  it = iter(it)
  for e in it:
    if e < it_min:
      continue
    else:
      if it_max is None or e < it_max:
        yield e
      break
  if it_max is not None:
    for e in it:
      if e >= it_max:
        return
      yield e
  else:
    for e in it:
      yield e

class K(object):
  def __init__(self,k, i, cb=None):
    self.i = i
    self.k = k
    self.cb = cb
  
  def __gt__(self, x):
    return self.i.__gt__(x.i)
  def __lt__(self, x):
    return self.i.__lt__(x.i)
  def __eq__(self, x):
    return self.i.__eq__(x.i)

    
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  len_a, len_b, len_c = map(len,[a,b,c])
  
  b_in_a = merge_mid(a,b)
  c_in_a = merge_mid(a,c)
  c_in_b = merge_mid(b,c)
  set_c_in_b = set(c_in_b)
  b_c = merge_right(b,c)
  set_b_c = set(b_c)
  c_b = merge_right(c,b)
  set_c_b = set(c_b)
  
  for i in b_in_a:
    for j in c_in_a:
      if j+len_c <= i or i+len_b <= j or (j-i in set_b_c|set_c_in_b or i-j in set_c_b) and comp_dup(0,i,j,a,b,c):
        return len_a
  
  set_b_in_a = set(b_in_a)
  set_c_in_a = set(c_in_a)
  a_b = merge_right(a,b)
  set_a_b = set(a_b)
  b_a = merge_right(b,a)
  set_b_a = set(b_a)
  a_c = merge_right(a,c)
  set_a_c = set(a_c)
  c_a = merge_right(c,a)
  set_c_a = set(c_a)
  
  
  
  can = merge(
    #a_c_b
    chain(
      (K(1, i+len_b, lambda:(
       (c_in_a and c_in_a[0]+len_c <= i) or (c_in_b and len_a <= i+c_in_b[-1]) or 
       any((i-j in set_c_b if i>j else j-i in set_c_in_b) and comp_dup(0,i,j,a,b,c) for j in iter_range(c_in_a+a_c, i-len_c))
      )) for i in a_b),
      [K(2, min(i+next(iter_range(c_b, len_a-i+1))+len_b for i in a_c), lambda:True)],
    ),
    #b_c_a
    chain(
      (K(3, i+len_a, lambda:(
       (c_in_b and c_in_b[0]+len_c <= i) or (c_in_a and len_b <= i+c_in_a[-1]) or 
       any((i-j in set_c_a if i>j else j-i in set_c_in_a) and comp_dup(0,i,j,b,a,c) for j in iter_range(c_in_b+b_c, i-len_c))
      )) for i in b_a),
      [K(4, min(i+next(iter_range(c_a, len_b-i+1))+len_a for i in b_c), lambda:True)],
    ),
    #a_b_c
    chain(
      (K(5, i+len_c, lambda:(
       (b_in_a and b_in_a[0]+len_b <= i) or
       any(i-j in set_b_c and comp_dup(0,i,j,a,c,b) for j in iter_range(b_in_a+a_b, i-len_b))
      )) for i in a_c),
      [K(6, min(i+next(iter_range(b_c, len_a-i+1))+len_c for i in a_b), lambda:True)],
    ),
    #c_b_a
    chain(
      (K(7, i+len_a, lambda:(
       (b_in_a and len_c <= i+b_in_a[-1]) or 
       any((i-j in set_b_a if i>j else j-i in set_b_in_a) and comp_dup(0,i,j,c,a,b) for j in iter_range(c_b, i-len_b))
      )) for i in c_a),
      [K(8, min(i+next(iter_range(b_a, len_c-i+1))+len_a for i in c_b), lambda:True)],
    ),
    #b_a_c
    chain(
      (K(9, i+len_c, lambda:(
       any(i-j in set_a_c and comp_dup(0,i,j,b,c,a) for j in iter_range(b_a, i-len_a))
      )) for i in iter_range(b_c, len_a-len_c+1)),
      [K(10, min(i+next(iter_range(a_c, len_b-i+1))+len_c for i in b_a), lambda:True)],
    ),
    #c_a_b
    chain(
      (K(11, i+len_b, lambda:(
       any(i-j in set_a_b and comp_dup(0,i,j,c,b,a) for j in iter_range(c_a, i-len_a))
      )) for i in iter_range(c_b, len_a-len_b+1)),
      [K(12, min(i+next(iter_range(a_b, len_c-i+1))+len_b for i in c_a), lambda:True)],
    ),
  )
  
  for k in can:
    if k.cb():
      return k.i
  
  return len_a + len_b + len_c

a=input()
b=input()
c=input()

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *

def comp(a,b,c=repeat("?")):
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a, b, c))

def comp_dup(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return comp(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

def _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

def _merge_right(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b, a[-lb+i:]):
      yield la-lb+i
  yield la

def merge_right(a,b):
  return list(_merge_right(a,b))

def iter_range(it, it_min, it_max=None):
  it = iter(it)
  for e in it:
    if e < it_min:
      continue
    else:
      if it_max is None or e < it_max:
        yield e
      break
  if it_max is not None:
    for e in it:
      if e >= it_max:
        return
      yield e
  else:
    for e in it:
      yield e

class K(object):
  def __init__(self,k, i, cb=None):
    self.i = i
    self.k = k
    self.cb = cb
  
  def __gt__(self, x):
    return self.i.__gt__(x.i)
  def __lt__(self, x):
    return self.i.__lt__(x.i)
  def __eq__(self, x):
    return self.i.__eq__(x.i)

    
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  len_a, len_b, len_c = map(len,[a,b,c])
  
  b_in_a = merge_mid(a,b)
  c_in_a = merge_mid(a,c)
  c_in_b = merge_mid(b,c)
  b_c = merge_right(b,c)
  set_b_c = set(b_c)
  c_b = merge_right(c,b)
  set_c_b = set(c_b)
  
  for i in b_in_a:
    for j in c_in_a:
      if j+len_c <= i or i+len_b <= j or (j-i in set_b_c or i-j in set_c_b) and comp_dup(0,i,j,a,b,c):
        return len_a
  
  set_b_in_a = set(b_in_a)
  set_c_in_a = set(c_in_a)
  set_c_in_b = set(c_in_b)
  a_b = merge_right(a,b)
  set_a_b = set(a_b)
  b_a = merge_right(b,a)
  set_b_a = set(b_a)
  a_c = merge_right(a,c)
  set_a_c = set(a_c)
  c_a = merge_right(c,a)
  set_c_a = set(c_a)
  
  can = merge(
    #a_c_b
    chain(
      (K(1, i+len_b, lambda:(
       (c_in_a and c_in_a[0]+len_c <= i) or (c_in_b and len_a <= i+c_in_b[-1]) or 
       any((i-j in set_c_b if i>j else j-i in set_c_in_b) and comp_dup(0,i,j,a,b,c) for j in iter_range(c_in_a+a_c, i-len_c))
      )) for i in a_b),
      (K(2, i+len_b, lambda:True) for i in range(len_a+1, len_a+len_c) if any(i-j in set_c_b for j in iter_range(a_c, i-len_c))),
    ),
    #b_c_a
    chain(
      (K(3, i+len_a, lambda:(
       (c_in_b and c_in_b[0]+len_c <= i) or (c_in_a and len_b <= i+c_in_a[-1]) or 
       any((i-j in set_c_a if i>j else j-i in set_c_in_a) and comp_dup(0,i,j,b,a,c) for j in iter_range(c_in_b+b_c, i-len_c))
      )) for i in b_a),
      (K(4, i+len_a, lambda:True) for i in range(len_b+1, len_b+len_c) if any(i-j in set_c_a for j in iter_range(b_c, i-len_c))),
    ),
    #a_b_c
    chain(
      (K(5, i+len_c, lambda:(
       (b_in_a and b_in_a[0]+len_b <= i) or
       any(i-j in set_b_c and comp_dup(0,i,j,a,c,b) for j in iter_range(b_in_a+a_b, i-len_b))
      )) for i in a_c),
      (K(6, i+len_c, lambda:True) for i in range(len_a+1, len_a+len_b) if any(i-j in set_b_c for j in iter_range(a_b, i-len_b))),
    ),
    #c_b_a
    chain(
      (K(7, i+len_a, lambda:(
       (b_in_a and len_c <= i+b_in_a[-1]) or 
       any((i-j in set_b_a if i>j else j-i in set_b_in_a) and comp_dup(0,i,j,c,a,b) for j in iter_range(c_b, i-len_b))
      )) for i in c_a),
      (K(8, i+len_a, lambda:True) for i in range(len_c+1, len_c+len_b) if any(i-j in set_b_a for j in iter_range(c_b, i-len_b))),
    ),
    #b_a_c
    chain(
      (K(9, i+len_c, lambda:(
       any(i-j in set_a_c and comp_dup(0,i,j,b,c,a) for j in iter_range(b_a, i-len_a))
      )) for i in iter_range(b_c, len_a-len_c+1)),
      (K(10, i+len_c, lambda:True) for i in range(max(len_b, len_a-len_c)+1, len_b+len_a) if any(i-j in set_a_c for j in iter_range(b_a, i-len_a))),
    ),
    #c_a_b
    chain(
      (K(11, i+len_b, lambda:(
       any(i-j in set_a_b and comp_dup(0,i,j,c,b,a) for j in iter_range(c_a, i-len_a))
      )) for i in iter_range(c_b, len_a-len_b+1)),
      (K(12, i+len_b, lambda:True) for i in range(max(len_c, len_a-len_b)+1, len_c+len_a) if any(i-j in set_a_b for j in iter_range(c_a, i-len_a))),
    ),
    
  )
  
  for k in can:
    if k.cb():
      return k.i
  
  return len_a + len_b + len_c

a=input()
b=input()
c=input()

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def chk(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    rt=[]
    for i in range(na):
        fl=True
        for j in range(min(na-i,nb)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                fl=False
                break
        if fl:
            rt+=[i]
    return rt+[na]

def tri_chk(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in ab:
        for r in bc:
            if l+r>=na or ac[bisect.bisect_left(ac,l+r)]==l+r:
                alt=max(na,l+nb,l+r+nc)
                if alt<rt:
                    rt=alt
    return rt

a=input()
b=input()
c=input()

na,nb,nc=map(len,(a,b,c))
ans=10**9
strs=[a,b,c]
chMat=[[chk(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_chk(i)
    ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(min(na-i,nb)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                alt=max(na,l+nb,na+nb+nc-(na-l)-(nb-r))
                if alt<rt:
                    rt=alt
    return rt

a=input()
b=input()
c=input()

na,nb,nc=map(len,(a,b,c))
ans=10**9
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def chk(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    rt=[]
    for i in range(na):
        fl=True
        for j in range(min(na-i,nb)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                fl=False
                break
        if fl:
            rt+=[i]
    return rt+[na]

def tri_chk(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in ab:
        for r in bc:
            if l+r>=na or ac[bisect.bisect(ac,l+r)]<na:
                alt=max(na,l+nb,l+r+nc)
                if alt<rt:
                    rt=alt
    return rt

a=input()
b=input()
c=input()

na,nb,nc=map(len,(a,b,c))
ans=10**9
strs=[a,b,c]
chMat=[[chk(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_chk(i)
    ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                alt=max(na,na+nb+nc-(na-l)-(nb-r))
                if alt<rt:
                    rt=alt
                    al,ar=l,r
    return rt

a=input()
b=input()
c=input()

na,nb,nc=map(len,(a,b,c))
ans=inf
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                if na+nb+nc-(na-l)-(nb-r)<rt:
                    rt=max(na,na+nb+nc-(na-l)-(nb-r))
                    al,ar=l,r
    return max(rt,na)

a=input()
b=input()
c=input()

na,nb,nc=map(len,(a,b,c))
ans=inf
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(min(nb,na-i)):
            if (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                if na+nb+nc-(na-l)-(nb-r)<rt:
                    rt=max(na,na+nb+nc-(na-l)-(nb-r))
                    al,ar=l,r
    return max(rt,na)

a=input()
b=input()
c=input()

na,nb,nc=map(len,(a,b,c))
ans=inf
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
c = sys.stdin.readline().strip()

global_min = sum(map(len, [a,b,c]))
def match(x, y, start_x):
    crt_x = start_x
    crt_y = 0
    while crt_x < len(x) and crt_y < len(y):
        if x[crt_x] == "?" or y[crt_y] == "?" or x[crt_x] == y[crt_y]:
            crt_x += 1
            crt_y += 1
        else:
            return False
    return True

def merge(a,b,c):
    """
       cccccccccc
     bbbbbbbbbb
    aaaaaaa
    """
    
    global global_min
    A, B, C = map(len, [a,b,c])
    for i in range(A):
        for j in range(B):
            # if already longer, no need to continue
            length = max(A,i+B) + max(j+C-B, 0)
            if length >= global_min:
                break
            if match(a, b, i) and match(b, c, j):
                global_min = min(length, global_min)
                return

merge(a,b,c)
merge(a,c,b)
merge(b,a, c)
merge(b,c,a)
merge(c,a,b)
merge(c,b,a)
print(global_min)

Submission status: Wrong Answer

Solution code:
import sys
a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
c = sys.stdin.readline().strip()

global_min = sum(map(len, [a,b,c]))
def match(x, y, start_x, start_y):
    crt_x = start_x
    crt_y = start_y
    while crt_x < len(x) and crt_y < len(y):
        if x[crt_x] == "?" or y[crt_y] == "?" or x[crt_x] == y[crt_y]:
            crt_x += 1
            crt_y += 1
        else:
            return False
    return True

def merge(a,b,c):
    """
       cccccccccc
     bbbbbbbbbb
    aaaaaaa
    """
    
    global global_min
    A, B, C = map(len, [a,b,c])
    for i in range(A):
        for j in range(B):
            # if already longer, no need to continue
            length = max(A,i+B) + max(j+C-B, 0)
            if length >= global_min:
                break
            if match(a, b, i, 0) and match(b, c, j, 0):
                global_min = min(length, global_min)

merge(a,b,c)
merge(a,c,b)
merge(b,a, c)
merge(b,c,a)
merge(c,a,b)
merge(c,b,a)
print(global_min)

Submission status: Wrong Answer

Solution code:
a = [input(),input(),input()]
l = [len(a[0]),len(a[1]),len(a[2])]
ans = l[0]+l[1]+l[2]

def check(a0, l0, a1, l1, delta):
    # stt1 >= stt0, stt1 - stt0 >=l0 must return True
    i = delta
    j = 0
    while (i<l0) and (j<l1):
        if a0[i] != a1[j]:
            if a0[i] != '?' and a1[j] != '?':
                return False
        i += 1
        j += 1
    return True

memo = [[[1]*4000 for i in range(3)] for j in range(3)]
comb2 = [(0,1),(1,0),(1,2),(2,1),(0,2),(2,0)]
for x, y in comb2:
    me = memo[x][y]
    a0, a1 = a[x],a[y]
    l0, l1 = l[x],l[y]
    for delta in range(0,l0):
        if not check(a0,l0, a1,l1, delta):
            me[delta] = 0

comb = [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]