Problem:
 Score : 600 points    Problem Statement We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i -th card from the left is A_i .  You will do the following operation N-1 times:   Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.   After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.  Find the maximum number of points you can gain.      Constraints  1 \leq N \leq 2000  1 \leq A_i \leq N         Input Input is given from Standard Input in the following format:  N  A_1  A_2  \cdots  A_{3N}       Output Print the maximum number of points you can gain.        Sample Input 1 2
1 2 1 2 2 1      Sample Output 1 2  Let us rearrange the five leftmost cards so that the integers written on the six cards will be 2\ 2\ 2\ 1\ 1\ 1 from left to right.  Then, remove the three leftmost cards, all of which have the same integer 2 , gaining 1 point.  Now, the integers written on the remaining cards are 1\ 1\ 1 .  Since these three cards have the same integer 1 , we gain 1 more point.  In this way, we can gain 2 points - which is the maximum possible.       Sample Input 2 3
1 1 2 2 3 3 3 2 1      Sample Output 2 1       Sample Input 3 3
1 1 2 2 2 3 3 3 1      Sample Output 3 3

Solution (Python):
def solve(n, aaa):
    dp = [[-1] * n for _ in range(n)]
    dp_max = [-1] * n
    ans = 0

    a0, a1 = sorted(aaa[:2])
    dp[a0][a1] = 0
    dp_max[a0] = 0
    dp_max[a1] = 0

    for k in range(n - 1):
        a0, a1, a2 = sorted(aaa[2 + 3 * k:5 + 3 * k])
        if a0 == a1 and a1 == a2:
            ans += 1
            continue

        dp_max_max = max(dp_max)
        update_tasks = []

        if a0 == a1 or a1 == a2:
            rev = a1 == a2
            if rev:
                a0, a2 = a2, a0

            for b in range(n):
                c, d = min(a0, b), max(a0, b)
                e, f = min(a2, b), max(a2, b)
                update_tasks.append((e, f, dp_max[b]))
                if dp[c][d] != -1:
                    update_tasks.append((e, f, dp[c][d] + 1))

            update_tasks.append((a0, a0, dp_max_max))
            if dp[a2][a2] != -1:
                update_tasks.append((a0, a0, dp[a2][a2] + 1))

            if rev:
                update_tasks.append((a2, a0, dp_max_max))
            else:
                update_tasks.append((a0, a2, dp_max_max))

        else:
            update_tasks.append((a0, a1, dp_max_max))
            update_tasks.append((a0, a2, dp_max_max))
            update_tasks.append((a1, a2, dp_max_max))
            if dp[a0][a0] != -1:
                update_tasks.append((a1, a2, dp[a0][a0] + 1))
            if dp[a1][a1] != -1:
                update_tasks.append((a0, a2, dp[a1][a1] + 1))
            if dp[a2][a2] != -1:
                update_tasks.append((a0, a1, dp[a2][a2] + 1))

            for b in range(n):
                b_max = dp_max[b]
                for a in (a0, a1, a2):
                    c, d = min(a, b), max(a, b)
                    update_tasks.append((c, d, b_max))

        for a, b, c in update_tasks:
            dp[a][b] = max(dp[a][b], c)
            dp_max[a] = max(dp_max[a], c)
            dp_max[b] = max(dp_max[b], c)

    a = aaa[-1]
    dp[a][a] += 1

    return max(map(max, dp)) + ans


