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

Fixed submission:

def poly_divide(f, g):
    n = len(g)
    a, b = f
    q = [0]*(n-1)
    r = 0
    q[-1] = g[-1]*inv[b%p]%p
    for i in range(n-2)[::-1]:
        q[i] = (g[i+1]-q[i+1]*a)*inv[b%p]%p
    r = g[0]-q[0]
    return q, r
  
def poly_product(f, g):
    n, m = len(f), len(g)
    res = [0]*(n+m-1)
    for i in range(n):
        for j in range(m):
            res[i+j]+=g[j]*f[i]
            res[i+j]%=p
    return res
def assign(f, x):
    tmp = 1
    res = 0
    n = len(f)
    for i in range(n):
        res+=f[i]*tmp
        tmp*=x
        tmp%=p
        res%=p
    return res
def c_mul(c, f):
    n = len(f)
    for i in range(n):
        f[i]*=c
        f[i]%=p
    return f
def poly_add(f, g):
    n = len(g)
    for i in range(n):
        f[i]+=g[i]
        f[i]%=p
    return f


p = int(input())
a = list(map(int, input().split()))
inv = [0]*p
P = [1]
for i in range(p):
    inv[i] = pow(i, p-2, p)
for i in range(p):
    b = [-i, 1]
    P = poly_product(b, P)
R = [0]*p
for i in range(p):
    b = [-i, 1]
    Q, _ = poly_divide(b, P)
    v = assign(Q, i)
    Q=c_mul(inv[v%p]*a[i], Q)
    R = poly_add(R, Q)
print(*R)

Buggy submission (verdict: Runtime Error):
import numpy as np
p = int(input())
a =list(map(int, input().split()))
Q = [0]*p
R = [0]*p

for i in range(p):
    R[i] = pow(i, p-2, p)
for i in range(p):
    res = 1
    for j in range(p):
        if i==j:
            continue
        res*=i-j
    Q[i] = a[i]*R[res%p]
C = [0]*(p+1)
C[0] = 1
for i in range(p):
    for j in range(i+1)[::-1]:
        C[j+1] += C[j]
        C[j] = -i*C[j]
ans = np.poly1d([0])
for i in range(p):
    ans += np.poly1d(C[::-1])/np.poly1d([1, -i])*np.poly1d([Q[i]])
res = ans[1]
res = list(map(lambda x:int(x)%p, res))
print(*res[::-1])
Problem p02981 (python)

Fixed submission:

N, A, B = map(int, input().split())
print(min(B, A*N))

Buggy submission (verdict: Runtime Error):
import math, sys
sys.setrecursionlimit(100000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+10)
T = [1]*(K+10)
for i in range(1, K+10):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        return res*K*P[l+1]%mod
    return res*T[l]%mod
print(count(0))
Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+10)
T = [1]*(K+10)
for i in range(1, K+10):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        if l+1> K-1:
            return 0
        return res*K*P[l+1]%mod
    if l>K-2:
        return 0
    return res*T[l]%mod
print(count(0))

Buggy submission (verdict: Runtime Error):
import math, sys
sys.setrecursionlimit(100000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+10)
T = [1]*(K+10)
for i in range(1, K+10):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        return res*K*P[l+1]%mod
    return res*T[l]%mod
print(count(0))

Buggy submission (verdict: Runtime Error):
import math, sys
sys.setrecursionlimit(1000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+1)
T = [1]*(K+1)
for i in range(1, K+1):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        return res*K*P[l+1]%mod
    return res*T[l]%mod
print(count(0))
Problem p02991 (python)

Fixed submission:
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//3)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
G3 = defaultdict(list)
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    if v == (T-1, 0):
        break
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//3)
Problem p03000 (python)

Fixed submission:
N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 0
ans = N+1
for i in range(N):
    cnt+=L[i]
    if cnt>X:
        ans = i+1
        break
print(ans)

Buggy submission (verdict: Runtime Error):
N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 0
for i in range(N):
    cnt+=L[i]
    if cnt>X:
        ans = i+1
        break
print(ans)
Problem p03026 (python)

Fixed submission:
import heapq
import sys
sys.setrecursionlimit(10000000)
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import heapq
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))
Problem p03044 (python)

