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:
import sys
input = sys.stdin.readline

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

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #print(DP)
    #print(x,y,z)

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)

    
    if x==y:
        for i in range(N+1):
            if MAXDP[i]!=-1:
                DP[i][z]=max(DP[i][z],MAXDP[x]+1)
                DP[z][i]=max(DP[z][i],MAXDP[x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if MAXDP[i]!=-1:
                DP[i][x]=max(DP[i][x],MAXDP[y]+1)
                DP[x][i]=max(DP[x][i],MAXDP[y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if MAXDP[i]!=-1:
                DP[i][y]=max(DP[i][y],MAXDP[z]+1)
                DP[y][i]=max(DP[y][i],MAXDP[z]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],0)
        DP[i][y]=DP[y][i]=max(DP[i][y],0)
        DP[i][z]=DP[z][i]=max(DP[i][z],0)

        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])

    DP[x][y]=xy
    DP[y][x]=xy

    DP[y][z]=yz
    DP[z][y]=yz

    DP[z][x]=zx
    DP[x][z]=zx

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])

#print(DP)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Submission status: Wrong Answer

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

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

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #print(DP)
    #print(x,y,z)

    NMAXDP=[i for i in MAXDP]

    xy=max(DP[x][y],DP[z][z]+1)
    yz=max(DP[y][z],DP[x][x]+1)
    zx=max(DP[z][x],DP[y][y]+1)

    
    if x==y:
        for i in range(N+1):
            if MAXDP[i]!=-1:
                DP[i][z]=max(DP[i][z],MAXDP[x]+1)
                DP[z][i]=max(DP[z][i],MAXDP[x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if MAXDP[i]!=-1:
                DP[i][x]=max(DP[i][x],MAXDP[y]+1)
                DP[x][i]=max(DP[x][i],MAXDP[y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if MAXDP[i]!=-1:
                DP[i][y]=max(DP[i][y],MAXDP[z]+1)
                DP[y][i]=max(DP[y][i],MAXDP[z]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    DP[x][y]=xy
    DP[y][x]=xy

    DP[y][z]=yz
    DP[z][y]=yz

    DP[z][x]=zx
    DP[x][z]=zx

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])

#print(DP)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
liter=2
print(a)
li=[a[0],a[1]]
space=[2 for i in range(3*n)]
print(space)

while liter<3*n:
    literm=min(liter+3,3*n)
    for i in range(liter, literm):
        li.append(a[i])
    print(int(liter/3),"+:",*li)
    if 3*n-1-liter>2:
        if li[liter]==li[liter+1] and li[liter+1]==li[liter+2]:
            li.pop(liter)
            li.pop(liter)
            li.pop(liter)
            break
    
    print(int(liter/3),"-:",*li)
    liter+=3

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())

ra=A[::-1]
B={ra[0]:0}
i=1
for a in ra:
    if a in B:
        continue
    else:
        B[a]=i
        i+=1

F=set([0])
i=count=ans=0
while count<N:
    D=[]
    c=0
    now=A[i]
    for a in A[i:i+5]:
        D.append([B[a],a])
        if c<D.count([B[a],a]):
            c+=1
            now=a
    D.sort()
    j=0
    while j<len(D):
        if D[j][1] in F:
            D=[D[j]]+D[:j]+D[j+1:]
        j+=1
    if c==3:
        ans+=1
        E=[]
        for l,r in D:
            if r==now:
                continue
            else:
                E.append(r)
        A=E+A[5:]
        count+=1
    else:
        E=[]
        for l,r in D:
            E.append(r)
        A=E[3:]+A[5:]
        for e in E[:3]:
            F.add(e)
        count+=1

if len(set(A))==1:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())

ra=A[::-1]
B={ra[0]:0}
i=1
for a in ra:
    if a in B:
        continue
    else:
        B[a]=i
        i+=1

i=count=ans=0
while count<N:
    D=[]
    c=0
    now=A[i]
    for a in A[i:i+5]:
        D.append([B[a],a])
        if c<D.count([B[a],a]):
            c+=1
            now=a
    D.sort()
    if c==3:
        ans+=1
        E=[]
        for l,r in D:
            if r==now:
                continue
            else:
                E.append(r)
        A=E+A[5:]
        count+=1
    else:
        E=[]
        for l,r in D:
            E.append(r)
        A=E[3:]+A[5:]
        count+=1

if len(set(A))==1:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())

ra=A[::-1]
B={ra[0]:0}
i=1
for a in ra:
    if a in B:
        continue
    else:
        B[a]=i
        i+=1

