CHCINEMA - Editorial

binary-search
dec15
easy
editorial
greedy

#1

PROBLEM LINK:

Contest
Practice

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_{ ext{max}} is the largest B such that f(B) is true, then the answer is simply \min(L+R+Z+B_{ ext{max}}, MN). B_{ ext{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_{ ext{max}}, where B_{ ext{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_{ ext{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_{ ext{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_{ ext{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

L + R + Z + b \le MN,

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

b \le N \left\lceil \frac{M}{2} \right\rceil.

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:

L + R + b + (b - N) \le MN

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:

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 right-hand side! Thus, we have no more need for binary search and we can simply compute B_{ ext{max}} to be \min(B, ext{[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)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester
Editorialist


#2

There’s actually an easier way to get the 3rd equation L+R+b+(b−N)≤MN:

Consider counting the number of armrests that the people will use. In total there are MN + N armrests in the theater (M+1 in each of the N rows), and the people will require L + R + 2b armrests (since the people using only the left or right armrest will only require 1, whereas the people requiring both armrests will need 2). Hence the equation is derived from the fact that the number of used armrests must be at most the total number of armrests:

L + R + 2b \le MN + N

L + R + b + (b - N) \le MN


#3

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 part-filled 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

LB-B

and not:

LLLB

LLLB

BZB-

BZB-


#4

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 :

https://www.codechef.com/viewsolution/8916459


#5

@kevinsogo Great Editorial !!! I don’t see why there are few upvotes … Keep up the good work
:smiley:


#6

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…
My O(1) solution: https://www.codechef.com/viewsolution/8885339


#7

Thank you for this simpler argument! When I have time I’ll try to update the editorial.


#8

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.


#9

i tried to think in the same way too


#10

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 :confused: