Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Wrong Answer

Solution code:
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+S[i]
            break
        dp[i+1][j+1]=dp[i+1][j]
        if len(dp[i][j+1])>len(dp[i+1][j]):
            dp[i+1][j+1]=dp[i][j+1]
print(dp[s][t])

Submission status: Wrong Answer

Solution code:
def dump(dp, i1_max, i2_max):
    for i1 in range(0, i1_max + 1):
        for i2 in range(0, i2_max + 1):
            print('%4d' % dp[i1][i2], end='')
        print()


s = input()
t = input()
s_len = len(s)
t_len = len(t)
inf = 1 << 60

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [[-inf for j in range(t_len + 1)] for i in range(s_len + 1)]
dp[0][0] = 0
for si in range(0, s_len + 1):
    for ti in range(0, t_len + 1):
        if si >= 1 and ti >= 1:
            if s[si - 1] == t[ti - 1]:
                dp[si][ti] = max(dp[si][ti], dp[si - 1][ti - 1] + 1)
        if si >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si - 1][ti])
        if ti >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si][ti - 1])

ans = ''
si = s_len
ti = t_len
dump(dp, si, ti)
while si != 0 and ti != 0:
    if si >= 1 and ti >= 1:
        if (dp[si - 1][ti - 1] == dp[si][ti] - 1) and s[si - 1] == t[ti - 1]:
            ans = s[si - 1] + ans
            si -= 1
            ti -= 1
            continue
    if si >= 1:
        if dp[si - 1][ti] == dp[si][ti]:
            si -= 1
            continue
    if ti >= 1:
        if dp[si][ti - 1] == dp[si][ti]:
            ti -= 1
            continue

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)
inf = 1 << 60

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [[-inf for j in range(t_len + 1)] for i in range(s_len + 1)]
dp[0][0] = 0
for si in range(0, s_len + 1):
    for ti in range(0, t_len + 1):
        if si >= 1 and ti >= 1:
            if s[si - 1] == t[ti - 1]:
                dp[si][ti] = max(dp[si][ti], dp[si - 1][ti - 1] + 1)
        if si >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si - 1][ti])
        if ti >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si][ti - 1])

ans = ''
si = s_len
ti = t_len
max_len = dp[si][ti]
while si != 0 and ti != 0:
    if si >= 1 and ti >= 1:
        if dp[si - 1][ti - 1] == dp[si][ti] - 1:
            ans = s[si - 1] + ans
            si -= 1
            ti -= 1
            continue
    if si >= 1:
        if dp[si - 1][ti] == dp[si][ti]:
            si -= 1
            continue
    if ti >= 1:
        if dp[si][ti - 1] == dp[si][ti]:
            ti -= 1
            continue

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)
inf = 1 << 60

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [[-inf for j in range(t_len + 1)] for i in range(s_len + 1)]
dp[0][0] = 0
for si in range(0, s_len + 1):
    for ti in range(0, t_len + 1):
        if s[si - 1] == t[ti - 1]:
            dp[si][ti] = max(dp[si][ti], dp[si - 1][ti - 1] + 1)
        dp[si][ti] = max(dp[si][ti], dp[si - 1][ti])
        dp[si][ti] = max(dp[si][ti], dp[si][ti - 1])

ans = ''
si = s_len
ti = t_len
max_len = dp[si][ti]
while si != 0 and ti != 0:
    if si >= 1 and ti >= 1:
        if dp[si - 1][ti - 1] == dp[si][ti] - 1:
            ans = s[si - 1] + ans
            si -= 1
            ti -= 1
            continue
    if si >= 1:
        if dp[si - 1][ti] == dp[si][ti]:
            si -= 1
            continue
    if ti >= 1:
        if dp[si][ti - 1] == dp[si][ti]:
            ti -= 1
            continue

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [[0 for j in range(t_len + 1)] for i in range(s_len + 1)]
for si in range(0, s_len + 1):
    for ti in range(0, t_len + 1):
        if si >= 1 and ti >= 1:
            if s[si - 1] == t[ti - 1]:
                dp[si][ti] = max(dp[si][ti], dp[si - 1][ti - 1] + 1)
        if si >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si - 1][ti])
        if ti >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si][ti - 1])

