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_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_left(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b[i:], a):
      yield -i
  yield -lb

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)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b1, a_b2, a_b3  = map(list, [merge_mid(a,b), merge_right(a,b), merge_left(a,b)])
  a_b = set(chain(a_b1, a_b2, a_b3))
  a_c1, a_c2, a_c3  = map(list, [merge_mid(a,c), merge_right(a,c), merge_left(a,c)])
  a_c = set(chain(a_c1, a_c2, a_c3))
  b_c1, b_c2, b_c3  = map(list, [merge_mid(b,c), merge_right(b,c), merge_left(b,c)])
  b_c = set(chain(b_c1, b_c2, b_c3))
  
  for i in a_b1:
    for j in a_c1:
      if j+lc <= i or i+lb <= j or j-i in b_c and comp_dup(0,i,j,a,b,c):
        return la
  
  can = merge(  
    (K(1, lb+i, (lambda:(a_c1 and a_c1[0]+lc <= i) or (b_c1 and la <= i+b_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:j+lc<=i+lb), a_c1+a_c2)))) for i in a_b2),
    (K(2, lb+i, (lambda:any(j-i in b_c for j in dropwhile((lambda j:j+lc<i), a_c2)))) for i in range(la+1, la+lc)),

    (K(3, la-i, (lambda:(b_c1 and i+b_c1[0]+lc <= 0) or (a_c1 and i+lb <= a_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:i<=j), a_c1+a_c3)))) for i in a_b3),
    (K(4, la-i, (lambda:any(j-i in b_c for j in dropwhile((lambda j:i+lb<j), a_c3)))) for i in range(-lb-1, -lb-lc-1, -1)),

    (K(5, lc+i, (lambda:(a_b1 and a_b1[0]+lb <= i) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:j+lb<=i+lc), a_b1+a_b2)))) for i in a_c2),
    (K(6, lc+i, (lambda:any(i-j in b_c for j in dropwhile((lambda j:j+lb<i), a_b2)))) for i in range(la+1, la+lb)),

    (K(7, la-i, (lambda:(a_b1 and i+lc <= a_b1[-1]) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:i<=j), a_b1+a_b3)))) for i in a_c3),
    (K(8, la-i, (lambda:any(i-j in b_c for j in dropwhile((lambda j:i+lc<j), a_b3)))) for i in range(-lc-1, -lb-lc-1, -1)),

    (K(9, lc+i, (lambda:any(i+j in a_c and comp_dup(-j,0,i,a,b,c) for j in takewhile((lambda j:la-j<i+lc), a_b3)))) for i in b_c2),
    (K(10, lc+i, (lambda:any(i+j in a_c for j in takewhile((lambda j:la-j<i), dropwhile((lambda j:la-j<i), a_b3))))) for i in range(lb+1, la+lb)),
    
    (K(11, lb-i, (lambda:any(i+j in a_c and comp_dup(-j,0,i,a,b,c) for j in takewhile((lambda j:i<-j), a_b2)))) for i in b_c3),
    (K(12, lb-i, (lambda:any(i+j in a_c for j in takewhile((lambda j:i<-j), dropwhile((lambda j:i+lc<-j), a_b2))))) for i in count(-lc-1, -1)),
  )
  
  for k in can:
    if k.cb():
      return k.i

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_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_left(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b[i:], a):
      yield -i
  yield -lb

