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;
}