Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02985 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,K=map(int, sys.stdin.readline().split())

 #階乗　前計算
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, K+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def npr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[n-r]) %mod



nl=[ [] for i in range(N+1) ]	#隣接リスト
C=[ 0 for i in range(N+1) ]	#入次数: 頂点に入ってくる辺数
 
for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	C[a]+=1
	nl[b].append(a)
	C[b]+=1


start=1
Visit=[ None for i in range(N+1) ] 
Visit[start]=1
 
p=None		#Parent
q=deque()
q.append( (p,start) )

ans=K

while q:
	p,current=q.popleft()
	flag=0
	for to in nl[current]:
		if Visit[to] is None:
			Visit[to]=1
			q.append( (current,to) )
			flag=1
	if p is None and flag:
		ans*=npr(K-1,C[current])
	elif p is not None and flag:
		ans*=npr(K-2,C[current]-1)
	ans%=mod
		

print ans

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
   
mod=10**9+7
ans=1
def dfs(par,cur,num):
    global ans
    ans*=num
    ans%=mod
    if par==-1: #ルートノードの時は
        num=K-1  #K-1色使用できる
    else:       #ルートノードじゃない時は
        num=K-2  #K-2色使用できる
    for to in al[cur]:
        if to!=par: #遷移候補が親でなければ、遷移
            dfs(cur,to,num)
            num-=1
dfs(-1,1,K)

print ans

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,K=map(int, sys.stdin.readline().split())
nl=[ [] for i in range(N+1) ]	#隣接リスト
C=[ 0 for i in range(N+1) ]	#入次数: 頂点に入ってくる辺数
 
for i in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	C[a]+=1
	nl[b].append(a)
	C[b]+=1


Visit=[ 0 for i in range(N+1) ]


for i,x in enumerate(C):
	if x==1:
		start=i
		break


#階乗　前計算
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, K+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def npr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[n-r]) %mod


q=deque()
q.append(start)
Visit[start]=1

ans=1

while q: 
	fro=q.popleft()
	cnt=1	# fro1から距離２までの頂点数。fro自体も含めるので１からスタート
	for to1  in nl[fro]:
		if Visit[to1]==0:
			Visit[to1]=1
			cnt+=1
		for to2 in nl[to1]:
			if Visit[to2]==0:
				Visit[to2]=1
				cnt+=1
				q.append(to2)
	if fro==start:
		#print "npr(",K,",",cnt,") ::::", npr(K,cnt)
		ans*=npr(K,cnt)
	else:
		#print "npr(",K-C[fro],",",cnt-1,") :::: ",npr(K-C[fro],cnt-1)
		ans*=npr(K-C[fro],cnt-1)
	ans%=mod

print ans
Problem p02997 (python)

Fixed submission:
N,K=map(int, raw_input().split())

torisu=(N-1)*(N-2)/2

if torisu<K:
	print -1
	quit()

print N-1+(torisu-K)

for i in range(2,N+1):
	print 1, i

cnt=0
for i in range(2,N+1):
	for j in range(i+1,N+1):
		if cnt==torisu-K:
			quit()
		print i,j
		cnt+=1

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import itertools
N,K=map(int, sys.stdin.readline().split())
cnt=(N-1)*(N-2)/2 #距離2の組み合わせができる最大の通り数
if cnt<K:
    print -1
    quit()
L=list( itertools.combinations(range(1,N+1),2) )

M=N-1+cnt-K
print M
for i in range(N-1):
    print L[i][0],L[i][1]

if N,K==100,0:
    for i in range(N,N+cnt-K-1):
            print L[i][0],L[i][1]
else:
    for i in range(N,N+cnt-K):
            print L[i][0],L[i][1]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import itertools
N,K=map(int, sys.stdin.readline().split())
cnt=(N-1)*(N-2)/2 #距離2の組み合わせができる最大の通り数
if cnt<K:
    print -1
    quit()
L=list( itertools.combinations(range(1,N+1),2) )

M=N-1+cnt-K
print M
for i in range(N-1):
    print L[i][0],L[i][1]

