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:

"""

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

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

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

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

"""

import sys
from sys import stdin

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

nmax = 0 #現在のdp配列中の最大値
maxin = [float("-inf")] * N #あるカードが入っている場合の最大値
three = 0 #3枚が同じ場合

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

for i in range(N-1):

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

    #全てが同じ場合、処理をパスする
    if cards[0] == cards[1] and cards[1] == cards[2]:
        three += 1
        continue

    change = [] #更新個所を覚えて置き、最後に一気に更新する (c1,c2,値)

    #2枚が同じ場合を処理する
    if cards[0] == cards[1]:
        nc = cards[0]
        for i in range(N):
            c1 = cards[2]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))
    if cards[1] == cards[2]:
        nc = cards[1]
        for i in range(N):
            c1 = cards[0]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))

    #1枚が同じ場合を処理する
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[0]][cards[0]]+1))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[1]][cards[1]]+1))
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,dp[cards[2]][cards[2]]+1))

    #新しいカードでそろえる場合
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,nmax))
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,nmax))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,nmax))

    #新しいカード+1の場合
    for c1 in cards:
        for c2 in range(N):
            tmpmax = maxin[c2]
            if c1 > c2:
                c1,c2 = c2,c1
            change.append((c1,c2,tmpmax))

    #dp配列の更新作業
    #nmaxとmaxinも更新する

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

    #print ("dp:",dp,file=sys.stderr)

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

Submission status: Wrong Answer

Solution code:

"""

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

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

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

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

"""

import sys
from sys import stdin

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

nmax = 0 #現在のdp配列中の最大値
maxin = [float("-inf")] * N #あるカードが入っている場合の最大値
three = 0 #3枚が同じ場合

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

for i in range(N-1):

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

    #全てが同じ場合、処理をパスする
    if cards[0] == cards[1] and cards[1] == cards[2]:
        three += 1
        continue

    change = [] #更新個所を覚えて置き、最後に一気に更新する (c1,c2,値)

    #2枚が同じ場合を処理する
    if cards[0] == cards[1]:
        nc = cards[0]
        for i in range(N):
            c1 = cards[2]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))
    if cards[1] == cards[2]:
        nc = cards[1]
        for i in range(N):
            c1 = cards[0]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))

    #1枚が同じ場合を処理する
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[0]][cards[0]]+1))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[1]][cards[1]]+1))
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,dp[cards[2]][cards[2]]+1))

    #新しいカードでそろえる場合
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,nmax))
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,nmax))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,nmax))

    #新しいカード+1の場合
    for c1 in cards:
        for c2 in range(N):
            tmpmax = maxin[c2]
            if c1 > c2:
                c1,c2 = c2,c1
            change.append((c1,c2,tmpmax))

    #dp配列の更新作業
    #nmaxとmaxinも更新する

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

    #print ("dp:",dp,file=sys.stderr)

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

Submission status: Wrong Answer

Solution code:

"""

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

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

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

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

"""

import sys
from sys import stdin

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

nmax = 0 #現在のdp配列中の最大値
maxin = [0] * N #あるカードが入っている場合の最大値
three = 0 #3枚が同じ場合

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

