Problem p02581 (python)

Fixed submission:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
def run():
    N, *A_ = map(int, read().split())
    dp = [[-INF] * (N+1) for _ in range(N+1)]
    dp_max = [-INF] * (N+1)
    a, b = A_[:2]
    dp[a][b] = dp[b][a] = dp_max[a] = dp_max[b] = 0

    triplets = 0
    chunks = []

    for i in range(N-1):
        x,y,z = A_[3*i+2 : 3*i+5]
        if x == y == z:
            triplets+=1
        else:
            chunks.append((x,y,z))

    for x,y,z in chunks:
        cache = []
        # transition : a = x = y
        if y == z:
            x,y,z = y,z,x
        elif z == x:
            x,y,z = z,x,y

        if x == y:
            for i in range(1, N+1):
                cache.append((z, i, dp[x][i] + 1))

        # trainsition : a = b = x
        cache.append((y, z, dp[x][x] + 1))
        cache.append((z, x, dp[y][y] + 1))
        cache.append((x, y, dp[z][z] + 1))

        # trainsition : only fill next
        MAX = max(dp_max)
        cache.append((x, y, MAX))
        cache.append((y, z, MAX))
        cache.append((z, x, MAX))
        for i in range(1, N+1):
            cache.append((i, x, dp_max[i]))
            cache.append((i, y, dp_max[i]))
            cache.append((i, z, dp_max[i]))

        # Update
        for a, b, value in cache:
            dp[a][b] = dp[b][a] = max(value, dp[a][b])
            dp_max[a] = max(dp_max[a], dp[a][b])
            dp_max[b] = max(dp_max[b], dp[a][b])

    a = A_[-1]
    dp[a][a] += 1
    dp_max[a] = max(dp[a][a], dp_max[a])

    print(max(dp_max) + triplets)
    #print(chunks)


if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def check_triple(L):
    ret = L[:]
    for l in L:
        if L.count(l) >= 3:
            for i in range(3):
                ret.remove(l)
            return True, ret
    return False, ret

def run():
    N, *A = map(int, read().split())
    dic = defaultdict(lambda : 0)
    for a in A:
        dic[a] += 1
    dp = [defaultdict(lambda:0) for i in range(N)]
    prim = sorted(A[:2])
    prim = tuple(prim)
    dp[0][prim] = 0
    for i in range(N-1):
        for key, score in dp[i].items():
            a, b = key
            temp_lis = [a,b] + A[2 + i * 3: 5 + i * 3]
            temp_lis = sorted(temp_lis)

            #print(temp_lis, '--->')
            ANS, temp_lis = check_triple(temp_lis)
            #print(temp_lis)
            if ANS:
                temp_lis = tuple(temp_lis)
                dp[i+1][temp_lis] = max(score + 1, dp[i+1][temp_lis])
            else:
                app = []
                for val in temp_lis:
                    if dic[val] > 2:
                        app.append(val)
                if len(app) < 2:
                    for v in temp_lis:
                        if not v in app:
                            app.append(v)
                            break
                app = sorted(app)
                for idx, a in enumerate(app):
                    for b in app[idx+1:]:
                        dp[i+1][(a, b)] = max(dp[i+1][(a,b)], score)

    ans = max(dp[N-1].values())

    for key, score in dp[N-1].items():
        a, b = key
        if a == b and a == A[-1]:
            ans = max(ans, score + 1)

    print(ans)



if __name__ == "__main__":
    #a = (1,2,3,4,5)
    #for i in range(1000000):
    #    check_triple(a)
    run()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def check_triple(L):
    ret = L[:]
    for l in L:
        if L.count(l) >= 3:
            for i in range(3):
                ret.remove(l)
            return True, ret
    return False, ret

def run():
    N, *A = map(int, read().split())
    dic = defaultdict(lambda : 0)
    for a in A:
        dic[a] += 1
    dp = [defaultdict(lambda:0) for i in range(N)]
    prim = sorted(A[:2])
    prim = tuple(prim)
    dp[0][prim] = 0
    for i in range(N-1):
        for key, score in dp[i].items():
            a, b = key
            temp_lis = [a,b] + A[2 + i * 3: 5 + i * 3]
            temp_lis = sorted(temp_lis)

            #print(temp_lis, '--->')
            ANS, temp_lis = check_triple(temp_lis)
            #print(temp_lis)
            if ANS:
                temp_lis = tuple(temp_lis)
                dp[i+1][temp_lis] = max(score + 1, dp[i+1][temp_lis])
            else:
                app = []
                for val in temp_lis:
                    if dic[val] > 2:
                        app.append(val)
                if len(app) < 2:
                    for v in temp_lis:
                        if not v in app:
                            app.append(v)
                            break
                app = sorted(app)
                for idx, a in enumerate(app):
                    for b in app[idx+1:]:
                        dp[i+1][(a, b)] = max(dp[i+1][(a,b)], score)

    ans = max(dp[N-1].values())

    for key, score in dp[N-1].items():
        a, b = key
        if a == b and a == A[-1]:
            ans = max(ans, score + 1)

    print(ans)



if __name__ == "__main__":
    #a = (1,2,3,4,5)
    #for i in range(1000000):
    #    check_triple(a)
    run()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def check_triple(L):
    ret = L[:]
    for l in L:
        if L.count(l) >= 3:
            val = l
            for i in range(3):
                ret.remove(l)
            return True, ret
    return False, ret

