CHEFKO - EDITORIAL

PROBLEM LINK:

Practice
Contest

Setter: Misha Chorniy
Tester: Rajat De
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Segment Intersection and Sorting.

PROBLEM:

Given N segments [L_i, R_i], find the length of maximum length segment intersection between any subset of size K of segments.

SUPER QUICK EXPLANATION

  • Sort the segments by the left end in non-decreasing order and if the left end is same, sort by the right end in non-increasing order.
  • Fix the starting point, say S, and considering all segments starting before or at S, suppose we have the endpoints of these segments. Then K-th from rightmost direction is the maximal right end, say E for given starting point. Fix left end of all segments as the starting point and find out K-th rightmost end. The answer is just max(S-E) for all values of S.

EXPLANATION

First of all, we know, that intersection of any subset of segments will both begin with the start point of a segment in the subset as well as end with some segment in the subset.

So, based on this, we can make a solution, by sorting all segments by their left end. Fix the left end of the current segment, say S as the left end, and considering all segments starting before or at S, we get a multiset of right ends. Since we want the length of the maximal intersection, we want to choose as larger right end as possible while having K segments in the set. So, we look for Kth rightmost end from all segments which started before S. Say this value is E. Hence, length of intersection is E-S. We can find the maximum value of E-S for all left ends of segments S.

This way, we can develop a brute solution, which considers every contiguous subset of size K of segments when sorted in increasing order of left ends. This gives time complexity O(N*K+N*logN) which will time out.

But, we can notice, that if we have the segments sorted by the left end in non-decreasing order, the set of segments will only extend to the right as we move the starting point to the right. This helps us in realizing, that we do not need to handle each start point separately.

We have a set of positions, and we need to find the Kth largest element from it. Elements are only added to this set. We can simply use an ordered set or using min-heap, this can be done. In min heap, whenever the size of the set exceeds K, remove the segment’s right end, which is ending earliest. The reason being, only by deleting the earliest ending segment we can get the segment intersection to be maximum. Also, the top element of min heap will give kth largest element, if the size of the heap is K.

So, the final solution is to make a min heap and add right ends to heap as we shift left end forward. Take the maximum of E-S and print the answer.

Time Complexity

Time complexity is O(N*logN) per test case, sorting takes O(N*logN), heap operations take O(logK).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2 Likes

I am doing same thing mentioned in editorial. Still getting wrong answer. Can someone help in finding mistake? Code link

I have really different solution.

I did Binary search over answer(length of subset).

Overall time complexity O(N*log^2(n)).

For each length I assume if answer exist then it will exist only from n segments…
i.e. starting from starting value of given segments and having length mid (i.e. (start+end)/2 in binary search).
So I do again Binary search for each n segments (starting from starting of… and having length=mid) and prefix sum to calculate how many times each of n segments will come in given segments. To do this I have to do BS and prefix sum.
#HERE is my accepted solution.

1 Like

Thing is it only contains binary search and sorting… nothing else…

@parth_patel15, nice solution. Check for border cases. For n == k, the check ‘if (i>=k)’ fails as i starts from 0.

strict time limit … my solution with binary search and ordered_set tle’d …


[1] tc O(nlogn^2)


  [1]: https://www.codechef.com/viewsolution/21337404

I guess you are hitting overflow while calculating mid. Take hi = 1e10, and calculate mid as lo+(hi-lo+1)/2 instead of (lo+hi+1)/2

//