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



Sample input:
2
1 2 1 2 2 1


Sample output:
2

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))

dp = [[-1000]*(n+1) for i in range(n+1)]
low = [-1000]*(n+1)
col = [-1000]*(n+1)
m = 0
dp[A[0]][A[1]] = 0
low[A[0]] = 0
col[A[1]] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    if a==b==c:
        base += 1
        continue
    q = []
    if a==b or b==c or c==a:
        if b==c:
            a,b,c = b,c,a
        elif c==a:
            a,b,c = a,c,b
        v = max(m,dp[c][c]+1)
        q.append((3,a,a,v))
        q.append((0,a,v))
        q.append((1,a,v))
        v1 = -2
        for i in range(1,n+1):
            dp[i][c] = max(dp[i][c],low[i],dp[i][a]+1)
            v1 = max(v1,dp[i][c])
            if dp[i][c] > low[i]:
                q.append((0,i,dp[i][c]))
        q.append((1,c,v1))
        v2 = -2
        for i in range(1,n+1):
            dp[c][i] = max(dp[c][i],col[i],dp[a][i]+1)
            v2 = max(v2,dp[c][i])
            if dp[c][i] > col[i]:
                q.append((1,i,dp[c][i]))
        q.append((0,c,v2))
        q.append((2,0,max(v,v1,v2)))
    
    else:
        for j in range(3):
            v = max(m,dp[c][c]+1)
            q.append((3,a,b,v))
            q.append((0,a,v))
            q.append((1,a,v))
            v1 = -2
            va = dp[a][a]+1
            vb = dp[b][b]+1
            for i in range(1,n+1):
                if i == b:
                    x = max(va,low[i],dp[i][c])
                    if x > low[i]:
                        q.append((0,i,x))
                elif i == a:
                    x = max(vb,low[i],dp[i][c])
                    if x > low[i]:
                        q.append((0,i,x))
                else:
                    x = max(va,vb,low[i],dp[i][c])
                    if x > low[i]:
                        q.append((0,i,x))
                v1 = max(v1,x)
                q.append((3,i,c,x))
            q.append((1,c,v1))
            v2 = -2
            for i in range(1,n+1):
                if i == b:
                    x = max(va,col[i],dp[c][i])
                    if x > col[i]:
                        q.append((0,i,x))
                elif i == a:
                    x = max(vb,col[i],dp[c][i])
                    if x > col[i]:
                        q.append((0,i,x))
                else:
                    x = max(va,vb,col[i],dp[c][i])
                    if x > col[i]:
                        q.append((0,i,dp[c][i]))
                v2 = max(v2,x)
                q.append((3,c,i,x))
            q.append((0,c,v2))
            q.append((2,0,max(v,v1,v2)))

            a,b,c = b,c,a
    for l in q:
        if l[0] == 0:
            low[l[1]] = max(low[l[1]],l[2])
        elif l[0] == 1:
            col[l[1]] = max(col[l[1]],l[2])
        elif l[0] == 2:
            m = max(m,l[2])
        else:
            dp[l[1]][l[2]] = max(dp[l[1]][l[2]],l[3])
        
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))

dp = [[-2]*(n+1) for i in range(n+1)]
low = [-2]*(n+1)
col = [-2]*(n+1)
m = 0
dp[A[0]][A[1]] = 0
low[A[0]] = 0
col[A[1]] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    if a==b or b==c or c==a:
        if b==c:
            a,b,c = b,c,a
        elif c==a:
            a,b,c = a,c,b
        v = max(m,dp[c][c]+1)
        q.append((3,a,a,v))
        q.append((0,a,v))
        q.append((1,a,v))
        v1 = -2
        for i in range(1,n+1):
            if max(low[i],dp[i][a]+1)>= 0:
                dp[i][c] = max(dp[i][c],low[i],dp[i][a]+1)
                v1 = max(v1,dp[i][c])
                if dp[i][c] > low[i]:
                    q.append((0,i,dp[i][c]))
        q.append((1,c,v1))
        v2 = -2
        for i in range(1,n+1):
            if max(col[i],dp[a][i]+1)>= 0:
                dp[c][i] = max(dp[c][i],col[i],dp[a][i]+1)
                v2 = max(v2,dp[c][i])
                if dp[c][i] > col[i]:
                    q.append((1,i,dp[c][i]))
        q.append((0,c,v2))
        q.append((2,0,max(v,v1,v2)))
    
    else:
        for j in range(3):
            v = max(m,dp[c][c]+1)
            q.append((3,a,b,v))
            q.append((0,a,v))
            q.append((1,a,v))
            
            for i in range(1,n+1):
                if low[i]>= 0:
                    dp[i][c] = low[i]
        
            for i in range(1,n+1):
                if col[i]>= 0:
                    dp[c][i] = col[i]
   
            q.append((2,0,v))

            a,b,c = b,c,a
    for l in q:
        if l[0] == 0:
            low[l[1]] = max(low[l[1]],l[2])
        elif l[0] == 1:
            col[l[1]] = max(col[l[1]],l[2])
        elif l[0] == 2:
            m = max(m,l[2])
        else:
            dp[l[1]][l[2]] = max(dp[l[1]][l[2]],l[3])
        
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Wrong Answer