ans = ''
si = s_len
ti = t_len
max_len = dp[si][ti]
while si != 0 and ti != 0:
    if si >= 1 and ti >= 1:
        if dp[si - 1][ti - 1] == dp[si][ti] - 1:
            ans = s[si - 1] + ans
            si -= 1
            ti -= 1
            continue
    if si >= 1:
        if dp[si - 1][ti] == dp[si][ti]:
            si -= 1
            continue
    if ti >= 1:
        if dp[si][ti - 1] == dp[si][ti]:
            ti -= 1
            continue

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [[0 for j in range(t_len + 1)] for i in range(s_len + 1)]
for si in range(1, s_len + 1):
    for ti in range(1, t_len + 1):
        if s[si - 1] == t[ti - 1]:
            dp[si][ti] = max(dp[si][ti], dp[si - 1][ti - 1] + 1)
        dp[si][ti] = max(dp[si][ti], dp[si - 1][ti])
        dp[si][ti] = max(dp[si][ti], dp[si][ti - 1])

ans = ''
si = s_len
ti = t_len
max_len = dp[si][ti]
while si != 0 and ti != 0:
    if si >= 1 and ti >= 1:
        if dp[si - 1][ti - 1] == dp[si][ti] - 1:
            ans = s[si - 1] + ans
            si -= 1
            ti -= 1
            continue
    if si >= 1:
        if dp[si - 1][ti] == dp[si][ti]:
            si -= 1
            continue
    if ti >= 1:
        if dp[si][ti - 1] == dp[si][ti]:
            ti -= 1
            continue

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [[0 for j in range(t_len + 1)] for i in range(s_len + 1)]
for si in range(1, s_len + 1):
    for ti in range(1, t_len + 1):
        if s[si - 1] == t[ti - 1]:
            dp[si][ti] = max(dp[si][ti], dp[si - 1][ti - 1] + 1)
        dp[si][ti] = max(dp[si][ti], dp[si - 1][ti])
        dp[si][ti] = max(dp[si][ti], dp[si][ti - 1])

ans = ''
si = s_len
ti = t_len
max_len = dp[si][ti]
while si != 0 and ti != 0:
    if si >= 1 and ti >= 1:
        if dp[si - 1][ti - 1] == dp[si][ti] - 1:
            ans = s[si - 1] + ans
            si -= 1
            ti -= 1
    if si >= 1:
        if dp[si - 1][ti] == dp[si][ti]:
            si -= 1
    if ti >= 1:
        if dp[si][ti - 1] == dp[si][ti]:
            ti -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]


def solve():
    for i, cs in enumerate(s):
        for j, ct in enumerate(t):
            if cs == ct:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    print(dp)

    i = len(s)-1
    j = len(t)-1
    ans = ""
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            ans += s[i]
            i -= 1
            j -= 1
        else:
            if dp[i+1][j+1] == dp[i+1][j]:
                j -= 1
            elif dp[i+1][j+1] == dp[i][j+1]:
                i -= 1
            else:
                break
    print("".join(reversed(ans)))


solve()

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

dp = [[0]*len(t) for _ in range(len(s))]


def solve():
    for i, cs in enumerate(s):
        for j, ct in enumerate(t):
            if cs == ct:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    i = len(s)-1
    j = len(t)-1
    ans = ""
    while 0 <= i and 0 <= j:
        if s[i] == t[j]:
            ans += s[i]
            i -= 1
            j -= 1
        else:
            if j != 0 and dp[i][j] == dp[i][j-1]:
                j -= 1
            elif i != 0 and dp[i][j] == dp[i-1][j]:
                i -= 1
            else:
                break
    print("".join(reversed(ans)))


solve()

Submission status: Wrong Answer

Solution code:
# x = input()
# n1 = len(x)
# y = input()
# n2 = len(y)
# dp = [[0 for i in range(n2+1)] for i in range(n1+1)]
# for i in range(1,n1+1):
# 	for j in range(1,n2+1):
# 		if(x[i-1] == y[j-1]):
# 			dp[i][j] = 1 + dp[i-1][j-1]
# 		else:
# 			dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
# i = n1
# j = n2
# c = min(n1,n2)
# o = ['' for i1 in range(min(n1,n2))]
# print(dp)
# while ((i>=0) and (j>=0)):
#  	if(dp[i][j] == (1 + dp[i-1][j-1])):
#  		i = i-1
#  		j = j-1
#  		o[c-1] = x[i]
#  		c -= 1
#  	elif(dp[i][j] == dp[i][j-1]):
#  		#print('2')
#  		j = j-1
#  	elif(dp[i][j] == dp[i-1][j]):
#  		#print('3')
#  		i = i-1
#  	elif(dp[i][j] == dp[i-1][j-1]):
#  		#print('4')
#  		i = i-1
#  		j = j-1
# print(''.join(o))
x = raw_input()
n1 = len(x)
y = raw_input()
n2 = len(y)
dp = [[0 for i in xrange(n2+1)] for i in xrange(n1+1)]
for i in xrange(1,n1+1):
	for j in xrange(1,n2+1):
		if(x[i-1] == y[j-1]):
			dp[i][j] = 1 + dp[i-1][j-1]
		else:
			dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
