Author: Shiven Sinha
Tester: Aryan Choudhary
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Segment Tree, Hall’s Theorem
PROBLEM
You’re given a row of M seats. N people want to buy tickets in this row. Person i wants exactly S_i number of tickets, all of which should be in the range [A_i, B_i]. It’s guaranteed that A_i \geq A_{i-1} for 2 ≤ i ≤ N.
For each i (1 ≤ i ≤ N), calculate the largest j (i ≤ j ≤ N) such that all people i \dots j can be accommodated together and given tickets according to their requirements.
QUICK EXPLANATION (HINTS):
Hint 1
We can build a bipartite graph in which the nodes on the left side denote people, and the other side represents seats. Notice that the problem is now a specific case of the bipartite matching problem. We only need to determine if a left-saturating matching exists and not rebuild the entire assignment. Does this remind you of Hall’s theorem?
Hint 2
What makes this setup of matching different from the general bipartite matching problem? How can Hall’s theorem be modified to handle this case more efficiently?
Hint 3
Notice that all nodes on the left have an edge to a continuous range of nodes on the right.
Hint 4
Try to find a sufficient condition for checking if we can accommodate a continuous range of people together.
Hint 5
For an interval of seats [l, r], let’s denote by F(l, r) the number of people p such that A[p] ≥ l and B[p] ≤ r. If there exists an interval of seats [l, r] such that F(l, r) > r-l+1, then there exists no matching which satisfies all people. How do we implement this?
Hint 6
Time to use the condition that A_i \leq A_{i+1}.
Hint 7
Use a segment tree to process the j pointer while scanning over i pointers in order.
EXPLANATION
Assume that every person wants precisely one ticket. If they want more, let’s create a duplicate person with the same A[i] and B[i] values for the number of tickets that they want. A greedy strategy to optimally assign seats to a set of people is:
- Sort the people by their A[i] (which is already done actually in the input)
- For each seat s from 1 to M in order (preferably after doing some compression), assign this seat to the person p who still doesn’t have a seat ticket and has A[p] ≤ i and B[p] ≥ i. If there are multiple such people, choose the one with the smallest value of B[p].
The intended solution takes an entirely different approach.
Note that this is a bipartite matching problem, with the additional constraint that the elements on the left side (people) always have edges to a continuous range of nodes on the right side (seats). Hall’s theorem can take a stricter form in this case. For an interval of seats [l, r], let’s denote by F(l, r) the number of people p such that A[p] ≥ l and B[p] ≤ r. If there exists an interval of seats [l, r] such that F(l, r) > r-l+1, then there exists no left-side-saturating matching (a matching in which all people get a seat and each set gets assigned to at most one person). Let’s call this [l, r] a violating range of seats. If there is no such range, a left-side-saturating matching definitely exists.
How do we use this efficiently?
I’ll first describe a way to check whether a given set of people can be accommodated together. We just need to check if a violating range of seats exists. Let’s say it is [l, r]. If such a range exists, we can see that we can also find a violating range in which both l and r appear somewhere in the arrays A or B. Otherwise, we can increase l until that is true and decrease r until that is true, and it will still be a violating range since F(l, r) remains the same and r-l+1 will decrease. So, let’s compress the ranges of seats.
Make a range-add range-max segment tree over the compressed seats, with values initially filled as -X, where X is the compressed seat’s actual (uncompressed) index. We loop over the people in decreasing order of A[i], and then add +S[i] to all positions with actual seat indices >= B[i] in this segment tree. Then, we query for the maximum in the segment tree. Let it be mx. If mx>1−A[i], we’ve confirmed that there exists a violating range of seats. This is because mx=k−r, where k is the number of people whose range of compressed seats lies completely inside [A[i], r]. Since mx>1−A[i], this implies k>r−A[i]+1. Congrats, we’ve found a violating range [A[i], r]! If we didn’t, then congrats! We can assign these seats to satisfy all people.
How do we use this to solve the problem at hand? For each i, let ans[i] denote the answer we are looking for. To calculate ans[i], we need to find the smallest suffix of people that need to be deleted such that the remaining suffix of people starting at i can be accommodated together. Let’s first calculate the smallest suffix that needs to be deleted such that there exists no r such that [A[i], r] is a violating range. Let this minimum suffix to be deleted be the one starting at position j+1. Then, ans[i] = min(ans[i+1], j). That means we can calculate the j for positions N to 1 in decreasing order and keep moving the j pointer backwards as needed. This is true because if the j required for position i is greater than the one required for i+1, it doesn’t matter. Because if we include those greater positions, then there will exist a violating range starting at position A[i+1]. So we can answer using two pointers.
Time Complexity: O(N * \log{N})