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:
l = ["","",""]
d = [["","",""],["","",""],["","",""]]
l[0] = str(input())
l[1] = str(input())
l[2] = str(input())
for i in range(3):
  for j in range(3):
    if i!=j:
      p = min(len(l[i]),len(l[j]))
      s = 0
      for k in reversed(range(p)):
        t = 0
        for x in range(k+1):
          if l[i][x-k-1]!=l[j][x]:
            if ((l[i][x-k-1]!="?") & (l[j][x]!="?")):
              t = 1
              break
        if t==0:
          s = k+1
          break
      d[i][j] = s
r = len(l[0])+len(l[1])+len(l[2])
u = (d[0][1]+d[1][2]+d[2][0])-min(min(d[0][1],d[1][2]),d[2][0])
v = (d[1][0]+d[2][1]+d[0][2])-min(min(d[1][0],d[2][1]),d[0][2])
print(r-min(u,v))

Submission status: Wrong Answer

Solution code:
import re
a = input()
b = input()
c = input()

def eq(x, y):
    if len(x) != len(y):
        return False
    for v1, v2 in zip(x, y):
        if v1 == "?" or v2 == "?":
            continue
        if v1 != v2:
            return False
    return True

def match(A, B):
    for i in reversed(range(len(A) + 1)):
        if eq(A[-i:], B[:i]):
            return i
    return 0

def merge(A, B, i):
    if i == 0:
        return A + B
    r = ""
    for v1, v2 in zip(A[-i:], B[:i]):
        if v1 == v2:
            r += v1
        elif v1 == "?":
            r += v2
        else:
            r += v1

    return A[:-i] + r + B[i:]

import itertools
minv = float('inf')
value = None
for v in itertools.permutations([a, b, c], r=3):
    A, B, C = v
    s = merge(A, B, match(A, B))
    s = merge(s, C, match(s, C))
    l = len(s)
    if minv >= l:
        minv = l
        value = s
print(value)

Submission status: Wrong Answer

Solution code:
def search(w1, w2):
	i = p = 0
	n1 = len(w1)
	n2 = len(w2)
	while i < n1 and p < n2:
		if w1[i] == w2[p] or w1[i] == "?" or w2[p] == "?":
			i += 1
			p += 1
		elif p == 0:
			i += 1
		else:
			i -= p - 1
			p = 0
		if i == n1:
			return p, i
	return p, i


from itertools import permutations
a = input()
b = input()
c = input()
s = len(a) + len(b) + len(c)
ans = 1e9
for n1, n2, n3 in permutations((a, b, c), 3):
	x, ii = search(n1, n2)
	t = list(n1)
	tt = list(n2)
	if x:
		for i in range(x):
			if not t[ii - x + i] == "?":
				tt[i] = t[ii - x + i]
	tt = "".join(tt + t[ii:])
	y, _ = search(tt, n3)
	ans = min(ans, s - x - y)
	# print(n1,n2,n3,x,y,tt,ii,s-x-y)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

def check_match(s, t):
    for x, y in zip(s[-len(t):], t):
        flag1 = x == y
        flag2 = x == "?" or y == "?"
        if not flag1 and not flag2:
            return False
    return True

def connect(x, y, z):
    idx_1 = 0
    for i in range(1, len(x) + 1):
        if check_match(x, y[:i]):
            idx_1 = max(idx_1, i)
            
    idx_2 = 0
    for i in range(1, len(y) + 1):
        if check_match(y, z[:i]):
            idx_2 = max(idx_2, i)
            
    return idx_1, idx_2

ans = 10000
for x, y, z in permutations([a, b, c], 3):
    idx_1, idx_2 = connect(x, y, z)
    ans = min(ans, len(x + y[idx_1:] + z[idx_2:]))
print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()


