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:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r
 
def merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    m = comp(a[i:],b)
    if m:
      yield i, (a[:i]+m+a[i+lb:], la)
 
def merge2(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    m = comp(b, a[-lb+i:])
    if m:
      yield la-lb+i, (a[:-lb+i]+m+b[-i:], la+i)
  yield la, (a+b, la+lb)
 
def merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    m = comp(b[i:], a)
    if m:
      yield -i, (b[:i]+m+a[len(b)-i:], la+i)
  yield -lb, (b+a, la+lb)
  
  
  
  
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b = dict(merge1(a,b))
  a_b2 = dict(merge2(a,b))
  a_b3 = dict(merge3(a,b))
  a_c = dict(merge1(a,c))
  a_c2 = dict(merge2(a,c))
  a_c3 = dict(merge3(a,c))
  b_c = dict(merge1(b,c))
  b_c2 = dict(merge2(b,c))
  b_c3 = dict(merge3(b,c))
  
  for i,(d, ld) in a_b.items():
    for j, (e, le) in a_c.items():
      if j+lc<=i or i+lb<=j:
        return la
      if j-i in b_c and comp(d[j:], c):
        return la
      if j-i in b_c2 and comp(d[j:j+lb], c):
        return la
      if j-i in b_c3 and comp(d[i:], c[i-j:]):
        return la
  
  for i,(d, ld) in a_b2.items():
    if abc <= ld:
      break
    for j, (e, le) in a_c.items()|a_c2.items():
      if j+lc<=i:
        abc = min(abc, ld)
        break
      if j-i in b_c and comp(d[j:la], c):
        abc = min(abc, ld)
        break
      if j-i in b_c3 and comp(d[i:la], c[i-j:]):
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
    for j, (e, le) in b_c.items():
      if la<=i+j:
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
    for j, (e, le) in a_c3.items():
      if j+lc<=i:
        abc = min(abc, ld-j)
        break
      if j-i in b_c3 and comp(d[i:], c[i-j:]):
        abc = min(abc, ld-j)
        break
    for j, (e, le) in b_c2.items():
      if la<=i+j:
        abc = min(abc, i+le)
        break
      if i+j in a_c2 and comp(d[i+j:la], c):
        abc = min(abc, i+le)
        break
      
      
  for i,(d, ld) in a_b3.items():
    if abc <= ld:
      break
    for j, (e, le) in a_c.items()|a_c3.items():
      if i+lb <= j:
        abc = min(abc, ld)
        break
      if j-i in b_c and comp(d[j-i+lc-1:-1:-1], c[::-1]):
        abc = min(abc, ld)
        break
      if j-i in b_c2 and comp(d[lb-1:-i-1:-1], c[i-j+lb-1::-1]):
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
    for j, (e, le) in b_c.items():
      if i+j+lc<=0:
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
      
    for j, (e, le) in a_c3.items():
      if i+lb<=j:
        abc = min(abc, le-i)
        break
      if j-i in b_c2 and comp(d[j-i:lb], c):
        abc = min(abc, le-i)
        break
      
    for j, (e, le) in b_c3.items():
      if i+j+lc<=0:
        abc = min(abc, ld-j)
        break
      if i+j in a_c3 and comp(d[-i:], c[-i-j:]):
        abc = min(abc, ld-j)
        break
  
  for i in range(1,lc):
    if abc < la+lb+i:
      break     
    for j, (e, le) in a_c2.items():
      if j-la-i in b_c3:
        return la+lb+i
    for j, (e, le) in b_c2.items():
      if j-la-i in a_c3:
        return la+lb+i
    
  return abc
 
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):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(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(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield i
  yield la

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

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp3(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
def main():
    a, b, c = [input() for _ in [0]*3]
    p = [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]

    def check(x, y):
        lx, ly = len(x), len(y)
        ans = {lx}
        for i in range(lx):
            for j in range(min(ly, lx-i)):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                ans.add(i)
        return ans

    def check2(x, y, z):
        lx, ly, lz = len(x), len(y), len(z)
        ans = lx+ly+lz
        dxy, dyz, dxz = d[(x, y)], d[(y, z)], d[(x, z)]
        for i in dxy:
            ans = min(ans, max(lx, i+ly)+lz)
            for j in dyz:
                if i+j in dxz or i+j >= lx:
                    ans = min(ans, max(lx, i+ly, i+j+lz))
            for j in range(ly, lx-ly):
                if i+j in dxz:
                    ans = min(ans, max(lx, i+j+lz))
        return ans

    d = {(x, y): check(x, y) for x, y, z in p}
    print(min([check2(x, y, z) for x, y, z in p]))


main()

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *
from collections import OrderedDict

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  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 comp3(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(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield 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 delay(f):
  yield f()



def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k.i
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *
from collections import OrderedDict

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, None

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

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

def merge_right(a,b):
  return dict(_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 delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))

  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *
from collections import OrderedDict

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, None

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

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

def merge_right(a,b):
  return OrderedDict(_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 delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *
from collections import defaultdict

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(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield 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 delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))

  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *
from collections import defaultdict

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(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield 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 delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  mid_set = {k:set(v) for k,v in mid.items()}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right_set = {k:set(v) for k,v in right.items()}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  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 *
from collections import defaultdict

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(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield 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 delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  mid_set = {k:set(v) for k,v in mid.items()}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right_set = {k:set(v) for k,v in right.items()}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid_set[1,2]|right_set[1,2] or i-j in right_set[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right_set[c,b] if i>j else j-i in mid_set[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  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:
a = input()
b = input()
c = input()

la = len(a)
lb = len(b)
lc = len(c)

def match(x,y):
    if x == y or x == "?" or y == "?":
        return True
    return False
    
ab = [True]*15000
ac = [True]*15000
bc = [True]*15000

for i in range(4000-lb,4000+la):
    for j in range(lb):
        if 4000 <= i+j < 4000+la:
            if not match(a[i+j-4000],b[j]):
                ab[i] = False

for i in range(4000-lc,4000+la):
    for j in range(lc):
        if 4000 <= i+j < 4000+la:
            if not match(a[i+j-4000],c[j]):
                ac[i] = False

for i in range(4000-lc,4000+lb):
    for j in range(lc):
        if 4000 <= i+j < 4000+lb:
            if not match(b[i+j-4000],c[j]):
                bc[i] = False

res = la+lb+lc

for i in range(0,8001):
    for j in range(4000-lc,4000+la+1):
        if ab[i] and ac[j]:
            if (j-i+4000 >= 15000) or bc[j-i+4000]:
                res = min(res, max(4000+la,i+lb,j+lc)-min(4000,i,j))

print(res)

Submission status: Wrong Answer

Solution code:
def main():
    a, b, c = [input() for _ in [0]*3]
    p = [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]

    def check(x, y):
        lx, ly = len(x), len(y)
        ans = {lx}
        for i in range(lx):
            for j in range(min(ly, lx-i)):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                ans.add(i)
        return ans

    def check2(x, y, z):
        lx, ly, lz = len(x), len(y), len(z)
        ans = lx+ly+lz
        dxy, dyz, dxz = d[(x, y)], d[(y, z)], d[(x, z)]
        for i in dxy:
            ans = min(ans, max(lx, i+ly)+lz)
            for j in dyz:
                if i+j in dxz or i+j >= lx:
                    ans = min(ans, max(lx, i+ly, i+j+lz))
        return ans

    d = {(x, y): check(x, y) for x, y, z in p}
    print(min([check2(x, y, z) for x, y, z in p]))


main()

Submission status: Wrong Answer

Solution code:
def main():
    a, b, c = [input() for _ in [0]*3]
    p = [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]

    def check(x, y):
        lx, ly = len(x), len(y)
        ans = {lx}
        for i in range(lx):
            for j in range(min(ly, lx-i)):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                ans.add(i)
        return ans

    def check2(x, y, z):
        ans = 10**6
        lx, ly, lz = len(x), len(y), len(z)
        dxy, dyz, dxz = d[(x, y)], d[(y, z)], d[(x, z)]
        for i in dxy:
            for j in dyz:
                ans = min(ans, max(lx, i+ly)+lz)
                if i+j in dxz or i+j >= lx:
                    ans = min(ans, max(lx, i+ly, i+j+lz))
        return ans

    d = {(x, y): check(x, y) for x, y, z in p}
    print(min([check2(x, y, z) for x, y, z in p]))


main()

Submission status: Wrong Answer

Solution code:
def main():
    a, b, c = [input() for _ in [0]*3]
    p = [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]

    def check(x, y):
        lx, ly = len(x), len(y)
        ans = {lx}
        for i in range(lx):
            for j in range(min(ly, lx-i)):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                ans.add(i)
        return ans

    def check2(x, y, z):
        ans = 10**6
        lx, ly, lz = len(x), len(y), len(z)
        dxy, dyz, dxz = d[(x, y)], d[(y, z)], d[(x, z)]
        for i in dxy:
            for j in dyz:
                if i+j in dxz or i+j >= lx:
                    ans = min(ans, max(lx, i+ly, i+j+lz))
        return ans

    d = {(x, y): check(x, y) for x, y, z in p}
    print(min([check2(x, y, z) for x, y, z in p]))


main()

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 delay(f):
  yield f()
    
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),
      delay(lambda: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),
      delay(lambda: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),
      delay(lambda: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),
      delay(lambda: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)),
      delay(lambda: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)),
      delay(lambda: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))