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:
import sys
import itertools
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A = list(input())
B = list(input())
C = list(input())

N = len(A)


def compare(x, y):
    # print("COMPARE:", x, y)
    if not (x and y):
        return False
    for a, b in zip(x, y):
        if a == b or a == '?' or b == '?':
            continue
        else:
            # print("False")
            return False
    # print("True")
    return True


def getNewStr(X, Y):
    ans = []
    for _ in range(2):
        X, Y = Y, X
        for i in range(N, -1, -1):
            if compare(X[-i:], Y[:i]):
                ans.append(X + Y[i:])
                break

    return ans


def getMaxStr(X, Y):
    # print("getMAX", X, Y)
    n = len(X)
    m = len(Y)
    ans = 0
    for i in range(n, -1, -1):
        if m < i:
            if compare(X[i - m:i], Y):
                ans = max(ans, m)
                break
        else:
            if compare(X[:i], Y[-i:]):
                ans = max(ans, i)
                break

    for i in range(n, -1, -1):
        if m < i:
            if compare(X[-i: -i + m], Y):
                ans = max(ans, m)
                break
        else:
            if compare(X[-i:], Y[i:]):
                ans = max(ans, i)
                break

    return ans


# まずAとBを比較
# 先頭から

ans = N * 3
# for _ in range(3):
# A, B, C = C, A, B

for A, B, C in itertools.permutations([A, B, C]):

    rs = getNewStr(A, B)

    # print("rs", rs)
    if not rs:
        continue

    for r in rs:
        m = getMaxStr(r, C)
        # print("r", r, "m", m)
        if m == 0:
            ans = min(ans, len(r)+len(C))
        elif m == len(C):
            ans = min(ans, len(r))
        else:
            ans = min(ans, len(r)+len(C)-m)

print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 20000, [1] * 20000, [1] * 20000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+10000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+10000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+10000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-2000, 2000):
        if ab[i+10000] and bc[j-i+10000] and ac[j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 20000, [1] * 20000, [1] * 20000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+10000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+10000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+10000]= 0
ans = 6000

for i in range(-2000, 2000):
    for j in range(-2000, 2000):
        if ab[i+10000] and bc[j-i+10000] and ac[j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 120000, [1] * 120000, [1] * 120000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+6000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+6000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+6000]= 0
ans = 6000

for i in range(-2000, 2000):
    for j in range(-2000, 2000):
        if ab[i+6000] and bc[j-i+6000] and ac[j+6000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wrapper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wrapper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))
  
@listify
def match(a,b):
  for i in range(len(a)+1):
    if comp_wild(a[i:], b):
      yield i

def solve(*keys):
  len_keys = list(map(len, keys))
  mt =  { (i,j):match(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  def candicate(x,y,z):
    ret = sum(len_keys)
    for i in mt[x,y]:
      if ret <= i+len_keys[y]:
        break
      for j in mt[y,z]:
        if ret <= i+j+len_keys[z]:
          break
        if len_keys[x] <= i+j or i+j in mt[x,z]:
          ret = min(ret, max(len_keys[x], i+len_keys[y], i+j+len_keys[z]))
          break
      if i+len_keys[y] < len_keys[x]:
        for j in mt[x,z]:
          if i+len_keys[y] < j:
            ret = min(ret, j+len_keys[z])
            break
    return ret
  
  return min( candicate(*xyz) for xyz in permutations(range(3), 3) )

print(solve(*(input() for i in range(3))))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wrapper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wrapper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))
  
@listify
def match(a,b):
  for i in range(len(a)+1):
    if comp_wild(a[i:], b):
      yield i

def solve(*keys):
  len_keys = list(map(len, keys))
  mt =  { (i,j):match(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  def candicate(x,y,z):
    ret = sum(len_keys)
    for i in mt[x,y]:
      if ret <= i+len_keys[y]:
        break
      for j in mt[y,z]:
        if ret <= i+j+len_keys[z]:
          break
        if len_keys[x] <= i+j or i+j in mt[x,z]:
          ret = min(ret, max(len_keys[x], i+len_keys[y], i+j+len_keys[z]))
          break
      if i+len_keys[y] < mt[x,z][-1]:
        ret = min(ret, mt[x,z][-1]+len_keys[z])
    
    return ret
  
  return min( candicate(*xyz) for xyz in permutations(range(3), 3) )

print(solve(*(input() for i in range(3))))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wrapper(*args, **kwargs):
    return set(fn(*args, **kwargs))
  return wrapper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))
  
@listify
def match(a,b):
  for i in range(len(a)+1):
    if comp_wild(a[i:], b):
      yield i