for i in range(N-1):

    cards = A[2+3*i:5+3*i]
    cards.sort()
    #print ("cards:",cards,file=sys.stderr)

    #全てが同じ場合、処理をパスする
    if cards[0] == cards[1] and cards[1] == cards[2]:
        three += 1
        continue

    change = [] #更新個所を覚えて置き、最後に一気に更新する (c1,c2,値)

    #2枚が同じ場合を処理する
    if cards[0] == cards[1]:
        nc = cards[0]
        for i in range(N):
            c1 = cards[2]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))
    if cards[1] == cards[2]:
        nc = cards[1]
        for i in range(N):
            c1 = cards[0]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))

    #1枚が同じ場合を処理する
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[0]][cards[0]]+1))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[1]][cards[1]]+1))
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,dp[cards[2]][cards[2]]+1))

    #新しいカードでそろえる場合
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,nmax))
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,nmax))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,nmax))

    #新しいカード+1の場合
    for c1 in cards:
        for c2 in range(N):
            tmpmax = maxin[c2]
            if c1 > c2:
                c1,c2 = c2,c1
            change.append((c1,c2,tmpmax))

    #dp配列の更新作業
    #nmaxとmaxinも更新する

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

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

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

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

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

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

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

            for i in range(n):
                dp0[i] = manm[i]
                dp1[i] = manm[i]
                dp2[i] = manm[i]
            if ma < pdp0+1:
                dp1[a2] = pdp0+1
            else:
                dp1[a2] = ma
            if ma < pdp1+1:
                dp0[a2] = pdp1+1
            else:
                dp0[a2] = ma
            if ma < pdp2+1:
                dp0[a1] = pdp2+1
            else:
                dp0[a1] = ma

            if manm[a1] < dp1[a2]:
                manm[a1] = dp1[a2]
            if manm[a2] < dp1[a2]:
                manm[a2] = dp1[a2]
            if manm[a0] < dp0[a2]:
                manm[a0] = dp0[a2]
            if manm[a2] < dp0[a2]:
                manm[a2] = dp0[a2]
            if manm[a1] < dp0[a1]:
                manm[a1] = dp0[a1]
            if manm[a0] < dp0[a1]:
                manm[a0] = dp0[a1]

            ma = max(manm)

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

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

                if manm[i] > dpp[i]+1 and manm[i] > dpip+1:
                    dpq[i] = manm[i]
                    if manm[q] < manm[i]:
                        do.append((q,manm[i]))
                else:
                    if dpp[i]+1 > dpip+1:
                        dpq[i] = dpq[i]+1
                    else:
                        dpq[i] = dpip+1
                    if manm[q] < dpq[i]:
                        do.append((q,dpq[i]))
                    do.append((i,dpq[i]))

                if manm[i] < pdpq+1:
                    dpp[i] = pdpq+1
                    manm[i] = pdpq+1
                    if manm[p] < pdpq+1:
                        do.append((p,pdpq+1))
                else:
                    dpp[i] = manm[i]
                    if manm[p] < manm[i]:
                        do.append((p,manm[i]))

            if ma > pdpp+1:
                dpp[q] = ma
            else:
                dpp[q] = pdpp+1

            if ma > pdpq+1:
                dpp[p] = ma
            else:
                dpp[p] = pdpq+1

            if manm[p] < dpp[p]:
                manm[p] = dpp[p]
            if manm[p] < dpp[q]:
                manm[p] = dpp[q]
            if manm[q] < dpp[q]:
                manm[q] = dpp[q]
            for i,j in do:
                if manm[i] < j:
                    manm[i] = j

            ma = max(manm)

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

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

    print(ma+add)



    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np


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

    a0, a1 = aaa[:2]
    if a0 > a1:
        a0, a1 = a1, a0
    dp[a0][a1] = 0

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

        if a0 == a1:
            if dp[a2][a2] != -1:
                dp[a0][a1] = max(dp[a0][a1], dp[a2][a2] + 1)

            for b in range(a0):
                if dp[b][a0] == -1:
                    continue
                c, d = min(a2, b), max(a2, b)
                dp[c][d] = max(dp[c][d], dp[b][a0] + 1)

            for b in range(a0 + 1, n):
                if dp[a0][b] == -1:
                    continue
                c, d = min(a2, b), max(a2, b)
                dp[c][d] = max(dp[c][d], dp[a0][b] + 1)

        elif a1 == a2:
            if dp[a0][a0] != -1:
                dp[a1][a2] = max(dp[a1][a2], dp[a0][a0] + 1)
               
            for b in range(a1):
                if dp[b][a1] == -1:
                    continue
                c, d = min(a0, b), max(a0, b)
                dp[c][d] = max(dp[c][d], dp[b][a1] + 1)

            for b in range(a1 + 1, n):
                if dp[a1][b] == -1:
                    continue
                c, d = min(a0, b), max(a0, b)
                dp[c][d] = max(dp[c][d], dp[a1][b] + 1)


        else:
            if dp[a0][a0] != -1:
                dp[a1][a2] = max(dp[a1][a2], dp[a0][a0] + 1)
            if dp[a2][a2] != -1:
                dp[a0][a2] = max(dp[a0][a2], dp[a1][a1] + 1)
            if dp[a2][a2] != -1:
                dp[a0][a1] = max(dp[a0][a1], dp[a2][a2] + 1)

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

    return dp.max() + ans


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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np


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

    a0, a1 = aaa[:2]
    if a0 > a1:
        a0, a1 = a1, a0
    dp[a0][a1] = 0

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

        if a0 == a1:
            for b in range(a0):
                if dp[b][a0] == -1:
                    continue
                c, d = min(a2, b), max(a2, b)
                dp[c][d] = max(dp[c][d], dp[b][a0] + 1)

            for b in range(a0 + 1, n):
                if dp[a0][b] == -1:
                    continue
                c, d = min(a2, b), max(a2, b)
                dp[c][d] = max(dp[c][d], dp[a0][b] + 1)

            if dp[a2][a2] != -1:
                dp[a0][a1] = max(dp[a0][a1], dp[a2][a2] + 1)

        elif a1 == a2:
            for b in range(a1):
                if dp[b][a1] == -1:
                    continue
                c, d = min(a0, b), max(a0, b)
                dp[c][d] = max(dp[c][d], dp[b][a1] + 1)

            for b in range(a1 + 1, n):
                if dp[a1][b] == -1:
                    continue
                c, d = min(a0, b), max(a0, b)
                dp[c][d] = max(dp[c][d], dp[a1][b] + 1)

            if dp[a0][a0] != -1:
                dp[a1][a2] = max(dp[a1][a2], dp[a0][a0] + 1)

        else:
            if dp[a0][a0] != -1:
                dp[a1][a2] = max(dp[a1][a2], dp[a0][a0] + 1)
            if dp[a2][a2] != -1:
                dp[a0][a2] = max(dp[a0][a2], dp[a1][a1] + 1)
            if dp[a2][a2] != -1:
                dp[a0][a1] = max(dp[a0][a1], dp[a2][a2] + 1)

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

    return dp.max() + ans


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

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

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

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

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

