# SPLITMIN - Editorial

Preparer: iceknight1093
Tester: satyam_343
Editorialist: iceknight1093

2347

Sorting

# PROBLEM:

You’re given N pairs of the form (A_i, B_i).
You also have two empty piles.

From each pair, choose exactly one element and add it to one of the two piles.
Find the minimum possible difference between the maximum elements of the piles. Both piles should be non-empty.

# EXPLANATION:

Let the two piles be P_1 and P_2.
Initially, both are empty.

Let’s fix the maximum element of P_1, say to x; then try to find the optimal maximum element y of P_2.
Without loss of generality, we can assume x \geq y as well; so our task is to find an element that’s as close to x as possible but less than it.
This is easily done with the help of sorting, for example.

However, there are a couple things to be careful about:

• First, if there’s a pair such that A_i \gt x and B_i \gt x, then having x as the larger maximum is not possible.
So, we need to ensure that for every pile, at least one element is \leq x.
In particular, we need x \geq \min(A_i, B_i) for all i.
Let M be the maximum among the \min(A_i, B_i) values. Then, x \geq M should hold.
• Second, we need to ensure that x and y don’t belong to the same pair; since if that were the case, we wouldn’t be able to pick both of them and put them in different piles.

With these two points in mind, we end up with a rather simple solution.
Let S be a sorted array of length 2N, containing all the elements A_i and B_i.
For example, if the pairs are (1, 2), (2, 3), (1, 4) then S = [1, 1, 2, 2, 3, 4].
Also, for each i, remember which pair S_i comes from.
Further, compute M = \max_{i=1}^N(\min(A_i, B_i)), as we saw above.

Then, for each i from 1 to N:

• Let’s try and treat S_i as x.
For this, S_i \geq M must hold; so if S_{i} \lt M then ignore this index.
• If S_i \geq x does indeed hold, then we need to choose y to be the closest possible element to it.
This, of course, is just S_{i-1}.
However, there is one catch: if S_i and S_{i-1} belong to the same pair, then the optimal value of y is S_{i-2} instead.
• Once y is found, the difference here is (S_i-y).
The final answer is the minimum value of this difference, across all i.

After sorting S, this obviously takes \mathcal{O}(N) time; so the algorithm as a whole takes \mathcal{O}(N\log N) time.

As an aside, notice that we only cared about the two maximums, and not how the other elements were distributed.
However, once x and y are fixed, it’s not hard to see that all the other elements can be distributed properly to achieve this, because of the condition x \geq M.

• Place x in P_1.
• Place y in P_2.
• For every one of the other N-2 pairs, we know one element exists that’s \leq x. Choose one such element and place it in P_1.
This way, the maximum of pile P_1 is x, and the maximum of pile P_2 is y, as we wanted.

# TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

# CODE:

Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
ios::sync_with_stdio(false); cin.tie(0);

int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<array<int, 2>> a;
for (int i = 0; i < n; ++i) {
int x, y; cin >> x >> y;
a.push_back({x, i});
a.push_back({y, i});
}
sort(begin(a), end(a));

int ans = INT_MAX, seen = 0;
vector<int> mark(n);
for (int i = 0; i < 2*n; ++i) {
seen += 1 - mark[a[i]];
mark[a[i]] = 1;
if (seen == n) {
if (a[i] == a[i-1]) ans = min(ans, a[i] - a[i-2]);
else ans = min(ans, a[i] - a[i-1]);
}
}
cout << ans << '\n';
}
}

Tester's code (C++)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
#define ll long long

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/
const ll MOD=1e9+7;
vector<ll> a;
ll x;
for(ll i=1;i<n;i++){
a.push_back(x);
}
a.push_back(x);
return a;
}
const ll MAX=3000300;
ll sum_n=0;
void dbug(vector<ll> a){
for(auto t:a){
cout<<t<<" ";
}
cout<<endl;
}
ll binpow(ll a,ll b,ll MOD){
ll ans=1;
a%=MOD;
while(b){
if(b&1)
ans=(ans*a)%MOD;
b/=2;
a=(a*a)%MOD;
}
return ans;
}
ll inverse(ll a,ll MOD){
return binpow(a,MOD-2,MOD);
}
ll gt(ll n,ll freq,ll k){
ll pw=(binpow(2,k,MOD-1)*freq)%(MOD-1);
ll now=(binpow(n,pw+1,MOD)-binpow(n,freq,MOD)+MOD)*inverse(n-1,MOD);
now%=MOD;
return now;
}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
bool check_distinct(vector<ll> a){
sort(a.begin(),a.end());
ll n=a.size();
for(ll i=1;i<n;i++){
assert(a[i]!=a[i-1]);
}
return true;
}
ll g(ll x){
return x;
}
void solve(){
sum_n+=n;
vector<pair<ll,ll>> track;
for(ll i=1;i<=n;i++){
track.push_back({l,i});
track.push_back({r,i});
}
sort(track.begin(),track.end());
multiset<ll> check;
vector<ll> used(n+5,0);
set<ll> found;
ll ans=(ll)(1e18);
for(auto it:track){
ll val=it.first,pos=it.second;
found.insert(pos);
if(found.size()==n){
if(used[pos]){
check.erase(check.find(used[pos]));
}
ans=min(ans,val-*(--check.end()));
if(used[pos]){
check.insert(used[pos]);
}
}
used[pos]=val;
check.insert(val);
}
cout<<ans<<"\n";
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
while(test_cases--){
solve();
}
assert(sum_n<=g(2e5));
assert(getchar()==-1);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
pairs = []
m = 0
for i in range(n):
a, b = map(int, input().split())
pairs.append((a, i))
pairs.append((b, i))
m = max(m, min(a, b))
pairs.sort()
ans = 10**9
for i in range(2*n):
if pairs[i] < m: continue
if pairs[i] == pairs[i-1]:
ans = min(ans, pairs[i] - pairs[i-2])
else:
ans = min(ans, pairs[i] - pairs[i-1])
print(ans)

2 Likes

In the Editorialist’s code, why did was ans calculated only when seen==N.

Commenting again because i got my answer.
We are starting the process of comparison because after seen==N all the lower values of any pair will be surely left behind now we are left with only the values that are higher in their pair. And if here we check for the difference we will obviously get the minimum value. if at some point we are getting the minimum difference we can hid the higher values by taking the lower values from their pair which are already passed below current index.
Absolutely genius code(Editorialist’s)!!!

CodeChef editorials are better than those of all other platforms

3 Likes

I have seen the video solutions for understanding but the difficulty level was not accurate and why its tagged as an easy level problem
In my opinion it should be tagged under medium or hard level problem

Even better, we can traverse and process the sorted vector in reverse order (greatest to lowest) and break out of it as soon as we get an element that is less than M.

Python code fails for test case

1
2
2 3
2 3

I think we should do a check if index is out of range or instead we can just take absolute of difference because otherwise we might get a negative answer.

can this be solved used DP ?