Please checkout week3 programs of Nptel Competative programming. Seriously they are very tough. If anyone could write a code in c++ and python3, please help. Question in below:
There is a book reading scheduled at a popular bookstore in the city. N book lovers
are expected to show up. The i-th customer comes to the show at time Si and leaves
at time Ei. At any point of time, the set of people who are present in the bookstore
bond over books, coffee, and conversation, and become friends. After the event is
done, it turns out that some precious books were missing from the store, and it looks
like there was a planned heist. So the police want to interrogate everyone who came
to the event, but unfortunately, they don’t have enough time to speak to all of them.
They are suspecting that there are X people involved in this theft. It is natural that
those X people would be friends with each other.
Now, recalling ideas that they learned in their undergraduate days, the police come
up with the following plan: they will schedule their interrogations so that for each
collection of X friends (where each pair of people in that subset are friends), there
will be at least one person who is interrogated from that subset. But to save their
time, they want to keep their total number of interrogations to a minimum. Given the
information of about how people came and went from the event, and the number X,
help them the police find the minimum number of interrogations to be scheduled.
Note: Two people are friends if they have common time at the bookstore. For
example, the person entering at time 1 and leaving at time 3 can be a friend with
another person entering at time 3 and leaving some time afterwards. But a person
leaving at time 3 cannot be a friend with another person entering at time 4.
Input
The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows. Each test case starts with a line
containing N and X. Each of the next N lines contains, the arrival Si and the
departure Ei of an attendee.
Output
For each test case, output a single line containing the minimum number of people
that the police should interrogate.
Constraints
1 ≤ T ≤ 100
1 ≤ X ≤ N ≤ 200
1 ≤ Si ≤ Ei ≤ 109
Example
Input:
3
3 2
1 3
3 5
4 6
4 3
1 8
2 9
3 10
4 11
4 3
1 5
4 9
8 13
12 17
Output:
1
2
0
Explanation
Example case 1.
Persons 1 and 2 are friends each other. Also Persons 2 and 3 are
friends with each other. So it is enough to interrogate gangster 2 only.
Example case 2.
All of the four persons are friends with each other. The police
suspects that the size of the group is 3. So it is enough to interrogate any two of
them.
Example case 3.
There is no group of 3 persons, where each of them are friends
with each other. So the police don’t need to interrogate anybody.