i=count=ans=0
while count<N:
    D=[]
    c=0
    now=A[i]
    for a in A[i:i+5]:
        D.append([B[a],a])
        if c<D.count([B[a],a]):
            c+=1
            now=a
    if c==3:
        ans+=1
        E=[]
        for l,r in D:
            if r==now:
                continue
            else:
                E.append(r)
        A=E+A[5:]
        count+=1
    else:
        E=[]
        for l,r in D:
            E.append(r)
        A=E[3:]+A[5:]
        count+=1

if len(set(A))==1:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
answer = 0
n = int(input())
a = list(map(int, input().split(" ")))
for i in range(n - 1):
    a = sorted(a[:5], key=a[:5].count, reverse=True) + a[5:]
    if a[0] == a[1] == a[2]:
        answer += 1
    del a[:3]

if a[0] == a[1] == a[2]:
    answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
b = a = list(map(int,input().split(" ")))
score = score1 =0
for i in range(n - 1):
    a = sorted(a[:5] , reverse=True) + a[5:]
    b = sorted(b[:5]) + b[5:]
    if (a[0] == a[1])  and a[0] == a[2]:
        score += 1
    if (b[0] == b[1])  and b[0] == b[2]:
        score1 += 1
    del a[:3]
    del b[:3]


if a[0] == a[1] == a[2]:
    score += 1

if b[0] == b[1] == b[2]:
    score1 += 1