def stack2(a, b):
    max_reduce = min(len(a), len(b))
    reduce = 0
    for i in reversed(range(max_reduce)):
        a_end = a[len(a)-i-1:]
        b_begin = b[:i+1]
        flag = True
        for j in range(len(a_end)):
            if a_end[j] != b_begin[j] and a_end[j] != '?' and b_begin[j] != '?':
                flag = False
                break
        if flag == True:
            reduce = len(a_end)
            break
    return reduce

S = len(a) + len(b) + len(c)

r1 = stack2(a, b) + stack2(b, c)
r2 = stack2(a, c) + stack2(c, b)
r3 = stack2(b, a) + stack2(a, c)
r4 = stack2(b, c) + stack2(c, a)
r5 = stack2(c, a) + stack2(a, b)
r6 = stack2(c, b) + stack2(b, a)

r = max(r1, r2, r3, r4, r5, r6)

print(S-r)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()

def check(left, right):
    for i in range(len(left)):
        if(left[i] != "?" and right[i] != "?" and left[i] != right[i]):
            return False
    return True

def merge(left, right):
    ans = ""
    for i in range(len(left)):
        if(left[i] == "?"):
            ans += right[i]
        else:
            ans += left[i]
    return ans

def connect(left, right):
    for i in range(len(left)):
        last_index = min(len(left), i + len(right))
        if(check(left[i:last_index], right[:last_index-i]) == True):
            if(last_index < len(left)):
                return left
            else:
                return left[:i] + merge(left[i:last_index], right[:last_index-i]) + right[last_index-i:]
    else:
        return left + right    

ansList = []
ansList.append(connect(a, connect(b, c)))
ansList.append(connect(a, connect(c, b)))
ansList.append(connect(b, connect(a, c)))
ansList.append(connect(b, connect(c, a)))
ansList.append(connect(c, connect(a, b)))
ansList.append(connect(c, connect(b, a)))

minAns = 99999
for ans in ansList:
    minAns = min(minAns, len(ans))
print(minAns)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
S = [input() for i in range(3)]

def combine(s,t):
    ns = len(s)
    nt = len(t)
    mi = 0
    res = ""
    for i in range(1,min(ns,nt)+1):
        ss = list(s[-i:])
        st = list(t[:i])
        same =True 
        for j,(x,y) in enumerate(zip(ss,st)):
            if x == y:
                continue
            elif x == '?':
                ss[j] = y
            elif y == '?':
                continue
            else:
                same = False
                break
        if same:
            mi = i
            res = ss
    return mi,"".join(res)


cand = []
for x,y,z in permutations(range(3),3):
    a,b,c = S[x],S[y],S[z]
    ##print(a,b,c)
    n,res = combine(a,b)
    if n == 0:
        ab = a+b
    else:
        ab = a[:-n] + res + b[n:]
    n,res = combine(ab,c)
    if n == 0:
        abc = ab + c
    else:
        abc = ab[:-n] + res + b[n:]
    cand.append(abc)

nans = list(map(lambda x : len(x), cand))
print(min(nans))

Submission status: Wrong Answer

Solution code:
a=list((input()))
b=list((input()))
c=list((input()))

def f(s,t):
    #print(s,t)
    for i,j in zip(s,t):
        if i == j or i=="?" or j=="?":
            pass
        else:
            return False
    else:
        return True
            
        
def calc(a,c):
    l=0
    r=len(a)*2+1
    while r-l>1:
        m=(l+r)//2
        if f(a[-m:],c[:m]):
            l = m
        else:
            r = m
        #print(l,m,r)
    return l
ans = len(a) +len(b) + len(c)
max_ = 0
for case in [((b,a),(a,c)),((a,b),(b,c)),((c,a),(a,b)),((c,b),(b,a)),((b,c),(c,a)),((a,c),(c,b))]:
    s = 0
    for i,j in case:
        s += (calc(i,j))//2
    max_ =max(max_,s)
print(ans-max_)

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

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

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

# MOD = 998244353


A, B, C = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(3)]
A = list(map(ord, A))
B = list(map(ord, B))
C = list(map(ord, C))

