D — Almost Triple Deletions

Author: Gheal

Hints

Hint 1

Consider the opposite problem: What is the smallest possible length of a final array?

Hint 2

For which arrays is the smallest possible final length equal to

$?

Hint 3

Considering the second hint, it is possible to completely remove some subsequences from the array.

Solution

Lemma: An array

$ can be fully deleted via a sequence of operations if and only if it satisfies both of the following constraints:

$ is even

The maximum frequency of any element in the array is at most

$.

Proof

If

$ is odd, then any final array will also have an odd length, which can't be

$.

An optimal strategy is to always delete one of the most frequent elements and any one of its neighbours. If the most frequent element occurs

$ times, then the final array will have at least

$ elements. Otherwise, this strategy ensures the full deletion of the array, since, after performing an operation, it is impossible for an element to occur more than

$ times in the array.

Since the maximum frequency of a value for every subsequence

$ can be computed in

$, it is possible to precompute all subsequences which can be deleted via a sequence of operations.

Let

$ be the maximum length of a final array consisting of

$ and some subarray from the first

$ elements. Initially,

$ is set to

$ if the prefix

$ can be fully deleted. Otherwise,

$.

For every pair of indices

$ and

$ (

$), if we can fully delete the subsequence

$, then we can append

$ to any final array ending in

$. Naturally,

$ will be strictly greater than

$. This gives us the following recurrence:

$

If we define a final array as a subarray of equal elements from the array

$, to which

$ is forcefully appended, then the final answer can be written as

$. Note that, when computing

$,

$ should not be compared to

$.

Total time complexity per testcase:

$.