def run():
    N, *A = map(int, read().split())

    dp = [defaultdict(lambda:0) for i in range(N)]
    prim = sorted(A[:2])
    prim = tuple(prim)
    dp[0][prim] = 0
    for i in range(N-1):
        for key, score in dp[i].items():
            a, b = key
            temp_lis = [a,b] + A[2 + i * 3: 5 + i * 3]
            temp_lis = sorted(temp_lis)

            #print(temp_lis, '--->')
            ANS, temp_lis = check_triple(temp_lis)
            #print(temp_lis)
            if ANS:
                dp[i+1][tuple(temp_lis)] = max(score + 1, dp[i+1][temp_lis])
            else:
                for idx, a in enumerate(temp_lis):
                    for b in temp_lis[idx+1:]:
                        dp[i+1][(a, b)] = max(dp[i+1][(a,b)], score)

    ans = max(dp[N-1].values())

    for key, score in dp[N-1].items():
        a, b = key
        if a == b and a == A[-1]:
            ans = max(ans, score + 1)

    print(ans)



if __name__ == "__main__":
    #a = [1,2,3,4,5]
    #for i in range(1000000):
    #    check_triple(a)
    run()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def check_triple(L):
    ret = L[:]
    for l in L:
        if L.count(l) >= 3:
            val = l
            for i in range(3):
                ret.remove(l)
            return True, ret
    return False, ret

def run():
    N, *A = map(int, read().split())

    dp = [defaultdict(lambda:0) for i in range(N)]
    prim = sorted(A[:2])
    prim = tuple(prim)
    dp[0][prim] = 0
    for i in range(N-1):
        for key, score in dp[i].items():
            a, b = key
            temp_lis = [a,b] + A[2 + i * 3: 5 + i * 3]
            temp_lis = sorted(temp_lis)

            #print(temp_lis, '--->')
            ANS, temp_lis = check_triple(temp_lis)
            #print(temp_lis)
            if ANS:
                dp[i+1][temp_lis] = max(score + 1, dp[i+1][temp_lis])
            else:
                for idx, a in enumerate(temp_lis):
                    for b in temp_lis[idx+1:]:
                        dp[i+1][(a, b)] = max(dp[i+1][(a,b)], score)

    ans = max(dp[N-1].values())

    for key, score in dp[N-1].items():
        a, b = key
        if a == b and a == A[-1]:
            ans = max(ans, score + 1)

    print(ans)



if __name__ == "__main__":
    #a = [1,2,3,4,5]
    #for i in range(1000000):
    #    check_triple(a)
    run()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50



def run():
    N, *A = map(int, read().split())
    A = A[::-1]

    dic = defaultdict(lambda:0)
    for a in A:
        dic[a] += 1

    score = 0
    while len(A) > 3:
        #print(A)
        tmp_dic = defaultdict(lambda:0)
        for i in range(5):
            tmp_a = A.pop()
            tmp_dic[tmp_a] += 1

        done = False
        for key, val in tmp_dic.items():
            if val == 3:
                score += 1
                del tmp_dic[key]
                done = True
                dic[key] -= 3
                break
            elif val > 3:
                score += 1
                tmp_dic[key] -= 3
                done = True
                dic[key] -= 3
                break

        if not done:
            lis = []
            for key in tmp_dic.keys():
                lis.append((dic[key], A[-5:].count(key), key))
            lis = sorted(lis, key = lambda x:x[0])
            cnt = 0
            #print(lis)
            for _, ,_,key in lis:
                if 3 - cnt > tmp_dic[key]:
                    cnt += tmp_dic[key]
                    dic[key] -= tmp_dic[key]
                    del tmp_dic[key]
                else:
                    dic[key] -= 3-cnt
                    tmp_dic[key] -= 3-cnt
                    cnt = 3

        for key, val in tmp_dic.items():
            for _ in range(val):
                A.append(key)
    if A[0] == A[1] and A[1] == A[2]:
        score += 1

    print(score)


if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50



def run():
    N, *A = map(int, read().split())
    A = A[::-1]

    dic = defaultdict(lambda:0)
    for a in A:
        dic[a] += 1

    score = 0
    while len(A) > 3:
        #print(A)
        tmp_dic = defaultdict(lambda:0)
        for i in range(5):
            tmp_a = A.pop()
            tmp_dic[tmp_a] += 1
        done = False
        for key, val in tmp_dic.items():
            if val == 3:
                score += 1
                del tmp_dic[key]
                done = True
                dic[key] -= 3
                break
            elif val > 3:
                score += 1
                tmp_dic[key] -= val
                done = True
                dic[key] -= 3
                break

        if not done:
            lis = []
            for key in tmp_dic.keys():
                lis.append((dic[key], key))
            lis = sorted(lis, key = lambda x:x[0])
            cnt = 0
            #print(lis)
            for _, key in lis:
                if 3 - cnt > tmp_dic[key]:
                    cnt += tmp_dic[key]
                    del tmp_dic[key]
                else:
                    tmp_dic[key] -= 3-cnt
                    cnt = 3
        for key, val in tmp_dic.items():
            for _ in range(val):
                A.append(key)
    if A[0] == A[1] and A[1] == A[2]:
        score += 1

    print(score)


if __name__ == "__main__":
    run()