class K(object):
  def __init__(self, i, cb=None):
    self.i = i
    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)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b1, a_b2, a_b3  = map(list, [merge_mid(a,b), merge_right(a,b), merge_left(a,b)])
  a_b = set(chain(a_b1, a_b2, a_b3))
  a_c1, a_c2, a_c3  = map(list, [merge_mid(a,c), merge_right(a,c), merge_left(a,c)])
  a_c = set(chain(a_c1, a_c2, a_c3))
  b_c1, b_c2, b_c3  = map(list, [merge_mid(b,c), merge_right(b,c), merge_left(b,c)])
  b_c = set(chain(b_c1, b_c2, b_c3))
  
  for i in a_b1:
    for j in a_c1:
      if j+lc <= i or i+lb <= j or j-i in b_c and comp_dup(0,i,j,a,b,c):
        return la
  
  can = merge(  
    (K(lb+i, (lambda:(a_c1 and a_c1[0]+lc <= i) or (b_c1 and la <= i+b_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:j+lc<=i+lb), a_c1+a_c2)))) for i in a_b2),
    (K(lb+i, (lambda:any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lc<i), a_c2)))) for i in count(la+1)),

    (K(la-i, (lambda:(b_c1 and i+b_c1[0]+lc <= 0) or (a_c1 and i+lb <= a_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:i<=j), a_c1+a_c3)))) for i in a_b3),
    (K(la-i, (lambda:any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:i+lb<j), a_c3)))) for i in count(-lb-1, -1)),

    (K(lc+i, (lambda:(a_b1 and a_b1[0]+lb <= i) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:j+lb<=i+lc), a_b1+a_b2)))) for i in a_c2),
    (K(lc+i, (lambda:any(i-j in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lb<i), a_b2)))) for i in count(la+1)),

    (K(la-i, (lambda:(a_b1 and i+lc <= a_b1[-1]) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:i<=j), a_b1+a_b3)))) for i in a_c3),
    (K(la-i, (lambda:any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in dropwhile((lambda j:i+lc<j), a_b3)))) for i in count(-lc-1, -1)),

    (K(lc+i, (lambda:any(i+j in a_c and comp_dup(-j,0,i,a,b,c) for j in takewhile((lambda j:la-j<i), dropwhile((lambda j:la-j<i), a_b3))))) for i in range(lb+1, la+lb)),
    (K(lb-i, (lambda:any(i+j in a_c and comp_dup(-i,0,j,a,b,c) for j in takewhile((lambda j:i<-j), dropwhile((lambda j:i+lc<-j), a_b2))))) for i in count(-lc-1, -1)),
  )
  
  for k in can:
    if k.cb():
      return k.i

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    s = sorted([input() for _ in range(3)])
    n = len(max(s, key=len))
    d = [[[None]*n for _ in range(3)] for _ in range(3)]
    ans = n*3
    for i in range(3):
        li = len(s[i])
        di = d[i]
        for j in range(3):
            if i == j:
                continue
            lj = len(s[j])
            dij = di[j]
            for k in range(li):
                notok = False
                for ni in range(k, li):
                    nj = ni - k
                    if nj >= lj:
                        break
                    if s[i][ni] == "?" or s[j][nj] == "?":
                        continue
                    if s[i][ni] != s[j][nj]:
                        notok = True
                dij[k] = notok
    f = lambda i, j, k: False if k>=len(s[i]) else d[i][j][k]
    for x in range(n):
        for y in range(n):
            if f(0, 1, x):
                continue
            if f(1, 2, y):
                continue
            if f(0, 2, x+y):
                continue
            now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
            if ans > now:
                ans = now
    print(ans)
                
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def match(s, t, ls, lt, i):
    return all(s[i + j] == '?' or t[j] == '?' or s[i + j] == t[j] for j in range(min(ls - i, lt)))


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

ab = [match(a, b, la, lb, i) for i in range(0, la)] + [True]
ac = [match(a, c, la, lc, i) for i in range(0, la)] + [True]
bc = [match(b, c, lb, lc, i) for i in range(0, lb)] + [True]
ba = [match(b, a, lb, la, i) for i in range(1, lb)] + [True]
ca = [match(c, a, lc, la, i) for i in range(1, lc)] + [True]
cb = [match(c, b, lc, lb, i) for i in range(1, lc)] + [True]
ab.extend(reversed(ba))
ac.extend(reversed(ca))
bc.extend(reversed(cb))

ans = la + lb + lc

# b→c→a でbとaの間に1文字以上間隔がある
for db in range(-lb - lc, -lb):
    for dc in range(-lc, db + 1):
        ac_ok = ac[dc]
        bc_ok = bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(la, db + lb, dc + lc) - db)

# b→a で重なるか間隔が無い
for db in range(-lb, 0):
    ab_ok = ab[db]
    if not ab_ok:
        continue
    for dc in range(db - lc, la + 1):
        ac_ok = True if dc < -lc else ac[dc]
        bc_ok = True if db + lb < dc else bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(la, db + lb, dc + lc) - min(db, dc))

# a→b で重なるか間隔が無い
for db in range(la + 1):
    ab_ok = ab[db]
    if not ab_ok:
        continue
    for dc in range(-lc, db + lb):
        ac_ok = True if la < dc else ac[dc]
        bc_ok = True if dc < db - lc else bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(la, db + lb, dc + lc) - min(0, dc))

# a→c→b でaとbの間に1文字以上間隔がある
for db in range(la + 1, la + lc):
    for dc in range(db - lc, la + 1):
        ac_ok = ac[dc]
        bc_ok = bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(la, db + lb, dc + lc))

print(ans)

