EVSTR - Editorial

Simple Solution

A very easy solution for this problem using binary search and bottom up dp.
First of all remove all even length contiguous segments.
Then note the index of end of previous value with same value a[i]. if it lies in an odd length segment. find number of even length segments between the 2 indices and subtract it from total elements to be deleted to find total elements to delete for making this even in regard to previous odd length segment.

If this is confusing try reading simple code.

Simple solution
#include<bits/stdc++.h>  
using namespace std; 
typedef long long int ll;
#define endl "\n"
ll arr[200001];
struct info{
    ll val,start,end;
};
vector<ll> adj[200001];
ll findd(ll val,ll l,ll r){
    ll start=0;
    ll end=adj[val].size()-1;
    ll mid;
    ll i1=-1,i2=-1;
    while(start<=end){
        mid=(start+end)/2;
        if(adj[val][mid]>=l){
            i1=mid;
            end=mid-1;
        }
        else {
           start=mid+1; 
        }
    }
    start=0;
    end=adj[val].size()-1;
    while(start<=end){
        mid=(start+end)/2;
        if(adj[val][mid]>r){
            end=mid-1;
        }
        else {
            i2=mid;
           start=mid+1; 
        }
    }
    //cout<<l<<" "<<r<<" "<<val<<" "<<i2<<" "<<i1<<endl;
    if(i2==-1||i1==-1){
        return 0;
    }
    if(adj[val][i2]<l||adj[val][i1]>r){
        return 0;
    }
    return max(0LL,i2-i1+1);
}
void solve(){
    ll n,m,i,j,k,a,b,c,d,x,y;
    cin>>n;
    for(ll i=0;i<=n;i++){
        adj[i].clear();
    }
    for(ll i=1;i<=n;i++){
        cin>>arr[i];
        adj[arr[i]].push_back(i);
    }
    i=1;
    vector<info> vp;
    vector<ll> dp(n+1);
    vp.push_back({0,0,0});
    vector<ll> mp(n+1);
    while(i<=n){
        j=i+1;
        while(j<=n&&arr[j]==arr[i]){// this is trivial 2 pointers.
            j++;
        }
        if((j-i)%2){// removing the even segments from further processing.
            vp.push_back({arr[i],i,j-1});// val start end
        }
        else {
            
        }
        i=j;//alright searching for next index.
    }
    vector<ll> v(n+1,0);
    for(i=0;i<vp.size();i++){
        if(mp[vp[i].val]!=0){
            v[i]=mp[vp[i].val];
        }
        mp[vp[i].val]=i;
    }
    for(i=1;i<vp.size();i++){
        ll ind=v[i];
        dp[i]=dp[i-1]+1;
        if(ind>0){
            // Previous odds are present;
            ll ox=findd(vp[i].val,vp[ind].end+1,vp[i].start-1);
            dp[i]=min(dp[i],dp[ind-1]+vp[i].start-vp[ind].end-1-ox);
            //cout<<vp[i].val<<" "<<ox<<" "<<dp[i]<<endl;
        }
    }
    cout<<dp[vp.size()-1]<<endl;
}
int main()  { 
    ll t=1;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>t; 
    while(t--){
       solve();
    }
    return 0;  
}

Optimised to O(N) the idea is same
#include<bits/stdc++.h>  
using namespace std; 
typedef long long int ll;
#define endl "\n"
ll arr[200001];
struct info{
    ll val,start,end;
};
vector<ll> adj[200001];
void solve(){
    ll n,m,i,j,k,a,b,c,d,x,y;
    cin>>n;
    for(ll i=0;i<=n;i++){
        adj[i].clear();
    }
    for(ll i=1;i<=n;i++){
        cin>>arr[i];
        adj[arr[i]].push_back(i);
    }
    i=1;
    vector<info> vp;
    vector<ll> dp(n+1);
    vp.push_back({0,0,0});
    vector<ll> mp(n+1);
    vector<ll> mp1(n+1,0);
    vector<ll> vv;
    vv.push_back(0);
    while(i<=n){
        j=i+1;
        while(j<=n&&arr[j]==arr[i]){// this is trivial 2 pointers.
            j++;
        }
        if((j-i)%2){// removing the even segments from further processing.
            vp.push_back({arr[i],i,j-1});// val start end
            vv.push_back(mp1[arr[i]]);
        }
        else {
            mp1[arr[i]]+=(j-i);
        }
        i=j;//alright searching for next index.
    }
    vector<ll> v(n+1,0);
    for(i=0;i<vp.size();i++){
        if(mp[vp[i].val]!=0){
            v[i]=mp[vp[i].val];
        }
        mp[vp[i].val]=i;
    }
    for(i=1;i<vp.size();i++){
        ll ind=v[i];
        dp[i]=dp[i-1]+1;
        if(ind>0){
            ll ox=vv[i]-vv[ind];
            dp[i]=min(dp[i],dp[ind-1]+vp[i].start-vp[ind].end-1-ox);
        }
    }
    cout<<dp[vp.size()-1]<<endl;
}
int main()  { 
    ll t=1;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>t; 
    while(t--){
       solve();
    }
    return 0;  
}

3 Likes

I just used a set and whenever I am getting an element that is already present in the set I am adding 2 to my answer and clearing the set. In the last I am printing (n - ans).
This is a bit easy to come with and is more intuitive.
My solution link.

8 Likes

My idea was to work only on odd length sub-arrays, so I compressed the input accordingly. Example: [1 1 1 2 2 3] → [1 3] , coz [2 2] and [1 1] is already a subsequence of equal length. And then I applied a similar DP approach as explained in the editorial. Can someone tell me why this is wrong through explanation or a test case??
Submission Link

Try [1 2 1 1 3 1]

2 Likes

it surely is.

can someone share problems based on same approach, it was pretty difficult to come up with this kind of information

Can someone explain for this case?
5 5 5 5 2 2
Here the longest even subsequence is of length 4. So as per solution we should delete both 2s. But answer should be 0 since the initial sequence is self sufficient.
Where am I going wrong?