PROBLEM LINK:Practice Setter: Mohammad Nematollahi DIFFICULTY:MediumHard 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
EXPLANATIONThe 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 ComplexityTime 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Jan, 16:21

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. answered 14 Jan, 22:54

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 answered 16 Jan, 04:28

"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 answered 14 Jan, 21:16
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.
(14 Jan, 23:32)
thanks, got it :)
(15 Jan, 00:29)

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 However, to actually stay within the time limit, I implemented a doublylinked list that discards all of the event points of the sets which already have the answer answered 15 Jan, 19:54
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)));
(15 Jan, 23:07)
1
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 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:
then the pair
(16 Jan, 18:04)
Got it. Thanks :D
(18 Jan, 01:47)

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. answered 25 Jan, 09:41

@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))$. answered 19 Jan, 08:55
Yes, I missed it. Thanks for catching.
(19 Jan, 18:57)
...and also I think that the $log(N)$ factor must not be multiplied by N.
(19 Jan, 21:27)
For Segment tree building, N*log(N) is there, at least in my implementation.
(19 Jan, 21:46)
But isn't building a segment tree $O(N)$ ? :
(20 Jan, 20:34)

@aakashsoni1999 Hey man great solution but is there any special reason for taking only 63 queries together or it was just a random selection . answered 26 Jan, 14:28

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. answered 26 Jan, 18:20

@aakashsoni1999 thanks buddy for the reply , could you just drop me a mail at anshushahi98@gmail.com so that we can discuss some interesting problems and concepts and i don't think you realize it but we have met once. answered 27 Jan, 13:57
