Remove from Both Ends
Autumn Tournament (2025)
Submission name: removal.cpp
Problem summary
Remove elements one at a time from either end of a nonnegative array. Find the minimum number of removals whose removed sum is exactly k, or report impossibility.
Input
n k, followed by n values.
Output
The minimum number of removals, or −1.
Constraints
1 ≤ n ≤ 1000000; 1 ≤ k ≤ 100000; 0 ≤ values < 300; memory limit 8 MB.
Worked example
Original statement sample.
Input
5 3 1 1 1 2 2
Output
2
Solution analysis
- After removing a prefix and a suffix, the retained elements form one contiguous interval. If the full sum is total, its sum must be total−k. Minimizing removals is therefore maximizing the length of an interval with that sum.
- All values are nonnegative, so maintain a sliding window. Add the right endpoint; while its sum exceeds the target, move the left endpoint right. Whenever the sum equals the target, update the longest retained length. An empty retained interval is allowed when target=0.
- In [1,1,1,2,2] with k=3, total=7 and target=4. A length-three interval [1,1,2] sums to 4, so removing the other two elements is optimal.
Why it works
Every legal removal sequence corresponds to a retained interval, and every retained interval can be obtained by such removals. Nonnegativity makes advancing the left endpoint safe whenever the sum is too large. Keeping the earliest remaining left endpoint also retains all available leading zeros and maximizes length.
Watch out. Negative values would invalidate this two-pointer method. Handle total<k and target=0. Do not discard zeros from a matching window unnecessarily.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every legal removal sequence corresponds to a retained interval, and every retained
// interval can be obtained by such removals. Nonnegativity makes advancing the left endpoint safe
// whenever the sum is too large.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long removedSum;
cin>>n>>removedSum;
vector<unsigned short>values(n);
long long total=0;
for(unsigned short&value:values){
cin>>value;
total+=value;
}
long long target=total-removedSum;
if(target<0){
cout<<-1<<'\n';
return 0;
}
int longest=target==0?0:-1;
int left=0;
long long windowSum=0;
for(int right=0;right<n;right++){
windowSum+=values[right];
while(left<=right&&windowSum>target){
windowSum-=values[left];
left++;
}
if(windowSum==target){
longest=max(longest,right-left+1);
}
}
cout<<(longest==-1?-1:n-longest)<<'\n';
}