Submission status: Wrong Answer

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

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

M = 10000
from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[A[0]*M + A[1]] = 0
for i in range(N-1):
    a,b,c = A[i*3+2:i*3+5]
    if a==b==c:
        for k in dp.keys():
            dp[k] += 1
        continue
    dp2 = defaultdict(lambda: 0)
    if a==b:
        for k in list(dp.keys()):
            x,y = divmod(k,M)
            if a==x:
                dp2[c*M + y] = max(dp2[c*M + y], dp[k] + 1)
            elif a==y:
                dp2[c*M + x] = max(dp2[c*M + x], dp[k] + 1)
            elif x==y==c:
                dp2[a*M + b] = max(dp2[a*M + b], dp[k] + 1)
            dp2[a*M + x] = max(dp2[a*M + x], dp[a*M + x])
            dp2[a*M + y] = max(dp2[a*M + y], dp[a*M + y])
            dp2[c*M + x] = max(dp2[c*M + x], dp[c*M + x])
            dp2[c*M + y] = max(dp2[c*M + y], dp[c*M + y])
            dp2[x*M + y] = max(dp2[x*M + y], dp[x*M + y])
        dp2[a*M + b] = max(dp2[a*M + b], dp[a*M + b])
        dp2[a*M + c] = max(dp2[a*M + c], dp[a*M + c])
    elif b==c:
        for k in list(dp.keys()):
            x,y = divmod(k,M)
            if b==x:
                dp2[a*M + y] = max(dp2[a*M + y], dp[k] + 1)
            elif b==y:
                dp2[a*M + x] = max(dp2[a*M + x], dp[k] + 1)
            elif x==y==a:
                dp2[b*M + c] = max(dp2[b*M + c], dp[k] + 1)
            dp2[b*M + x] = max(dp2[b*M + x], dp[b*M + x])
            dp2[b*M + y] = max(dp2[b*M + y], dp[b*M + y])
            dp2[a*M + x] = max(dp2[a*M + x], dp[a*M + x])
            dp2[a*M + y] = max(dp2[a*M + y], dp[a*M + y])
            dp2[x*M + y] = max(dp2[x*M + y], dp[x*M + y])
        dp2[b*M + c] = max(dp2[b*M + c], dp[b*M + c])
        dp2[b*M + a] = max(dp2[b*M + a], dp[b*M + a])
    elif c==a:
        for k in list(dp.keys()):
            x,y = divmod(k,M)
            if c==x:
                dp2[b*M + y] = max(dp2[b*M + y], dp[k] + 1)
            elif c==y:
                dp2[b*M + x] = max(dp2[b*M + x], dp[k] + 1)
            elif x==y==b:
                dp2[c*M + a] = max(dp2[c*M + a], dp[k] + 1)
            dp2[c*M + x] = max(dp2[c*M + x], dp[c*M + x])
            dp2[c*M + y] = max(dp2[c*M + y], dp[c*M + y])
            dp2[b*M + x] = max(dp2[b*M + x], dp[b*M + x])
            dp2[b*M + y] = max(dp2[b*M + y], dp[b*M + y])
            dp2[x*M + y] = max(dp2[x*M + y], dp[x*M + y])
        dp2[c*M + a] = max(dp2[c*M + a], dp[c*M + a])
        dp2[c*M + b] = max(dp2[c*M + b], dp[c*M + b])
    else:
        for k in list(dp.keys()):
            x,y = divmod(k,M)
            if x==y==a:
                dp2[b*M + c] = max(dp2[b*M + c], dp[k] + 1)
            elif x==y==b:
                dp2[c*M + a] = max(dp2[c*M + a], dp[k] + 1)
            elif x==y==c:
                dp2[a*M + b] = max(dp2[a*M + b], dp[k] + 1)
            dp2[a*M + x] = max(dp2[a*M + x], dp[a*M + x])
            dp2[a*M + y] = max(dp2[a*M + y], dp[a*M + y])
            dp2[b*M + x] = max(dp2[b*M + x], dp[b*M + x])
            dp2[b*M + y] = max(dp2[b*M + y], dp[b*M + y])
            dp2[c*M + x] = max(dp2[c*M + x], dp[c*M + x])
            dp2[c*M + y] = max(dp2[c*M + y], dp[c*M + y])
            dp2[x*M + y] = max(dp2[x*M + y], dp[x*M + y])
        dp2[a*M + b] = max(dp2[a*M + b], dp[a*M + b])
        dp2[b*M + c] = max(dp2[b*M + c], dp[b*M + c])
        dp2[c*M + a] = max(dp2[c*M + a], dp[c*M + a])
    dp = dp2

