Nasser's Array Reduction (Editorial)

Solution

General Idea:

Observe that deleting a subarray of equal elements is equivalent to removing an entire block of consecutive identical values. Therefore, it is useful to compress the array into segments, where each segment stores the value and its frequency.

Since we can perform at most two deletions, our goal becomes maximizing the total number of removed elements.

There are two main possibilities.

First, delete the two largest segments independently. If the segment sizes are s_1 and s_2, we remove s_1 + s_2 elements.

Second, delete a middle segment whose neighbors have the same value. After removing the middle segment, the two neighboring cases merge into a single larger segment. If their sizes are $x$, $y$, and $z$, the total removable elements become:

We simply scan the compressed array to evaluate this merging scenario and also track the two largest segments.

Finally, if the maximum removable count is $\mathrm{cnt}$, the minimum remaining array size is:

The compression and scanning steps are linear. Sorting the segments dominates the running time and requires \mathcal{O}(n \log n) in the worst case, giving an overall complexity of \mathcal{O}(n \log n) per test case.

#include <bits/stdc++.h>
using namespace std;

#define vec vector
#define all(x) x.begin(), x.end()
#define Moageza ios::sync_with_stdio(false);cin.tie(nullptr);

void solve(){
    int n;
    cin>>n;

    vec<pair<int,int>> v;
    pair<int,int> cur={0,0};

    for(int i=0;i<n;i++){
        int x;
        cin>>x;

        if(cur.first==0) cur={1,x};
        else if(cur.second==x) cur.first++;
        else{
            v.push_back(cur);
            cur={1,x};
        }
    }
    v.push_back(cur);

    int cnt=0;

    for(int i=1;i+1<v.size();i++){
        if(v[i-1].second==v[i+1].second){
            cnt=max(cnt,
                v[i-1].first+v[i].first+v[i+1].first);
        }
    }

    sort(all(v));

    if(v.size()>=2)
        cnt=max(cnt,
            v.back().first+v[v.size()-2].first);
    else
        cnt=v.back().first;

    cout<<n-cnt;
}

int main(){
    Moageza

    int t;
    cin>>t;

    while(t--){
        solve();
        cout<<'\n';
    }
}