Closest Value
National Olympiad — Municipal round
Submission name: closest.cpp
Problem summary
Among sums of two entries at different indices, minimize the absolute difference from a target v. Equal values at different indices may be used.
Input
n and v, followed by n integers.
Output
The minimum absolute difference |a[i]+a[j]−v| for i≠j.
Constraints
The PDF gives 0 < n < 200,000, but a pair requires n≥2. This solution assumes n≥2. Values and v are in [−1,000,000, 1,000,000].
Worked example
An independently prepared example for this explanation.
Input
4 12 2 4 7 9
Output
1
Solution analysis
- Sort the values and start with one pointer at each end.
- Record the difference for the current pair.
- If its sum is below v, move the left pointer right; if above v, move the right pointer left.
- Stop if the sum equals v or the pointers meet.
Why it works
If the current sum is below v, using the same left value with any smaller right value only makes it farther below v. Discard that left value. Symmetrically, an excessive sum allows discarding the right value. These safe eliminations retain an optimal pair.
Watch out. Indices must differ: stop at left == right. The published n=1 bound has no defined pair; no output convention is specified for it.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<climits>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long target;
cin>>n>>target;
vector<long long>a(n);
for(auto&x:a){
cin>>x;
}
if(n<2){
return 0; // The statement defines an answer only for a pair.
}
sort(a.begin(),a.end());
int left=0,right=n-1;
long long best=LLONG_MAX;
while(left<right){
long long sum=a[left]+a[right];
best=min(best,llabs(sum-target));
if(sum==target){
break;
}
if(sum<target){
++left;
}
else{
--right;
}
}
cout<<best<<'\n';
}