ans = max(dp.values())
if A[-1]*M + A[-1] in dp:
    ans = max(ans, dp[(A[-1]*M + A[-1])] + 1)
print(ans)

Submission status: Wrong Answer

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

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

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[(A[0], A[1])] = 0
for i in range(N-1):
    a,b,c = A[i*3+2:i*3+5]
    if a==b==c:
        for k in dp.keys():
            dp[k] += 1
        continue
    dp2 = defaultdict(lambda: 0)
    if a==b:
        for x,y in list(dp.keys()):
            if a==x:
                dp2[(c,y)] = max(dp2[(c,y)], dp[(x,y)] + 1)
            elif a==y:
                dp2[(c,x)] = max(dp2[(c,x)], dp[(x,y)] + 1)
            elif x==y==c:
                dp2[(a,b)] = max(dp2[(a,b)], dp[(x,y)] + 1)
            dp2[(a,x)] = max(dp2[(a,x)], dp[(a,x)])
            dp2[(a,y)] = max(dp2[(a,y)], dp[(a,y)])
            dp2[(c,x)] = max(dp2[(c,x)], dp[(c,x)])
            dp2[(c,y)] = max(dp2[(c,y)], dp[(c,y)])
            dp2[(x,y)] = max(dp2[(x,y)], dp[(x,y)])
        dp2[(a,b)] = max(dp2[(a,b)], dp[(a,b)])
        dp2[(a,c)] = max(dp2[(a,c)], dp[(a,c)])
    elif b==c:
        for x,y in list(dp.keys()):
            if b==x:
                dp2[(a,y)] = max(dp2[(a,y)], dp[(x,y)] + 1)
            elif b==y:
                dp2[(a,x)] = max(dp2[(a,x)], dp[(x,y)] + 1)
            elif x==y==a:
                dp2[(b,c)] = max(dp2[(b,c)], dp[(x,y)] + 1)
            dp2[(b,x)] = max(dp2[(b,x)], dp[(b,x)])
            dp2[(b,y)] = max(dp2[(b,y)], dp[(b,y)])
            dp2[(a,x)] = max(dp2[(a,x)], dp[(a,x)])
            dp2[(a,y)] = max(dp2[(a,y)], dp[(a,y)])
            dp2[(x,y)] = max(dp2[(x,y)], dp[(x,y)])
        dp2[(b,c)] = max(dp2[(b,c)], dp[(b,c)])
        dp2[(b,a)] = max(dp2[(b,a)], dp[(b,a)])
    elif c==a:
        for x,y in list(dp.keys()):
            if c==x:
                dp2[(b,y)] = max(dp2[(b,y)], dp[(x,y)] + 1)
            elif c==y:
                dp2[(b,x)] = max(dp2[(b,x)], dp[(x,y)] + 1)
            elif x==y==b:
                dp2[(c,a)] = max(dp2[(c,a)], dp[(x,y)] + 1)
            dp2[(c,x)] = max(dp2[(c,x)], dp[(c,x)])
            dp2[(c,y)] = max(dp2[(c,y)], dp[(c,y)])
            dp2[(b,x)] = max(dp2[(b,x)], dp[(b,x)])
            dp2[(b,y)] = max(dp2[(b,y)], dp[(b,y)])
            dp2[(x,y)] = max(dp2[(x,y)], dp[(x,y)])
        dp2[(c,a)] = max(dp2[(c,a)], dp[(c,a)])
        dp2[(c,b)] = max(dp2[(c,b)], dp[(c,b)])
    else:
        for x,y in list(dp.keys()):
            if x==y==a:
                dp2[(b,c)] = max(dp2[(b,c)], dp[(x,y)] + 1)
            elif x==y==b:
                dp2[(c,a)] = max(dp2[(c,a)], dp[(x,y)] + 1)
            elif x==y==c:
                dp2[(a,b)] = max(dp2[(a,b)], dp[(x,y)] + 1)
            dp2[(a,x)] = max(dp2[(a,x)], dp[(a,x)])
            dp2[(a,y)] = max(dp2[(a,y)], dp[(a,y)])
            dp2[(b,x)] = max(dp2[(b,x)], dp[(b,x)])
            dp2[(b,y)] = max(dp2[(b,y)], dp[(b,y)])
            dp2[(c,x)] = max(dp2[(c,x)], dp[(c,x)])
            dp2[(c,y)] = max(dp2[(c,y)], dp[(c,y)])
            dp2[(x,y)] = max(dp2[(x,y)], dp[(x,y)])
        dp2[(a,b)] = max(dp2[(a,b)], dp[(a,b)])
        dp2[(b,c)] = max(dp2[(b,c)], dp[(b,c)])
        dp2[(c,a)] = max(dp2[(c,a)], dp[(c,a)])
    dp = dp2

