PROBLEM LINK:
Author: Balajiganapathi
Tester: Kevin Atienza
Editorialist: Kevin Atienza
DIFFICULTY:
Medium-hard
PREREQUISITES:
Tree-based sets, maps
PROBLEM:
There are N seats in a row numbered 1 to N from left to right. You are given two types of events:
- 1 — A person arrives. Persons are numbered in order of their arrival. He will occupy the seat which is farthest possible from any nearest seated persons, and if there are ties, the leftmost among them.
- 2 i — Person i leaves.
For each person arriving, output the seat number that he occupies.
QUICK EXPLANATION:
Let’s call a maximal contiguous row of available seats a segment. A segment can be described by the location of its two endpoints. If a person arrives and takes a seat from a given segment, his/her location is uniquely determined by the endpoints. Let’s call that seat the available seat.
We maintain a set S of segment, ordered decreasingly by the distance of the available seat from the nearer endpoint. In case of ties, the leftmost segment goes first. Also, maintain a mapping M from each endpoint to the corresponding endpoint in the segment it belongs to. Finally, also maintain the location L of each person, and the number of people that have already arrived (and possibly left).
When person arrives, pop the first element of S. Let’s say the segment is (i,j). Let k be the location of the available seat. Person p goes to seat k (so update L). If i < k, add the new segment (i,k-1) to S. Also if k < j, add the new segment (k+1,j) to S. Remember to update M always.
When a person leaves, using L, get his/her location k. Using M, determine the segments immediately to the left and right of k (which may or may not exist). Pop these segments from S, and insert the merged segment to S. Remember to update M always.
EXPLANATION:
Let’s call a maximal contiguous row of available seats a segment. A segment can be described by the location of its two endpoints, (i,j). Also, if a person arrives and takes a seat from a given segment, his/her location is uniquely determined by the endpoints i and j. Let’s call that seat the available seat.
Note that the available seat is generally the middlemost seat, or if there are two middlemost seats, the left one. This is true except when the segment contains seat 1 or seat N, in which case the available seat is that seat. More specifically, let A(i,j) be the location of the available seat for the segment (i,j). Then we easily calculate it using:
The number of seats N can be very large, so obviously we cannot maintain an array of size N. Instead, we simply collect all segments (i,j) in a set, say S. We must then ensure that this set is correct after each operation, without reconstructing S from scratch every time.
Now, when a person arrives, in which segment does he/she seat? Obviously, it must be the one where the distance of the available seat from the nearest taken seat is maximized. Let D(i,j) be this value. We can calculate this using the following:
If there are ties, we choose the leftmost segment.
Now, let’s say the new person seats in the segment (i,j). Let k = D(i,j) (so the person seats in location k). Now that there is a person in k, the segment (i,j) is not valid any more. However, in place of (i,j), there are now potentially two new segments: (i,k-1) and (k+1,j), which we possibly insert to S. We say “potentially” because it’s possible that either segment (or both) do not exist: (i,k-1) is only valid if i < k, and (k+1,j) is only valid if k < j.
The following figure demonstrates the segments (i,k-1) and (k+1,j). A # represents an occupied seat.
i j
.--------------------------------------.
...# # # i . . . . . k . . . . . . j # # #...
'--------------' '-----------------'
i k-1 k+1 j
Now, what if a person leaves? First, we must know its location k. Next, we must somehow know the segments immediately to the left and right of k, say (i,k-1) and (k+1,j). Note that either segment (or both) may not exist, but let’s assume for now that they do. Then we simply remove these two segments from S, and insert a new segment formed when location k becomes available, which is simply (i,j). Now, when (i,k-1) doesn’t exist, the new segment inserted is (k,j). When (k+1,j) doesn’t exist, the new segment inserted is (i,k). Finally, if both don’t exist, then the new segment is simply (k,k).
From these operations, we now know which operations we must be able to perform efficiently:
- Find the segment (i,j) with the largest D(i,j), and in case of ties, the leftmost one.
- For each person leaving, find its location.
- For each location, find the segments immediately to its left or right, if any.
For the first one, we can simply order the segments in S in decreasing D(i,j), then in increasing i. Thus, the segment (i,j) we want is simply the first one in S!
To get the location of a person, we can simply maintain a dictionary/map, say L, giving the location of each person, and then update it when a person arrives.
Finally, given some location, say k, we want to get the segment immediately to the left and right of k. Since the only times we do this operation is when k is occupied, we know that k-1 and k+1 must be endpoints. In this case, we can simply maintain another mapping, say M, giving for each endpoint of a segment the location of the “other” endpoint. In other words, for every segment (i,j), M[i] = j and M[j] = i. We can easily update this map whenever we insert or remove a segment from S. Using M, the left and right segments are then simply (M[k-1],k-1) and (k+1,M[k+1]) (if k-1 or k+1 exists as keys in M, respectively).
Combining all of these, we can now process each query efficiently!
Time Complexity:
O(Q \log Q)