PROBLEM LINK:Setter Igor Barenblat DIFFICULTY:Easy PREREQUISITES:Combinatorics, Finding $^{n}C_k\% p$ using Fermat's Little Theorem, Data structures like multiset. PROBLEM:Find number of ways to choose $K$ out of $N$ segments such that their common intersection is empty. Common intersection, in other words, means $L_1 \cap L_2 \cap ... \cap L_k = \phi$ $i.e. (empty/null)$. Print answer modulo ${10}^{9}+7$ QUICK EXPLANATION:Key to AC Its very easy if you have some practice in combinatorics, else the intuition may seem tricky. Finding number of violating cases was easier than finding number of good ones. Calculating answer as $Ans=Total$ $CasesBad$ $Cases$. Total cases, obviously, is $^{n}C_k$. We precalculate the inverse and factorial of required numbers to calculate $^{n}C_k$ in $O(1)$ time. We can easily maintain a $multiset$ (to maintain order). We can easily formalize when all $K$ elements intersect as if $min(R_1,R_2,..,R_{k1}) \ge L_i$ where segment $\{L_i,R_i\}$ is the segment under consideration. After this, its simple calculation of $^{n}C_k$. We will discuss derivation under explanation section. (WHAT? You want me to give away everything in Quick Explanation? xD.) EXPLANATION:This editorial will have a single section. Its assumed that you went through how to calculate $^{n}C_k$ as we wont be discussing this in detail in official part. We will simply see the intuition and derivation of formula. I will give whatever links I can for $^{n}C_k$ in Chef Vijju's Bonus Corner :). We will refer to @mgch (tester's) solution for implementation. 1. How to deduce that ans is calculated by finding number of bad combinations and subtracting them from total combinations? This comes with practice. Really! It will seem something trivial to someone who is well versed with such questions. However, if you want what concrete steps we can analyze are
2. I have taken the input. What next? Well, whats next? We solve the question! The very first thing to do is, we sort the segments. We sort the segments in increasing order of $L_i$. If $L_i$ are same, then the segment with larger $R_i$ comes first. Why $R_i$ in descending order? Simple, because if $L_i$ are same, then inserting larger segment first helps us to easily find if $k$ segments intersect. (Why?Q1) Now we will maintain a multiset of lines. Multiset is used as it keeps them in sorted order. There are many implementations on what to store and how to use. Giving details of most easy one, I quote "we need not make a custom data type, merely storing the end points of lines can do." (Why?Q2) A hint is given in tab below. The multiset will store the $R_i$ in ascending order. Now, when do $2$ horizontal lines intersect? Can you try framing conditions on when they interesect and when they dont? Now, we will follow a straightforward procedure
Lets discuss the intuition behind it. Step $1$ is simple looping. Step $2$, we discussed above when line intersect and when they dont. We need all $k$ lines to intersect for a way to be violating. Hence, if $i'th$ lines doesn't intersect, we delete the line with smallest $R_i$ from multiset. Now, either the multiset is empty, or we have number of lines which intersect with given $i'th$ line. (Why?Q3) Now, what we have in multiset is a set of lines which intersect with $i'th$ line. We must choose $i'th$ line, and are free to choose rest $k1$ lines from the multiset. If, thus, size of multiset is $p$, then number of ways of choosing $k1$ lines is simply $^{p}C_{k1}$. A simple code for above is given below
SOLUTION:The codes which I received are pasted below for reference. This is done so that you dont have to wait for @admin to link solutions up :). Please copy them and paste at a place where you are comfortable to read :). Editorialist's solution will be put on demand. :) $Time$ $ComplexityO(NlogN)$ CHEF VIJJU'S CORNER:1. Ans Q1 Why $R_i$ in descending order? Simple, because if $L_i$ are same, then inserting larger segment first helps us to easily find if $k$ segments intersect. 2. Ans Q2I quote "we need not make a custom data type, merely storing the end points of lines can do." (Why?Q2) 3. Ans Q3Now, either the multiset is empty, or we have number of lines which intersect with given $i'th$ line. 4. You can find inversefactorial in $O(N)$ time. Refer here or at tester's code. 5. What lies in here? 6. Test Case Bank 7. Related Problems
This question is marked "community wiki".
asked 16 Jun '18, 21:20

I have a doubt regarding "Q1 Why Ri in descending order?" I think the order of Ri does not matter, because we will not remove any element in step 2 expect for the first interval with same Li. Hence the computations in step 3 does not care about the order of Ri. Am I missing something? I also ran a random test case check for Ri increasing and Ri decreasing and there was no difference in the result. answered 18 Jun '18, 10:54
1
Yes it is not necessary. I was also gonna comment the same. Reason: Only where sorting order would have mattered was in case of same Li. But Ri>=Li gurantees that Ri's for same Li's would stay in the multiset for all elements having Lj=Li.
(18 Jun '18, 11:09)
2
Oh is it so? Could be. The schedule was very tight, and I saw tester take lot of pain to make the comp function sort lines this way. I will do the needful. Will first show this to @mgch to help me verify and then do the needed changes. Thanks again! (I got your intuition now. Its just that there is very less time for experimenting. Thanks for pointing it out :D)
(18 Jun '18, 11:36)

My approach : This approach is giving wrong answer verdict. Please tell me what I have missed. answered 18 Jun '18, 13:46
@tamiliit I am sorry I forgot to mention j > i. I'll update it.
(18 Jun '18, 14:14)
@tamiliit thanks :)
(18 Jun '18, 16:01)

@shahanurag consider intervals [1, 2], [3, 4], [5, 6]. For the interval [5, 6] x = 2. "choosing (k1) segments from those x segments which overlap with {Li, Ri}" u will count (x)C(k  1). But actually [1, 2] and [3, 4] does not intersect with [5, 6] You need to be very careful while arguing for optimality of greedy solutions. @update: If you want to automatically find test cases where your solution fails, I suggest you copy code from https://www.codechef.com/viewsolution/18937928 and put your logic in greedy2 function and run function_check in main. Pro tip also adjust N_MAX and V_MAX to get simpler test cases. answered 18 Jun '18, 14:07