memo = {}
Q = ord('?')


def get_ok_idx(A, B):
    key = str(A) + str(B)
    if key in memo:
        return memo[key]
    ret = []
    for i in range(len(A) + 1):
        for a, b in zip(A[i:], B):
            if a != b and a != Q and b != Q:
                break
        else:
            ret.append(i)
    memo[key] = ret
    return ret


# A = np.array(A, dtype=int)
# B = np.array(B, dtype=int)
# C = np.array(C, dtype=int)

def solve(A, B, C):
    ok_ab = get_ok_idx(A, B)
    ok_bc = get_ok_idx(B, C)
    ok_cb = get_ok_idx(C, B)
    ok_ac = get_ok_idx(A, C)

    ok_ab_flags = [False] * (len(A) + 1)
    ok_bc_flags = [False] * (len(B) + 1)
    ok_cb_flags = [False] * (len(C) + 1)
    ok_ac_flags = [False] * (len(A) + 1)
    for i in ok_ab:
        ok_ab_flags[i] = True
    for i in ok_bc:
        ok_bc_flags[i] = True
    for i in ok_cb:
        ok_cb_flags[i] = True
    for i in ok_ac:
        ok_ac_flags[i] = True

    ret = INF
    for ab, bc in itertools.product(ok_ab, ok_bc):
        if ab + bc >= len(A) or ok_ac_flags[ab + bc]:
            ret = min(ret, max(len(A), ab + len(B), ab + bc + len(C)))
    for ac, bc in itertools.product(ok_ac, ok_bc):
        if ac - bc < 0:
            continue
        if ac - bc >= len(A) or ok_ab_flags[ac - bc]:
            ret = min(ret, max(len(A), ac - bc + len(B), ac + len(C)))
    for ab, ac in itertools.product(ok_ab, ok_ac):
        if ab < ac and (ac - ab >= len(B) or ok_ab_flags[ac - ab]):
            ret = min(ret, max(len(A), ab + len(B), ac + len(C)))
        elif ac < ab and (ab - ac >= len(C) or ok_ac_flags[ab - ac]):
            ret = min(ret, max(len(A), ab + len(B), ac + len(C)))
    return ret


ans = len(A) + len(B) + len(C)
ans = min(ans, solve(A, B, C))
ans = min(ans, solve(A, C, B))
ans = min(ans, solve(B, A, C))
ans = min(ans, solve(B, C, A))
ans = min(ans, solve(C, A, B))
ans = min(ans, solve(C, B, A))
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(a, b, c):
    ans = 6000
    # for line in get_merge_points(a, b, one_result=False):
    #     # print(line)
    #     ans = min(ans, list(get_merge_points(line, c, one_result=True))[0])
    # return ans
    for b_index in range(len(a) + 1):
        for c_index in range(b_index, b_index + len(b) + 1):
            if max(len(a), b_index + len(b), c_index + len(c)) > ans:
                break
            if check(a, b, c, b_index, c_index):
                ans = min(ans, max(len(a), b_index + len(b), c_index + len(c)))
                break

    return ans


def check(a, b, c, b_index, c_index):
    # a and b
    for p in range(b_index, min(c_index, len(a), b_index + len(b))):
        if a[p] and b[p - b_index] and a[p] != b[p - b_index]:
            return False

    for p in range(c_index, min(b_index + len(b), c_index + len(c))):
        if c[p - c_index] and b[p - b_index] and c[p - c_index] != b[p - b_index]:
            return False

    for p in range(c_index, min(len(a), b_index + len(b), c_index + len(c))):
        if a[p] == b[p - b_index] == c[p - c_index] or (
                (a[p] == 0) + (b[p - b_index] == 0) + (c[p - c_index] == 0)) > 2:
            continue
        elif a[p] and b[p - b_index] and c[p - c_index] and (
                a[p] != b[p - b_index] or b[p - b_index] != c[p - c_index] or c[p - c_index] != a[p]):
            return False
        elif a[p] == b[p - b_index] or a[p] == c[p - c_index] or b[p - b_index] == c[p - c_index]:
            continue
        else:
            return False
    return True


