Almost Triple Deletions (Codeforces 1699D)
Tags: Greedy, dp

You are given an integer $$$n$$$ and an array $$$a_1,a_2,\ldots,a_n$$$.In one operation, you can choose an index $$$i$$$ ($$$1 \le i \lt n$$$) for which $$$a_i \neq a_{i+1}$$$ and delete both $$$a_i$$$ and $$$a_{i+1}$$$ from the array. After deleting $$$a_i$$$ and $$$a_{i+1}$$$, the remaining parts of the array are concatenated.For example, if $$$a=[1,4,3,3,6,2]$$$, then after performing an operation with $$$i=2$$$, the resulting array will be $$$[1,3,6,2]$$$.What is the maximum possible length of an array of equal elements obtainable from $$$a$$$ by performing several (perhaps none) of the aforementioned operations?

Input: Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The following lines contain the descriptions of the test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of array $$$a$$$.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10\,000$$$.

Output: For each testcase, print a single integer, the maximum possible length of an array of equal elements obtainable from $$$a$$$ by performing a sequence of operations.

Note: For the first testcase, an optimal sequence of operations would be: $$$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$$$.For the second testcase, all elements in the array are already equal.For the third testcase, the only possible sequence of operations is: $$$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$$$. Note that, according to the statement, the elements deleted at each step must be different.For the fourth testcase, the optimal sequence of operations is: $$$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$$$.For the fifth testcase, one possible reachable array of two equal elements is $$$[4,4]$$$.

Sample Inputs:
5
7
1 2 3 2 1 3 3
1
1
6
1 1 1 2 2 2
8
1 1 2 2 3 3 1 1
12
1 5 2 3 3 3 4 4 4 4 3 3

Sample Outputs:
3
1
0
4
2

Solution (Python):
t = int(input())
for i in range(t):
    num = int(input())
    a = [-1] + [int(i) - 1 for i in input().split()] + [-1]
    dp = [-1] * (num + 2)
    dp[0] = 0
    for i in range(0, num + 1):
        if dp[i] == -1:
            continue
        oc = [0] * num
        m = 0
        for j in range(i + 1, num + 2):
            if 2 * m <= j - i - 1 and (j - i - 1) % 2 == 0 and (a[i] == -1 or a[j] == -1 or a[i] == a[j]):
                dp[j] = max(dp[j], dp[i] + 1)
            if a[j] != -1:
                oc[a[j]] += 1
                m = max(m, oc[a[j]])
    print(dp[num + 1] - 1)

Solution (Python):
def solve():
    pass
t = int(input())
for _ in range(t):
    n = int(input())
    a = [-1] + [int(n) - 1 for n in input().split()] + [-1]
    dp = [-1] * (n + 2)
    dp[0] = 0
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        oc = [0] * n
        gap = 0
        for j in range(i + 1, n + 2):
            if 2 * gap <= j - i - 1 and (j - i - 1) % 2 == 0 and (a[i] == -1 or a[j] == -1 or a[i] == a[j]):
                dp[j] = max(dp[j], dp[i] + 1)
            if a[j] != -1:
                oc[a[j]] += 1
                gap = max(gap, oc[a[j]])
    print(dp[n + 1] - 1)

Solution (Python):
def solve():
    pass
t = int(input())
for _ in range(t):
    n = int(input())
    a = [-1] + [int(n) - 1 for n in input().split()] + [-1]
    dp = [-1] * (n + 2)
    dp[0] = 0
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        oc = [0] * n
        gap = 0
        for j in range(i + 1, n + 2):
            if 2 * gap <= j - i - 1 and (j - i - 1) % 2 == 0 and (a[i] == -1 or a[j] == -1 or a[i] == a[j]):
                dp[j] = max(dp[j], dp[i] + 1)
            if a[j] != -1:
                oc[a[j]] += 1
                gap = max(gap, oc[a[j]])
    print(dp[n + 1] - 1)