NOTALLFL - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

DIFFICULTY:

Simple

PREREQUISITES:

Ad-hoc, Two-pointers

PROBLEM:

Given an array with values from 1 to K, find the maximum length of a subarray which does not contain all K values.

QUICK EXPLANATION 1

Iterate over the right index of the subarray. If we maintain the last index each value occurred while iterating, we can calculate the answer for each right index efficiently.

QUICK EXPLANATION 2

We can use two-pointers, where for each l, we maintain the maximum r of a subarray which satisfies the constraints, along with the frequencies of each value in the subarray and the number of values in the subarray.

EXPLANATION 1:

Let’s simplify the problem slightly: We want to find the maximum length of a subarray, with the additional constraint that the subarray has to end at index r.

What is the condition that a subarray [l, r] contains the element x? Let last_x be the index of the rightmost occurrence of x less than or equal to r. [l, r] will contain x if and only if l \le last_x.

So, in order to make sure [l, r] contains less than K values, we just needs to make sure that l > last_y for some y (then element y won’t be in the subarray). This condition can be rewritten as l > \min(last_i).

This means that we can set l to \min(last_i)+1. The maximum length of a subarray ending at r is then r-(\min(last_i)+1)+1=r-\min(last_i).

Now, in order to find the answer for the entire array, we just need to iterate through all r and find the maximum answer from all r. In order to make the algorithm efficient, we need to do the following two things efficiently:

  1. Updating last as we iterate over r.
  2. Finding \min(last_i).

Updating last is easy: at the start of each iteration, we set last_{A_r} to r, and the other values of last don’t change.

In order to find \min(last_i), we should store all last_i in a data structure which supports adding/removing elements and finding the minimum element (like set in C++).

This works in O(n \log n) or O(n) depending on implementation.

EXPLANATION 2:

Notice that if subarray [l, r] satisfies does not have all K values, then subarray [l+1, r] also does not have all K values. Thus, if we iterate over l from left to right, r will only increase. This is a sign that we can use two-pointers.

A general template for two-pointers looks like:

for(int l=0, r=0; l<n; ++l) {
	while(we can add element r)
		add element r;
	ans=max(ans, r-l);
	remove element l;
}

Our trouble lies in checking if we can add element r. We can do it naively in O(n) time (by checking the values in [l, r] directly), but we want something which will work in constant time.

In order to do that, we should maintain some information about our current subarray [l, r-1]. Specifically, we should maintain:

  1. c_i, which is the count of value i in the subarray.
  2. c2, which is the number of distinct values which appear in the subarray.

We can maintain c_i pretty easily when we add/remove an element, as shown below:

for(int l=0, r=0; l<n; ++l) {
	while(we can add element r) {
		//add element r
		++c[r];
	}
	ans=max(ans, r-l);
	//remove element l
	--c[l];
}

For c2, there are different cases for adding or removing an element.

When we add an element, we check if that element has appeared before in the subarray, and if it hasn’t, we increment c2.

When we remove an element, we check if that element will disappear in the subarray, and if it will, we decrement c2.

The updated code is shown below:

for(int l=0, r=0; l<n; ++l) {
	while(we can add element r) {
		//add element r
		if(c[r]==0)
			++c2;
		++c[r];
	}
	ans=max(ans, r-l);
	//remove element l
	--c[l];
	if(c[l]==0)
		--c2;
}

Finally, let’s see how we can check if we are able to add element r. As long as c2 < k after adding, element r can be added. The exact condition is included below:

for(int l=0, r=0; l<n; ++l) {
	while(r+1<n&&(c[r]>0||c2<k-1)) {
		//add element r
		if(c[r]==0)
			++c2;
		++c[r];
	}
	ans=max(ans, r-l);
	//remove element l
	--c[l];
	if(c[l]==0)
		--c2;
}