Fixed submission:
import sys

sys.setrecursionlimit(1000000)
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10000)
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)

Buggy submission (verdict: Runtime Error):
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)

Buggy submission (verdict: Runtime Error):
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)

Buggy submission (verdict: Runtime Error):
n=int(input())
mat=[[]*n for _ in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)

Buggy submission (verdict: Runtime Error):
n=int(input())
mat=[[]*n for _ in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    if kw[1]%2==1:
        p*=-1
    group[kw[0]]=p
    for kwi in mat[kw[0]]:
        if kwi[0]!=l:
            C(kwi, p, kw[0])
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)
Problem p03046 (python)

Fixed submission:
M, K = map(int, input().split())
if K>(1<<M)-1:
    print(-1)
elif M == 1 and K == 1:
    print(-1)
elif M == 1 and K == 0:
    print(0, 0, 1, 1)
elif M == 0 and K == 0:
    print(0, 0)
elif M == 0:
    print(-1)
else:
    N = 1<<M
    ans = list(range(K))+list(range(K+1, N))+[K]+list(range(K+1, N))[::-1]+list(range(K))[::-1]+[K]
    print(*ans)

Buggy submission (verdict: Runtime Error):
M, K = map(int, input().split())
if K>1<<M-1:
    print(-1)
elif M == 1 and K == 1:
    print(-1)
elif M == 1 and K == 0:
    print(0, 0, 1, 1)
elif M == 0 and K == 0:
    print(0, 0)
elif M == 0:
    print(-1)
else:
    N = 1<<M
    ans = list(range(K))+list(range(K+1, N))+[K]+list(range(K+1, N))[::-1]+list(range(K))[::-1]+[K]
    print(*ans)
Problem p03062 (python)

Fixed submission:
n=int(input())
a=list(map(int, input().split()))
pos=[]
nega=[]

for i in range(n):
    if a[i]>=0:
        pos.append(a[i])
    else:
        nega.append(a[i])
if len(pos)==0:
    if len(nega)%2==0:
        print(abs(sum(a)))
    else:
        print(abs(sum(a))+max(a)*2)
elif len(nega)==0:
    print(sum(a))
elif len(nega)%2==0:
    print(sum(pos)-sum(nega))
else:
    if min(pos)>-max(nega):
        print(sum(pos)-sum(nega)+max(nega)*2)
    else:
        print(sum(pos)-sum(nega)-min(pos)*2)

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int, input().split()))
pos=[]
nega=[]
for i in range(n):
    if a[i]>=0:
        pos.append(a[i])
    else:
        nega.append(a[i])
if len(nega)%2==0:
    print(sum(pos)-sum(nega))
else:
    if min(pos)>-max(nega):
        print(sum(pos)-sum(nega)+max(nega)*2)
    else:
        print(sum(pos)-sum(nega)-min(pos)*2)
Problem p03078 (python)

Fixed submission:
from heapq import heappush, heappop
s=set()
q=[]
x, y, z, k = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse=True)
b=sorted(list(map(int, input().split())), reverse=True)
c=sorted(list(map(int, input().split())), reverse=True)
heappush(q, (-(a[0]+b[0]+c[0]), 0, 0, 0))
def push(d, e, f):
    if (d, e, f) not in s and 0<=d<x and 0<=e<y and 0<=f<z:
        heappush(q, (-(a[d]+b[e]+c[f]), d, e, f))
        s.add((d, e, f))
for i in range(k):
    p, d, e, f =heappop(q)
    print(-p)
    push(d+1, e, f)
    push(d, e+1, f)
    push(d, e, f+1)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop
s=set()
q=[]
x, y, z, k = map(int, input().split())
a=sorted(list(map(int, input().split())), reverse=True)
b=sorted(list(map(int, input().split())), reverse=True)
c=sorted(list(map(int, input().split())), reverse=True)
heapq.heappush(q, (-(a[0]+b[0]+c[0]), 0, 0, 0))
def push(d, e, f):
    if (d, e, f) not in s and 0<=d<x and 0<=e<y and 0<=f<z:
        heapq.heappush(q, (-(a[d]+b[e]+c[f]), d, e, f))
        s.add((d, e, f))