n = int(input())
aaa = [a - 1 for a in map(int, input().split())]
ans = solve(n, aaa)
print(ans)

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:] - 1
    dp = np.full((n, n), -1, dtype=np.int16)
    dp_max = np.full(n, -1, dtype=np.int16)
    ans = 0

    a0, a1 = sorted(aaa[:2])
    dp[a0][a1] = 0
    dp_max[a0] = 0
    dp_max[a1] = 0

    for k in range(n - 1):
        a0, a1, a2 = sorted(aaa[2 + 3 * k:5 + 3 * k])
        if a0 == a1 and a1 == a2:
            ans += 1
            continue

        dp_max_max = dp_max.max()
        update_tasks = []

        if a0 == a1 or a1 == a2:
            rev = a1 == a2
            if rev:
                a0, a2 = a2, a0

            for b in range(n):
                c, d = min(a0, b), max(a0, b)
                e, f = min(a2, b), max(a2, b)
                update_tasks.append((e, f, dp_max[b]))
                if dp[c][d] != -1:
                    update_tasks.append((e, f, dp[c][d] + 1))

            update_tasks.append((a0, a0, dp_max_max))
            if dp[a2][a2] != -1:
                update_tasks.append((a0, a0, dp[a2][a2] + 1))

            if rev:
                update_tasks.append((a2, a0, dp_max_max))
            else:
                update_tasks.append((a0, a2, dp_max_max))

        else:
            update_tasks.append((a0, a1, dp_max_max))
            update_tasks.append((a0, a2, dp_max_max))
            update_tasks.append((a1, a2, dp_max_max))
            if dp[a0][a0] != -1:
                update_tasks.append((a1, a2, dp[a0][a0] + 1))
            if dp[a1][a1] != -1:
                update_tasks.append((a0, a2, dp[a1][a1] + 1))
            if dp[a2][a2] != -1:
                update_tasks.append((a0, a1, dp[a2][a2] + 1))

            for b in range(n):
                b_max = dp_max[b]
                for a in (a0, a1, a2):
                    c, d = min(a, b), max(a, b)
                    update_tasks.append((c, d, b_max))

        for a, b, c in update_tasks:
            dp[a][b] = max(dp[a][b], c)
            dp_max[a] = max(dp_max[a], c)
            dp_max[b] = max(dp_max[b], c)

    a = aaa[-1]
    dp[a][a] += 1

    return dp.max() + ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

if N==1:
    if A[0]==A[1]==A[2]:
        print(1)
    else:
        print(0)
    exit()

INF = float('inf')
ans = 0
dp = [[-INF]*(N+1) for _ in range(N+1)]
dp[A[0]][A[1]] = dp[A[1]][A[0]] = 0
maxdp = [max(row) for row in dp]
use = {A[0], A[1]}

for i in range(N-1):
    a,b,c = A[i*3+2:i*3+5]
    if a==b==c:
        ans += 1
        continue
    update = []
    if a==b:
        for j in use:
            update.append((j,c, max(dp[a][j], dp[j][a]) + 1))
    elif b==c:
        for j in use:
            update.append((j,a, max(dp[b][j], dp[j][b]) + 1))
    elif c==a:
        for j in use:
            update.append((j,b, max(dp[c][j], dp[j][c]) + 1))
    update.append((a,b, dp[c][c] + 1))
    update.append((b,c, dp[a][a] + 1))
    update.append((c,a, dp[b][b] + 1))
    mx = max(maxdp)
    update.append((a,b, mx))
    update.append((b,c, mx))
    update.append((c,a, mx))
    for j in use:
        update.append((j,a, maxdp[j]))
        update.append((j,b, maxdp[j]))
        update.append((j,c, maxdp[j]))
    for l,m,n in update:
        dp[l][m] = dp[m][l] = max(dp[l][m], dp[m][l], n)
        maxdp[l] = max(maxdp[l], n)
        maxdp[m] = max(maxdp[m], n)
    use.add(a)
    use.add(b)
    use.add(c)

tmp = max(maxdp)
tmp = max(tmp, dp[A[-1]][A[-1]] + 1)
ans += tmp
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

n = int(input())
a = list(map(int,input().split()))

a.append(n+1)
a.append(n+1)

dp = [[-1]*(n+2) for i in range(n+2)]
ma = [-1]*(n+2)

dp[a[0]][a[1]] = 0
ma[a[0]] = 0
ma[a[1]] = 0

after = 0

for i in range(n):
    x,y,z = a[3*i+2],a[3*i+3],a[3*i+4]
    if x == z:
        y,z = z,y
    if y == z:
        x,z = z,x
    
    if x == z:
        after += 1
        continue

    
    tank = []

    if x != y:
        for i in range(n+1):
            tank.append((i,x,ma[i]))
            tank.append((i,y,ma[i]))
            tank.append((i,z,ma[i]))       
        tank.append((x,y,max(max(ma),dp[z][z] + 1)))
        tank.append((x,z,max(max(ma),dp[y][y] + 1)))
        tank.append((y,z,max(max(ma),dp[x][x] + 1)))
    else:
        for i in range(n+1):
            tank.append((i,x,ma[i]))
            tank.append((i,y,ma[i]))
            tmp = ma[i]
            if dp[i][x] != -1:
                tmp = max(tmp,dp[i][x] + 1)
            if dp[x][i] != -1:
                tmp = max(tmp,dp[x][i] + 1)
            tank.append((i,z,tmp))
        tank.append((x,y,max(max(ma),dp[z][z] + 1)))
        tank.append((x,z,max(max(ma),dp[y][y] + 1)))
        tank.append((y,z,max(max(ma),dp[x][x] + 1)))

    for p,q,c in tank:
        dp[p][q] = max(dp[p][q],c)
        ma[p] = max(ma[p],c)
        ma[q] = max(ma[q],c)

res = 0
for i in range(n+2):
    for j in range(n+2):
        res = max(res,dp[i][j])

print(res+after)

Solution (Python):

N = int(input())
A = list(map(int, input().split()))


ans = [[-N] * (N+1) for _ in range(N+1)]

a0, a1 = A[:2]
ans[a0][a1] = 0
ans[a1][a0] = 0



ma = [-N] * (N+1) 

ma[a0] = 0
ma[a1] = 0

all_max = 0


add = 0


for i in range(N - 1): 
    
    a, b, c = A[3 * i + 2], A[3 * i + 3], A[3 * i + 4]
    
    if a == b == c:
        add += 1
        continue
    Q = []
    for _ in range(3):
        a, b, c = b, c, a
        
        
        
        Q.append((a, b, max(all_max, ans[c][c] + 1)))
        
        
        for j in range(1, N + 1):
            
            val = ma[j]
            
            if b == c:
                val = max(val, ans[b][j] + 1)
            Q.append((a, j, val))
            
        
        
    for i, j, val in Q:
        
        ans[i][j] = max(ans[i][j], val)
        ans[j][i] = max(ans[j][i], val)
        
        ma[i] = max(ma[i], val)
        ma[j] = max(ma[j], val)
        all_max = max(all_max, val)
        

answer = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        
        if i == j == A[-1]:
            answer = max(answer, ans[i][j] + 1)
        else:
            answer = max(answer, ans[i][j])
            
print(answer + add)

Solution (Python):
"""

https://atcoder.jp/contests/abc176/tasks/abc176_f

dp[i][c1][c2] = 先頭2枚がc1とc2(c1<=c2)の時の答えの最大
で解けるようだ
毎回の処理をO(N)に抑えなくてはいけない

3枚が同じときは取っちゃえばいいので、3枚みたいな変数を用意しておいて答えに足せばいい
2枚が同じな時、更新するべきはc1とc2のうち片方以上が同じな場合
→残る2枚は確定するので、O(N)の更新が必要
1枚あるのをセットにする場合、c1=c2である。残りの2枚は確定するので、O(1)で更新できる。

セットにせず、カードを交換する場合も考える
新しいカードでそろえる場合は、渡される2枚は関係ないので、maxを持っておき、それで置き換えればいい
新しい+古いカードの場合は、そのカードを含む最大で更新すればいい？
→O(N)で更新するために、あるカードを含む数値の最大をもっておく

"""

import sys
from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
for i in range(3*N):
    A[i] -= 1

nmax = 0 
maxin = [float("-inf")] * N 
three = 0 

dp = [ [float("-inf")] * N for i in range(N) ]
c1,c2 = A[:2]
if c1 > c2:
    c1,c2 = c2,c1
dp[c1][c2] = 0
maxin[c1] = 0
maxin[c2] = 0


for i in range(N-1):

    cards = A[2+3*i:5+3*i]
    cards.sort()

    
    if cards[0] == cards[1] and cards[1] == cards[2]:
        three += 1
        continue

    change = [] 

    
    if cards[0] == cards[1]:
        nc = cards[0]
        for i in range(N):
            c1 = cards[2]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))
    if cards[1] == cards[2]:
        nc = cards[1]
        for i in range(N):
            c1 = cards[0]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))

    
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[0]][cards[0]]+1))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[1]][cards[1]]+1))
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,dp[cards[2]][cards[2]]+1))

    
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,nmax))
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,nmax))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,nmax))

    
    for c1 in cards:
        for c2 in range(N):
            tmpmax = maxin[c2]
            if c1 > c2:
                change.append((c2,c1,tmpmax))
            else:
                change.append((c1,c2,tmpmax))

    
    

    for c1,c2,tmp in change:
        nmax = max(nmax,tmp)
        dp[c1][c2] = max(dp[c1][c2],tmp)
        maxin[c1] = max(maxin[c1],tmp)
        maxin[c2] = max(maxin[c2],tmp)

    

nmax = max(nmax , dp[A[-1]][A[-1]] + 1)
print (nmax + three)

Solution (Python):
n = int(input())
a = [*map(int, input().split())]
for i in range(n * 3):
    a[i] -= 1

INF = 1<<30
dp = [[-INF] * n for i in range(n)]
mx = [-INF] * n
mx_all = -INF
add_all = 0

dp[a[0]][a[1]] = dp[a[1]][a[0]] = 0
mx[a[0]] = mx[a[1]] = 0
mx_all = 0

for i in range(n - 1):
    x, y, z = sorted(a[i * 3 + 2 : i * 3 + 5])
    update = []
    
    if x == y == z:
        add_all += 1
        continue
    
    if x == y:
        for j in range(n):
            update.append((j, z, dp[j][x] + 1))
    if y == z:
        for j in range(n):
            update.append((j, x, dp[j][y] + 1))
    
    update.append((y, z, dp[x][x] + 1))
    update.append((x, z, dp[y][y] + 1))
    update.append((x, y, dp[z][z] + 1))
    
    for j in range(n):
        update.append((j, x, mx[j]))
        update.append((j, y, mx[j]))
        update.append((j, z, mx[j]))
    
    update.append((y, z, mx_all))
    update.append((x, z, mx_all))
    update.append((x, y, mx_all))
    
    for j, k, val in update:
        if dp[j][k] < val:
            dp[j][k] = dp[k][j] = val
        if mx[j] < val:
            mx[j] = val
        if mx[k] < val:
            mx[k] = val
        if mx_all < val:
            mx_all = val


if mx_all < dp[a[-1]][a[-1]] + 1:
    mx_all = dp[a[-1]][a[-1]] + 1
print(mx_all + add_all)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    a = [int(i)-1 for i in ipt().split()]
    dp = [[-10000]*n for i in range(n)]
    add = 0
    ma = 0
    manm = [-10000]*n
    manm[a[0]] = 0
    manm[a[1]] = 0

    dp[a[0]][a[1]] = 0
    for k in range(3,3*n,3):
        a0 = a[k-1]
        a1 = a[k]
        a2 = a[k+1]

        if a0 == a1 == a2:
            add += 1

        elif a0 != a1 != a2 != a0:
            pdp0 = dp[a0][a0]*1
            pdp1 = dp[a1][a1]*1
            pdp2 = dp[a2][a2]*1
            dp0 = dp[a0]
            dp1 = dp[a1]
            dp2 = dp[a2]

            
            for i in range(n):
                dp0[i] = manm[i]
                dp1[i] = manm[i]
                dp2[i] = manm[i]

            
            if ma < pdp0+1:
                dp1[a2] = pdp0+1
            else:
                dp1[a2] = ma
            
            if ma < pdp1+1:
                dp0[a2] = pdp1+1
            else:
                dp0[a2] = ma
            
            if ma < pdp2+1:
                dp0[a1] = pdp2+1
            else:
                dp0[a1] = ma

            
            manm[a0] = max(dp0)
            manm[a1] = max(dp1)
            manm[a2] = max(dp2)
            if manm[a2] < dp1[a2]:
                manm[a2] = dp1[a2]
            if manm[a2] < dp0[a2]:
                manm[a2] = dp0[a2]
            if manm[a1] < dp0[a1]:
                manm[a1] = dp0[a1]
            ma = max(manm)

        else:
            if a0 == a1:
                p = a0
                q = a2
            elif a1 == a2:
                p = a1
                q = a0
            else:
                p = a2
                q = a1
            pdpp = dp[p][p]*1
            pdpq = dp[q][q]*1
            dpp = dp[p]
            dpq = dp[q]

            do = []
            dpip = [dp[i][p] for i in range(n)]
            
            for i in range(n):

                if manm[i] >= dpp[i]+1 and manm[i] >= dpip[i]+1:
                    dpq[i] = manm[i]
                else:
                    if dpp[i] > dpip[i]:
                        dpq[i] = dpp[i]+1
                    else:
                        dpq[i] = dpip[i]+1
                do.append((q,dpq[i]))
                do.append((i,dpq[i]))
            
            for i in range(n):
                if manm[i] > dpp[i]:
                    dpp[i] = manm[i]
                    do.append((p,manm[i]))
            
            if ma > pdpq+1:
                dpp[p] = ma
            else:
                dpp[p] = pdpq+1
            do.append((p,dpp[p]))
            
            if ma > pdpp+1:
                dpp[q] = ma
            else:
                dpp[q] = pdpp+1
            do.append((p,dpp[q]))
            do.append((q,dpp[q]))

            
            for i,j in do:
                if manm[i] < j:
                    manm[i] = j
            ma = max(manm)

    dp[a[-1]][a[-1]] += 1

    ma = 0
    for i in dp:
        for j in i:
            if j > ma:
                ma = j

    print(ma+add)



    return None

if __name__ == '__main__':
    main()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    ans = [[-N] * (N+1) for _ in range(N+1)]
    a0, a1 = A[:2]
    ans[a0][a1] = 0
    ans[a1][a0] = 0
    ma = [-N] * (N+1)
    ma[a0] = 0
    ma[a1] = 0
    mama = 0
    add = 0
    for i in range(N-1):
        a, b, c = A[i*3+2:i*3+5]
        if a == b == c:
            add += 1
            continue
        Q = []
        for _ in range(3):
            a, b, c = b, c, a
            
            Q.append((a, b, max(mama, ans[c][c] + 1)))
            
            for j in range(1, N+1):
                val = ma[j]
                if b == c:
                    val = max(val, ans[b][j] + 1)
                Q.append((a, j, val))
        for i, j, val in Q:
            ans[i][j] = max(ans[i][j], val)
            ans[j][i] = max(ans[j][i], val)
            ma[i] = max(ma[i], val)
            ma[j] = max(ma[j], val)
            mama = max(mama, val)
    ANS = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            if i == j == A[-1]:
                ANS = max(ANS, ans[i][j] + 1)
            else:
                ANS = max(ANS, ans[i][j])
    print(ANS + add)


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
I=2*N
D=[[-I]*(N+1)for _ in range(N+1)]
M=0
r=[-I]*(N+1)
def c(i,j,k):
    D[i][j]=max(k,D[i][j])
    D[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
X=A[0]
Y=A[1]
D[X][Y]=0
D[Y][X]=0
r[X]=0
r[Y]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,max(M,D[Z][Z]+1)))
    C.append((Y,Z,max(M,D[X][X]+1)))
    C.append((X,Z,max(M,D[Y][Y]+1)))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in C:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
I=2*N
D=[[-I]*(N+1)for _ in range(N+1)]
M=0
r=[-I]*(N+1)
def c(i,j,k):
    D[i][j]=max(k,D[i][j])
    D[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
D[A[0]][A[1]]=0
D[A[1]][A[0]]=0
r[A[0]]=0
r[A[1]]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,D[Z][Z]+1))
    C.append((Y,Z,D[X][X]+1))
    C.append((X,Z,D[Y][Y]+1))
    C.append((X,Y,M))
    C.append((X,Z,M))
    C.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in C:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
INF = 2*N
DP = [[-INF]*(N+1) for _ in range(N+1)]
M = 0
rowM = [-INF]*(N+1)

def chmax(i,j,k):
    DP[i][j] = max(k,DP[i][j])
    DP[j][i] = max(k,DP[j][i])
    rowM[i] = max(rowM[i],DP[i][j])
    rowM[j] = max(rowM[j],DP[i][j])
    global M
    M = max(M,k)

ans = 0
DP[A[0]][A[1]] = 0
DP[A[1]][A[0]] = 0
rowM[A[0]] = 0
rowM[A[1]] = 0
for i in range(N-1):
    new = A[3*i+2:3*i+5]
    change = []
    if len(set(new)) == 1:
        ans += 1
        continue
    if len(set(new)) == 2:
        for j in range(3):
            if new.count(new[j]) == 2:
                X = new[j]
            else:
                Y = new[j]
        for j in range(1,N+1):
            change.append((j,Y,DP[X][j]+1))
    X,Y,Z = new
    change.append((X,Y,DP[Z][Z]+1))
    change.append((Y,Z,DP[X][X]+1))
    change.append((X,Z,DP[Y][Y]+1))
    change.append((X,Y,M))
    change.append((X,Z,M))
    change.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            change.append((j,new[k],rowM[j]))
    for j,k,l in change:
        chmax(j,k,l)
M = max(M,DP[A[-1]][A[-1]]+1)
print(ans+M)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
N = len(A) // 3
A = A[:3*N]

A.append(0)
A.append(0)

ans = 0
def ind(a, b):
  t = sorted((a, b))
  return t[0] * (N+1) + t[1]
def inv(i):
  b = i % (N+1)
  a = i // (N + 1)
  return a, b

dp = [-1] * (N+1)**2
dp[ind(A[0],A[1])] = 0
current_max = 0
dp1 = [-1] * (N+1)
dp1[A[0]] = 0
dp1[A[1]] = 0

ans = 0
for i in range(0, N):
  a = A[2+3*i] 
  b = A[2+3*i+1]
  c = A[2+3*i+2]
  
  if a == b == c:
    ans+=1
    continue
  dp_new = {}
  for x, y, z in [(a, b, c), (b, c, a), (c, a, b)]:
    
    i = ind(y, z)
    if i not in dp_new:
      dp_new[i] = 0
    dp_new[i] = max(dp_new[i], current_max)
    if dp[ind(x, x)] >= 0:
      dp_new[i] = max(dp_new[i], dp[ind(x, x)] + 1)
    
    
    for t in range(1, N+1):
      i = ind(t,z)
      
      if dp1[t] >= 0:
        if i not in dp_new:
          dp_new[i]=0
        dp_new[i] = max(dp_new[i], dp1[t])
      
      if x == y and dp[ind(t, x)] >= 0:
        if i not in dp_new:
          dp_new[i] = 0
        dp_new[i] = max(dp_new[i], dp[ind(t, x)] + 1)
        
  
  
  for i, s in dp_new.items():
    dp[i] = max(dp[i], s)
    ta, tb = inv(i)
    dp1[ta] = max(dp1[ta], s)
    dp1[tb] = max(dp1[tb], s)
    current_max = max(current_max, s)


print(ans + max(dp1))

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-5] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(ma, X[a2][a2] + 1), max(ma, X[a1][a1] + 1)
        X[a2] = [max(x, m) for x, m in zip(X[a2], MA)]
        MA = [max(m, x1, x2) for m, x1, x2 in zip(MA, X[a1], X[a2])]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        X[a][b], X[a][c], X[b][c] = max(ma, X[c][c] + 1), max(ma, X[b][b] + 1), max(ma, X[a][a] + 1)
        X[a] = [max(x, m) for x, m in zip(X[a], MA)]
        X[b] = [max(x, m) for x, m in zip(X[b], MA)]
        X[c] = [max(x, m) for x, m in zip(X[c], MA)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(m, xa, xb, xc) for m, xa, xb, xc in zip(MA, X[a], X[b], X[c])]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-10**10] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        X[a2] = [max(X[a2][j], MA[j]) for j in range(N+1)]
        MA = [max(m, x1, x2) for m, x1, x2 in zip(MA, X[a1], X[a2])]
        MA[a1] = max(MA[a1], max(X[a1]), X[a2][a1])
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        
        X[a][b], X[a][c], X[b][c] = max(ma, X[c][c] + 1), max(ma, X[b][b] + 1), max(ma, X[a][a] + 1)
        X[a] = [max(x, m) for x, m in zip(X[a], MA)]
        X[b] = [max(x, m) for x, m in zip(X[b], MA)]
        X[c] = [max(x, m) for x, m in zip(X[c], MA)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(m, xa, xb, xc) for m, xa, xb, xc in zip(MA, X[a], X[b], X[c])]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-10**10] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        
        
        
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        
        X[a2] = [max(X[a2][j], MA[j]) for j in range(N+1)]
        MA = [max(MA[j], X[a1][j], X[a2][j]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]), X[a2][a1])
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        X[a][b], X[a][c], X[b][c] = max(X[a][b], ma, X[c][c] + 1), max(X[a][c], ma, X[b][b] + 1), max(X[b][c], ma, X[a][a] + 1)
        X[a] = [max(X[a][j], MA[j]) for j in range(N+1)]
        X[b] = [max(X[b][j], MA[j]) for j in range(N+1)]
        X[c] = [max(X[c][j], MA[j]) for j in range(N+1)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(MA[j], X[a][j], X[b][j], X[c][j]) for j in range(N+1)]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()


n = ni()
a = na()

dp = [[-99999999] * (n+1) for _ in range(n+1)]
dp[a[0]][a[1]] = 0

dprow = [-99999999] * (n+1)
dprow[a[0]] = 0
dprow[a[1]] = 0

margin = 0
for i in range(2, 3*n-2, 3):
    if a[i] == a[i+1] and a[i+1] == a[i+2]:
        margin += 1
    else:
        q = []
        for jj in range(i, i+3):
            if dp[a[jj]][a[jj]] < 0:
                continue
            if jj == i:
                q.append((a[i+1], a[i+2], dp[a[jj]][a[jj]] + 1))
            if jj == i+1:
                q.append((a[i], a[i+2], dp[a[jj]][a[jj]] + 1))
            if jj == i+2:
                q.append((a[i], a[i+1], dp[a[jj]][a[jj]] + 1))

        for jj in range(i, i+3):
            for kk in range(jj+1, i+3):
                if a[jj] == a[kk]:
                    rem = i+i+1+i+2-jj-kk
                    for t in range(n+1):
                        if dp[a[jj]][t] >= 0:
                            q.append((t, a[rem], dp[a[jj]][t] + 1))
                        if dp[t][a[jj]] >= 0:
                            q.append((t, a[rem], dp[t][a[jj]] + 1))
        for j in range(n+1):
            if dprow[j] >= 0:
                for k in (a[i], a[i + 1], a[i + 2]):
                    q.append((j, k, dprow[j]))
        mx = max(dprow)
        for jj in range(i, i+3):
            for kk in range(jj+1, i+3):
                q.append((a[jj], a[kk], mx))
        for u in q:
            dp[u[0]][u[1]] = max(dp[u[0]][u[1]], u[2])
            dprow[u[0]] = max(dprow[u[0]], u[2])
            dprow[u[1]] = max(dprow[u[1]], u[2])
        
        
        
        
        

ans = max(*dprow, dp[a[-1]][a[-1]] + 1)

print(ans+margin)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(A):
    A = A - 1
    N = len(A) // 3
    A = np.append(A, (N, N))
    INF = 1 << 30
    dp = np.full((N + 1, N + 1), -INF, np.int64)
    a, b = A[:2]
    dp[a, b] = dp[b, a] = 0
    dp_max = np.full(N + 1, -INF, np.int64)
    dp_max[a] = dp_max[b] = 0
    add = 0
    update = np.empty((100 * N, 3), np.int64)
    for n in range(N):
        a, b, c = A[3 * n + 2:3 * n + 5]
        if a == b == c:
            add += 1
            continue
        p = 0
        
        for _ in range(3):
            a, b, c = b, c, a
            update[p], p = (a, b, dp_max.max()), p + 1
            for k in range(N):
                update[p], p = (k, a, dp_max[k]), p + 1

        for _ in range(3):
            a, b, c = b, c, a
            
            if a == b:
                for k in range(N):
                    
                    update[p], p = (c, k, dp[a, k] + 1), p + 1
            
            update[p], p = (b, c, dp[a, a] + 1), p + 1
        for i in range(p):
            a, b, x = update[i]
            dp[a, b] = dp[b, a] = max(dp[a, b], x)
            dp_max[a] = max(dp_max[a], x)
            dp_max[b] = max(dp_max[b], x)
    return dp_max.max() + add

A = np.array(read().split(), np.int64)[1:]

print(main(A))