You are not logged in. Please login at www.codechef.com to post your questions!

×

SONYASEG - Editorial

3
1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Igor Barenblat
Tester- Misha Chorniy
Editorialist- You wont believe who this guy is when you click here

DIFFICULTY:

Easy

PRE-REQUISITES:

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$ $Cases-Bad$ $Cases$. Total cases, obviously, is $^{n}C_k$.

We pre-calculate 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_{k-1}) \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-

  • Easy formalization of condition when all $K$ segments intersect.
  • Total ways are easy to find. Simply $^{n}C_k$
  • We will see below that a direct formula exists to find number of violating segments.

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.

View Content

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?

View Content

Now, we will follow a straightforward procedure-

  1. For every segment $\{L_i,R_i\}$ do the following-
  2. WHILE multiset is not empty, and the lines dont intersect- Delete the line with smallest $R_i$ from multiset and check again.
  3. Number of violating ways using this segment $\{L_i,R_i\}$ are $^{p}C_{k-1}$ where $p=size \space of \space multiset$
  4. Insert end-point of this line in the set.

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 $k-1$ lines from the multiset. If, thus, size of multiset is $p$, then number of ways of choosing $k-1$ lines is simply $^{p}C_{k-1}$. A simple code for above is given below-

    multiset < int > f;
    int bad = 0;
    for (int i = 1; i <= n; ++i) {
        while (!f.empty() && *f.begin() < p[i].first) {
            f.erase(f.begin());
        }
        bad = (bad + 1LL * comb(f.size(), k - 1)) % MOD;//comb(a,b)=aCb
        f.insert(p[i].second);
    }

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 :).

Setter

View Content

Tester

View Content

Editorialist's solution will be put on demand. :)

$Time$ $Complexity-O(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.

View Content

2. Ans Q2-I quote "we need not make a custom data type, merely storing the end points of lines can do." (Why?Q2)

View Content

3. Ans Q3-Now, either the multiset is empty, or we have number of lines which intersect with given $i'th$ line.

View Content

4. You can find inverse-factorial in $O(N)$ time. Refer here or at tester's code.

5. What lies in here?

View Content

6. Test Case Bank

View Content

7. Related Problems-

This question is marked "community wiki".

asked 16 Jun '18, 21:20

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 18 Jun '18, 16: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.

My code: https://www.codechef.com/viewsolution/18937928

link

answered 18 Jun '18, 10:54

tamiliit's gravatar image

3★tamiliit
765
accept rate: 30%

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) soham12346★
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) vijju123 ♦♦5★

Do you have a list of ALL problems for which you've made editorials? :D

Seriously, this is god level editorial-preparation skill!

Take a bow! /\

link

answered 18 Jun '18, 00:49

thecodearrow's gravatar image

3★thecodearrow
252
accept rate: 14%

edited 18 Jun '18, 01:00

Thank you for your kind words :). You can access the editorials (and hence problems) by looking at my discuss profile.

(18 Jun '18, 01:01) vijju123 ♦♦5★

My approach :
1) sort according to Li in increasing order.
2) for each segment {Li, Ri} calculate the number of segments which have Lj < Ri(j > i) (let it be = x)
3) add (n-i-1)C(k-1) - (x)C(k-1) to answer because the total number of sets of segments formed with {Li, Ri} in the set would be choosing (k-1) from (n-i-1) (as we don't want to double count we look at segments from [i,n-1] only) and the number of wrong sets would be = choosing (k-1) segments from those x segments which overlap with {Li, Ri}.
Code

This approach is giving wrong answer verdict. Please tell me what I have missed.

link

answered 18 Jun '18, 13:46

shahanurag's gravatar image

4★shahanurag
11
accept rate: 0%

edited 18 Jun '18, 14:14

@tamiliit I am sorry I forgot to mention j > i. I'll update it.

(18 Jun '18, 14:14) shahanurag4★

@tamiliit thanks :)

(18 Jun '18, 16:01) shahanurag4★

@shahanurag consider intervals [1, 2], [3, 4], [5, 6].

For the interval [5, 6] x = 2. "choosing (k-1) 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.

link

answered 18 Jun '18, 14:07

tamiliit's gravatar image

3★tamiliit
765
accept rate: 30%

edited 18 Jun '18, 14:21

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,820
×900
×647
×191
×34
×17

question asked: 16 Jun '18, 21:20

question was seen: 1,422 times

last updated: 18 Jun '18, 23:07