Sharing Points
National Olympiad — National round (2021 season)
Submission name: sets.cpp
Problem summary
Partition X-sorted points into two nonempty sets A and B, minimizing the horizontal width of A plus the vertical height of B.
Input
N, followed by N points X Y in nondecreasing X order.
Output
The minimum possible width-plus-height.
Constraints
2 ≤ N ≤ 2000000; 0 ≤ X,Y ≤ 10^8.
Worked example
An independently prepared example for this explanation.
Input
11 1 28 5 24 11 14 13 43 19 29 23 6 28 25 36 51 39 32 44 29 50 21
Output
36
Solution analysis
- Once the leftmost and rightmost A points are chosen, move every point between them into A. This preserves its width and can only reduce B’s height. Thus an optimum exists with A equal to one contiguous interval [l,r], and B its nonempty complement.
- Precompute prefix and suffix Y minima and maxima. For fixed r, the complement height is max(prefixMax[l−1],suffixMax[r+1])−min(prefixMin[l−1],suffixMin[r+1]). Prefix maxima increase with l and prefix minima decrease, so two binary searches partition the possible l into at most four ranges according to which extreme comes from the prefix.
- Within each range, the objective is X[r] plus a suffix constant and one of four static expressions: −X[l], prefixMax[l−1]−X[l], −prefixMin[l−1]−X[l], or prefixMax[l−1]−prefixMin[l−1]−X[l]. A segment tree stores the minimum of all four expressions, allowing each range to be queried efficiently. Prefix-only and suffix-only A intervals are checked separately. In the sample, taking A positions 2 through 8 has width 28 and leaves B height 8, giving 36; including intermediate points is harmless.
Why it works
Expanding A to its X interval never increases the objective, establishing interval sufficiency. Prefix/suffix extrema give exactly the complementary B height. The two monotone thresholds cover every interior l and identify exactly the applicable algebraic expression, so each range-minimum query finds its best possible left endpoint. Considering every right endpoint and both one-sided cases therefore considers an optimum, while every evaluated interval is feasible.
Watch out. Both sets must remain nonempty, so never choose A as the entire array. Equal X coordinates are allowed. Use all four cases for whether the prefix or suffix supplies each Y extreme.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
// Algorithm: Once the leftmost and rightmost A points are chosen, move every point between them
// into A.
using namespace std;
using Values=array<int,4>;
const int INFIMUM=1000000000;
Values combine(const Values&a,const Values&b){
Values result;
for(int i=0;i<4;++i){
result[i]=min(a[i],b[i]);
}
return result;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>x(n),y(n),prefixMax(n),prefixMin(n),suffixMax(n),suffixMin(n);
for(int i=0;i<n;++i){
cin>>x[i]>>y[i];
prefixMax[i]=i==0?y[i]:max(prefixMax[i-1],y[i]);
prefixMin[i]=i==0?y[i]:min(prefixMin[i-1],y[i]);
}
for(int i=n-1;i>=0;--i){
suffixMax[i]=i==n-1?y[i]:max(suffixMax[i+1],y[i]);
suffixMin[i]=i==n-1?y[i]:min(suffixMin[i+1],y[i]);
}
vector<Values>tree(2*n,Values{INFIMUM,INFIMUM,INFIMUM,INFIMUM});
for(int left=1;left<n;++left){
tree[n+left]={-x[left],prefixMax[left-1]-x[left],-prefixMin[left-1]-x[left],
prefixMax[left-1]-prefixMin[left-1]-x[left]};
}
for(int node=n-1;node>0;--node){
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
auto query=[&](int left,int right,int kind){
int result=INFIMUM;
for(left+=n,right+=n+1;left<right;left/=2,right/=2){
if(left&1){
result=min(result,tree[left++][kind]);
}
if(right&1){
result=min(result,tree[--right][kind]);
}
}
return result;
};
long long answer=INFIMUM;
for(int right=0;right+1<n;++right){
answer=min(answer,1LL*x[right]-x[0]+suffixMax[right+1]-suffixMin[right+1]);
}
for(int left=1;left<n;++left){
answer=min(answer,1LL*x[n-1]-x[left]+prefixMax[left-1]-prefixMin[left-1]);
}
for(int right=1;right+1<n;++right){
int high=suffixMax[right+1],low=suffixMin[right+1];
int maxThreshold=static_cast<int>(
upper_bound(prefixMax.begin(),prefixMax.begin()+right,high)-prefixMax.begin());
int lo=0,hi=right;
while(lo<hi){
int middle=(lo+hi)/2;
if(prefixMin[middle]>=low){
lo=middle+1;
}
else{
hi=middle;
}
}
int minThreshold=lo;
auto consider=[&](int left,int last,int kind,int constant){
left=max(left,1);
last=min(last,right);
if(left<=last){
answer=min(answer,1LL*x[right]+query(left,last,kind)+constant);
}
};
consider(1,min(maxThreshold,minThreshold),0,high-low);
consider(maxThreshold+1,minThreshold,1,-low);
consider(minThreshold+1,maxThreshold,2,high);
consider(max(maxThreshold,minThreshold)+1,right,3,0);
}
cout<<answer<<'\n';
}