Submission status: Wrong Answer

Solution code:
def match(s, t, ls, lt, i):
    return all(s[i + j] == '?' or t[j] == '?' or s[i + j] == t[j] for j in range(min(ls - i, lt)))


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

ab = [match(a, b, la, lb, i) for i in range(la)] + [True]
ac = [match(a, c, la, lc, i) for i in range(la)] + [True]
ba = [match(b, a, lb, la, i) for i in range(lb)] + [True]
bc = [match(b, c, lb, lc, i) for i in range(lb)] + [True]
ca = [match(c, a, lc, la, i) for i in range(lc)] + [True]
cb = [match(c, b, lc, lb, i) for i in range(lc)] + [True]
ab.extend(reversed(ba[1:]))
ac.extend(reversed(ca[1:]))
bc.extend(reversed(cb[1:]))

ans = la + lb + lc

# b→c→a でbとaの間に1文字以上間隔がある
for db in range(-lb - lc, -lb):
    for dc in range(-lc, db + 1):
        ac_ok = ac[dc]
        bc_ok = bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, -db + la)

# b→a で重なるか間隔が無い
for db in range(-lb, 0):
    ab_ok = ab[db]
    if not ab_ok:
        continue
    for dc in range(db - lc, la + 1):
        ac_ok = True if dc < -lc else ac[dc]
        bc_ok = True if db + lb < dc else bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(la, dc + lc) - min(db, dc))

# a→b で重なるか間隔が無い
for db in range(la + 1):
    ab_ok = ab[db]
    if not ab_ok:
        continue
    for dc in range(-lc, db + lb):
        ac_ok = True if la < dc else ac[dc]
        bc_ok = True if dc < db - lc else bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(db + lb, dc + lc) - min(0, dc))

# a→c→b でaとbの間に1文字以上間隔がある
for db in range(la + 1, la + lc):
    for dc in range(db - lc, la + 1):
        ac_ok = ac[dc]
        bc_ok = bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, db + lb)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def same(x,y):
        xn,yn=len(x),len(y)
        # x,yの一致する位置を調べる
        # xの先頭の位置は4000で固定
        res = [True] * 8005
        # yが前
        for i in range(1, yn):
            for c0, c1 in zip(x, y[i:]):
                if c0 != q and c1 != q and c0 != c1:
                    res[4000 - i] = False
                    break
        # xが後
        for i in range(xn):
            for c0, c1 in zip(x[i:], y):
                if c0 != q and c1 != q and c0 != c1:
                    res[4000 + i] = False
                    break
        return res

    q=ord("?")
    a=[ord(c) for c in SI()]
    b=[ord(c) for c in SI()]
    c=[ord(c) for c in SI()]
    an,bn,cn=len(a),len(b),len(c)
    #a,cの一致を調べる
    ab=same(a,b)
    ac=same(a,c)
    bc=same(b,c)
    # editorialの通りやろうと思ったけど8000*8000=64000000はきつそうなので
    # a,b,cの順番決め打ちの2000*2000*6=24000000でやる
    ans=an+bn+cn
    # a,b,c
    for i in range(an+1):
        for j in range(bn+1):
            if ab[4000+i] and bc[4000+j] and ac[4000+i+j]:
                r=max(an,i+bn,i+j+cn)
                ans=min(ans,r)
    # a,c,b
    for i in range(an+1):
        for j in range(cn+1):
            if ab[4000+i+j] and bc[4000-j] and ac[4000+i]:
                r=max(an,i+cn,i+j+bn)
                ans=min(ans,r)
    # b,a,c
    for i in range(bn+1):
        for j in range(an+1):
            if ab[4000-i] and bc[4000+i+j] and ac[4000+j]:
                r=max(bn,i+an,i+j+cn)
                ans=min(ans,r)
    # b,c,a
    for i in range(bn+1):
        for j in range(cn+1):
            if ab[4000-i-j] and bc[4000+i] and ac[4000-j]:
                r=max(bn,i+cn,i+j+an)
                ans=min(ans,r)
    # c,a,b
    for i in range(cn+1):
        for j in range(an+1):
            if ab[4000+j] and bc[4000-i-j] and ac[4000-i]:
                r=max(cn,i+an,i+j+bn)
                ans=min(ans,r)
    # c,b,a
    for i in range(cn+1):
        for j in range(bn+1):
            if ab[4000-j] and bc[4000-i] and ac[4000-i-j]:
                r=max(cn,i+bn,i+j+an)
                ans=min(ans,r)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