def get_merge_points(base, ext, one_result=True):
    for point in range(len(base) + 1):
        flag = set()
        for i in range(point, min(len(base), point + len(ext))):
            if base[i] == ext[i - point]:
                '?? or aa'
                continue
            elif base[i] == 0 or ext[i - point] == 0:
                flag.add(i)
            else:
                break
        else:
            if one_result:
                yield max(len(base), point + len(ext))
                return
            if len(base) > point + len(ext):
                source = list(base)
            else:
                source = list(base[:point]) + list(ext)

            for f in flag:
                source[f] = base[f] if base[f] != 0 else ext[f - point]
            yield source


def convert(st):
    result = []
    for s in st:
        if s == '?':
            result.append(0)
        else:
            result.append(ord(s) - 90)
    return result


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

get_merge_points(a, b)

print(min(
    solve(a, b, c),
    solve(a, c, b),
    solve(b, a, c),
    solve(b, c, a),
    solve(c, a, b),
    solve(c, b, a)
))

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()

def calc(a,b):
    ans = ''
    for i in range(len(a)):
        len_ab = min(len(a)-i, len(b))
        tmp_a = a[i: i+len_ab]
        tmp_b = b[:len_ab]
        tmp = ''
        flag = 1
        for j in range(len_ab):
            if(tmp_a[j]==tmp_b[j]):
                tmp += tmp_a[j]
            elif(tmp_a[j]=='?'):
                tmp += tmp_b[j]
            elif(tmp_b[j]=='?'):
                tmp += tmp_a[j]
            else:
                flag = 0
                break
        if(flag == 1):
            ans = ans + tmp + a[i+len_ab:] + b[len_ab:]
            return(ans)
        else:
            ans += a[i]
    return(a+b)

ans = [0]*12
ans[0] = calc(calc(a,b),c)
ans[1] = calc(calc(a,c),b)
ans[2] = calc(calc(b,a),c)
ans[3] = calc(calc(b,c),a)
ans[4] = calc(calc(c,a),b)
ans[5] = calc(calc(c,b),a)
ans[6] = calc(a,calc(b,c))
ans[7] = calc(a,calc(c,b))
ans[8] = calc(b,calc(a,c))
ans[9] = calc(b,calc(c,a))
ans[10] = calc(c,calc(a,b))
ans[11] = calc(c,calc(b,a))

ans_n = len(ans[0])
for i in range(1,12):
    ans_n = min(ans_n, len(ans[i]))


print(ans_n)

Submission status: Wrong Answer

Solution code:
subs = [input() for i in range(3)]
m = []
for sub in subs:
    tmp = sub
    for sub2 in subs:
        if sub != sub2:
            if sub2[0] == sub[-1]:
                sub += sub2[1:]
            elif sub[0] == sub2[-1]:
                sub = sub2[:-1] + sub
    if not tmp == sub:
        m.append(sub)

if len(m)>0:
    print(max([len(i) for i in m]))
else:
    print(max([len(i) for i in subs]))

Submission status: Wrong Answer

Solution code:

from collections import deque
from itertools import permutations

def match(s, t):
    results = [s + t]
    for i in range(len(s)):
        # i文字分をずらす
        res = s[:i]
        check = True
        for sc, tc in zip(s[i:], t):
            if sc == tc:
                res += sc
            elif sc == '?':
                res += tc
            elif tc == '?':
                res += sc
            else:
                check = False
                break

        res += t[len(s) - i:]

        if check:
            results.append(res)

    return results
                

def submit():
    a = input()
    b = input()
    c = input()

    min_len = float('inf')
    res = None
    for s1, s2, s3 in permutations([a, b, c]):
        cand = match(s1, s2)
        for c in cand:
            t = match(c, s3)
            for e in t:
                if min_len > len(e):
                    min_len = len(e)
                    res = e
    print(res)
    print(min_len)