def solve(*keys):
  len_keys = list(map(len, keys))
  mt =  { (i,j):match(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  def candicate(x,y,z):
    ret = sum(len_keys)
    for i in mt[x,y]:
      for j in mt[y,z]:
        if len_keys[x] <= i+j or i+j in mt[x,z]:
          ret = min(ret, max(len_keys[x], i+len_keys[y], i+j+len_keys[z]))
    return ret
  
  return min( candicate(*xyz) for xyz in permutations(range(3), 3) )

print(solve(*(input() for i in range(3))))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wrapper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wrapper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))
  
@listify
def match(a,b):
  for i in range(len(a)+1):
    if comp_wild(a[i:], b):
      yield i

def solve(*keys):
  len_keys = list(map(len, keys))
  mt =  { (i,j):match(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  def candicate(x,y,z):
    ret = sum(len_keys)
    for i in mt[x,y]:
      if ret <= i+len_keys[y]:
        break
      for j in mt[y,z]:
        if ret <= i+j+len_keys[z]:
          break
        if len_keys[x] <= i+j or i+j in mt[x,z]:
          ret = min(ret, max(len_keys[x], i+len_keys[y], i+j+len_keys[z]))
          break
    return ret
  
  return min( candicate(*xyz) for xyz in permutations(range(3), 3) )

print(solve(*(input() for i in range(3))))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from functools import wraps

def setify(fn):
  @wraps(fn)
  def wrapper(*args, **kwargs):
    return set(fn(*args, **kwargs))
  return wrapper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))
  
@setify
def match(a,b):
  for i in range(len(a)+1):
    if comp_wild(a[i:], b):
      yield i

def solve(*keys):
  len_keys = list(map(len, keys))
  mt =  { (i,j):match(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  def candicate(x,y,z):
    ret = sum(len_keys)
    for i in mt[x,y]:
      if ret <= i+len_keys[y]:
        break
      for j in mt[y,z]:
        if ret <= i+j+len_keys[z]:
          break
        if len_keys[x] <= i+j or i+j in mt[x,z]:
          ret = min(ret, max(len_keys[x], i+len_keys[y], i+j+len_keys[z]))
          break
    return ret
  
  return min( candicate(*xyz) for xyz in permutations(range(3), 3) )

print(solve(*(input() for i in range(3))))

Submission status: Wrong Answer

Solution code:
def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 120000, [1] * 120000, [1] * 120000

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+6000]= 0
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+6000]= 0
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+6000]= 0
ans = 6000