for i in range(k):
    p, d, e, f =heapq.heappop(q)
    print(-p)
    push(d+1, e, f)
    push(d, e+1, f)
    push(d, e, f+1)
Problem p03091 (python)

Fixed submission:
import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<=1:
    print('No')
    sys.exit()
v = cnt.index(4)
for v0 in G[v]:
    now = v0
    p = v
    while True:
        for nv in G[now]:
            if nv == p:
                continue
            p = now
            now = nv
            break
        if now == v:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')

Buggy submission (verdict: Runtime Error):
import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
print(1/0)
v = cnt.index(4)
for v0 in G[v]:
    now = v0
    p = v
    while True:
        for nv in G[now]:
            if nv == p:
                continue
            p = now
            now = nv
            break
        if now == v:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')
Problem p03126 (python)

Fixed submission:
n,m = map(int, input().split())
q=[input() for i in range(n)]
l=[i+1 for i in range(m)]
l1=[i+1 for i in range(m)]
for i in q:
  t=list(map(int, i.split()))
  for k in l1:
    if (k not in t[1:]):
      if k in l:
      	l.remove(k)
print(len(l))

Buggy submission (verdict: Runtime Error):
n,m = map(int, input().split())
q=[input() for i in range(n)]
l=[i+1 for i in range(m)]
l1=[i+1 for i in range(m)]
for i in q:
  t=list(map(int, i.split()))
  for k in l1:
    if (k not in t[1:]):
      l.remove(k)
print(len(l))
Problem p03134 (python)

Fixed submission:
mod = 998244353
import sys
sys.setrecursionlimit(10**9)
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
dp = [[0]*(N*2+1) for _ in range(N*2+1)]
for i in range(N*2+1)[::-1]:
    for j in range(N*2+1)[::-1]:
        if i+j == N*2:
            dp[i][j] = 1
            continue
        n = min(i+j+1, N)
        s = Sum[n]
        if i<s:
            dp[i][j]+=dp[i+1][j]
        if 2*n-s>j:
            dp[i][j]+=dp[i][j+1]
        dp[i][j]%=mod
print(dp[0][0])

Buggy submission (verdict: Runtime Error):
mod = 998244353
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
from functools import lru_cache
@lru_cache(maxsize=10**8)
def dp(i, j):
    n = min(i+j+1, N)
    if i+j == N*2:
        return 1
    res = 0
    s = Sum[n]
    if i<s:
        res+=dp(i+1, j)
    if j<2*n-s:
        res+=dp(i, j+1)
    return res%mod
print(dp(0, 0))

Buggy submission (verdict: Runtime Error):
mod = 998244353
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
from functools import lru_cache

@lru_cache(maxsize=1000)
def dp(i, j):
    n = min(i+j+1, N)
    if i+j == N*2:
        return 1
    res = 0
    s = Sum[n]
    if i<s:
        res+=dp(i+1, j)
    if j<2*n-s:
        res+=dp(i, j+1)
    return res%mod
print(dp(0, 0))
Problem p03160 (python)

Fixed submission:
N = int(input())
h = list(map(int, input().split()))
dp = [0]*N
for i in range(1, N):
    if i-2>=0:
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    else:
        dp[i] = dp[i-1]+abs(h[i]-h[i-1])
print(dp[-1])

Buggy submission (verdict: Runtime Error):
sys.setrecursionlimit(10**9)
N = int(input())
h = list(map(int, input().split()))
memo = [-1]*N
def dp(i):
    if memo[i]>=0:
        return memo[i]
    if i == 0:
        memo[i] = 0
        return 0
    if i>=2:
        memo[i] = min(dp(i-1)+abs(h[i]-h[i-1]), dp(i-2)+abs(h[i]-h[i-2]))
    else:
        memo[i] = dp(i-1)+abs(h[i]-h[i-1])
    return memo[i]
print(dp(N-1))