if __name__ == "__main__":
    submit()

Submission status: Wrong Answer

Solution code:
a=list((input()))
b=list((input()))
c=list((input()))

def f(s,t):
    #print(s,t)
    for i,j in zip(s,t):
        if i == j or i=="?" or j=="?":
            pass
        else:
            return False
    else:
        return True
            
        
def calc(a,c):
    l=0
    r=len(a)*2+1
    while r-l>1:
        m=(l+r)//2
        if f(a[-m:],c[:m]):
            l = m
        else:
            r = m
        #print(l,m,r)
    return l
ans = len(a) +len(b) + len(c)
max_ = 0
for case in [((b,a),(a,c)),((a,b),(a,c))]:
    s = 0
    for i,j in case:
        s += (calc(i,j))//2
    max_ =max(max_,s)
print(ans-max_)

Submission status: Wrong Answer

Solution code:
def inner(a,b,la,lb):
  for i in range(lb-la+1):
    for j in range(la):
      if a[j]=='?' or a[j]==b[i+j]:
        continue
      elif b[i+j]=='?':
        continue
      else:
        break
    else:
      return True
  return False

def head(a,b,la):
  for i in range(la,-1,-1):
    for j in range(i):
      if a[j]=='?' or a[j]==b[-(i-j)]:
        continue
      elif b[-(i-j)]=='?':
        continue
      else:
        break
    else:
      return b+a[i:]

def tail(a,b,la):
  for i in range(la,-1,-1):
    for j in range(i):
      if a[-(i-j)]=='?' or a[-(i-j)]==b[j]:
        continue
      elif b[j]=='?':
        continue
      else:
        break
    else:
      return a+b[i:]
      break

a=input()
la=len(a)
b=input()
lb=len(b)
c=input()
lc=len(c)
arr=[[a,la],[b,lb],[c,lc]]
arr=sorted(arr,key=lambda x:x[1])
a,la=arr[0]
b,lb=arr[1]
c,lc=arr[2]
tmp1=head(a,c,la)
tmp2=tail(a,c,la)
ans1=min(len(head(b,tmp1,lb)),len(tail(b,tmp1,lb)))
if inner(b,tmp1,lb,len(tmp1)):
  ans1=min(ans1,len(tmp1))
ans2=min(len(head(b,tmp2,lb)),len(tail(b,tmp2,lb)))
if inner(b,tmp2,lb,len(tmp2)):
  ans2=min(ans2,len(tmp2))
ans3=10**18
if inner(a,c,la,lc):
  ans3=min(len(head(b,c,lb)),len(tail(b,c,lb)))
  if inner(b,c,lb,lc):
    ans3=min(ans3,lc)
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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


def make_chain(a, b, i):
    chain = a[:i]
    for j in range(len(b)):
        if len(a) <= i + j:
            break
        if a[i + j] == b[j]:
            chain += a[i + j]
            continue
        if a[i + j] == "?":
            chain += b[j]
            continue
        if b[j] == "?":
            chain += a[i + j]
            continue
        return ""
    if i + len(b) > len(a):
        chain += b[len(a) - i:]
    else:
        chain += a[i + len(b): ]
    return chain


def kmp(s1, s2):
    s = "%s!%s" % (s1, s2)
    p = [0] * len(s)
    for i in range(1, len(s)):
        k = p[i - 1]
        while k > 0 and s[k] != s[i]:
            k = p[k - 1]
        if s[k] == s[i] or s[k] == '?' or s[i] == '?':
            k += 1
        p[i] = k
    return len(s1) - p[-1] + len(s2)

best_size = len(A) + len(B) + len(C)
for a, b, c in permutations([A, B, C]):
    for i in range(len(a) + 1):
        chain = make_chain(a, b, i)
        if chain:
            size = kmp(chain, c)
            if size:
                best_size = min(best_size, size)
                break