for i in range(-2000, 2000):
    for j in range(-2000, 2000):
        if ab[i+6000] and bc[j-i+6000] and ac[j+6000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Wrong Answer

Solution code:
def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 120000, [1] * 120000, [1] * 120000

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+6000]= 0
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+6000]= 0
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+6000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+10000] and bc[j-i+10000] and ac[j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Wrong Answer

Solution code:
def match(x, y):
    """
    １文字x, yが一致するか少なくとも一方が？であればTrueを返す。
    """
    return x == y or x == "?" or y == "?"


def func(a, b, c, la, lb, lc):
    """
    文字列の並びがa->b->cの場合を仮定して考える。
    aに対するb, cの配置が高々2000 * 2000通りあるので、文字列が一致するかの判定はO(1)でしないとTLE。
    これは先にaとb、bとc、aとcに対して文字列の一致を前処理確認しておけばOK <= 思いつかなかったので反省。

    ab[i] = (b[0]をa[i]から重ねたとき、合成文字列は一致するか)
    bc[i] = (c[0]をb[i]から重ねたとき、合成文字列は一致するか)
    ac[i] = (c[0]をa[i]から重ねたとき、合成文字列は一致するか)
    とおく。後ろに[True] * 2000を付け加えているのはaとbがdisjointな場合を考慮するため。
    """
    ab = [True] * (la + 2000)
    bc = [True] * (lb + 2000)
    ac = [True] * (la + 2000)

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

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

    for i in range(la):
        for j in range(min(la - i, lc)):
            if not match(a[i + j], c[j]):
                ac[i] = False
                break
    #print("ab={}".format(ab[:la]))
    #print("bc={}".format(bc[:lb]))
    #print("ac={}".format(ac[:la]))
    """
    前処理終わり。これより実際の比較を行う。
    """
    ans = la + lb + lc
    for i in range(la):
        for j in range(lb):
            if ab[i] and bc[j] and ac[i + j]:
                preans = max(la, i + lb, i + j + lc)
                ans = min(ans, preans)

    return ans

def main():
    a = input()
    b = input()
    c = input()
    la = len(a)
    lb = len(b)
    lc = len(c)
    ans = func(a, b, c, la, lb, lc)
    ans = min(ans, func(a, c, b, la, lc, lb))
    ans = min(ans, func(b, a, c, lb, la, lc))
    ans = min(ans, func(b, c, a, lb, lc, la))
    ans = min(ans, func(c, a, b, lc, la, lb))
    ans = min(ans, func(c, b, a, lc, lb, la))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

def comstr(p,q):
  ans = []
  for i in range(len(p)):
    flg = False
    ans = [p[:i]]
    pi = i
    qi = 0
    while pi < len(p) and qi < len(q):
      if p[pi] == q[qi]:
        ans.append(q[qi])
      elif p[pi] == '?':
        ans.append(q[qi])
      elif q[qi] == '?':
        ans.append(p[pi])
      else:
        flg = True
        break
      pi += 1
      qi += 1
    if flg:
      continue
    break
  if flg:
    return p + q
  if pi < len(p):
    ans.append(p[pi:])
  elif qi < len(q):
    ans.append(q[qi:])
  return "".join(ans)

def comstr2(x,y,z):
  return comstr(comstr(x,y),z)

cand = [comstr2(a,b,c), comstr2(a,c,b), comstr2(b,a,c), comstr2(b,c,a), comstr2(c,a,b), comstr2(c,b,a)]
#print(cand)
print(min(list(map(len,cand))))

Submission status: Wrong Answer

Solution code:
def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A = len(a)
B = len(b)
C = len(c)
ab = [False] * 20000
bc = [False] * 20000
ca = [False] * 20000

for i in range(A):
    for j in range(B):
        if match(a[i], b[j]):
            ab[i - j + 10000]= True
for i in range(B):
    for j in range(C):
        if match(b[i], c[j]):
            bc[i - j + 10000]= True
for i in range(C):
    for j in range(A):
        if match(c[i], a[j]):
            ca[i - j + 10000]= True
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if not ab[i + 10000] and not bc[i + 10000] and not ca[i + 10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

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(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 comp33(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]) and comp(a[m-i:n-i],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 comp33(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:
a = input()
b = input()
c = input()
la = len(a)
lb = len(b)
lc = len(c)

def match(x, y):
    """
    １文字x, yが一致するか少なくとも一方が？であればTrueを返す。
    """
    return x == y or x == "?" or y == "?"


def func(a, b, c, la, lb, lc):
    """
    文字列の並びがa->b->cの場合を仮定して考える。
    aに対するb, cの配置が高々2000 * 2000通りあるので、文字列が一致するかの判定はO(1)でしないとTLE。
    これは先にaとb、bとc、aとcに対して文字列の一致を前処理確認しておけばOK <= 思いつかなかったので反省。

    ab[i] = (b[0]をa[i]から重ねたとき、合成文字列は一致するか)
    bc[i] = (c[0]をb[i]から重ねたとき、合成文字列は一致するか)
    ac[i] = (c[0]をa[i]から重ねたとき、合成文字列は一致するか)
    とおく。後ろに[True] * 2000を付け加えているのはaとbがdisjointな場合を考慮するため。
    """
    ab = [True] * (la + 2000)
    bc = [True] * (lb + 2000)
    ac = [True] * (la + 2000)

    for i in range(la):
        for j in range(min(la - i, lb)):
            if not match(a[i + j], b[j]):
                ab[i] = False
                break
    
    for i in range(lb):
        for j in range(min(lb - i, lc)):
            if not match(b[i + j], c[j]):
                bc[i] = False
                break
    
    for i in range(la):
        for j in range(min(la - i, lc)):
            if not match(a[i + j], c[j]):
                ac[i] = False
                break
    
    """
    前処理終わり。これより実際の比較を行う。
    """
    ans = 6000
    for i in range(la):
        for j in range(lb):
            if ab[i] and bc[j] and ac[i + j]:
                preans = max(la, i + j + lc)
                ans = min(ans, preans)
    
    return ans


ans = func(a, b, c, la, lb, lc)
ans = min(ans, func(a, c, b, la, lc, lb))
ans = min(ans, func(b, a, c, lb, la, lc))
ans = min(ans, func(b, c, a, lb, lc, la))
ans = min(ans, func(c, a, b, lc, la, lb))
ans = min(ans, func(c, b, a, lc, lb, la))
print(ans)

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  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:
a = input()
b = input()
c = input()


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = {i: True for i in range(-10000, 10001)}
    for i in range(len(s)):
        for j in range(len(t)):
            if not comp(s[i], t[j]):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ca = check(c, a)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ca[c_idx] and check_bc[b_idx - c_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
a = input()
b = input()
c = input()


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = defaultdict(lambda: True, )
    for i in range(len(s)):
        for j in range(len(t)):
            if not comp(s[i], t[j]):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ca = check(c, a)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ca[c_idx] and check_bc[b_idx - c_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)

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]) 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 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 0
  
  return la
 
a=input()
b=input()
c=input()
 
print(min_merge(a,b,c))

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
  
  return la
 
a=input()
b=input()
c=input()
 
print(min_merge(a,b,c))