PROBLEM LINK:Author: Andrii Omelianenko 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:
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:
SolutionClearly 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 bpeople actually cause any trouble. This is because: Observation 1: $l$ lpeople, $r$ rpeople and $z$ zpeople can always fill a row of length $l+r+z$. The only restriction is that a rperson can't be directly to the left of a lperson, One way for them to seat would be to place the lpeople, then the rpeople, then the zpeople, 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 bpeople, 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 bpeople are the root of all our troubles, we'll want to minimize the number of bpeople in the grid. In other words, we want to seat the l, r or zpeople 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 zpeople are seated. The idea is to start with an optimal arrangement. Suppose that in this arrangement not all l, r and zpeople are seated. Then we can always replace any bperson with a l, r or zperson and we will still be left with a valid seating arrangement, and we can repeat until all l, r and zpeople are placed. Replacing a bperson with anyone else is okay because a bperson 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 zpeople. This also implies that the answer is $L+R+Z+B_{\text{max}}$, where $B_{\text{max}}$ is the largest number of bpeople 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 zpeople with $b$ bpeople 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$ bpeople, then you can place $b_2$. This is true: simply remove one $b_1  b_2$ bpeople, and the whole configuration is still valid! Observation 4 is very useful, because it allows us to compute $B_{\text{max}}$ with binary search:
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 $$L + R + Z + b \le MN,$$ Otherwise there aren't enough seats to place all people. Next, let's only consider the bpeople for now. Can we place $b$ bpeople by themselves in the theater? What is the maximum number of bpeople that can be placed in the theater? Clearly, no two bpeople 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$ bpeople (where $\left\lceil x \right\rceil$ is the ceiling function). Thus, the maximum number of bpeople 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 $$b \le N \left\lceil \frac{M}{2} \right\rceil.$$ Next, can we place the other people along with the $b$ bpeople? The zpeople can be placed anywhere, so we first focus on the l and r people. Is it possible to place the l and rpeople with $b$ bpeople in the theater? Not necessarily: Observation 5: In a row containing only l, r and b people, one of the seats between any two bpeople must be empty. To see this, consider two bpeople with no other bpeople in between. Clearly, there must be at least one seat between them, because bpeople can't be seated together. Let $c$ be the number of seats in between. Now, suppose all these seats are filled with l and rpeople. Clearly there are $c1$ armrests between the bpeople, 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$ bpeople in a row (containing no zpeople), then there must be at least $b1$ empty seats. Thus, $L+R+2b1\le M$ But can we always make sure that there are exactly $b1$ empty seats? Yes! Observation 6: One can place $L$ lpeople, $R$ rpeople and $b>0$ bpeople in a row of $M$ seats in such a way that there are exactly $b1$ empty seats. In other words, a seating arrangement exists if and only if $L+R+2b1\le M$. The idea is simple. Use the first $L$ seats to seat the lpeople, then the next $2b1$ seats to seat the bpeople (leaving spaces in between), and finally the next $R$ seats for the rpeople. Now, what if there are $N$ rows? Well, clearly the number of empty, "wasted" seats depends on the number of gaps between bpeople among all rows, and our goal now is to minimize this number. Since there are $\max(0,b1)$ gaps in a row with $b$ bpeople, one way is to distribute the $b$'s as evenly as possible. This way, we can calculate the minimum number of gaps given $b$ bpeople:
Thus, a third requirement for $f(b)$ to be true would be: 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 bperson 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:
We've just shown above that these are all necessary conditions. To see that they are sufficient, suppose these are all satisfied. Then:
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 constanttime solutionEven 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:
These three statements can be combined into a single statement: $$b \le \min\left(MN  L  R  Z, N \left\lceil \frac{M}{2} \right\rceil, \left\lfloor \frac{(M+1)N  L  R}{2} \right\rfloor\right)$$ But this means that the maximum $b$ satisfying this inequality is simply the value at the righthand 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):
Time Complexity:$O(\log B)$ or $O(1)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Dec '15, 16:21

@kevinsogo Great Editorial !!!! I don't see why there are few upvotes ... Keep up the good work :D answered 17 Dec '15, 21:19

I have a different solution, where I placed the left and right people optimally first, then as many both people as I could, and then finally the z people can fill in the rest. Link to AC solution: https://www.codechef.com/viewsolution/8949513 This is an O(1) solution (fastest solution for the problem) and slightly intuitive, at least to me. What I am doing, is in each row, I am placing as many left and right as possible, and keeping just 1 seat empty for the both. This always works, irrespective of how many lefts or rights are there. I place them by starting with all the lefts, then 1 both, and then all the rights  LLLL....LBR....RRR Once all the lefts and rights are finished, then I will have one row with part (maybe 0) left and rights, and other empty rows. The partfilled row can now be filled with alternate both and z. This will also be the case for the empty rows. This greedy approach works. A complication arises if m is even, when before putting all the L and R in the first rows greedily, we should fill in the first/last seats in each row first (thus making m essentially odd). For example, if we have 4*4 grid, 6L, 0R, 7B and 2Z, ideal placements would be: LLLB LBZB LBZB LBB and not: LLLB LLLB BZB BZB answered 15 Dec '15, 00:00
1
I also thought the same idea..i think there was a slight fault in my implementation because i was not sure whether it would work or not. Now I will try.
(15 Dec '15, 14:54)
i tried to think in the same way too
(18 Dec '15, 23:08)
I did the exact same thing. Was having too many problems in implementation and moreover, I thought it was a bit too complex, as I didn't have any concrete proof for it and was basing my observations solely on manual test cases :/
(19 Dec '15, 10:49)

The answer simply depends on how we fit the "both type" of people, as we can always fit any number(obviously less than equal to m*n) of l, z, and r type of people. It can be observed that the maximum number of b type people in a row would be maximum if the number of seats are odd. So, the optimality is to always keep the number of available seats in each row odd by placing the l and r type of people at the left and right edges respectively. When this is done, there may/may not be exactly 1 left or right person left, whom we can safely assume to be "both type" person. After that b type people are filled in each row, and after the remaining seats with z type of people. This will guarantee the optimality because we are making sure to fit the maximum number of "both type" people possible with an assumption of fitting all the left and right people, and obviously, all the z people are used to fill the left out voids. The above argument can be implemented in O(1) time. Althogh it may not seem clear but My solution implements this argument : answered 15 Dec '15, 21:56

My approach consisted of first filling the theater with B people as much as possible, then filling in the vacancy with L and R (L and R are of same type here), and at the same time removing some B's if required, finally the Z people act as fillers only... answered 18 Dec '15, 19:04