This solution works in O(n).

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
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){
			assert(cnt>0);
			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 T;
int n,k;
int arr[100100];
int sm_n=0;
int col[100100];
int main(){
	//freopen("01.txt","r",stdin);
	//freopen("01o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		n=readIntSp(1,100000);
		k=readIntLn(2,100000);
		sm_n+= n;
		assert(sm_n<=1000000);
		for(int i=0;i<n;i++){
			if(i==n-1){
				arr[i]=readIntLn(1,k);
			} else{
				arr[i]=readIntSp(1,k);
			}
		}
		for(int i=1;i<=k;i++){
			col[i] = -1;
		}
		int mx=1;
		for(int i=0;i<n;i++){
			mx = max(mx,i-col[arr[i]] - 1);
			col[arr[i]]=i;
		}
		for(int i=1;i<=k;i++){
			mx=max(mx,n-col[i]-1);
		}
		cout<<mx<<endl;
	}
	assert(getchar()==-1);
}
Tester's Solution
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
int a[123456];
int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
    	int n,k;
    	int i;
    	cin>>n>>k;
    	rep(i,n){
    		cin>>a[i];
    	}
    	i=0;
    	int j=0,maxi=0;
    	int cnt=0;
    	map<int,int> mapi;
    	while(j<n){
    		if(mapi[a[j]]==0 && cnt==k-1){
    			mapi[a[i]]--;
    			if(mapi[a[i]]==0)
    				cnt--;
    			i++;
    			continue;
    		}
    		mapi[a[j]]++;
    		
    		if(mapi[a[j]]==1)
    			cnt++;
    		j++;
    		maxi=max(j-i,maxi);
 
    	}
    	cout<<maxi<<endl;	
    }
    return 0;   
}
Editorialist's Solution 1
#include <bits/stdc++.h>
using namespace std;

int n, k, a[100000];

void solve() {
	//input
	cin >> n >> k;
	map<int, int> last;
	for(int i=0; i<n; ++i) {
		cin >> a[i];
		//at first all elements have not appeared
		last[a[i]]=-1;
	}

	//check if all k values appear
	if(last.size()<k) {
		cout << n << "\n";
		return;
	}

	//store all last occurrences in set
	set<array<int, 2>> s;
	for(auto p : last)
		s.insert({p.second, p.first});

	//fix right end of subarray
	int ans=0;
	for(int i=0; i<n; ++i) {
		//update last occurrence for a[i]
		s.erase({last[a[i]], a[i]});
		last[a[i]]=i;
		s.insert({last[a[i]], a[i]});
		//max subarray
		ans=max(i-(*s.begin())[0], ans);
	}

	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--)
		solve();
}
Editorialst's Solution 2
#include <bits/stdc++.h>
using namespace std;

int n, k, a[100000], c[100000];

void solve() {
	//input
	cin >> n >> k;
	for(int i=0; i<n; ++i)
		cin >> a[i], --a[i];

	//make sure k is not too large
	if(k>n) {
		cout << n << "\n";
		return;
	}

	int ans=0;
	//count of values in subarray
	int c2=0;
	for(int l=0, r=0; l<n; ++l) {
		//check if we can extend r
		//make sure that c2 < k after extending
		while(r<n&&(c[a[r]]||c2<k-1)) {
			if(!c[a[r]])
				++c2;
			++c[a[r]];
			++r;
		}
		//update ans
		ans=max(r-l, ans);
		//element l is removed
		--c[a[l]];
		if(!c[a[l]])
			--c2;
	}

	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--)
		solve();
}

HIDDEN TRAPS:

  • It is not guaranteed that sum of K over all test cases is small, so your code could TLE (depending on implementation) if it works in O(N+K) per test case.

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

8 Likes

I used an array to maintain the frequency and whenever the count is reaching k, I m incrementing the left pointer. Here is the code:
#include
#include <bits/stdc++.h>
using namespace std;
#define lld long long int