Solution code:
from typing import List


class DP:
    N: int
    table: List[List[int]]
    max_all: int
    max_arr: List[int]
    inc: int

    def __init__(self, N: int, x: int, y: int):
        self.N = N
        self.table = [[-(1 << 28)] * (N + 1) for _ in range(N + 1)]
        self.table[x][y] = self.table[y][x] = 0
        self.max_all = 0
        self.max_arr = [-(1 << 28)] * (N + 1)
        self.max_arr[x] = self.max_arr[y] = 0
        self.inc = 0

    def update(self, p: int, q: int, r: int) -> None:
        if p == q == r:
            self.inc += 1
            return

        npqr = self._update_pqr(p, q, r)
        nqrp = self._update_pqr(q, r, p)
        nrpq = self._update_pqr(r, p, q)

        npq = self._update_pq(p, q)
        nqr = self._update_pq(q, r)
        nrp = self._update_pq(r, p)

        np = self._update_p(p)
        nq = self._update_p(q)
        nr = self._update_p(r)

        pq, qr, rp = None, None, None

        if p == q:
            pq = self._update_pair(p, r)

        if q == r:
            qr = self._update_pair(q, p)

        if r == p:
            rp = self._update_pair(r, q)

        self._update_maximum(q, r, npqr)
        self._update_maximum(r, p, nqrp)
        self._update_maximum(p, q, nrpq)

        self._update_maximum(p, q, npq)
        self._update_maximum(q, r, nqr)
        self._update_maximum(r, p, nrp)

        for k in range(self.N + 1):
            self._update_maximum(k, p, np[k])
            self._update_maximum(k, q, nq[k])
            self._update_maximum(k, r, nr[k])

        if pq:
            for k in range(self.N + 1):
                self._update_maximum(k, r, pq[k])

        if qr:
            for k in range(self.N + 1):
                self._update_maximum(k, p, qr[k])

        if rp:
            for k in range(self.N + 1):
                self._update_maximum(k, q, rp[k])


    def _update_maximum(self, x: int, y: int, v: int) -> None:
        self.table[x][y] = self.table[y][x] = v
        self.max_all = max(self.max_all, v)
        self.max_arr[x] = max(self.max_arr[x], v)
        self.max_arr[y] = max(self.max_arr[y], v)

    def _update_pair(self, p: int, q: int) -> List[int]:
        return [max(self.table[k][q], self.table[k][p] + 1, self.table[p][k] + 1) for k in range(self.N + 1)]

    def _update_pqr(self, p: int, q: int, r: int) -> int:
        return max(self.table[q][r], self.table[p][p] + 1)

    def _update_pq(self, p: int, q: int) -> int:
        return max(self.table[p][q], self.max_all)

    def _update_p(self, p) -> List[int]:
        return [max(self.table[p][k], self.table[k][p], self.max_arr[k]) for k in range(self.N + 1)]

    def ans(self):
        return self.max_all + self.inc


N = int(input())
A = list(map(int, input().split())) + [0, 0]

dp = DP(N, A[0], A[1])

for i in range(N):
    Z = A[3 * i + 2: 3 * i + 5]
    dp.update(Z[0], Z[1], Z[2])

print(dp.ans())

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
from typing import List, Tuple

N = int(input())
A = list(map(int, input().split())) + [0, 0]

