PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Ritesh Gupta
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Partition by multiple range endpoints
PROBLEM:
You’re given N ranges [l_1,r_1],[l_2,r_2],\dots,[l_N,r_N]. You have to divide the ranges into two non-empty subsets in such a way that each range is in exactly one subset and whenever two ranges have a common point, they are in the same subset.
You can delete any number of ranges (possibly zero) and then divide the remaining ranges into such non-empty subsets. You have to determine the minimum number of ranges you need to delete to achieve it.
QUICK EXPLANATION:
Split the whole axis into disjoint set of ranges and clear the one having minimum number of covering ranges.
EXPLANATION:
Basically, you need to delete some ranges in such a way that the remaining set of ranges can be split in two fully unconnected sets. To do this we may split the whole [1,10^9] into disjoint union of ranges by the endpoints of ranges given in the input.
Then each range of this disjoint union is covered by some finite number of ranges which may be calculated by utilizing counter of open ranges over scan-line. Now if some point separates two set of ranges, it shouldn’t be covered by any range and thus shouldn’t be covered the whole (disjoint) range containing it and vice versa if some range is completely freed of covering ranges then any point inside it may separate input ranges in disjoint sets.
Only thing we should keep track of is that both subsets are non-empty, which means that the left endpoint of cleared range is not smaller than \min(r_1, \dots, r_N) (there’s at least one range to the left of it) and the right endpoint is not greater than \max(l_1, \dots, l_N) (there’s at least one range to the right of it). In this way you can drop extra checks for the case of l_k=r_k.
void solve() {
int N;
cin >> N;
int l, r;
map<int, int> open, close;
set<int> ends;
int L = 1, R = 1e9;
for(int i = 0; i < N; i++) {
cin >> l >> r;
ends.insert(l);
ends.insert(r);
L = max(L, l);
R = min(R, r);
open[l]++;
close[r]++;
}
int ans = N;
int balance = 0;
for(auto it = begin(ends); it != prev(end(ends)); ++it) {
balance += open[*it] - close[*it];
if(*it >= R && L >= *next(it)) {
ans = min(ans, balance);
}
}
cout << (ans == N ? -1 : ans) << "\n";
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