int main() {
	int t,n,k,m,x,ans=0,d,y,l,b,i,j,z,count;
	cin>>t;
	while(t--){
		cin>>n>>k;
		int arr[n];
		int carr[n]={0};
		count=0;
		l=-1;
		for(i=0;i<n;i++){
			cin>>arr[i];
		}
		for(i=0;i<n;i++){
			x=arr[i];
			if(carr[x]==0){
				count+=1;
			}
			carr[x]+=1;
			while(count>=k){
				l+=1;
				y=arr[l];
				carr[y]-=1;
				//cout<<y<<" "<<carr[y]<<endl;
				if(carr[y]==0){
					count-=1;
				}
				
			}
			ans=max(ans,i-l);
		}
		cout<<ans<<endl;
	}

	return 0;
}

What’s wrong with this solution?

1 Like

You need to make sure k<=n in the beginning, because if k>n, your carr will not be big enough.

1 Like

I have a submission with carr[k+1] as well. It gives wrong answer.

Send the new code please

2 Likes

Can u pls help me why this doesnt work?
https://www.codechef.com/viewsolution/29987013
i used set to count unique elements

can you tell me what’s wrong in this one???
https://www.codechef.com/viewsolution/29987692

Please tell me the test case for which it fails.
https://www.codechef.com/viewsolution/29978532

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lld long long int

int main() {
	int t,n,k,m,x,ans=0,d,y,l,b,i,j,z,count;
	cin>>t;
	while(t--){
		cin>>n>>k;
		int arr[n];
		int carr[k+1]={0};
		count=0;
		l=-1;
		for(i=0;i<n;i++){
			cin>>arr[i];
		}
		for(i=0;i<n;i++){
			x=arr[i];
			if(carr[x]==0){
				count+=1;
			}
			carr[x]+=1;
			while(count>=k){
				l+=1;
				y=arr[l];
				carr[y]-=1;
				//cout<<y<<" "<<carr[y]<<endl;
				if(carr[y]==0){
					count-=1;
				}
				
			}
			ans=max(ans,i-l);
		}
		cout<<ans<<endl;
	}

	return 0;
}

@tmwilliamlin, can you please see once?

@spd_25 you are initializing the ans outside the testcase loop.
initialize the ans=0 inside the while(t–) and your code is correct.

Can someone explain the intuition behind applying the two pointers approach here I don’t actually get it

The first paragraph of explanation 2 explains it, right?

@tmwilliamlin I wanted to ask why there is a condition c[a[R]] in the while loop in your solution (the solution having the two pointers approach) is the condition R<n and c[a[r]] || c2<k has been added wouldn’t be enough to just add R<n and c2<k. correct me if i am wrong?

I have c2<k-1 not c2<k

what’s wrong with this
please see this
https://www.codechef.com/viewsolution/30029505

Here’s what I wrote earlier.

https://www.codechef.com/viewsolution/30039099

#include <bits/stdc++.h>
using namespace std;
int a[100001],b[100001];
int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,k,i,j,flag=0;
cin>>n>>k;
int a[n+1],b[k+1],len=0,mini=0;
bool visited[k+1]={0};
memset(b,-1,4*sizeof(b));
a[0]=0;
for(i=1;i<=n;i++){
cin>>a[i];
visited[a[i]]=1;
}
for(i=1;i<=k;i++){
if(visited[i]==0){
flag=1;
break;}
}
if(flag==1)
cout<<n<<endl;
else{
for(i=1;i<=n;i++){
if(b[a[i]]==-1){
b[a[i]]=i;
len=i-1;}
else{
len=max(len,i-b[a[i]]);
b[a[i]]=i;
}
}
mini=b[1];
for(i=2;i<=k;i++){
mini=min(b[i],mini);
}
// cout<<mini<<" ";
len=max(len,n-mini);
cout<<len<<endl;}
}
return 0;
}

Your code fails in test case like this
1
7 3
1 2 2 3 2 2 1

@tmwilliamlin Can you please help me i used a approach where if all the flavors are not in the array directly give the length of the array as the answer else find the gap between the least frequent flavor and the maximum gap becomes the answer…but i am getting wrong answer for my code…can you please tell me the test case where my approach fails…here is the link for my code…https://www.codechef.com/viewsolution/30760683