i = n1
j = n2
c = min(n1,n2)
o = ['' for i1 in xrange(min(n1,n2))]
while (i>=0 and j>=0):
 	if(dp[i][j] == 1 + dp[i-1][j-1]):
 		i = i-1
 		j = j-1
 		o[c-1] = x[i]
 		c -= 1
 	if(dp[i][j] == dp[i][j-1]):
 		j = j-1
 	if(dp[i][j] == dp[i-1][j]):
 		i = i-1
 	if(dp[i][j] == dp[i-1][j-1]):
 		i = i-1
 		j = j-1
print(''.join(o))

Submission status: Wrong Answer

Solution code:
x = raw_input()
n1 = len(x)
y = raw_input()
n2 = len(y)
dp = [[0 for i in xrange(n2+1)] for i in xrange(n1+1)]
for i in xrange(1,n1+1):
	for j in xrange(1,n2+1):
		if(x[i-1] == y[j-1]):
			dp[i][j] = 1 + dp[i-1][j-1]
		else:
			dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
i = n1
j = n2
c = min(n1,n2)
o = ['' for i1 in range(min(n1,n2))]
while ((i>=0) and (j>=0)):
 	if(dp[i][j] == (1 + dp[i-1][j-1])):
 		i = i-1
 		j = j-1
 		o[c-1] = x[i]
 		c -= 1
 	elif(dp[i][j] == dp[i][j-1]):
 		#print('2')
 		j = j-1
 	elif(dp[i][j] == dp[i-1][j]):
 		#print('3')
 		i = i-1
 	elif(dp[i][j] == dp[i-1][j-1]):
 		#print('4')
 		i = i-1
 		j = j-1
print(''.join(o))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
ls, lt = len(s), len(t)
dp = [[0 for _ in range(lt+1)] for _ in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[ls][lt])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()
t = ns()

lens = len(s)
lent = len(t)

dp = [[0]*(lent+1) for _ in range(lens+1)]

for idx in range(lens):
    for jdx in range(lent):
        dp[idx+1][jdx+1] = max(dp[idx][jdx] + bool(s[idx] == t[jdx]),
                               dp[idx+1][jdx],
                               dp[idx][jdx+1])
    
def lcs(spos: int, tpos: int, cur: str, s:str, t:str, dp: list) -> str:

    if spos == 0 or tpos == 0:
        return cur
    
    else:
        nrth = dp[spos-1][tpos]
        west = dp[spos][tpos-1]
        ntws = dp[spos-1][tpos-1]
        
        mx = max(nrth, west, ntws)
        
        if mx == ntws:
            return lcs(spos-1, tpos-1, cur+s[spos-1], s,t,dp)
 
        
        if mx == nrth:
            return lcs(spos-1, tpos, cur, s, t, dp)
        
        else:
            return lcs(spos, tpos-1, cur, s, t, dp)
            
           

            
            
print(lcs(lens, lent, "", s, t, dp)[::-1])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()
t = ns()

lens = len(s)
lent = len(t)

dp = [[0]*(lent+1) for _ in range(lens+1)]

for idx in range(lens):
    for jdx in range(lent):
        dp[idx+1][jdx+1] = max(dp[idx][jdx] + bool(s[idx] == t[jdx]),
                               dp[idx+1][jdx],
                               dp[idx][jdx+1])
    
def lcs(spos: int, tpos: int, cur: str, s:str, t:str, dp: list) -> str:
    if spos == 0 or tpos == 0:
        return cur
    
    else:

        if dp[spos][tpos] == dp[spos-1][tpos-1]+1:
            return lcs(spos-1, tpos-1, cur+s[spos-1], s,t,dp)
            
        elif dp[spos][tpos] == dp[spos-1][tpos]:
            return lcs(spos-1, tpos, cur, s, t, dp)
            
        else:
            return lcs(spos, tpos-1, cur, s, t, dp)
            