for i in range(N,N+cnt-K):
    print L[i][0],L[i][1]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import itertools
N,K=map(int, sys.stdin.readline().split())
cnt=(N-1)*(N-2)/2 #距離2の組み合わせができる最大の通り数
if cnt<K:
    print -1
    quit()
L=list( itertools.combinations(range(1,N+1),2) )

for i in range(N-1):
    print L[i][0],L[i][1]

for i in range(N,N+cnt-K):
    print L[i][0],L[i][1]
Problem p03006 (python)

Fixed submission:
import itertools

N=input()
if N==1:
	print 1
	quit()

XY=[ map(int, raw_input().split())  for _ in range(N) ]
XY.sort(key=lambda x:(x[0],x[1]) )

D={}

C=list( itertools.combinations( range(1,N+1), 2) )

for b1, b2 in C:
	x1=XY[b1-1][0]
	y1=XY[b1-1][1]
	x2=XY[b2-1][0]
	y2=XY[b2-1][1]

	dx=x2-x1
	dy= y2-y1
	if (dx,dy) not in D:
		D[(dx,dy)]=1
	else:
		D[(dx,dy)]+=1

print N-max( D.values() )

Buggy submission (verdict: Runtime Error):
import itertools

N=input()
XY=[ map(int, raw_input().split())  for _ in range(N) ]
XY.sort(key=lambda x:(x[0],x[1]) )

D={}

C=list( itertools.combinations( range(1,N+1), 2) )

for b1, b2 in C:
	x1=XY[b1-1][0]
	y1=XY[b1-1][1]
	x2=XY[b2-1][0]
	y2=XY[b2-1][1]

	dx=x2-x1
	dy= y2-y1
	if (dx,dy) not in D:
		D[(dx,dy)]=1
	else:
		D[(dx,dy)]+=1

print N-max( D.values() )
Problem p03007 (python)

Fixed submission:
import sys

N=input()
A=map(int, sys.stdin.readline().split())
A.sort()
min_A=A[0]
max_A=A[-1]

L=[]
for i in range(1,N-1):
	v=A[i]
	if v<0:
		L.append( (max_A, v) )
		max_A-=v
	else:
		L.append( (min_A, v) )
		min_A-=v
else:
	L.append( (max_A,min_A) )
	print max_A-min_A
	for x,y in L:
		print x,y

Buggy submission (verdict: Runtime Error):
import sys

N=input()
A=map(int, sys.stdin.readline().split())
A.sort()

L=[]
for i in range(N-1):
	if i==0:
		next=A[i]-A[i+1]
		L.append( (A[i], A[i+1]) )

	else:
		if i==N-2:
			if A[i+1]<next:
				ans=next-A[i+1]
				L.append( (next,A[i+1]) )
			else:
				ans=A[i+1]-next
				L.append( (A[i+1],next) )
		else:
			L.append( (next, A[i+1]) )
			next=next-A[i+1]
else:
	print ans
	for x, y in L:
		print x,y

Buggy submission (verdict: Runtime Error):
import sys

N=input()
A=map(int, sys.stdin.readline().split())
A.sort()

L=[]
for i in range(N-1):
	if i==0:
		next=A[i]-A[i+1]
		L.append( (A[i], A[i+1]) )

	else:
		if i==N-2:
			L.append( (A[i+1],next) )
			ans=A[i+1]-next
		else:
			L.append( (next, A[i+1]) )
			next=next-A[i+1]
else:
	print ans
	for x, y in L:
		print x,y
Problem p03074 (python)

Fixed submission:
N,K=map(int, raw_input().split())
S=raw_input()

if "0" not in S:
	print len(S)
	quit()
L=[]
if S[0]=="0": L.append(0)
for i,x in enumerate(S):
	if i==0:
		cnt=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
	prev=x
else:
	L.append(cnt)

if S[-1]=="0": L.append(0)

LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)

K=min(K,len(L)/2)