print(best_size)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations as permi
input = sys.stdin.readline
a = list(input())[: -1]
b = list(input())[: -1]
c = list(input())[: -1]
mx = max(len(a), len(b), len(c))
def check(k):
  for p in permi([a, b, c], 3):
    x = p[0]
    y = p[1]
    z = p[2]
    x += ["?"] * (mx - len(x))
    y += ["?"] * (mx - len(y))
    z += ["?"] * (mx - len(z))
    for i in range(k + 1):
      if len(x) < i: continue
      if len(y) < k - i: continue
      isok = 1
      s = x[: ]
      t = y[: ]
      for j in range(i):
        if s[-i + j] != t[j]:
          if s[-i + j] == "?": s[-i + j] = t[j]
          elif t[j] == "?": t[j] = s[-i + j]
          else:
            isok = 0
            break
      if isok == 0: continue
      u = z[: ]
      for j in range(k - i):
        if t[-i + j] != u[j]:
          if t[-i + j] == "?": t[-i + j] = u[j]
          elif u[j] == "?": u[j] = t[-i + j]
          else:
            isok = 0
            break
      #print(s, t, u, isok, k, k - i)
      if isok: return True
  return False

ok = 0
ng = len(a) + len(b) + len(c) - max(len(a), len(b), len(c)) + 1
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(len(a) + len(b) + len(c) - ok)

Submission status: Wrong Answer

Solution code:
a=input()
b=input()
c=input()
def swap(a,b):
    if len(a)<len(b):
        return b,a
    return a,b
b,c=swap(c,b)
a,b=swap(a,b)
b,c=swap(b,c)
def check(a,b):
   for i in range(len(a)):
       if a[i]!="?" and b[i]!="?" and a[i]!=b[i]:
           return False
   return True
A,B,C=len(a),len(b),len(c)
ba=[B]
ab=[B]
bina=0
for i in range(1,B):
    if check(b[i:],a[:B-i]):
        ba.append(i)
    if check(b[:B-i],a[A-B+i:]):
        ab.append(i)
for i in range(A-B+1):
    if check(b,a[i:i+B]):
        bina=1
ca=[C]
ac=[C]
cina=0
for i in range(1,C):
    if check(c[i:],a[:C-i]):
        ca.append(i)
    if check(c[:C-i],a[A-C+i:]):
        ac.append(i)
for i in range(A-C+1):
    if check(c,a[i:i+C]):
        cina=1
if bina and cina:
    ans=A
elif bina:
    ans=A+min(min(ca),min(ac))
elif cina:
    ans=A+min(min(ba),min(ab))
if bina or cina:
    print(ans)
    quit()
cb=[C]
bc=[C]
cinb=0
for i in range(1,C):
    if check(c[i:],b[:C-i]):
        cb.append(i)
    if check(c[:C-i],b[B-C+i:]):
        bc.append(i)
for i in range(B-C+1):
    if check(c,b[i:i+C]):
        cinb=1
if cinb:
    print(A+min(min(ab),min(ba)))
    quit()
ans=min(A+C+min(min(ab),min(ba)),A+B+min(min(ca),min(ac)),A+B+min(min(cb),min(bc)))

ca=set(ca)
ac=set(ac)
for i in ba:
    for j in cb:
        if i+j in ca:
            ans=min(ans,A+i+j)
    for j in bc:
        if B-i+j-A<=0:
            ans=min(ans,A+i+j)
        if B-i+j-A in ac:
            ans=min(ans,B+j-A)
for i in ab:
    for j in bc:
        if i+j in ac:
            ans=min(ans,A+i+j)
    for j in cb:
        if B-i+j-A<=0:
            ans=min(ans,A+i+j)
        if B-i+j-A in ca:
            ans=min(ans,B+j-A)
print(ans)

Submission status: Wrong Answer

Solution code:

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def jojo(a,b):
    minlen = min(len(a),len(b))
    n=0
    for i in range(minlen):
        if a[-1*i]=="?" or b[i]=="?":
            n+=1
        elif a[-1*(i+1)]==b[i]:
            n+=1
        else:
            return n
    return n

