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. 