ans=0
len_lsum=len(LSUM)
for l in range(0,len_lsum,2):
	r=l+2*K+1
	if r < len_lsum:
		ans=max(ans , LSUM[r]-LSUM[l])

print ans

Buggy submission (verdict: Runtime Error):
N,K=map(int, raw_input().split())
S=raw_input()

if "0" not in S:
	print len(S)
	quit()

L=[]
zero_kukan=0
for i,x in enumerate(S):
	if i==0:
		cnt=1
		if x=="0": zero_kukan+=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
			if x=="0": zero_kukan+=1
	prev=x
else:
	L.append(cnt)

K=min(K, zero_kukan)


LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)


#print "L :::: ",L
#print "LSUM  :::: ",LSUM

lsum_len=len(LSUM)

#print "lsum_len  :::: ",lsum_len

h=2*K+1

ans=0
if S[0]=="1":
	for l in range(0,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
else:
	ans=max(ans, LSUM[2*K]-LSUM[0])
	for l in range(1,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
	
	ans=max(ans, LSUM[lsum_len-1]-LSUM[lsum_len-1-2*K])
print ans

Buggy submission (verdict: Runtime Error):
N,K=map(int, raw_input().split())
S=raw_input()

if "0" not in S:
	print len(S)
	quit()

L=[]
for i,x in enumerate(S):
	if i==0:
		cnt=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
	prev=x
else:
	L.append(cnt)	


LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)


#print "L :::: ",L
#print "LSUM  :::: ",LSUM

lsum_len=len(LSUM)

#print "lsum_len  :::: ",lsum_len

h=2*K+1

ans=0
if S[0]=="1":
	for l in range(0,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
else:
	ans=max(ans, LSUM[2*K]-LSUM[0])
	for l in range(1,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
	
	ans=max(ans, LSUM[lsum_len-1]-LSUM[lsum_len-1-2*K])
print ans
Problem p03112 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import itertools

A,B,Q=map(int, sys.stdin.readline().split())

S=[  int(sys.stdin.readline()) for i in range(A) ]
T=[  int(sys.stdin.readline()) for i in range(B) ]
X=[  int(sys.stdin.readline()) for i in range(Q) ]


for x in X:
	sx=bisect_left(S, x)
	tx=bisect_left(T, x)

	s_temp=[]
	if sx==0:
		s_temp.append(S[sx])	
	elif 0<sx<A:
		s_temp.append(S[sx-1])
		s_temp.append(S[sx])
	else:
		s_temp.append(S[sx-1] )


	t_temp=[]
	if tx==0:
		t_temp.append(T[tx])	
	elif 0<tx<B:
		t_temp.append(T[tx-1])
		t_temp.append(T[tx])
	else:
		t_temp.append(T[tx-1] )


	ans=float("inf")

	for s in s_temp:
		for t in t_temp:
			ans=min(ans, abs(s-x)+abs(s-t) )

	for t in t_temp:
		for s in s_temp:	
			ans=min(ans, abs(t-x)+abs(s-t) )

	print ans

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import itertools

A,B,Q=map(int, sys.stdin.readline().split())

S=[  int(sys.stdin.readline()) for i in range(A) ]
T=[  int(sys.stdin.readline()) for i in range(B) ]
X=[  int(sys.stdin.readline()) for i in range(Q) ]


for x in X:
	sx=bisect_left(S, x)
	tx=bisect_left(T, x)

	s_temp=[]
	if sx==0:
		s_temp.append(S[sx])	
	elif 0<sx<A:
		s_temp.append(S[sx-1])
		s_temp.append(S[sx])
	else:
		s_temp.append(S[sx-1] )


	t_temp=[]
	if tx==0:
		t_temp.append(T[tx])	
	elif 0<tx<A:
		t_temp.append(T[tx-1])
		t_temp.append(T[tx])
	else:
		t_temp.append(T[tx-1] )


	ans=float("inf")

	for s in s_temp:
		for t in t_temp:
			ans=min(ans, abs(s-x)+abs(s-t) )

	for t in t_temp:
		for s in s_temp:	
			ans=min(ans, abs(t-x)+abs(s-t) )

	print ans
Problem p03128 (python)

Fixed submission:
T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

N,M=map(int, raw_input().split())
A=map(int, raw_input().split())


P=[]
for i in A:
	P.append(T[i-1])


dp=[ None for i in range(N+1) ]
dp[0]=""


for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:

				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )


print dp[N]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

match=[None,2,5,5,4,5,6,3,7,6]

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		dp_src=dp[i-match_cnt]  #dpの遷移元
		if 0<=i-match_cnt and dp_src is not None:
			if dp[i] is None:
				dp[i]=dp_src+str(a)
			else:
				if int(dp[i])<int( dp_src+str(a) ):
					dp[i]=dp_src+str(a)
				
print dp[N]

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

match=[None,2,5,5,4,5,6,3,7,6]

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		if dp[i-match_cnt] is not None:
			if dp[i] is None:
				dp[i]=dp[i-match_cnt]+str(a)
			else:
				if int(dp[i])<int( dp[i-match_cnt]+str(a) ):
					dp[i]=dp[i-match_cnt]+str(a)
				
print dp[N]
Problem p03138 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

keta=0

for i in range(50,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break



C=[ 0 for i in range(keta) ]	#桁ごとのbit 1の出現回数


for a in A:
	for k in range(keta-1,-1,-1):
		#print "k, a>>k, (a>>k)&1 ::::: ",k, a>>k, (a>>k)&1
		if (a>>k)&1:		#その桁のbitが1なら、出現回数に+1
			C[k]+=1



X=0	# f(x)が最大となるX


len_c=len(C)

for i in range(len_c-1,-1,-1):
	ci=C[i]
	if  C[i]<(N+1)/2:
		if X+2**i<=K:
			X+=2**i		#桁ごとに見て、ゼロの数が多ければ、f(x)が最大となるXとなるXのidx番目の桁は1になる
					#1と0が同数の場合は、その桁を0にしたほうが、Xが小さくなるので有利

ans=0
for a in A:
	ans+=X^a

print ans

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

keta=0

for i in range(30,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break


C=[ 0 for i in range(keta) ]	#桁ごとのbit 1の出現回数

for a in A:
	for k in range(keta,-1,-1):
	#	print k, x>>k, (x>>k)&1
		if (a>>k)&1:		#その桁のbitが1なら、出現回数に+1
			C[k]+=1



X=0	# f(x)が最大となるX


for idx, i in enumerate(C):
	if i<=N/2:
		X+=2**idx	#桁ごとに見て、ゼロの数が多ければ、f(x)が最大となるXとなるXのidx番目の桁は1になる

ans=0
for a in A:
	ans+=X^a

print ans

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

keta=0

for i in range(15,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break


C=[ 0 for i in range(keta) ]	#桁ごとのbit 1の出現回数

for a in A:
	for k in range(keta,-1,-1):
	#	print k, x>>k, (x>>k)&1
		if (a>>k)&1:		#その桁のbitが1なら、出現回数に+1
			C[k]+=1



X=0	# f(x)が最大となるX


for idx, i in enumerate(C):
	if i<=N/2:
		X+=2**idx	#桁ごとに見て、ゼロの数が多ければ、f(x)が最大となるXとなるXのidx番目の桁は1になる

ans=0
for a in A:
	ans+=X^a

print ans
Problem p03148 (python)

Fixed submission:
import sys

N,K=map(int, sys.stdin.readline().split()) 
T=[ map(int, sys.stdin.readline().split()) for i in range(N) ]
T=sorted(T, key=lambda x:(x[0],-x[1]))

KI=[]	#KIND
A=[]	#Nokori

x=None
for t,d in T:
	if t != x:
		KI.append(d)
		x=t
	else:
		A.append(d)

KI.sort(reverse=True)
A.sort(reverse=True)

KI_S=[0]		#KI Ruiseki sum
A_S=[0]		#A Ruiseki sum

for x in KI: KI_S.append( KI_S[-1]+x )
for x in A:  A_S.append( A_S[-1]+x )


la=len(A_S)
lk=len(KI_S)

ans=0
for k in range(1,K+1):
	if K-k<la and k<lk:
		ans=max (ans , KI_S[k]+k**2+A_S[K-k] )

print ans

Buggy submission (verdict: Runtime Error):
import sys

N,K=map(int, sys.stdin.readline().split()) 
T=[ map(int, sys.stdin.readline().split()) for i in range(N) ]
T=sorted(T, key=lambda x:(x[0],-x[1]))

KI=[]	#KIND
A=[]	#Nokori

x=None
for t,d in T:
	if t != x:
		KI.append(d)
		x=t
	else:
		A.append(d)

KI.sort(reverse=True)
A.sort(reverse=True)

KI_S=[0]		#KI Ruiseki sum
A_S=[0]		#A Ruiseki sum

for x in KI: KI_S.append( KI_S[-1]+x )
for x in A:  A_S.append( A_S[-1]+x )


l=len(A_S)

ans=0
for k in range(1,K+1):
	if K-k<l:
		ans=max (ans , KI_S[k]+k**2+A_S[K-k] )

print ans
Problem p03157 (python)

Fixed submission:
from collections import deque

H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 


V=[ [ 0 for i in range(W) ] for j in range(H) ]


def dfs(x,y,current):
	bc=0	#black count
	wc=0	#white count
	q = deque([]) 
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.popleft()

		if current == "#":	  bc+=1
		else:  wc+=1

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				next=S[x+dx][y+dy] 
				if V[x+dx][y+dy]==0 and current !=next:
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy,next) )

	return bc*wc




ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#" and V[x][y]==0:
			ans+=dfs(x,y, "#")

print ans

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)

H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 
V=[ [ 0 for i in range(W) ] for j in range(H) ]

ret=0
def dfs(x,y,current):
	global ret
	V[x][y]=1
	if current==".":
		ret+=1
	else:
		ret+=0

	for dx,dy in D:
		if 0<=x+dx<H and 0<=y+dy<W:
			if V[x+dx][y+dy]==0:
				if S[x+dx][y+dy] != current:
					if current==".":
						dfs(x+dx,y+dy,"#")
					else:
						dfs(x+dx,y+dy,".")
	return ret


ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			V=[ [ 0 for i in range(W) ] for j in range(H) ]
			ans+=dfs(x,y, "#")

print ans

Buggy submission (verdict: Runtime Error):
H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 
V=[ [ 0 for i in range(W) ] for j in range(H) ]

ret=0
def dfs(x,y,current):
	global ret
	V[x][y]=1
	if current==".":
		ret+=1
	else:
		ret+=0

	for dx,dy in D:
		if 0<=x+dx<H and 0<=y+dy<W:
			if V[x+dx][y+dy]==0:
				if S[x+dx][y+dy] != current:
					if current==".":
						dfs(x+dx,y+dy,"#")
					else:
						dfs(x+dx,y+dy,".")
	return ret


ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			V=[ [ 0 for i in range(W) ] for j in range(H) ]
			ans+=dfs(x,y, "#")

print ans
Problem p03165 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
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
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )


ans=""
def lcs(i,j):
	global ans
	if dp[i][j]==0:
		return
	else:
		if s[i]==t[j]:
			lcs(i-1,j-1)
			ans+=s[i]
		else:
			if dp[i-1][j]>=dp[i][j-1]:
				lcs( i-1, j )
			else:
				lcs( i, j-1)

lcs(len_s, len_t)
print ans

Buggy submission (verdict: Runtime Error):
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
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )


ans=""
def lcs(i,j):
	global ans
	if dp[i][j]==0:
		return
	else:
		if s[i]==t[j]:
			lcs(i-1,j-1)
			ans+=s[i]
		else:
			if dp[i-1][j]>=dp[i][j-1]:
				lcs( i-1, j )
			else:
				lcs( i, j-1)

lcs(len_s, len_t)
print ans

Buggy submission (verdict: Runtime Error):
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=[ [ "" for j in range(len_t+1) ] for i in range(len_s+1)   ]

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
			S[i][j]=S[i-1][j-1]+s[i]
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )
			if dp[i-1][j]>=dp[i][j-1]:
				S[i][j]=S[i-1][j]
			else:
				S[i][j]=S[i][j-1]


print S[-1][-1]
Problem p03166 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

N,M=map(int, sys.stdin.readline().split())

nl=[ [] for i in range(N+1) ] 

for i in range(M):
	x,y=map(int, raw_input().split())
	nl[x].append(y)


memo={}

def depth(n):
	if n in memo: return memo[n]
	ret=0
	if len( nl[n] )==0:
		return 0
	else:
		for x in nl[n]:
			ret=max(ret, depth(x)+1)
	memo[n]=ret
	return ret


ans=0
for i in range(1,N+1):
	ans=max( ans , depth(i) )