# input
A = input()
B = input()
C = input()

ipt = (A, B, C)

# process
def eq(s, t):
    for i in range(len(s)):
        if s[i] != t[i] and s[i] != "?" and t[i] != "?":
            return False
    return True

def getConNumNum(s, t):
    flg = True
    if len(s) > len(t):
        s, t = t, s
        flg = False

    f, b = 0, 0
    for i in reversed(range(1, len(s)+1)):
        if b < 1 and eq(s[-i:],t[:i]):
            b = i
        if f < 1 and eq(s[:i],t[-i:]):
            f = i

    if flg:
        return (b, f)
    else:
        return (f, b)

def connect(s, t, n):
    sl = list(s)
    tl = list(t)

    for i in range(len(s)-n):
        if sl[i] == "?":
            sl[i] = "a"
    
    for i in range(n, len(t)):
        if tl[i] == "?":
            tl[i] = "a"

    for i in range(n):
        if sl[-n+i] == "?":
            sl[-n+i] = tl[i]
    sl.extend(tl[n:])
    return "".join(map(str, sl))

conNum = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
for i, j in ((0, 1), (1, 2), (2, 0)):
    # conNum[i][j], conNum[j][i] = getConNumNum(ipt[i], ipt[j])
    b, f = getConNumNum(ipt[i], ipt[j])
    conNum[i][j] = b
    conNum[j][i] = f

strs = [] 
for i in range(3):
    for j in range(3):
        if i == j:
            continue

        k = 3-(i+j)
        sl = len(ipt[i]) + len(ipt[j]) + len(ipt[k]) - conNum[i][j]
        strs.append((sl - conNum[j][k], i, j, k))
        strs.append((sl - conNum[k][i], k, i, j))

_, i, j, k = min(strs)
ans = connect(connect(ipt[i], ipt[j], conNum[i][j]), ipt[k], conNum[j][k])

# output
# print(conNum)
# print(strs)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools 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 merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge2(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 merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b[i:], a):
      yield -i
  yield -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_b1, a_b2, a_b3  = map(list, [merge1(a,b), merge2(a,b), merge3(a,b)])
  a_b = set(chain(a_b1, a_b2, a_b3))
  a_c1, a_c2, a_c3  = map(list, [merge1(a,c), merge2(a,c), merge3(a,c)])
  a_c = set(chain(a_c1, a_c2, a_c3))
  b_c1, b_c2, b_c3  = map(list, [merge1(b,c), merge2(b,c), merge3(b,c)])
  b_c = set(chain(b_c1, b_c2, b_c3))
  
  for i in a_b1:
    for j in a_c1:
      if j+lc <= i or i+lb <= j or j-i in b_c and comp_dup(0,i,j,a,b,c):
        return la
  
  can = (  
    chain(
      (lb+i for i in a_b2 if (a_c1 and a_c1[0]+lc <= i) or (b_c1 and la <= i+b_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:j+lc<=i+lb), a_c1+a_c2))),
      (lb+i for i in count(a_b2[-1]+1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lc<i), a_c2))),
    ),
    
    chain(
      (la-i for i in a_b3 if (b_c1 and i+b_c1[0]+lc <= 0) or (a_c1 and i+lb <= a_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:i<=j), a_c1+a_c3))),
      (la-i for i in count(a_b3[-1]-1, -1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:i+lb<j), a_c3))),
    ),
    
    chain(
      (lc+i for i in a_c2 if (a_b1 and a_b1[0]+lb <= i) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:j+lb<=i+lc), a_b1+a_b2))),
      (lc+i for i in count(a_c2[-1]+1) if any(i-j in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lb<i), a_b2))),
    ),
    
    chain(
      (la-i for i in a_c3 if (a_b1 and i+lc <= a_b1[-1]) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:i<=j), a_b1+a_b3))),
      (la-i for i in count(a_c3[-1]-1, -1) if any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in dropwhile((lambda j:i+lc<j), a_b3))),
    ),
  )
  
  return min(map(next, can))

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 10010
    BC = [1] * 10010
    AC = [1] * 10010
    for i in range(-lb, la+1):
        AB[i] = check(A[max(0, i):min(la, i+lb)], B[max(0, -i):min(lb, la-i)])
    for i in range(-lc, lb+1):
        BC[i] = check(B[max(0, i):min(lb, i+lc)], C[max(0, -i):min(lc, lb-i)])
    for i in range(-lc, la+1):
        AC[i] = check(A[max(0, i):min(la, i+lc)], C[max(0, -i):min(lc, la-i)])

    ans = la+lb+lc
    for i in range(-lb-lc-3, la+lc+3):
        if not AB[i]:
            continue
        for j in range(-lc-3, lb+3):
            if BC[j] and AC[i+j]:
                l = min(0, i, i+j)
                r = max(la, lb+i, lc+i+j)
                #print(i, j, l, r, r-l)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 10010
    BC = [1] * 10010
    AC = [1] * 10010
    for i in range(-lb, la+1):
        AB[i] = check(A[max(0, i):min(la, i+lb)], B[max(0, -i):min(lb, la-i)])
    for i in range(-lc, lb+1):
        BC[i] = check(B[max(0, i):min(lb, i+lc)], C[max(0, -i):min(lc, lb-i)])
    for i in range(-lc, la+1):
        AC[i] = check(A[max(0, i):min(la, i+lc)], C[max(0, -i):min(lc, la-i)])

    ans = la+lb+lc
    for i in range(-lb-lc-3, la+lc+3):
        if not AB[i]:
            continue
        for j in range(-lc, lb+1):
            if BC[j] and AC[i+j]:
                l = min(0, i, i+j)
                r = max(la, lb+i, lc+i+j)
                #print(i, j, l, r, r-l)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 10010
    BC = [1] * 10010
    AC = [1] * 10010
    for i in range(-lb, la+1):
        AB[i] = check(A[max(0, i):min(la, i+lb)], B[max(0, -i):min(lb, la-i)])
    for i in range(-lc, lb+1):
        BC[i] = check(B[max(0, i):min(lb, i+lc)], C[max(0, -i):min(lc, lb-i)])
    for i in range(-lc, la+1):
        AC[i] = check(A[max(0, i):min(la, i+lc)], C[max(0, -i):min(lc, la-i)])

    ans = la+lb+lc
    for i in range(-lb-lc, la+lc+1):
        if not AB[i]:
            continue
        for j in range(-lc, lb+1):
            if BC[j] and AC[i+j]:
                l = min(0, i, i+j)
                r = max(la, lb+i, lc+i+j)
                #print(i, j, l, r, r-l)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

