Help with how to solve CHFRAN

Here is the link to the problem CHFRAN from the December Long Challenge 2019. I have been trying to understand how to solve the problem by seeing the solutions that received 100 pts. But unfortunately i am not able to understand the logic that solves the problem​:sweat_smile::sweat_smile:. I was trying to understand this solution by @tmwilliamlin and this solution by @singhpriyank . Thanks in advance and appreciate anyone :blush::blush: who takes the time and helps me understand the logic behind the problem and the solutions since the official editorials are not out yet.

1 Like

Hi ankurkayal,
Posting my query here because the same question is under consideration.
I am also upsolving questions that I wasn’t able to do in the challenge. I wrote this solution https://www.codechef.com/viewsolution/28405596 . I scored 85 and got TLE in 3rd Subtask. Would be happy if some could help me with this. Thanks in advance!

For logic see this-https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/
This is maximum interval overlap.
But in CHEFRAN we need to find minimum interval overlap using similar approach.
Keeping in mind to not choosing points before first departure and after last arrival as those points will not give us two disjoint sets.

3 Likes

I can explain my solution. https://www.codechef.com/viewsolution/28115708

Basically you sort all intervals by start point. Traverse all those segments and keep a count of how many are open at the same time. You add 1 when you parse a new point, and remove 1 when it’s closed. To see when they close efficiently, add the end-point to a priority queue, and peek at it before adding (

If you draw those segments, you’ll see that you should cut where the amount of intervals is minimal - and just keep in mind the edges - which don’t separate into 2 non empty groups (hasClosed variable in my code and my last if/else).

This might help you understand
https://www.codechef.com/viewsolution/28117510

Sort the intervals according to r_i in increasing order. Now let us go through all the intervals from the right (Highest r_i first). For each interval, let us assume that r_i is our answer, i.e., this is the last interval in our first group. Basically, all the intervals before our current interval (including our current interval) form one subset. Now we need to see how many intervals on the right of our current interval we have to remove. For this, we maintain a priority queue containing the l_j we have come across till now. If the l_j in priority queue is greater than our current r_i then we know the range containing l_j can be used in our second subset. So at each step, our priority queue will contain the intervals that we have to remove to make the 2 subsets. Since we require both subsets to be non-empty, we start our loop from last but one interval and we have to check that our priority queue does not contain all the intervals to the right of our current interval. We just have to take the minimum priority queue size as the minimum number of ranges to be deleted.

4 Likes

you can also use bit just sort the vector of ranges in ascending order of starting points with the known disjoint set union find number of disjoint sets if that number is greater than=2 then plainly output 0 as answer
else

COOL we have all ranges connnected to each other that is related to other now we can find a answer if and only if maximum of stating point is less than= minimum of ending points than plainly output -1 dry and run you will get it.

after that just do check with binary search in sorted ranges that for current range to include in one set than find the nearest range with startpoint greater than the end point of current range if we are able to find it correctly (lets name it x range) then we can put both this ranges in two different sets now the task remains is to delete how many ranges that intersects with both of the above selected ranges that also can be done easily with the help of

Fenwick tree.

we can find number of ranges with end point greater than the start point of this x range and we have to delete all these ranges to make it possible. for reference check my solution.

my chfran solution

1 Like

This is a good solution thank you for helping me out.

1 Like

I understood your logic but i couldn’t understand this part of the program. Can you please explain me?

Line no 25 to 26
if (n - i - 1 - pq.size() != 0)
ans = min(ans, (int)pq.size());

Can you explain me this please? :blush::blush:

My second subset should be non-empty. This just ensures that. Like, the priority_queue should not contain all the elements. Then only can I consider it for my answer

1 Like

Thanks got it :smile::smile:

This was a very nice problem :slight_smile:

Is this because “whenever two ranges have a common point, they are in the same subset.” which also means that they can be kept in the same subset even if they don’t have anything in common?

@crvineeth97

1 Like

Yes! That is the case.

@crvineeth97 Thanks for explaining this awesome approach. Also clever macros used to for pairs ( F ans S ) :sweat_smile::sparkles:

Here is my implementation with your strategy with verbose comments.
https://www.codechef.com/viewsolution/28444037

1 Like

Also will really appreciate if any one could help me know the cause of TLE at Help with how to solve CHFRAN (TLE at 3rd sub task but no TLE with original constraints ).

This would really help a beginner like me and ( many more beginners most probably? ) in improving in future. :sparkles:

My guess is that the declaration of two 2*N length vectors in every test case is causing the TLE. Try declaring it globally.

It didn’t solve the issue :frowning:
Here is my submission https://www.codechef.com/viewsolution/28473222

You can try a few more optimizations

  1. Make all variables global
  2. Use scanf, printf instead of cin, cout
  3. Store the value of 2*N in another variable so that it isn’t calculated in the loop every time
  4. Use arrays instead of vectors
  5. Using int instead of long long

If, even after all the above optimizations, it doesn’t get accepted, then the comparator function might be the problem because of 2 comparisons every time for 2N log (2N) elements

1 Like

Thanks a lot !
Using pair instead of struct helped. Thus compare function must be the issue.
Here is the final solution https://www.codechef.com/viewsolution/28478477

1 Like