Problem p03165 (python)

Fixed submission:
# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
lenS = len(s)
lenT = len(t)

dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
  for j in range(1,lenT+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
      
m = lenS
n = lenT
ans = ""
while m or n:
  if dp[m][n] == dp[m-1][n]:
    m -= 1
    continue
  elif dp[m][n] == dp[m][n-1]:
    n -= 1
    continue
  else:
    m -= 1
    n -= 1
    ans = "".join([s[m],ans])
    continue
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
lenS = len(s)
lenT = len(t)

dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
  for j in range(1,lenT+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
      
m = lenS
n = lenT
ans = ""
while m or n:
  if dp[m][n] == dp[m-1][n]:
    m -= 1
    continue
  elif dp[m][n] == dp[m][n-1]:
    n -= 1
    continue
  else:
    m -= 1
    n -= 1
    ans = "".join([s[m],ans])
    continue
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
lenS = len(s)
lenT = len(t)

dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
  for j in range(1,lenT+1):
    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])
      
m = lenS
n = lenT
ans = ""
while m or n:
  if dp[m][n] == dp[m-1][n]:
    m -= 1
    continue
  elif dp[m][n] == dp[m][n-1]:
    n -= 1
    continue
  else:
    m -= 1
    n -= 1
    ans = "".join([s[m],ans])
    continue
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
sys.setrecursionlimit(200000)

X = input()
Y = input()
lenX = len(X)
lenY = len(Y)
dp = np.full((lenX+1,lenY+1),"-1",dtype=object)
dp[0,:]=""
dp[:,0]=""
def f(i,j):
  if dp[i][j]=="-1":
    x = X[i-1]
    y = Y[j-1]
    lo = f(i-1,j-1)
    l = f(i,j-1)
    o = f(i-1,j)
    if x==y:
      dp[i][j]="".join([lo,x])
    else:
      if len(l)>=len(o):
        dp[i][j]=l
      else:
        dp[i][j]=o
  return dp[i][j]

print(f(lenX,lenY))

Buggy submission (verdict: Runtime Error):
import numpy as np
X = input()
Y = input()
lenX = len(X)
lenY = len(Y)
dp = np.full((lenX+1,lenY+1),"-1",dtype=object)
dp[0,:]=""
dp[:,0]=""
def f(i,j):
  if dp[i][j]=="-1":
    x = X[i-1]
    y = Y[j-1]
    lo = f(i-1,j-1)
    l = f(i,j-1)
    o = f(i-1,j)
    if x==y:
      dp[i][j]="".join([lo,x])
    else:
      if len(l)>=len(o):
        dp[i][j]=l
      else:
        dp[i][j]=o
  return dp[i][j]
print(f(lenX,lenY))

Buggy submission (verdict: Runtime Error):
import numpy as np

q = int(input())
for k in range(q):
  X = input()
  Y = input()
  lenX = len(X)
  lenY = len(Y)
  dp = np.full((lenX+1,lenY+1),-1)
  dp[0,:]=0
  dp[:,0]=0
  def f(i,j):
    if dp[i][j]==-1:
      x = X[i-1]
      y = Y[j-1]
      if x==y:
        dp[i][j]=max(f(i-1,j-1)+1,f(i-1,j),f(i,j-1))
      else:
        dp[i][j]=max(f(i-1,j),f(i,j-1))
    return dp[i][j]
  print(int(f(lenX,lenY)))