A = sr(); B = sr(); C = sr()

def check(x, y):
    l = min(len(x), len(y))
    flag = True
    for i in range(l):
        if x[i] == '?' or y[i] == '?':
            continue
        if x[i] != y[i]:
            flag = False
            break
    return flag

def merge(x, y, i):
    l = len(x)
    if check(x[i:], y):
        return x[:i] + y
    else:
        return None

answer = ' ' * (len(A) + len(B) + len(C))
for x, y, z in permutations([A, B, C], 3):
    lx = len(x)
    for i in range(lx):
        x2 = merge(x, y, i)
        if x2 is None:
            continue
        lx2 = len(x2)
        for i in range(lx2):
            x3 = merge(x2, z, i)
            if x3 is None:
                continue
            if len(x3) < len(answer):
                answer = x3
      
print(len(answer))
# 25

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

def concat1(x,y,len_only=False):
    n = len(x)
    m = len(y)
    if len_only:
        ret = [n+m]
    else:
        ret = [x+y]
    for i in range(n):
        con_flag = False
        d = {}
        for j in range(i,min(i+m,n)):
            if x[j] == '?' and y[j-i] != '?':
                d[j] = y[j-i]
            elif x[j] != y[j-i] and x[j] != '?' and y[j-i] != '?':
                con_flag = True
                break
            else:
                continue
        if con_flag:
            continue
        else:
            if len_only:
                if n-i <= m-1:
                    ret.append(m+i)
                else:
                    ret.append(n)
            else:
                if n-i <= m-1:
                    now = x+y[n-i:]
                    for k,v in d.items():
                        now[k] = v
                else:
                    now = x
                    for k,v in d.items():
                        now[k] = v
                ret.append(now)

    return ret

def concat2(xlist,y):
    ans = float('inf')
    for x in xlist:
        now = concat1(x,y,len_only=True)
        min_ = min(now)
        if min_ < ans:
            ans = min_
    return ans


ret1 = concat2(concat1(a,b),c)
#ret2 = concat2(concat1(a,c),b)
#ret3 = concat2(concat1(b,a),c)
#ret4 = concat2(concat1(b,c),a)
#ret5 = concat2(concat1(c,a),b)
#ret6 = concat2(concat1(c,b),a)

print(ret1)
#print(min(ret1,ret2,ret3,ret4,ret5,ret6))

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

