Parrty - editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Mohammad Nematollahi
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Segment Tree and Implementation would do.

PROBLEM:

Given N people numbered 1 to N and M conflict pairs of people, answer Q queries of format. Given K pairs in a query namely [L_i, R_i] inviting all people in range [L_i, R_i] to party. Determine if all people invited to party get along or not.

QUICK EXPLANATION

  • The brute solution to answer each query in O(N+M) time can be easily written. This solution takes O(Q*(N+M)) in the worst case if all queries consist of a single interval of people invited and shall time out.
  • We can develop another solution answering each query in O(K^2) time by iterating over every pair of intervals in the query and checking if both of the intervals contain a pair of people who do not get along. If it holds true for any pair of intervals in query, answer is NO, otherwise YES. This solution too won’t work as it may take time to answer if there are too many intervals in few queries.
  • To find out whether any pair of an interval of people contains any conflict pair, we shall use segment tree operations.
  • Now combine the above two solutions, using the first solution when K is large, and the second solution when K is small, to fit the overall solution into the time limit.

EXPLANATION

The solution to this problem is based on merging two slower solutions to fit the time limit, so let us discuss both solutions.

Brute Solution:

To answer each query in O(N+M) time, we can simply maintain an array included, marking all the elements present in intervals and then iterating over all conflict pairs to check if both persons in any pair are included or not. This solution performs well when there are few queries with a high number of intervals.

Segment Tree Solution:

We can also build a solution which, for each query check all pairs of intervals to see if the first member of any conflict pair lies in the first interval and second person of conflict pair lie in the second interval of selected pair. If we tried to maintain a set of conflict pairs, it shall time out. We need something smarter.

Let us store these queries and answer them all together efficiently.

What we can do is, to build a range max Segment tree initially filled with -1 and start considering each person one by one. While considering yth person, Consider all conflict pairs (x,y), x < y and update these positions with value y.

Now, whenever we have an ith interval in query [L, R] where R is the person being considered, we can check all intervals ending before L and check if range max of any interval is always strictly smaller than L. The reasoning is as follows.

Considering only first i persons, when we reach the ith person, we update all positions having a conflict with the ith person with value i. Now, If any interval has range maximum x if implies that in that interval, there is a person having a conflict with the xth person. So to check if any conflict pair is there, we iterate over all intervals ending before the current interval and check if this interval has a conflict with any person having index \geq L. (Meaning people in the current interval). This compares all unordered pairs of intervals and thus, runs in O((N+M)*log(N)+\sum K^2) to answer all queries.

This solution won’t work due to square factor and shall time out when there are few queries with a large number of intervals.

Merging solutions:

Let us define a limit SQ. We use brute solution when K \geq SQ achieving worst case when K = SQ taking O(Q*(N+M)). This may seem large, but here, Q*SQ \leq 2*10^5

We shall use the second solution when K < SQ as our second solution is good in answering queries when K is small. If all queries are answered by this solution, it takes O((N+M)*log(N)+\sum K^2*log(N)) time. But, since K < SQ, \sum K cannot exceed 2*10^5*SQ.

By choosing a reasonable value of SQ, we can achive O((N+M)*Q/SQ +(N+M)*log(N)+Q*SQ*log(N)).

Implementation hints:

It is useful in the second solution to sort the intervals beforehand so you only need to check intervals indexed up to the current interval. Additionally, do not forget to consider the case when a conflicting pair lies inside a single interval only in the second solution. This can be easily handled by considering the pair of an interval with itself too.

There are quite a number of problems merging solutions, but I don’t remember any at present, so please share the link of any problem you know using a similar idea.

Time Complexity

Time complexity of this solution is O((N+M)*Q/SQ +(N+M)*log(N)+Q*SQ*log(N)) in worst case.
Memory complexity is O(N*log(N)+M+\sum K) in worst case.

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:

3 Likes

“Now, whenever we have an ith interval in query [L,R] where R is the person being considered, we can check all intervals ending before L and check if range max of any interval is always strictly smaller than L”

Could this part of the editorial be explained for the following test case:

N=5, M=1

The conflicting pair is (1,5)

The query is K=2 and the ranges are [1,2], [3,4]

The range maximum for [1,2] would be 5 which isn’t less than 3 but the answer is still “YES”. I’m sorry if i understood the explanation incorrectly as your solution gives “YES” as expected but it isn’t expected from what i understood by the explanation above.

I was also trying the editorial’s solution with the same type of segment tree but couldn’t because of cases like the above and had to store all conflictions in the segment tree and perform binary searches during queries. My solution

1 Like

This question was more or less almost on the lines of this question :
https://www.codechef.com/problems/CHANOQ

Could be a good upsolve for this problem.

5 Likes

Position 1 shall be updated with 5 only when we are considering 5th person, but range max of segment [1, 2] is checked when perosn 2 is considered.

thanks, got it :slight_smile:

The problem can also be solved with Mo’s algorithm. The idea is as follow: for each of the pair, mark all sets which covers both the ending of the pair as NO. Since transitioning from one pair to the other take at most O(\sum{2K}) by going through all of the event points between the pairs’ endings, we can perform a Mo’s algorithm to get the complexity of O(2Klog(2K) + Q * \sqrt{\sum{2K}}), first by sorting the event points, then sort the pairs similarly to the well-known Mo’s algorithm.

However, to actually stay within the time limit, I implemented a doubly-linked list that discards all of the event points of the sets which already have the answer NO. My solution.

1 Like

Can you please explain your approach in details? Please include explanation for line 57 of your code:

que[i].pos[j] = distance(ve + 1, upper_bound(ve + 1, ve + sz + 1, make_pair(que[i].pos[j], Q)));

I used coordinate compression (might be unnecessary) and bitvectors for this problem and CHANOQ. Running is O(S * Q / 64). It probably runs faster than the editorial solution. https://www.codechef.com/viewsolution/22251382

3 Likes

My approach is to compress all of the coordinates (which from now on I shall call as event points), and for each pair, I maintain the sets that lie on both endings of this pair. These sets will have the answer NO, and after processing through all of the pairs, the remaining sets will have the answer YES.

That line means that I change the position of the pair’s endings to the actual position on the event points array. For example, if my sorted event points are:

1, 2, 2, 3, 3, 3, 4

then the pair [2, 3] corresponds to the half-closed interval [4, 7) on this sorted event points.

1 Like

Got it. Thanks :smiley:

@taran_1407 In the 4th line of merging solutions section, isn’t the complexity

O(N+ M*log(N)+\sum K^2*log(N))

since for every pair we perform an RMQ in O(log(N)) and for every edge we perform an update in O(log(N)).

Yes, I missed it. Thanks for catching.

…and also I think that the log(N) factor must not be multiplied by N.

For Segment tree building, N*log(N) is there, at least in my implementation.

But isn’t building a segment tree O(N) ? :expressionless:

https://www.codechef.com/viewsolution/22596468 .It can be solved without segment tree by solving 63 queries together. Set those bits of person ,according to in which queries this person is present then traverse the M conflicting pairs to check both of them are having same set bit or not.

1 Like

@aakashsoni1999 Hey man great solution but is there any special reason for taking only 63 queries together or it was just a random selection .

The reason is that a long long int uses 8 bytes that means 64 bits are used to store it and we can set only 63 bits because the last bit is used for sign.
So we cannot solve more number of queries than this together.

@aakashsoni1999 thanks buddy for the reply , could you just drop me a mail at [email protected] so that we can discuss some interesting problems and concepts and i don’t think you realize it but we have met once.