print ans

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)

N,M=map(int, sys.stdin.readline()..split())

nl=[ [] for i in range(N+1) ] 
f=[ 0 for i in range(N+1) ]
dp=[ 0 for i in range(N+1) ]

for i in range(M):
	x,y=map(int, sys.stdin.readline()..split())
	nl[x].append(y)
	f[y]=1

start=[]
for i in range(1,N+1):
	if f[i]==0:
		start.append(i)


def dfs(v):
	for u in nl[v]:
		dp[u]=max( dp[u], dp[v]+1)
		dfs(u)


for s in start:
	dfs(s)

print max(dp)
Problem p03171 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ 0 for i in range(N) ]  for j in range(N) ]

def func(x,y,cnt):
	if dp[x][y]!=0: return dp[x][y]

	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret+=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret+=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)


print dp[0][N-1]
Problem p03238 (python)

Fixed submission:
N=input()
if N==1:
	print "Hello World"
else:
	A=input()
	B=input()
	print A+B

Buggy submission (verdict: Runtime Error):
N=input()
if N==1:
  	print "Hello World"
else:
  	A=input()
    B=input()
   	print A+B
Problem p03244 (python)

Fixed submission:
from collections import Counter
n=input()
A=map(int,raw_input().split())

M0=[]
M1=[]

