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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def calc(b, c, M):
    for j in range(1, n+1):
        dp[j][c] = max(dp[j][c], dp[j][b] + 1, dp[b][j] + 1)
        dp[c][j] = max(dp[c][j], dp[j][b] + 1, dp[b][j] + 1)
        M = max(M, dp[j][c], dp[c][j])
    return M

n = I()
a = LI()

dp = [[-inf] * (n+1) for _ in range(n+1)]
dp[a[0]][a[1]] = 0
dp[a[1]][a[0]] = 0
tmp = 0
M = 0
for i in range(1, n):
    a1, a2, a3 = a[3*i-1], a[3*i], a[3*i+1]
    new_M = M
    if a1 == a2 and a2 == a3:
        tmp += 1
        continue
    if a1 == a2:
        b = a1
        c = a3
        new_M = calc(b, c, M)
    elif a2 == a3:
        b = a2
        c = a1
        new_M = calc(b, c, M)
    elif a3 == a1:
        b = a3
        c = a2
        new_M = calc(b, c, M)
    dp[a1][a2] = max(dp[a1][a2], M)
    dp[a2][a1] = max(dp[a2][a1], M)
    dp[a2][a3] = max(dp[a2][a3], M)
    dp[a3][a2] = max(dp[a3][a2], M)
    dp[a3][a1] = max(dp[a3][a1], M)
    dp[a1][a3] = max(dp[a1][a3], M)
    M = new_M

a_last = a[-1]
ans = dp[a_last][a_last] + 1
for i in range(1, n+1):
    for j in range(1, n+1):
        ans = max(ans, dp[i][j])
ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def calc(b, c):
    for j in range(1, n+1):
        dp[j][c] = max(dp[j][c], dp[j][b] + 1, dp[b][j] + 1)
        dp[c][j] = max(dp[c][j], dp[j][b] + 1, dp[b][j] + 1)

n = I()
a = LI()
dp = [[-inf] * (n+1) for _ in range(n+1)]
dp[a[0]][a[1]] = 0
tmp = 0
for i in range(1, n):
    a1, a2, a3 = a[3*i-1], a[3*i], a[3*i+1]
    if a1 == a2 and a2 == a3:
        tmp += 1
        continue
    if a1 == a2:
        b = a1
        c = a3
        calc(b, c)
    elif a2 == a3:
        b = a2
        c = a1
        calc(b, c)
    elif a3 == a1:
        b = a3
        c = a2
        calc(b, c)
a_last = a[-1]
ans = dp[a_last][a_last] + 1
for i in range(1, n+1):
    for j in range(1, n+1):
        ans = max(ans, dp[i][j])
ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[[-1]*(N+1)for _ in range(N+1)]
M=0
r=[-1]*(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)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[[-1]*(N+1)for _ in range(N+1)]
M=0
r=[-1]*(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
    else:
        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)

Submission status: Wrong Answer

Solution code:
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,A[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)

Submission status: Wrong Answer

Solution code:
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])
    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,A[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)

Submission status: Wrong Answer

Solution code:
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])
    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][Y]+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,A[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)

Submission status: Wrong Answer

Solution code:
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)
queueM = [-INF]*(N+1)

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

ans = 0
DP[A[0]][A[1]] = 0
rowM[A[0]] = 0
queueM[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[Y][X]+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,A[k],rowM[j]))
            change.append((j,A[k],queueM[j]))
    for j,k,l in change:
        chmax(j,k,l)
M = max(M,DP[A[-1]][A[-1]]+1)
print(ans+M)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
N = len(A) // 3
A = A[:3*N]
#print(N, A)
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
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]
  #print(a,b,c)
  if a == b == c:
    ans+=1
    continue
  dp_new = {}
  for x, y, z in [(a, b, c), (b, c, a), (c, a, b)]:
    # choose 1 (x), leave y, z
    i = ind(y,z)
    if i not in dp_new:
      dp_new[i] = 0
    if dp[ind(x, x)] >= 0:
      dp_new[i] = max(dp_new[i], dp[ind(x, x)] + 1)
    
    # choose 2 (x, y), leave t, z
    for t in range(1, N+1):
      i = ind(t,z)
      # Not making three
      if dp1[t] >= 0:
        if i not in dp_new:
          dp_new[i]=0
        dp_new[i] = max(dp_new[i], dp1[t])
      # Making three (x==y)
      if x == y:
        if 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)
        
  #print({inv(i):v for i, v in dp_new.items() })
  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)