print(lcs(lens, lent, "", s, t, dp)[::-1])

Submission status: Wrong Answer

Solution code:
s, t = raw_input().strip(), raw_input().strip()
n, m = len(s), len(t)

dp = [[0 for i in xrange(m)] for j in xrange(n)]

dp[0][0] = int(s[0] == t[0])

i = 0
for j in xrange(1, m):
    if s[i] == t[j]: dp[i][j] = 1
    else: dp[i][j] = dp[i][j - 1]

j = 0
for i in xrange(1, n):
    if s[i] == t[j]: dp[i][j] = 1
    else: dp[i][j] = dp[i - 1][j]

for i in xrange(1, n):
    for j in xrange(1, m):
        if i == 0 and j == 0: continue
        if s[i] == t[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

c = [0 for i in xrange(dp[n - 1][m - 1])]

print len(c)

st = len(c) - 1
i, j = n - 1, m - 1
while st >= 0:
    if s[i] == t[j]:
        c[st] = s[i]
        i -= 1
        j -= 1
        st -= 1
    else:
        if i >= 1 and j >= 1:
            if dp[i][j - 1] < dp[i - 1][j]: i -= 1
            else: j -= 1
        else:
            if i >= 1: i -= 1
            else: j -= 1

print ''.join(c)

Submission status: Wrong Answer

Solution code:
#import resource
import sys
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#threading.Thread(target=main).start()
#import threading
#threading.stack_size(2**26)
#sys.setrecursionlimit(10**8)
mod=(10**9)+7
#fact=[1]
#for i in range(1,1000001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*1000001
#ifact[1000000]=pow(fact[1000000],mod-2,mod)
#for i in range(1000000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import math
import heapq
from random import randint as rn
from Queue import Queue as Q
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def GCD(x, y):
   while(y):
       x, y = y, x % y
   return x
"""**************************************************************************"""
s1=sin()
s2=sin()
l1=len(s1)
l2=len(s2)
dp=[[0 for i in range(l2+1)] for j in range(l1+1)]
for i in range(1,l1+1):
    for j in range(1,l2+1):
        if(s1[i-1]==s2[j-1]):
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
l=[]
i=l1
j=l2
while(dp[i][j]!=0):
    t=dp[i][j]-1
    if(dp[i-1][j-1]==t):
        i-=1
        j-=1
        l.append(s1[i])
    elif(dp[i-1][j]>=dp[i][j-1]):
        i-=1
    else:
        j-=1
l=l[::-1]
stdout.write("".join(l)+"\n")

Submission status: Wrong Answer

Solution code:
#import resource
import sys
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#threading.Thread(target=main).start()
import threading
threading.stack_size(2**26)
sys.setrecursionlimit(10**8)
mod=(10**9)+7
#fact=[1]
#for i in range(1,1000001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*1000001
#ifact[1000000]=pow(fact[1000000],mod-2,mod)
#for i in range(1000000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import math
import heapq
from random import randint as rn
from Queue import Queue as Q
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def GCD(x, y):
   while(y):
       x, y = y, x % y
   return x
"""**************************************************************************"""
s1=sin()
s2=sin()
l1=len(s1)
l2=len(s2)
dp=[[0 for i in range(l2+1)] for j in range(l1+1)]
for i in range(1,l1+1):
    for j in range(1,l2+1):
        if(s1[i-1]==s2[j-1]):
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
l=[]
i=l1
j=l2
while(dp[i][j]!=0):
    t=dp[i][j]-1
    if(dp[i-1][j-1]==t):
        i-=1
        j-=1
        l.append(s1[i])
    elif(dp[i-1][j]>=dp[i][j-1]):
        i-=1
    else:
        j-=1
print "".join(l[::-1])

Submission status: Wrong Answer

Solution code:
#import resource
import sys
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#threading.Thread(target=main).start()
import threading
threading.stack_size(2**26)
sys.setrecursionlimit(10**8)
mod=(10**9)+7
#fact=[1]
#for i in range(1,1000001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*1000001
#ifact[1000000]=pow(fact[1000000],mod-2,mod)
#for i in range(1000000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import math
import heapq
from random import randint as rn
from Queue import Queue as Q
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def GCD(x, y):
   while(y):
       x, y = y, x % y
   return x
"""**************************************************************************"""
s1=sin()
s2=sin()
l1=len(s1)
l2=len(s2)
dp=[[0 for i in range(l2+1)] for j in range(l1+1)]
for i in range(1,l1+1):
    for j in range(1,l2+1):
        if(s1[i-1]==s2[j-1]):
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
l=[]
i=l1
j=l2
while(dp[i][j]!=0):
    t=dp[i][j]-1
    if(dp[i-1][j-1]==t):
        i-=1
        j-=1
        l.append(s1[i])
    elif(dp[i-1][j]>=dp[i][j-1] and dp[i-1][j]>=dp[i-1][j-1]):
        i-=1
    elif(dp[i-1][j-1]>=dp[i][j-1] and dp[i-1][j-1]>=dp[i-1][j]):
        i-=1
        j-=1
    else:
        j-=1
print "".join(l[::-1])

Submission status: Wrong Answer

Solution code:
s=[ord(ch)-97 for ch in input()]
t=[ord(ch)-97 for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame

for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=(dp[i][j-1] if dp[i][j-1]>dp[i-1][j] else dp[i-1][j])

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>0 and j>0:
    if s[j]==t[i] and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)
if i==0:
    res.append(t[0])
elif j==0:
    res.append(s[0])


print("".join(chr(i+97) for i in reversed(res)))

Submission status: Wrong Answer

Solution code:
s = ' ' + input()
t = ' ' + input()
dp = [[0 for _ in range(len(t))] for _ in range(len(s))]
for i in range(1, len(s)):
    for j in range(1, len(t)):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

i, j = len(s)-1, len(t)-1
ret = ''
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1]:
        ret += s[i]; i -= 1; j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