for i in range(n):
	if i%2==0: M0.append(A[i])
	else: M1.append(A[i])

C0=Counter(M0)
C1=Counter(M1)

L0=sorted(C0.items(), key=lambda x:x[1], reverse=True)
L1=sorted(C1.items(), key=lambda x:x[1], reverse=True)

a0=None
a1=None

if L0[0][0]!=L1[0][0]:
	a0=L0[0][0]
	a1=L1[0][0]
	b0=L0[0][0]
	b1=L1[0][0]
elif L0[0][0]==L1[0][0]:
	a0=L0[0][0]
	if len(L1)==1:
		a1=-1
	else:
		a1=L1[1][0]

	b1=L1[0][0]
	if len(L0)==1:
		b0=-1
	else:
		b0=L0[1][0]

ans0=0
ans1=0
for x in M0:
	if x!=a0:
		ans0+=1

for x in M1:
	if x!=a1:
		ans0+=1

ans1=0
for x in M0:
	if x!=b0:
		ans1+=1

for x in M1:
	if x!=b1:
		ans1+=1

print min(ans0, ans1)

Buggy submission (verdict: Runtime Error):
from collections import Counter
n=input()
A=map(int,raw_input().split())

M0=[]
M1=[]

for i in range(n):
	if i%2==0: M0.append(A[i])
	else: M1.append(A[i])

C0=Counter(M0)
C1=Counter(M1)

l0=len(C0)
l1=len(C1)

ans=0
if l0>1:
	L=sorted(C1.items(), key=lambda x:x[1])
	ans=0
	for i in range(l0-1):
		ans+=L[i][1]

if l1>1:
	L=sorted(C1.items(), key=lambda x:x[1])
	ans=0
	for i in range(l1-1):
		ans+=L[i][1]

print ans