Buggy submission (verdict: Runtime Error):
N = int(input())
h = list(map(int, input().split()))
memo = [-1]*N
def dp(i):
    if memo[i]>=0:
        return memo[i]
    if i == 0:
        memo[i] = 0
        return 0
    if i>=2:
        memo[i] = min(dp(i-1)+abs(h[i]-h[i-1]), dp(i-2)+abs(h[i]-h[i-2]))
    else:
        memo[i] = dp(i-1)+abs(h[i]-h[i-1])
    return memo[i]
print(dp(N-1))
Problem p03163 (python)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype = np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
print(dp.max())

Buggy submission (verdict: Runtime Error):
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype = np.int64)
for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
print(dp.max())
Problem p03166 (python)

Fixed submission:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
H = [0]*N
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    H[y-1]+=1

def topological_sort(G, H):
    res = []
    st0 = set()
    for v, n in enumerate(H):
        if n == 0:
            st0.add(v)
    while st0:
        v = st0.pop()
        res.append(v)
        for nv in G[v]:
            H[nv]-=1
            if H[nv] == 0:
                st0.add(nv)
    return res
i_to_v = topological_sort(G, H)
v_to_i = [0]*N
for i in range(N):
    v_to_i[i_to_v[i]] = i
dp = [0]*N
for i in range(N-1):
    for nv in G[i_to_v[i]]:
        dp[v_to_i[nv]] = max(dp[i]+1, dp[v_to_i[nv]])
print(max(dp))

Buggy submission (verdict: Runtime Error):
import numpy as np
mod = 10**9+7
def MatPower(A, k):
    B = np.identity(len(A), dtype = object)
    while k:
        if k&1:
            B = np.dot(A, B)%mod
        A = np.dot(A, A)%mod
        k//=2
    return B
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype = object)
v = np.array([1]*N, dtype = object).T
An = MatPower(a, K)
v = np.dot(An, v)%mod
ans = 0
for i in range(N):
    ans+=v[i]
    ans%=mod
print(ans)
Problem p03169 (python)

Fixed submission:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(c1+c2+c3+1) for i in range(c2+c3+1)] for j in range(c3+1)]
    for i in range(c3+1):
        for j in range(c2+c3+1):
            for k in range(c1+c2+c3+1):
                if i+j+k>N:
                    continue
                if i>0 and j<c2+c3:
                    dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
                if j>0 and k<c1+c2+c3:
                    dp[i][j][k]+=(j/N)*dp[i][j-1][k+1]
                if k>0:
                    dp[i][j][k]+=(k/N)*dp[i][j][k-1]
                if  i+j+k == 0:
                    continue
                dp[i][j][k]+=1
                dp[i][j][k]*=N/(i+j+k)
    print(dp[c3][c2][c1])
main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(c1+c2+c3+1) for i in range(c2+c3+1)] for j in range(c3+1)]

    for i in range(c3+1):
        for j in range(c2+c3+1):
            for k in range(c1+c2+c3+1):
                if i+j+k>N:
                    continue
                if i>0 and j<N:
                    dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
                if j>0 and k<N:
                    dp[i][j][k]+=(j/N)*dp[i][j-1][k+1]
                if k>0:
                    dp[i][j][k]+=(k/N)*dp[i][j][k-1]
                if  i+j+k == 0:
                    continue
                dp[i][j][k]+=1
                dp[i][j][k]*=N/(i+j+k)
    print(dp[c3][c2][c1])
main()
Problem p03174 (python)

Fixed submission:
mod = 10**9+7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0]*(1<<N)
dp[0] = 1
for s in range(1, 1<<N):
    women = []
    for i in range(N):
        if (1<<i)&s:
            women.append(i)
    m = len(women)-1
    for w in women:
        if a[m][w] == 1:
            dp[s]+=dp[s^(1<<w)]
            dp[s]%=mod
print(dp[-1])

Buggy submission (verdict: Runtime Error):
def main()
    mod = 10**9+7
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*(1<<N)
    dp[0] = 1
    def bitcount(i): # i < 2^32
        i = i - ((i >> 1) & 0x55555555)
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
        return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
    for s in range(1, 1<<N):
        women = []
        m = bitcount(s)-1
        for w in range(N):
            if a[m][w] == 1 and s&1<<w:
                dp[s]+=dp[s^(1<<w)]
                dp[s]%=mod
    print(dp[-1])
main()