a = list(str(input()))
b = list(str(input()))
c = list(str(input()))

def min_len(X):
    min_ = float('inf')
    for x in X:
        if len(x) < min_:
            min_ = len(x)
    return min_

def concat1(x,y):
    ret = []
    n = len(x)
    m = len(y)
    for i in range(n):
        con_flag = False
        for j in range(i,min(i+m,n)):
            if x[j] != y[j-i] and x[j] != '?' and y[j-i] != '?':
                con_flag = True
                break
        if con_flag:
            continue
        else:
            if n-i <= m-1:
                ret.append(x+y[n-i:])
            else:
                ret.append(x)
    return ret

def concat2(xlist,y):
    ans = float('inf')
    for x in xlist:
        now = concat1(x,y)
        min_ = min_len(now)
        if min_ < ans:
            ans = min_
    return ans


ret1 = concat2(concat1(a,b),c)
ret2 = concat2(concat1(a,c),b)
ret3 = concat2(concat1(b,a),c)
ret4 = concat2(concat1(b,c),a)
ret5 = concat2(concat1(c,a),b)
ret6 = concat2(concat1(c,b),a)

print(min(ret1,ret2,ret3,ret4,ret5,ret6))

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

ques = ord('?')

def Z_algo2(s):
    ls = len(s)
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and (s[j] == s[i+j] or s[j] == '?' or s[i+j] == '?'):
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    return lcp

def Z_algo(s,t):
  l = [0]*len(t)
  for i in range(len(t)):
    j = 0
    while j < len(s) and i+j < len(t) and (s[j] == t[i+j] or s[j] == ques or t[i+j] == ques):
      j += 1
    l[i] = j
  return l

a = list(map(ord, list(ns())))
b = list(map(ord, list(ns())))
c = list(map(ord, list(ns())))

l = [a, b, c]
g = [[0]*3 for _ in range(3)]
for i in range(3):
    for j in range(3):
        if i != j:
            g[i][j] = Z_algo(l[i],l[j])
            # print(i,j,g[i][j])
ans = sum(len(x) for x in l)
for i in range(3):
    for j in range(3):
        if i == j: continue
        k = 3-i-j
        li = [ii for ii in range(len(l[i])) if g[j][i][ii] >= min(len(l[i]) - ii, len(l[j]))]
        lj = [ii for ii in range(len(l[j])) if g[k][j][ii] >= min(len(l[j]) - ii, len(l[k]))]
        lk = [ii for ii in range(len(l[i])) if g[k][i][ii] >= min(len(l[i]) - ii, len(l[k]))]
        if li:
            c = max(len(l[i]), min(li) + len(l[j])) + len(l[k])
            if ans > c: ans = c
        for ii in li:
            for jj in lj:
                kk = ii + jj
                if kk >= len(l[i]) or g[k][i][kk] >= min(len(l[i]) - kk, len(l[k])):
                    c = max(len(l[i]), ii + len(l[j]), kk + len(l[k]))
                    if ans > c: ans = c

print(ans)

Submission status: Wrong Answer

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

A = input().rstrip()
B = input().rstrip()
C = input().rstrip()

def check(P1, P2, P3):
    L1 = len(P1)
    L2 = len(P2)
    L3 = len(P3)
    L = max([L1, L2, L3])*2+3

    P12 = [True]*L
    for i2 in range(-L2, L1+1):
        for l in range(max(i2, 0), min(i2+L2, L1)):
            if P1[l] != "?" and P2[l-i2] != "?" and P1[l] != P2[l-i2]:
                P12[i2] = False
                break
    
    P13 = [True]*L
    for i3 in range(-L3, L1+1):
        for l in range(max(i3, 0), min(i3+L3, L1)):
            if P1[l] != "?" and P3[l-i3] != "?" and P1[l] != P3[l-i3]:
                P13[i3] = False
                break
    
    P23 = [True]*L
    for i3 in range(-L3, L2+1):
        for l in range(max(i3, 0), min(i3+L3, L2)):
            if P2[l] != "?" and P3[l-i3] != "?" and P2[l] != P3[l-i3]:
                P23[i3] = False
                break

    ans = L1 + L2 + L3
    for i2 in range(-L2, L1+1):
        for i3 in range(-L3, L1+1):
            if P12[i2] and P13[i3] and P23[i3-i2]:
                ans = min(ans, max([L1, L2+i2, L3+i3]) - min([0, i2, i3]))
    return ans



print(min([check(A, B, C), check(B, A, C), check(C, A, B)]))