EVSTR - Editorial

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. :slight_smile:

17 Likes

Can you explain the intuition that lead you to this dp formulation ?

5 Likes

Think of it as selecting intervals starting and ending at equal valued positions. We want to select the maximum number of intervals such that none of them should be overlapping. So it’s kind of opening and closing intervals. DP_0 denotes the longest subsequence such that all elements are paired. DP_x denote the longest subsequence such that the last element, valued x is unpaired.

Does this intuition helps?

8 Likes

Yeah this makes perfect sense now, thanks for such a well written editorial :slight_smile:

5 Likes

If I consider the given integer sequence as 2 2 2 2 1 1 2
It needs 0 operations right?

2 Likes

NO, it should take 1 operation to remove last 2

1 Like

Why is there a need to remove last 2, because the maximal contiguous subsequence of 2 is “2 2 2 2” which is already even

1 Like

A subsequence is maximal if it is not contained in a larger contiguous subsequence which contains only equal integers. So 2 2 2 2 is one maximal contiguous subsequence over same digits, and sequence of 2 present after 1 forms another such maximal contiguous subsequence over same digits.

2 Likes

Can someone please help me debug my idea?

My (O(n) ) approach is as follows:
Convert the array into such that each pairs in the original sequence are converted to '-1’s.
eg: 1 2 2 2 1 3 1 3 3 => 1 -1 -1 2 1 3 1 -1 -1
After this I iterate through this array, such that whenever I get a number that isn’t -1 (not paired yet), I have three choices:
a) check if it exists in any unpaired numbers seen till now (kept track of with a set), if yes, empty this set and pair these two numbers (that is the cost is now updated with → length of set - 1 .
b) if it doesn’t exist in any unpaired till now, check if I can pair it with next-to-next by deleting a successive number. If so, the cost is updated by 1, and the cost of all unpaired numbers till now. (i.e., cost += set.size() ).
next-to-next number is A[i+2] for every A[i].
eg: 4 5 6 1 2 1, I delete the 2, and do the cost is updated by 4 (cost += 3 + 1)
c) if the next-to-next number is not equal to the current number (A[i+2] != A[i]), then I add A[i] to the set of unpaired numbers and move on.

At the end I delete all the unpaired numbers till now, cost += set.size() .

Any suggestion would be appreciated.

My code

I am new to this forum, so I am sorry if this may not be the right place to ask this

1 Like

Maybe it was only me but the maximal definition wasn’t clear enough to explain what the problem was asking for.

A better way to explain the problem statement would perhaps be
Generate such a sequence which can be partitioned into consecutive subarrays consisting of unique repeated elements and each subarray should be of even length.

6 Likes

If someone is still stuck December Lunchtime 2020 Division 1 Even Sequence: Dynamic Programming - YouTube

Can someone help me understand the test case 2? Wouldn’t the answer be 1 coz by deleting element three all maximal subsequences have even length.
Sequence\space After\space Deletion\space of\space 3

2 2 2 10 2 10 1 1 5 5

Maximal\space Contiguous\space Subsequences

2 2 2 2 
10 10
1 1
5 5

Or\space am\space I\space missing\space something\space ?

1 Like

No, The correct answer is 3. The language of the question can be written in a better way. Instead of subsequences, if they would have written subarray will make the question a bit easy to understand.
Ya so your 1st step is correct removal of 3.
2. Remove the 2 which is on 5th position.
3. Remove the first element that is 2 which is in the starting position.
So your final array will be 2 2 10 10 1 1 5 5.

1 Like

So, you are saying that all the elements of each individual a[i] like here, 2, 1, 10, 5. They should occur as a contiguous subarrays and should have even length.
Am\space I\space right\space?

is the time limit quite tight. I am getting TLE in one test case from much time?
https://www.codechef.com/viewsolution/40853634

Can someone help me in understand the approach used in Setters’s solution.

The question was a bit confusing. I read it 5-6 times and still didn’t got the right meaning.

you are using recursion dp and in each recursion there are some binary searches, i think this is giving TLE,
Also , you are passing the vectors in each function using reference, can you try to solve by declaring them globally.

P.S. the intended solution is VERY simple, look at the author’s solution :slight_smile:

I have even removed the binary searches then also it is giving TLE. I think I have to write recursion as loop

I am doing like when I encounter a odd subsequence we have two options either we can remove a element from it or merge it with a near odd subsequence.

1 Like