def resolve():
    readline=sys.stdin.readline

    a=readline().strip()
    b=readline().strip()
    c=readline().strip()

    abc=len(a)+len(b)+len(c)
    #p1=jojo(a,b)+jojo(b,c)
    #p2=jojo(a,c)+jojo(c,b)
    #p3=jojo(b,a)+jojo(a,c)
    #p4=jojo(b,c)+jojo(c,a)
    #p5=jojo(c,a)+jojo(a,b)
    #p6=jojo(c,b)+jojo(b,a)
    bbb=max(jojo(a,b),jojo(b,a),jojo(b,c),jojo(c,b))
    ccc=max(jojo(a,c),jojo(c,a),jojo(b,c),jojo(c,b))
    aaa=max(jojo(a,b),jojo(b,a),jojo(a,c),jojo(c,a))

    #print(abc-max(p1,p2,p3,p4,p5,p6))
    print(abc-bbb-ccc-aaa+max(aaa,bbb,ccc))
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from itertools import permutations
def main():
    C = [ input() for _ in range(3)]
    LC = [ len(c) for c in C]
    ans = sum(LC)
    for P in permutations( range(3)):
        now = sum(LC)
        a, b, c = P[0], P[1], P[2]
        X, Y, Z = C[a], C[b], C[c]
        x, y, z = LC[a], LC[b], LC[c]
        for i in range(x):
            # if x - i > y:
            #     continue
            check = True
            for j in range(i, min(x,i+y)):
                if X[j] == '?' or Y[j-i] == '?' or X[j] == Y[j-i]:
                    continue
                check = False
                break
            if check:
                if i+y <= x:
                    W = X[:i]
                    for j in range(i,i+y):
                        if X[j] == '?' or Y[j-i] == '?':
                            W += '?'
                        else:
                            W += X[j]
                    W += X[i+y:]
                    now -= y
                    y = x
                else:
                    W = X[:i]
                    for j in range(i,x):
                        if X[j] == '?' or Y[j-i] == '?':
                            W += '?'
                        else:
                            W += X[j]
                    W += Y[x-i:]
                    now -= x-i
                    y = now-z
                break
        else:
            W = X+Y
            y += x
        second = now
        for i in range(y):
            check = True
            for j in range(i, min(y,i+z)):
                if W[j] == '?' or Z[j-i] == '?' or W[j] == Z[j-i]:
                    continue
                check = False
                break
            if check:
#                print(i)
                if i+z <= y:
                    now -= z
                else:
                    now -= y-i
                break
        if y < z:
            y, z = z, y
            W, Z = Z, W
        for i in range(1,z):
            check = True
            for j in range(i):

                if W[j] == '?' or Z[z-j-1] == '?' or W[j] == Z[z-j-1]:
                    continue
                check = False
                break
            if check:
                second -= i+1
#        print(X, Y, W, Z, y, now)
        if now < ans:
            ans = now
        if second < ans:
            ans = second
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import copy
#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s,L):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = 0
    i = L
    j = 0
    while i < N:
        while i+j < N and (s[j] == s[i+j] or s[j] == "?" or s[i+j] == "?"):
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

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


shaaa = ["$"]*2001
def de(x):
    n = len(x)
    for i in range(n):
        if x[i] == "$":
            return x[:i] 
    return x

def unite(x,y):
    y = y + shaaa
    X,Y = len(x),len(y)
    z = Z_algorithm(y+x,Y)

    tmp = -1
    for i in range(Y,X+Y):
        if z[i]+i == X+Y or z[i] == Y:
            tmp = i
            break


    if tmp == -1:
        return de(x+y)
    else:
        if z[tmp] == Y:
            res = x
            for i in range(tmp-Y,tmp):
                if res[i+Y-tmp] == "?":
                    res[i] = y[i-(tmp-Y)]
            return de(res)
        else:
            res = x
            for i in range(tmp-Y,X):
                if res[i] == "?":
                    res[i] = y[i-(tmp-Y)]
            for i in range(X-tmp+Y,Y):
                res.append(y[i])
            return de(res)