# 解説に沿って解いてみる
# 完全には理解していないので、理解したことまでをコードにし、試行錯誤的に答えに近づいてみる

# DP[i][x][y]: = i 回目の操作の後、一番左の数字が x で、二番目に左の数字が y であるときの、i 回目までの操作で得た総得点の最大値とします。


def score_and_next_cards(x: int, y: int, Z: List[int]) -> Tuple[int, List[int]]:
    if Z[0] == Z[1] == Z[2]:
        return 1, [x, y]
    elif x == y and Z.count(x) >= 1:
        U = list(filter(lambda u: u != x, Z))
        if len(U) == 2:
            return 1, U
        elif len(U) == 1:
            return 1, [U[0], x]
        else:
            return 1, [x, x]

    elif Z.count(x) >= 2:
        U = list(filter(lambda u: u != x, Z))
        if len(U) > 0:
            return 1, [U[0], y]
        else:
            return 1, [x, y]

    elif Z.count(y) >= 2:
        U = list(filter(lambda u: u != y, Z))
        if len(U) > 0:
            return 1, [U[0], x]
        else:
            return 1, [x, y]

    else:
        return 0, [x, y] + Z


dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][A[0]][A[1]] = 0

for i in range(N):
    Z = A[3 * i + 2: 3 * i + 5]
    for x in range(N + 1):
        for y in range(x, N + 1):
            if dp[i][x][y] < 0:
                continue

            # print("in", x, y)

            score, next_cards = score_and_next_cards(x, y, Z)

            # print(score, next_cards)

            l = len(next_cards)
            for v in range(l):
                for w in range(v + 1, l):
                    dp[i + 1][next_cards[v]][next_cards[w]] = max(dp[i + 1][next_cards[v]][next_cards[w]], dp[i][x][y] + score)
                    # print("memo", i, v, w)

    # print(dp[i], dp[i + 1])


ans = 0
for x in range(N + 1):
    for y in range(N + 1):
        ans = max(ans, dp[N][x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input().strip())+2
A = list(map(int,input().split()))+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
  dpmaxj[d] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
  dpmaxj[a] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1
  dpmaxj[a] = 1
  dpmaxj[b] = 1
  dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      dp[i][j] = 0
      dp[j][i] = 0
      dpmaxj[i] = 0
      dpmaxj[j] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
      update(k,c)
      update(c,k)
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
      update(k,b)
      update(b,k)
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
      update(k,a)
      update(a,k)
  dp[b][c] = max(dp[b][c],dpd[a] + 1)
  dp[c][b] = max(dp[c][b],dpd[a] + 1)
  dp[a][c] = max(dp[a][c],dpd[b] + 1)
  dp[c][a] = max(dp[c][a],dpd[b] + 1)
  dp[a][b] = max(dp[a][b],dpd[c] + 1)
  dp[b][a] = max(dp[b][a],dpd[c] + 1)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax)
  dp[b][a] = max(0,dp[b][a],prevdpmax)
  dp[b][c] = max(0,dp[b][c],prevdpmax)
  dp[c][b] = max(0,dp[c][b],prevdpmax)
  dp[a][c] = max(0,dp[a][c],prevdpmax)
  dp[c][a] = max(0,dp[c][a],prevdpmax)
  update(a,b)
  update(a,c)
  update(b,a)
  update(b,c)
  update(c,a)
  update(c,b)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j])
    dp[j][b] = max(dp[j][b],prevdpmaxj[j])
    dp[j][c] = max(dp[j][c],prevdpmaxj[j])
    dp[a][j] = max(dp[a][j],prevdpmaxj[j])
    dp[b][j] = max(dp[b][j],prevdpmaxj[j])
    dp[c][j] = max(dp[c][j],prevdpmaxj[j])
    update(j,a)
    update(j,b)
    update(j,c)
    update(a,j)
    update(b,j)
    update(c,j)