#print(doubles)
print(ans + max(dp))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
N = len(A) // 3
A = A[:3*N]
#print(N, A)
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
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]
  #print(a,b,c)
  if a == b == c:
    ans+=1
    continue
  dp_new = {}
  for x, y, z in [(a, b, c), (b, c, a), (c, a, b)]:
    # choose 1 (x), leave y, z
    i = ind(y,z)
    if i not in dp_new:
      dp_new[i] = 0
    if dp[ind(x, x)] >= 0:
      dp_new[i] = max(dp_new[i], dp[ind(x, x)] + 1)
    
    # choose 2 (x, y), leave t, z
    for t in range(1, N+1):
      i = ind(t,z)
      # Not making three
      dp_new[i] = dp1[t]
      # Making three (x==y)
      if x == y:
        if dp[ind(t, x)] >= 0:
          dp_new[i] = dp[ind(t, x)] + 1
        
  #print({inv(i):v for i, v in dp_new.items() })
  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)

#print(doubles)
print(ans + max(dp))

Submission status: Wrong Answer

Solution code:
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)))

Submission status: Wrong Answer

Solution code:
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[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(ma, X[a2][a2], X[a1][a1] + 1)
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) 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)))

Submission status: Wrong Answer

Solution code:
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[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(ma, X[a2][a2], X[a1][a1] + 1)
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) 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]) 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)))

Submission status: Wrong Answer

Solution code:
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, X[a1][j], X[j][a1]) 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]) 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, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
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, X[a1][j], X[j][a1]) 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]) 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], X[a][b], X[a][c])
        MA[b] = max(MA[b], X[a][b], X[b][c])
        MA[c] = max(MA[c], X[a][c], X[b][c])
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
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, X[a1][j], X[j][a1]) 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]) for j in range(N+1)]
        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(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], X[a][b], X[a][c])
        MA[b] = max(MA[b], X[a][b], X[b][c])
        MA[c] = max(MA[c], X[a][c], X[b][c])
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
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[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(ma, X[a2][a2], X[a1][a1] + 1)
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) 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]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[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], X[a][b], X[a][c])
        MA[b] = max(MA[b], X[a][b], X[b][c])
        MA[c] = max(MA[c], X[a][c], X[b][c])
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
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[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], 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]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[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], X[a][b], X[a][c])
        MA[b] = max(MA[b], X[a][b], X[b][c])
        MA[c] = max(MA[c], X[a][c], X[b][c])
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
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, X[a1][j], X[j][a1]) 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, X[a2][a2], max(X[a1]))
        MA = [max(MA[j], X[a1][j]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[a2], X[a2][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], X[a][b], X[a][c])
        MA[b] = max(MA[b], X[a][b], X[b][c])
        MA[c] = max(MA[c], X[a][c], X[b][c])
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
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, X[a1][j], X[j][a1]) 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, X[a2][a2], max(X[a1]))
        MA = [max(MA[j], X[a1][j]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[a2], X[a2][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], X[a][b], X[a][c])
        MA[b] = max(MA[b], X[a][b], X[b][c])
        MA[c] = max(MA[c], X[a][c], X[b][c])
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
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, X[a1][j], X[j][a1]) 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, X[a2][a2], max(X[a1]))
        MA = [max(MA[j], X[a1][j]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[a2], X[a2][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], X[a][b], X[a][c])
        MA[b] = max(MA[b], X[a][b], X[b][c])
        MA[c] = max(MA[c], X[a][c], X[b][c])
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter


def giveup(count, inheritable, thr):
    inh_thr = 3 - thr
    for i in range(n):
        if count[i] >= thr:
            count[i] = 3
        if count[i] >= 1:
            inheritable[i] -= inh_thr


n, *aaa = map(int, sys.stdin.buffer.read().split())
if n == 1:
    print(1)
    exit()

aaa = [a - 1 for a in aaa]
count = [0] * n
inheritable = [2] * n
ans = 0
for i in range(5):
    a = aaa[i]
    count[a] += 1
    if count[a] == 3:
        ans += 1

for j in range(n - 2):
    cnt = Counter(aaa[5 + j * 3:8 + j * 3])
    if len(cnt) == 1:
        count[aaa[5 + j * 3]] = 3
        ans += 1
    elif len(cnt) == 2:
        (a2, _), (a1, _) = cnt.most_common()
        if count[a2] == 1 and inheritable[a2] >= 1:
            ans += 1
            giveup(count, inheritable, 2)
        elif count[a1] == 2 and inheritable[a1] == 2:
            ans += 1
            giveup(count, inheritable, 1)
        count[a2] += 2
        count[a1] += 1
    else:
        for a in cnt:
            if count[a] == 2 and inheritable[a] == 2:
                ans += 1
                giveup(count, inheritable, 1)
        for a in cnt:
            count[a] += 1

if count[aaa[-1]] == 2 and inheritable[aaa[-1]] == 2:
    ans += 1

print(ans)