print(max([score,score1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
b = a = list(map(int,input().split(" ")))
score = score1 =0
for i in range(n - 1):
    a = sorted(a[:5] , reverse=True) + a[5:]
    b = sorted(b[:5]) + b[5:]
    print(b)
    if (a[0] == a[1])  and a[0] == a[2]:
        score += 1
    if (b[0] == b[1])  and b[0] == b[2]:
        score1 += 1
    del a[:3]
    del b[:3]


if a[0] == a[1] == a[2]:
    score += 1

if b[0] == b[1] == b[2]:
    score1 += 1

print(max([score,score1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split(" ")))
score = 0
for i in range(n - 1):
    a = sorted(a[:5] , reverse=True) + a[5:]
    if (a[0] == a[1])  and a[0] == a[2]:
        score += 1
    del a[:3]

if a[0] == a[1] == a[2]:
    score += 1

print(score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

dp=[[-INF]*N for _ in range(N)]
dp[max(A[0],A[1])][min(A[0],A[1])]=0
A=A[2:]

ans=0
MAX=0
MAX_one=[0]*N
for i in range(N-1):
    tmp=A[i*3:i*3+3]
    tmp.sort()
    if tmp[0]==tmp[1]==tmp[2]:
        ans+=1
    else:
        if tmp[0]==tmp[1] or tmp[1]==tmp[2]:
            if tmp[0]==tmp[1]:
                rem=tmp[2]
            else:
                rem=tmp[0]
            for j in range(N):
                dp[max(j,rem)][min(j,rem)]=max(dp[max(j,rem)][min(j,rem)],dp[max(tmp[1],j)][min(tmp[1],j)]+1)
                MAX=MAX_one[j]=MAX_one[rem]=max(MAX,dp[max(j,rem)][min(j,rem)])
        else:
            for k in range(3):
                dp[max(tmp[(k+1)%3],tmp[(k+2)%3])][min(tmp[(k+1)%3],tmp[(k+2)%3])]=max(dp[max(tmp[(k+1)%3],tmp[(k+2)%3])][min(tmp[(k+1)%3],tmp[(k+2)%3])],dp[tmp[k]][tmp[k]]+1)
                MAX=MAX_one[tmp[(k+1)%3]]=MAX_one[tmp[(k+2)%3]]=max(MAX,dp[max(tmp[(k+1)%3],tmp[(k+2)%3])][min(tmp[(k+1)%3],tmp[(k+2)%3])])
                
        for k in range(3):
            dp[max(tmp[k],tmp[(k+1)%3])][min(tmp[k],tmp[(k+1)%3])]=MAX_one[tmp[k]]=MAX_one[tmp[(k+1)%3]]=MAX
            for j in range(N):
                dp[max(j,tmp[k])][min(j,tmp[k])]=max(dp[max(j,tmp[k])][min(j,tmp[k])],MAX_one[j],MAX_one[tmp[k]])
                MAX_one[j]=MAX_one[tmp[k]]=max(MAX_one[tmp[k]],MAX_one[j])
ans+=max(MAX,dp[A[-1]][A[-1]]+1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

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

for i in range(2, 3 * N - 1, 3):
    x, y, z = A[i], A[i + 1], A[i + 2]
    if x == y == z:  # x, y, z 3文字すべて等しい
        base += 1
    else:
        q = deque()
        for _ in range(3):
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            v = max(dp[z][z] + 1, dp[N][N])
            q.append((x, y, v))
            x, y, z = z, x, y
        while q:
            a, b, v = q.popleft()
            dp[a][b] = max(dp[a][b], v)
            dp[b][a] = max(dp[b][a], v)
            dp[N][a] = max(dp[N][a], v)
            dp[N][b] = max(dp[N][b], v)
            dp[a][N] = max(dp[a][N], v)
            dp[b][N] = max(dp[b][N], v)
            dp[N][N] = max(dp[N][N], v)

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)

Submission status: Wrong Answer

Solution code:
from collections import deque


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

INF = float('inf')
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
dp[A[0]][A[1]] = 0
dp[A[1]][A[0]] = 0
base = 0

for i in range(N - 1):
    x, y, z = A[i * 3 + 2: i * 3 + 5]
    if x == y == z:  # x, y, z 3文字すべて等しい
        base += 1
    else:
        q = deque()
        for _ in range(3):
            v = max(dp[x][y], max(dp[z][z] + 1, dp[N][N]))
            q.append((x, y, v))
            for k in range(N):
                v = max(dp[k][x], dp[k][N])
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            x, y, z = z, x, y
        while q:
            a, b, v = q.popleft()
            dp[a][b] = max(dp[a][b], v)
            dp[b][a] = max(dp[b][a], v)
            dp[N][a] = max(dp[N][a], v)
            dp[N][b] = max(dp[N][b], v)
            dp[a][N] = max(dp[a][N], v)
            dp[b][N] = max(dp[b][N], v)
            dp[N][N] = max(dp[N][N], v)

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
point = 0
for i in range(n-1):
	
	map = {}
	for j in range(5):
		if a[j] in map:
			map[a[j]] += 1
		else:
			map[a[j]] = 1

	for x in map:
		if map[x] >= 3:
			for l, j in enumerate(a[:5]):
				if j == x:
					a.insert(0, a.pop(l))
			break
		elif map[x] == 2:
			
			l = 0
			w = 5
			while l < w:
				if a[l] == x:
					a.insert(4, a.pop(l))
					w -= 1
				else:
					l += 1

	if a[0] == a[1] == a[2]:
		point +=1
	a = a[3:]

if a[0] == a[1] == a[2]:
	point +=1

print(point)

Submission status: Wrong Answer

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,dp[c][c]+1)

        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a

    for a,b,v in q:
        dp[a][b] = dp[b][a] = max(dp[a][b],dp[b][a],v)
        low[a] = low[b] = max(low[a],low[b],v)      
    m = m1
    
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 = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,dp[c][c]+1)

        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a

    for a,b,v in q:
        dp[a][b] = dp[b][a] = max(dp[b][a],v)
        low[a] = low[b] = max(low[b],v)      
    m = m1
    
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 = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0

low[a] = 0

base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,dp[c][c]+1)

        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a

    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1

print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Wrong Answer

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

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Wrong Answer

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

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
    for j in range(3):
        q.append((a,b,dp[c][c]+1))
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Wrong Answer

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

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

    triplets = 0
    chunks = []

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

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

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

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

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

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

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


if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

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

    triplets = 0
    chunks = []

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

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

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

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

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

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

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


if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

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

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

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

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

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

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

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



if __name__ == "__main__":
    run()

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]
    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
        v1 = -1000
        for i in range(1,n+1):
            x = max(dp[a][i],dp[i][a])+1
            if dp[i][c] < x:
                q.append((3,i,c,x))
                q.append((0,i,x))
            v1 = max(x,v1)
        q.append((1,c,v1))
        q.append((2,0,v1))
    
    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,b,v))
        q.append((2,0,v))
        a,b,c = b,c,a
    for j in range(3):
        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]
        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 = [[-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]
    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
        v1 = -2
        for i in range(1,n+1):
            x = max(low[a],col[a])+1
            if dp[i][c] < x:
                q.append((3,i,c,x))
                q.append((0,i,x))
            v1 = max(x,v1)
        q.append((1,c,v1))
        q.append((2,0,v1))
    
    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,b,v))
        q.append((2,0,v))
        a,b,c = b,c,a
    for j in range(3):
        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]
        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,b,v))
            q.append((2,0,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]

            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,b,v))
            q.append((2,0,v))
            a,b,c = b,c,a
        for j in range(3):
            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]

            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)