print(ret[::-1])

Submission status: Wrong Answer

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_f
"""
from collections import defaultdict
s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [[0] * (lt + 1) for _ in range(ls + 1)]

pre = defaultdict(lambda: defaultdict(tuple))

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = 1 + dp[i][j]
            pre[i + 1][j + 1] = (i, j)
        else:
            if dp[i + 1][j] >= dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
                pre[i + 1][j + 1] = (i + 1, j)
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]
                pre[i + 1][j + 1] = (i, j + 1)

# print(dp[ls][lt])

ans = ''
y = ls
x = lt
while pre[y][x]:
    ny, nx = pre[y][x]
    if ny < ls and nx < lt and s[ny] == t[nx]:
        ans = s[ny] + ans
    y = ny
    x = nx

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import sys
import re
import math
import itertools
import collections
import bisect
import fractions
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
# fractions.gcd(x,y)
def lcm(a,b): return a*b//fractions.gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def eof(t): print(t); exit()


s=input()
t=input()

def sol(s,t):
    a=len(s)
    b=len(t)
    l=[[0 for i in range(a+1)] for j in range(b+1)]
    for i in range(1,b+1):
        for j in range(1,a+1):
            if (t[i-1]!=s[j-1]): l[i][j]=max(l[i][j-1],l[i-1][j])
            if (t[i-1]==s[j-1]): l[i][j]=l[i-1][j-1]+1
    res=""
    chk=l[-1][-1]
    for i in range(b,0,-1):
        for j in range(a,-1,-1):
            if l[i][j]<chk:
                res=s[j]+res
                chk-=1
                break
    return res

print(sol(s,t))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import sys
import re
import math
import itertools
import collections
import bisect
import fractions
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
# fractions.gcd(x,y)
def lcm(a,b): return a*b//fractions.gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def eof(t): print(t); exit()


s=input()
t=input()

def sol(s,t):
    a=len(s)
    b=len(t)
    l=[[0 for i in s] for j in t]
    for i in range(b):
        for j in range(a):
            if (t[i]==s[j]):
                 l[i][j]=1
    res=""
    for i in range(b-1,-1,-1):
        for j in range(a-1,-1,-1):
            if (l[i][j]==1):
                res+=s[j]
                a=j
                break
    return res[::-1]

x=sol(s,t)
y=sol(t,s)
print(x if len(x)>=len(y) else y)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import sys
import re
import math
import itertools
import collections
import bisect
import fractions
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
# fractions.gcd(x,y)
def lcm(a,b): return a*b//fractions.gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def eof(t): print(t); exit()


s=input()
t=input()

def sol(s,t):
    a=len(s)
    b=len(t)
    l=[[0 for i in s] for j in t]
    for i in range(b):
        for j in range(a):
            if (t[i]==s[j]):
                 l[i][j]=1
    res=""
    for i in range(b-1,-1,-1):
        for j in range(a-1,-1,-1):
            if (l[i][j]==1):
                res+=s[j]
                a=j+1
                break
    return res[::-1]

x=sol(s,t)
y=sol(t,s)
print(x if len(x)>=len(y) else y)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import sys
import re
import math
import itertools
import collections
import bisect
import fractions
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
# fractions.gcd(x,y)
def lcm(a,b): return a*b//fractions.gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def eof(t): print(t); exit()


s=input()
t=input()
a=len(s)
b=len(t)
l=[[0 for i in s] for j in t]
for i in range(b):
    for j in range(a):
        if (t[i]==s[j]):
             l[i][j]=1
res=""
for i in range(b-1,-1,-1):
    for j in range(a-1,-1,-1):
        if (l[i][j]==1):
            res+=s[j]
            a=j+1
            break
print(res[::-1])

Submission status: Wrong Answer

Solution code:
S,T = input(),input()
x,y = len(S),len(T)

dp = [[0]*(y+1) for _ in range(x+1)]

for i,s in enumerate(S):
  for j,t in enumerate(T):
    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + int(s==t))
    print(s,t,dp)
    
a = ""
while x > 0 and y > 0:
  if dp[x][y] == dp[x-1][y]:
    x -= 1
  elif dp[x][y] == dp[x][y-1]:
    y -= 1
  else:
    x -= 1
    y -= 1
    a += S[x]

print(a[::-1])

Submission status: Wrong Answer

Solution code:
s=raw_input()
t=raw_input()

len_s=len(s)
len_t=len(t)

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=""
l=0

for i in range(1,len_s+1):
	for j in range(1,len_t+1):
		if s[i]==t[j]:
			dp[i][j]=dp[i-1][j-1]+1
			if dp[i][j]>l:
				S+=s[i]
				l+=1
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )

print S

Submission status: Wrong Answer

Solution code:
def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = ["" for i in range(LT)]
  T = [0 for i in range(LT)]
  
  start = ""
  
  for i in range(LS):
    flag = False
    if DP[0] == "":
      if s[i] == t[0]:
        DP[0] = s[i]
        start = DP[0]
        T[0] = 1
        flag = True
    k = start
    for j in range(1, LT):
      if s[i] == t[j]:
        if T[j] == 0:
          if not flag:
            T[j] = 1
            flag = True
            k = DP[j] + s[i]
        elif len(k) < len(DP[j]):
          k = DP[j]
        else:
          T[j] = 0
        DP[j] = k     
      else:
        flag = False
        if len(k) < len(DP[j]):
          k = DP[j]
        else:
          DP[j] = k
          T[j] = 0
  print(DP[-1])
  
main()

Submission status: Wrong Answer

Solution code:
def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = ["" for i in range(LT)]
  T = [0 for i in range(LT)]
  
  start = ""
  
  for i in range(LS):
    flag = False
    if DP[0] == "":
      if s[i] == t[0]:
        DP[0] = s[i]
        start = DP[0]
        T[0] = 1
        flag = True
    k = start
    for j in range(1, LT):
      if s[i] == t[j]:
        if T[j] == 0:
          if not flag:
            T[j] = 1
            flag = True
            k = DP[j] + s[i]
        if len(k) < len(DP[j]):
          k = DP[j]
        DP[j] = k     
      else:
        flag = False
        if len(k) < len(DP[j]):
          k = DP[j]
        else:
          DP[j] = k
          T[j] = 0
          
  print(DP[-1])
  
main()

Submission status: Wrong Answer

Solution code:
def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = ["" for i in range(LT)]
  T = [0 for i in range(LT)]
  
  start = ""
  
  for i in range(LS):
    flag = False
    if DP[0] == "":
      if s[i] == t[0]:
        DP[0] = s[i]
        start = DP[0]
        T[0] = 1
        flag = True
    k = start
    for j in range(1, LT):
      if s[i] == t[j]:
        if T[j] == 0:
          if not flag:
            T[j] = 1
            flag = True
          if len(k) < len(DP[j]) + 1:
            k = DP[j] + s[i]
          DP[j] = k     
      else:
        flag = False
        if len(k) < len(DP[j]):
          k = DP[j]
        else:
          DP[j] = k
          T[j] = 0
          
  print(DP[-1])
  
main()