Longest Equal Segment after Replacements
Autumn Tournament (2024)
Submission name: replace.cpp
Problem summary
Replace at most k elements of an array by arbitrary numbers. Find the maximum length of a contiguous segment that can become entirely equal.
Input
n k, followed by n values.
Output
The maximum segment length.
Constraints
1 < n < 1000000; 0 < k < 1000; values are integers from 0 to 29.
Worked example
Original statement sample.
Input
8 2 0 1 2 1 1 0 0 1
Output
5
Solution analysis
- A window of length len can become equal using len−maxFrequency replacements, by keeping its most common value. Maintain counts for the 30 values while advancing the right endpoint.
- For a linear-time implementation keep bestFrequency, the largest frequency ever reached while the window grows. If length−bestFrequency>k, remove the leftmost value. This historical maximum may exceed the current true maximum, so a retained window is not always itself valid; nevertheless its maximum length is a valid achievable answer.
- The maintained window length never decreases: each new element adds one position and at most one position is removed. If the historical maximum is B, there was an earlier maintained window containing B equal elements. Its length is no greater than the current length L. It can be extended within the processed prefix to length L, requiring at most L−B≤k replacements. Thus a possibly stale current window still certifies an achievable length. In the sample, the first five values contain three ones; two replacements give length 5.
Why it works
The maintained length is nondecreasing and satisfies L−bestFrequency≤k. A previous window witnessing bestFrequency has length at most L; extending that witness to length L within the processed prefix proves that L is achievable. Conversely, when a genuinely valid optimal window is being scanned, its true maximum frequency is no larger than the historical maximum, so the weaker test cannot discard its left endpoint before its right endpoint is processed. Therefore the recorded maximum is exactly optimal.
Watch out. Do not claim every maintained window is valid when using the historical maximum. Recomputing the exact maximum after deletions is another correct approach, but costs an extra factor of up to 30.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,allowed;
cin>>n>>allowed;
vector<int>values(n);
array<int,30>frequency{};
int left=0;
int bestFrequency=0;
int answer=0;
for(int right=0;right<n;right++){
cin>>values[right];
frequency[values[right]]++;
bestFrequency=max(bestFrequency,frequency[values[right]]);
// Historical maximum is enough to track the best achievable length.
if(right-left+1-bestFrequency>allowed){
frequency[values[left]]--;
left++;
}
answer=max(answer,right-left+1);
}
cout<<answer<<'\n';
}