CHFRAN - Editorial

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.

2 Likes

Do we need to delete ranges to make exactly 2 subsets or atleast 2 subsets ? I feel that the problem statement isn’t exactly clear on that part.

1 Like

Exactly 2 subsets

In that case, that given solution is wrong. Assume the ranges are 1-20, 2-3, 5-6 & 7-8. This solution gives 1. For exactly 2 sets the answer should be 2.

I’ve used Greedy approach to get my desired result.
Sort the coordinates and chose the best coordinates that could be placed after the picked coordinate.

Use unordered_map to store processed data.

Code - here

deleting 1-20 , you can create subset 1 having range 2-3 and subset 2 having ranges 5-6,7-8 . Similarly deletion can be done at co-ordinate 6 and 7 also you will get same result as 1. Please do correct me if i’m wrong

Hi! I’ve created a video solution for this problem, explaining my approach. Hope it’s useful!

Atleast 2 for sure