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:
# -*- 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
if N == 3:
  print(1)
  exit()

A = IL()+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = 0
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
      

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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
      dpmaxk[c] = max(dpmaxk[c],dp[c][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
      dpmaxk[b] = max(dpmaxk[b],dp[b][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
      dpmaxk[a] = max(dpmaxk[a],dp[a][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b],dp[a][c])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c],dp[b][a])
  dpmaxk[c] = max(dpmaxk[c],dp[c][a],dp[c][b])
  dpmaxl[a] = max(dpmaxl[a],dp[b][a],dp[c][a])
  dpmaxl[b] = max(dpmaxl[b],dp[c][b],dp[a][b])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c],dp[b][c])
  
  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[a][a],prevdpmax)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxk[j])
    dp[j][b] = max(dp[j][b],prevdpmaxk[j])
    dp[j][c] = max(dp[j][c],prevdpmaxk[j])
    dp[a][j] = max(dp[a][j],prevdpmaxl[j])
    dp[b][j] = max(dp[b][j],prevdpmaxl[j])
    dp[c][j] = max(dp[c][j],prevdpmaxl[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
if N == 3:
  print(1)
  exit()

A = IL()+[N-1,N]
INF = -N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = 0
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
      

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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
      dpmaxk[c] = max(dpmaxk[c],dp[c][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
      dpmaxk[b] = max(dpmaxk[b],dp[b][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
      dpmaxk[a] = max(dpmaxk[a],dp[a][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b],dp[a][c])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c],dp[b][a])
  dpmaxk[c] = max(dpmaxk[c],dp[c][a],dp[c][b])
  dpmaxl[a] = max(dpmaxl[a],dp[b][a],dp[c][a])
  dpmaxl[b] = max(dpmaxl[b],dp[c][b],dp[a][b])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c],dp[b][c])
  
  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[a][a],prevdpmax)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxk[j])
    dp[j][b] = max(dp[j][b],prevdpmaxk[j])
    dp[j][c] = max(dp[j][c],prevdpmaxk[j])
    dp[a][j] = max(dp[a][j],prevdpmaxl[j])
    dp[b][j] = max(dp[b][j],prevdpmaxl[j])
    dp[c][j] = max(dp[c][j],prevdpmaxl[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
if N == 3:
  print(1)
  exit()

A = IL()+[N-1,N]

dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = 0
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
      

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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
      dpmaxk[c] = max(dpmaxk[c],dp[c][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
      dpmaxk[b] = max(dpmaxk[b],dp[b][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
      dpmaxk[a] = max(dpmaxk[a],dp[a][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b],dp[a][c])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c],dp[b][a])
  dpmaxk[c] = max(dpmaxk[c],dp[c][a],dp[c][b])
  dpmaxl[a] = max(dpmaxl[a],dp[b][a],dp[c][a])
  dpmaxl[b] = max(dpmaxl[b],dp[c][b],dp[a][b])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c],dp[b][c])
  
  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[a][a],prevdpmax)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxk[j])
    dp[j][b] = max(dp[j][b],prevdpmaxk[j])
    dp[j][c] = max(dp[j][c],prevdpmaxk[j])
    dp[a][j] = max(dp[a][j],prevdpmaxl[j])
    dp[b][j] = max(dp[b][j],prevdpmaxl[j])
    dp[c][j] = max(dp[c][j],prevdpmaxl[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
if N == 3:
  print(1)
  exit()

A = IL()+[N-1,N]

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 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

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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
      dpmaxk[c] = max(dpmaxk[c],dp[c][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
      dpmaxk[b] = max(dpmaxk[b],dp[b][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
      dpmaxk[a] = max(dpmaxk[a],dp[a][k])
      dpmaxl[k] = max(dpmaxl[k],dp[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])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b],dp[a][c])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c],dp[b][a])
  dpmaxk[c] = max(dpmaxk[c],dp[c][a],dp[c][b])
  dpmaxl[a] = max(dpmaxl[a],dp[b][a],dp[c][a])
  dpmaxl[b] = max(dpmaxl[b],dp[c][b],dp[a][b])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c],dp[b][c])
  
  dp[a][b] = max(dp[a][b],prevdpmax)
  dp[b][a] = max(dp[b][a],prevdpmax)
  dp[b][c] = max(dp[b][c],prevdpmax)
  dp[c][b] = max(dp[c][b],prevdpmax)
  dp[a][c] = max(dp[a][c],prevdpmax)
  dp[c][a] = max(dp[a][a],prevdpmax)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxk[j])
    dp[j][b] = max(dp[j][b],prevdpmaxk[j])
    dp[j][c] = max(dp[j][c],prevdpmaxk[j])
    dp[a][j] = max(dp[a][j],prevdpmaxl[j])
    dp[b][j] = max(dp[b][j],prevdpmaxl[j])
    dp[c][j] = max(dp[c][j],prevdpmaxl[j])

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