PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Noszály Áron
Tester: Rahul Dugar
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Dynamic Programming
PROBLEM
Given a sequence A containing N integers, Find the minimum number of operations required to make it an even sequence, where an operation is defined as deleting any element or inserting any positive integer at any position in the given sequence.
An even sequence is a sequence, in which every maximal consecutive subsegment containing the same value has an even length. That is, the run-length encoding of the given sequence contains only even values.
QUICK EXPLANATION
- Deleting elements can be proven to be better than inserting in all cases, thus insertion is ignored.
- Instead of deleting, we can try selecting the longest even sequence appearing as a subsequence. Say the length of this sequence is L, we can delete the remaining N-L characters to make an even sequence.
- Longest even subsequence can be computed using dynamic programming, maintaining the length of longest even subsequence ending with value x for each value, and the parity of length.
EXPLANATION
As mentioned in the quick explanation, let’s try proving why deletion can achieve the same or better results.
Why Deletion is better
Considering a maximal odd length subsegment containing the same character, we insert one occurrence of the same character making this subsegment good. If we insert one element for each such subsegment, we get an even sequence, although operation count is not minimized.
But we can also achieve this effect by deleting one occurrence for each maximal odd length subsegment since we care only for parity.
Now consider a case where deletion can be better. 1 2 1 If we try using insertions, we can make an even sequence using 3 operations, whereas deleting 2 make it an even sequence in one operation. It happens because it deleted one bad segment and merged two bad subsegments, saving two operations.
So, whatever we achieve with insertion, can be achieved with deletion. So ignoring insertion from now on.
From Deletion to Selection
Now, deleting some elements can be seen as selecting the remaining elements. Since we want to delete the least number of elements possible, it is optimal to select the largest number of elements possible.
Hence, we need to find the longest subsequence of the given sequence, which is an even sequence.
Here comes the last bit of observation for this approach. Considering an even sequence, let’s make pairs of 2 elements each, both should be equal. There is no other constraint imposed by even sequence.
Dynamic Programming
Now, let’s consider sequence A from left to right and assume DP_x denote the largest odd length even-sequence ending with an unpaired x after considering a prefix of A. Also, Let DP_0 denote largest even length even-sequence.
So, whenever we get an element x, either we can
- extend largest odd length even-sequence denoted by DP_x to get candidate for largest even length even-sequence denoted by DP_0
- extend largest even length even-sequence denoted by DP_0 to get candidate for largest odd length even-sequence denoted by DP_x
Formally, we need to perform simultaneous update DP_x = max(DP_x, DP_0+1) and DP_0 = max(DP_0, DP_x+1). Before considering any element, we have DP_0 = 0 and DP_x = -\infin for 1 \leq x \leq N.
The final length of the longest even-sequence is given by DP_0, and the number of operations is given by N-DP_0
The code turns out to be surprisingly short, which can be referred to below.
TIME COMPLEXITY
The time complexity is O(N) per test case.
The memory complexity is O(N) per test case.
SOLUTIONS
Setter's Solution
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#ifndef ONLINE_JUDGE
# define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
# define LOG(x) ((void)0)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);
template<typename T> T getint() {
T val=0;
char c;
bool neg=false;
while((c=gc()) && !(c>='0' && c<='9')) {
neg|=c=='-';
}
do {
val=(val*10)+c-'0';
} while((c=gc()) && (c>='0' && c<='9'));
return val*(neg?-1:1);
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)
int main() {
IO;
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;++i) cin>>a[i];
vector<pair<int,int>> grps;
grps.eb(-1, 0);
grps.eb(a[0], 0);
for(int i=0;i<n;++i) {
if(grps.back().xx==a[i]) {
grps.back().yy++;
}else {
grps.eb(a[i],1);
}
}
int m=sz(grps);
vector<int> dp(m);
vector<int> utolso(200001,1e9);
vector<int> utolso_sz(200001);
dp[0]=0;
int minusz=0;
for(int i=1;i<m;++i) {
dp[i]=dp[i-1]+(grps[i].yy%2);
dp[i]=min(dp[i], utolso[grps[i].xx]+minusz+(grps[i].yy+utolso_sz[grps[i].xx])%2);
minusz+=grps[i].yy;
if(grps[i].yy%2==1) {
utolso[grps[i].xx]=-minusz+dp[i-1];
utolso_sz[grps[i].xx]=grps[i].yy;
}else {
utolso[grps[i].xx]-=grps[i].yy;
}
}
cout<<dp.back()<<"\n";
}
return 0;
}
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
int subtask_n=200000,subtask_a=200000;
int a[200005];
int dp[200005][2];
void solve() {
int n=readIntLn(1,subtask_n);
fr(i,1,n)
if(i!=n)
a[i]=readIntSp(1,min(n,subtask_a));
else
a[i]=readIntLn(1,min(n,subtask_a));
int maxi=0;
fr(i,1,n) {
dp[i][1]=-1;
dp[i][0]=0;
}
fr(i,1,n) {
dp[a[i]][0]=max(dp[a[i]][1]+1,dp[a[i]][0]);
dp[a[i]][1]=max(dp[a[i]][1],maxi+1);
maxi=max(maxi,dp[a[i]][0]);
}
cout<<n-maxi<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(7);
int t=readIntLn(1,10);
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class EVSTR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[] A = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
int[] maxLength = new int[1+N];
Arrays.fill(maxLength, -N);
maxLength[0] = 0;
for(int x:A){
int max0 = maxLength[0], maxX = maxLength[x];
maxLength[x] = Math.max(maxX, max0+1);
maxLength[0] = Math.max(max0, maxX+1);
}
pn(N-maxLength[0]);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new EVSTR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
VIDEO EDITORIAL:
Feel free to share your approach. Suggestions are welcomed as always. 
