Comparable Incomes
National Olympiad — National round
Submission name: money.cpp
Problem summary
Choose the largest subset of at least three incomes such that the sum of any two distinct members is strictly larger than every other member. If no qualifying triple exists, return 1.
Input
n, followed by n incomes.
Output
Maximum subset size, or 1.
Constraints
2 < n < 200000; 2879 < each income < 1000000.
Worked example
An independently prepared example for this explanation.
Input
5 3000 4000 6000 8000 9000
Output
4
Solution analysis
- Sort the incomes. A selected set qualifies precisely when its two smallest values sum to more than its largest.
- For each left endpoint, extend a monotone right endpoint while this inequality holds. The maximal interval is the best set with these smallest two values.
Why it works
Any omitted value between the second smallest and largest can be included without invalidating the inequality. Replacing the second smallest by the next sorted value permits a contiguous optimal interval. Testing every left endpoint therefore finds an optimum.
Watch out. The inequality is strict. The fallback is 1, never 2.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>a(n);
for(int&x:a){
cin>>x;
}
sort(a.begin(),a.end());
int ans=1,r=0;
for(int l=0;l+2<n;l++){
r=max(r,l+2); // Only the two smallest and largest constrain a sorted interval.
while(r<n&&a[l]+a[l+1]>a[r]){
r++;
}
if(r-l>=3){
ans=max(ans,r-l);
}
}
cout<<ans<<'\n';
}