CRCFLAV-Editorial

editorial
, , , ,
1

PROBLEM LINK:

CRCFLAV

Author: aniket_111
Tester: sahoomirnalin
Editorialist: aniket_111

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Contiguous array, two pointers

PROBLEM:

A Pastry chef made N pieces of pastries, numbered them 1 through N and arranged them in this order in a row. There are K possible types of flavours (numbered 1 through K); for each valid i, the i-th piece of pastry has a flavour Ai.

The Chef wants to select a contiguous subsegment of the pieces of pastry such that there is at least one flavour which does not occur in that subsegment. Find the maximum possible length of such a subsegment of cakes.

EXPLANATION

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.

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).

TIME COMPLEXITY

Time complexity is O(n) per test case

SOLUTIONS:

#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();
}