print(min(
len(unite(unite(a,b),c)),
len(unite(unite(a,c),b)),
len(unite(unite(b,a),c)),
len(unite(unite(b,c),a)),
len(unite(unite(c,a),b)),
len(unite(unite(c,b),a))))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return input().rstrip()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("inf")

#solve
def solve():
    a = S()
    b = S()
    c = S()
    def f(a, b, c):
        lena, lenb, lenc = len(a), len(b), len(c)
        dpab = [inf] * (lena + 1)
        dpbc = [inf] * (lenb + 1)
        dpac = [inf] * (lena + 1)
        for l in range(lena + 1):
            f = 0
            tl = l
            for r in range(lenb):
                if l == lena:
                    break
                if a[l] == b[r] or a[l] == "?" or b[r] == "?":
                    l += 1
                    continue
                else:
                    f = 1
                    break
            if f:
                continue
            dpab[tl] = max(tl + lenb, lena)

        for l in range(lenb + 1):
            f = 0
            tl = l
            for r in range(lenc):
                if l == lenb:
                    break
                if b[l] == c[r] or b[l] == "?" or c[r] == "?":
                    l += 1
                    continue
                else:
                    f = 1
                    break
            if f:
                continue
            dpbc[tl] = max(tl + lenc, lenb)

        for l in range(lena + 1):
            f = 0
            tl = l
            for r in range(lenc):
                if l == lena:
                    break
                if a[l] == c[r] or a[l] == "?" or c[r] == "?":
                    l += 1
                    continue
                else:
                    f = 1
                    break
            if f:
                continue
            dpac[tl] = max(tl + lenc, lena)

        res = lena + lenb + lenc
        for l in range(lena + 1):
            for r in range(lenb + 1):
                lr = l + r
                if dpab[l] != inf and dpbc[r] != inf:
                    if lr > lena:
                        res = min(l + dpbc[r], res)
                    else:
                        if dpac[lr] != inf:
                            if dpbc[r] == lenb:
                                res = min(res, dpab[l])
                            else:
                                res = min(res, dpac[lr])
        return res
    ans = len(a) + len(b) + len(c)
    ans = min(ans, f(a, b, c))
    ans = min(ans, f(a, c, b))
    ans = min(ans, f(b, a, c))
    ans = min(ans, f(b, c, a))
    ans = min(ans, f(c, b, a))
    ans = min(ans, f(c, a, b))
    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
a = input()
b = input()
c = input()
ans = len(a)+len(b)+len(c)
l = len(a)+len(b)+len(c)
for X, Y, Z in permutations((a, b, c), 3):
  #XY
  sameXY = min(len(X), len(Y))
  while sameXY > 0:
    ok = True
    i = 0
    while i < sameXY:
      if X[-(sameXY-i)] != Y[i] and X[-(sameXY-i)] != "?" and Y[i] != "?":
        ok = False
        break
      i += 1
    if ok:
      break
    sameXY -= 1
  if sameXY == 0:
    if X in Y:
      sameXY = len(X)
    elif Y in X:
      sameXY = len(Y)
      Y = X
  #YZ
  sameYZ =  min(len(Y), len(Z))
  while sameYZ > 0:
    ok = True
    i = 0
    while i < sameYZ:
      if Y[-(sameYZ-i)] != Z[i] and Y[-(sameYZ-i)] != "?" and Z[i] != "?":
        ok = False
        break
      i += 1
    if ok:
      break
    sameYZ -= 1
  if sameYZ == 0:
    if Y in Z:
      sameYZ = len(Y)
    elif Z in Y:
      sameYZ = len(Z)
  ans = min(ans, l-sameXY-sameYZ)
print(ans)