print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()+2
A = IL()+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
  dpmaxj[d] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
  dpmaxj[a] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1
  dpmaxj[a] = 1
  dpmaxj[b] = 1
  dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      dp[i][j] = 0
      dp[j][i] = 0
      dpmaxj[i] = 0
      dpmaxj[j] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
      update(k,c)
      update(c,k)
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
      update(k,b)
      update(b,k)
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
      update(k,a)
      update(a,k)
  dp[b][c] = max(dp[b][c],dpd[a] + 1)
  dp[c][b] = max(dp[c][b],dpd[a] + 1)
  dp[a][c] = max(dp[a][c],dpd[b] + 1)
  dp[c][a] = max(dp[c][a],dpd[b] + 1)
  dp[a][b] = max(dp[a][b],dpd[c] + 1)
  dp[b][a] = max(dp[b][a],dpd[c] + 1)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax)
  dp[b][a] = max(0,dp[b][a],prevdpmax)
  dp[b][c] = max(0,dp[b][c],prevdpmax)
  dp[c][b] = max(0,dp[c][b],prevdpmax)
  dp[a][c] = max(0,dp[a][c],prevdpmax)
  dp[c][a] = max(0,dp[c][a],prevdpmax)
  update(a,b)
  update(a,c)
  update(b,a)
  update(b,c)
  update(c,a)
  update(c,b)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j])
    dp[j][b] = max(dp[j][b],prevdpmaxj[j])
    dp[j][c] = max(dp[j][c],prevdpmaxj[j])
    dp[a][j] = max(dp[a][j],prevdpmaxj[j])
    dp[b][j] = max(dp[b][j],prevdpmaxj[j])
    dp[c][j] = max(dp[c][j],prevdpmaxj[j])
    update(j,a)
    update(j,b)
    update(j,c)
    update(a,j)
    update(b,j)
    update(c,j)
z = A[-1]-1
print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()+2
A = IL()+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxk = [-INF for i in range(N)]
dpmaxl = [-INF for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
  dpmaxk[d] = 1
  dpmaxk[e] = 1
  dpmaxl[d] = 1
  dpmaxl[e] = 1
  dpmax = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
  dpmaxk[a] = 1
  dpmaxk[e] = 1
  dpmaxl[a] = 1
  dpmaxl[e] = 1
  dpmax = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1
  dpmaxk[a] = 1
  dpmaxk[b] = 1
  dpmaxl[a] = 1
  dpmaxl[b] = 1
  dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      dp[i][j] = 0
      dp[j][i] = 0
      dpmaxk[i] = 0
      dpmaxk[j] = 0
      dpmaxl[i] = 0
      dpmaxl[j] = 0
  dpmax = 0 

def update(i,j):
  dpmaxk[i] = max(dpmaxk[i],dp[i][j])
  dpmaxl[j] = max(dpmaxk[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxk = dpmaxk[:]
  prevdpmaxl = dpmaxl[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
      update(k,c)
      update(c,k)
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
      update(k,b)
      update(b,k)
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
      update(k,a)
      update(a,k)
  dp[b][c] = max(dp[b][c],dpd[a] + 1)
  dp[c][b] = max(dp[c][b],dpd[a] + 1)
  dp[a][c] = max(dp[a][c],dpd[b] + 1)
  dp[c][a] = max(dp[c][a],dpd[b] + 1)
  dp[a][b] = max(dp[a][b],dpd[c] + 1)
  dp[b][a] = max(dp[b][a],dpd[c] + 1)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax)
  dp[b][a] = max(0,dp[b][a],prevdpmax)
  dp[b][c] = max(0,dp[b][c],prevdpmax)
  dp[c][b] = max(0,dp[c][b],prevdpmax)
  dp[a][c] = max(0,dp[a][c],prevdpmax)
  dp[c][a] = max(0,dp[c][a],prevdpmax)
  update(a,b)
  update(a,c)
  update(b,a)
  update(b,c)
  update(c,a)
  update(c,b)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxk[j],prevdpmaxl[j])
    dp[j][b] = max(dp[j][b],prevdpmaxk[j],prevdpmaxl[j])
    dp[j][c] = max(dp[j][c],prevdpmaxk[j],prevdpmaxl[j])
    dp[a][j] = max(dp[a][j],prevdpmaxk[j],prevdpmaxl[j])
    dp[b][j] = max(dp[b][j],prevdpmaxk[j],prevdpmaxl[j])
    dp[c][j] = max(dp[c][j],prevdpmaxk[j],prevdpmaxl[j])
    update(j,a)
    update(j,b)
    update(j,c)
    update(a,j)
    update(b,j)
    update(c,j)
z = A[-1]-1
print(max(dp[N-2][N-1],dp[N-1][N-2])+score+1)