ans = max(dp.values())
ans = max(ans, dp[(A[-1], A[-1])] + 1)
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, 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(dp[j][c], dp[c][j], m)
    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]
    nm = m
    if a1 == a2 and a2 == a3:
        tmp += 1
        continue
    if a1 == a2:
        b = a1
        c = a3
        nm = calc(b, c, m)
    elif a2 == a3:
        b = a2
        c = a1
        nm = calc(b, c, m)
    elif a3 == a1:
        b = a3
        c = a2
        nm = calc(b, c, m)
    if a1 == a2 or a1 == a3 or a2 != a3:
        dp[a2][a3] = max(dp[a2][a3], dp[a1][a1] + 1)
    nm = max(nm, dp[a1][a1] + 1)
    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[a1][a3] = max(dp[a1][a3], m)
    dp[a3][a1] = max(dp[a3][a1], m)
    for j in range(n):
        dp[j][a1] = max(dp[j][a1], m)
        dp[a1][j] = max(dp[a1][j], m)
        dp[j][a2] = max(dp[j][a2], m)
        dp[a2][j] = max(dp[a2][j], m)
        dp[j][a3] = max(dp[j][a3], m)
        dp[a3][j] = max(dp[a3][j], m)
    m = nm

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, m):
    for j in range(1, n+1):
        dp[j][c] = max(dp[j][c], dp[j][b] + 1, dp[b][j] + 1)
        m = max(dp[j][c], m)
    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]
    nm = m
    if a1 == a2 and a2 == a3:
        tmp += 1
        continue
    if a1 == a2:
        b = a1
        c = a3
        nm = calc(b, c, m)
    elif a2 == a3:
        b = a2
        c = a1
        nm = calc(b, c, m)
    elif a3 == a1:
        b = a3
        c = a2
        nm = calc(b, c, m)
    if a1 == a2 or a1 == a3 or a2 != a3:
        dp[a2][a3] = max(dp[a2][a3], dp[a1][a1] + 1)
    nm = max(nm, dp[a1][a1] + 1)
    dp[a1][a2] = max(dp[a1][a2], m)
    dp[a2][a3] = max(dp[a2][a3], m)
    dp[a1][a3] = max(dp[a1][a3], m)
    for j in range(n):
        dp[j][a1] = max(dp[j][a1], m)
        dp[j][a2] = max(dp[j][a2], m)
        dp[j][a3] = max(dp[j][a3], m)
    m = nm

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()))
INF = 2*N
DP = [[-INF]*(N+1) for _ in range(N+1)]
M = 0
rowM = [-INF]*(N+1)

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

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