PROBLEM LINK:
Author: Andrii Omelianenko
Tester: Sergey Kulik
Editorialist: Kevin Atienza
PREREQUISITES:
Binary search, greedy algorithms
PROBLEM:
In the cinema hall there are N rows with M seats each. There are armrests at each side of every seat, but there is only one armrest between two adjacent seats. L people only need the left armrest, R of them need just the right one, Z need none and B need both. What is the maximum number of people that can attend the show?
QUICK EXPLANATION:
If L + R + Z \ge MN, then the answer is MN. Otherwise, define f(b) to be true if all L+R people who need one armrest plus b people who need both armrests can all attend the show together, otherwise itās false. f(b) is true iff the following two conditions are true:
- L + R + b + (b - N) \le MN
- b \le N \left\lceil \frac{M}{2} \right\rceil
If B_{\text{max}} is the largest B such that f(B) is true, then the answer is simply \min(L+R+Z+B_{\text{max}}, MN). B_{\text{max}} can be computed with binary search.
Note that an O(1) solution is possible.
EXPLANATION:
To ease the discussion, weāll name the four kinds of people:
- A l-person needs just the left armrest.
- A r-person needs just the right armrest.
- A b-person needs both armrests.
- A z-person needs no armrests.
Solution
Clearly trying all configurations of people is too slow (except for small subtasks), because there are so many configurations! We must find a way to prune the search. One way would be to discover some properties that the optimal solution must satisfy, to reduce the number of configurations.
Immediately we can observe a few things. First, notice that only the b-people actually cause any trouble. This is because:
Observation 1: l l-people, r r-people and z z-people can always fill a row of length l+r+z.
The only restriction is that a r-person canāt be directly to the left of a l-person, One way for them to seat would be to place the l-people, then the r-people, then the z-people, in that order. There are many other ways!
As an immediate consequence, in the original problem:
Observation 2: If L + R + Z \ge MN, then one can fill the whole theater seat completely.
Thus, when L + R + Z \ge MN, the solution is simply MN. and so in the following discussions we can assume that L + R + Z < MN.
Now, in this case, we are forced to place b-people, because there arenāt simply enough l-, r- and z- people to fill all seats. As above, there are still too many configurations to try, but we can reduce them significantly with a new observation: Since the b-people are the root of all our troubles, weāll want to minimize the number of b-people in the grid. In other words, we want to seat the l-, r- or z-people first. But is this always possible? The following says it is:
Observation 3: If L + R + Z < MN, then thereās always an optimal seating arrangement such that all l-, r- and z-people are seated.
The idea is to start with an optimal arrangement. Suppose that in this arrangement not all l-, r- and z-people are seated. Then we can always replace any b-person with a l-, r- or z-person and we will still be left with a valid seating arrangement, and we can repeat until all l-, r- and z-people are placed. Replacing a b-person with anyone else is okay because a b-person has all the requirements of all other kinds of people.
Thus, we can restrict ourselves to finding optimal arrangements having a seat for all l-, r- and z-people. This also implies that the answer is L+R+Z+B_{\text{max}}, where B_{\text{max}} is the largest number of b-people that can be placed in the theater along all other L+Z+R people. Our goal now is to find B_{\text{max}}.
Letās define the function f(b). f(b) is true if you can place all l-, r- and z-people with b b-people in the theater, otherwise itās false. Our first observation is the following:
Observation 4: If b_1 > b_2, then f(b_1) \implies f(b_2).
This simply means that if you can place b_1 b-people, then you can place b_2. This is true: simply remove one b_1 - b_2 b-people, and the whole configuration is still valid!
Observation 4 is very useful, because it allows us to compute B_{\text{max}} with binary search:
- Let b_l = 0 and b_r = B + 1. Clearly f(b_l) is true and f(b_r) is false.
- While b_r - b_l > 1, do the following. Let b_m = \frac{b_l + b_r}{2}. If f(b_m) is true, set b_l := b_m, otherwise set b_r := b_m.
- B_{\text{max}} is now b_l.
The reason the second step works is that if we find a number b_m such that f(b_m) is false, then we can essentially ignore all higher b s since they are all false by Observation 4. But if f(b_m) is true, then we can ignore all lower b s since weāre searching for the maximum b such that f(b) is true.
What remains is to compute f(b) itself. One obvious requirement would be
Otherwise there arenāt enough seats to place all people.
Next, letās only consider the b-people for now. Can we place b b-people by themselves in the theater? What is the maximum number of b-people that can be placed in the theater? Clearly, no two b-people can be seated together, so around half of the seats will be empty. In fact, in a row of M seats, one can only place up to \left\lceil \frac{M}{2} \right\rceil b-people (where \left\lceil x \right\rceil is the ceiling function). Thus, the maximum number of b-people we can place in the theater with N rows is simply N \left\lceil \frac{M}{2} \right\rceil, and the second requirement for f(b) to be true is that
Next, can we place the other people along with the b b-people? The z-people can be placed anywhere, so we first focus on the l- and r- people. Is it possible to place the l- and r-people with b b-people in the theater? Not necessarily:
Observation 5: In a row containing only l-, r- and b- people, one of the seats between any two b-people must be empty.
To see this, consider two b-people with no other b-people in between. Clearly, there must be at least one seat between them, because b-people canāt be seated together. Let c be the number of seats in between. Now, suppose all these seats are filled with l- and r-people. Clearly there are c-1 armrests between the b-people, not including the ones they use. But there are c l- or r- people using at least c armrests, which is more than available. Thus, at least one must be empty.
A natural consequence would be that if there are b b-people in a row (containing no z-people), then there must be at least b-1 empty seats. Thus, L+R+2b-1\le M But can we always make sure that there are exactly b-1 empty seats? Yes!
Observation 6: One can place L l-people, R r-people and b>0 b-people in a row of M seats in such a way that there are exactly b-1 empty seats. In other words, a seating arrangement exists if and only if L+R+2b-1\le M.
The idea is simple. Use the first L seats to seat the l-people, then the next 2b-1 seats to seat the b-people (leaving spaces in between), and finally the next R seats for the r-people.
Now, what if there are N rows? Well, clearly the number of empty, āwastedā seats depends on the number of gaps between b-people among all rows, and our goal now is to minimize this number. Since there are \max(0,b-1) gaps in a row with b b-people, one way is to distribute the b's as evenly as possible. This way, we can calculate the minimum number of gaps given b b-people:
- If b \le N, then the number of gaps is 0, because we can place all b-people in distinct rows.
- If b > N, then the number of gaps is b - N, because after placing N b-people in distinct rows, every b-person subsequently seated increases the number of gaps by one.
Thus, a third requirement for f(b) to be true would be:
The (b - N) term is the number of gaps that are generated by the b-people overall. Notice that if b \le N, this statement is easily seen to be true.
Another way of interpreting L + R + b + (b - N) \le MN would be the following: In a row of M seats, there are M+1 armrests, so there are (M+1)N armrests in total. However, each l- and r- person uses one armrest, and each b-person uses two, so overall L + R + 2b armrests are used. Thus, it must be the case that L + R + 2b \le (M+1)N, which is equivalent to L + R + b + (b - N) \le MN.
Interestingly, we now have all the sufficient requirements for f(b) to be true!
Observation 7: f(b) is true if and only if all these three conditions are satisfied:
- L + R + Z + b \le MN
- b \le N \left\lceil \frac{M}{2} \right\rceil
- L + R + b + (b - N) \le MN
Weāve just shown above that these are all necessary conditions. To see that they are sufficient, suppose these are all satisfied. Then:
- First, distribute the b b-people as evenly as possible among the rows.
- Next, distribute the l-people and r-people among the rows in any way (as long as the conditions in Observation 6 is satisfied).
- Use the layout described in the proof of Observation 6 to seat the people in each row.
- Finally, fill in all remaining seats with the z-people.
Note that the three conditions guarantee that all these steps are possible! Since f(b) can now be calculated in O(1) time, we can now calculate the answer in O(\log B)-time with binary search!
A constant-time solution
Even though the binary search solution is fast enough to pass all subtasks, itās actually possible to compute the answer in O(1) time. The key is to manipulate the conditions for f(b) to be true. After a simple rearrangement of terms, they are seen to be equivalent to the following:
- b \le MN - L - R - Z
- b \le N \left\lceil \frac{M}{2} \right\rceil
- b \le \left\lfloor \frac{(M+1)N - L - R}{2} \right\rfloor
These three statements can be combined into a single statement:
But this means that the maximum b satisfying this inequality is simply the value at the right-hand side! Thus, we have no more need for binary search and we can simply compute B_{\text{max}} to be \min(B, \text{[right hand side of the above]}). This gives us the following one liner in Python (not including input code):
print min(N * M, Z + L + R + min(B, N * (M + 1) - L - R >> 1, N * (M + 1 >> 1)))
Time Complexity:
O(\log B) or O(1)
