CHN01 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest
Problems

Author: -
Tester: Kevin Atienza, Jingbo Shang
Editorialist: Kevin Atienza

PREREQUISITES:

Binary search

PROBLEM:

There are three types of contests:

  • Type 1: 1 easy, 1 medium, 1 hard
  • Type 2: 1 easy, 2 medium
  • Type 3: 2 easy, 1 medium

There are e easy, m medium, and h hard problems. What is the maximum number of contests you can conduct so that no two contests are of the same type?

The following is guaranteed: e \ge m \ge h.

QUICK EXPLANATION:

Binary search on the answer x. (You may use the lower bound 0 and upper bound m+1).

It is possible to conduct x contests if and only if

\min(e-x, \lceil x/2 \rceil) + \min(m-x, \lceil x/2 \rceil) + \min(h, \lceil x/2 \rceil) \ge x

(Note that you can only do up to \lceil x/2 \rceil of each type of contest.)

EXPLANATION:

An easier question would be: given x, is it possible to conduct x contests satisfying the rules? If we can answer this, then we can answer the problem by simply starting at some upper bound, say x = m+1 (because all contests need a medium problem), and decrementing until we find the largest number of contests we can conduct. If we can answer it quickly enough, this algorithm will pass the time limit.

So given x, let’s find out if it is possible to conduct x contests satisfying the rules.

The first observation is that all contests need at least one easy and one medium problem. So if e < x or m < x, then it’s already impossible. Otherwise, we reserve x easy and medium problems for the x contests, so there are e-x easy and m-x medium problems left. After this, things become a bit simpler, because:

  • Type 1 contests only need 1 more hard
  • Type 2 contests only need 1 more medium
  • Type 3 contests only need 1 more easy

So the problem becomes: Given e-x easy, m-x medium, and h hard problems, is it possible to take x of these and arrange them in a line so that no two consecutive problems are the same? Clearly \lceil x/2 \rceil is the most we can take of the same kind of problem (why?), so if

\min(e-x, \lceil x/2 \rceil) + \min(m-x, \lceil x/2 \rceil) + \min(h, \lceil x/2 \rceil) < x

then the task is already impossible. But if instead

\min(e-x, \lceil x/2 \rceil) + \min(m-x, \lceil x/2 \rceil) + \min(h, \lceil x/2 \rceil) \ge x,

can we do it? We will show that it is indeed possible.

Since at this point the roles of e-x, m-x and h are symmetric, we will write these numbers as a_1, a_2 and a_3, and assume they’re sorted, i.e. a_1 \le a_2 \le a_3. And we’ll call the problems type 1, 2 and 3, instead of easy, medium and hard (since they’re reordered). Note that the following is true:

\min(a_1, \lceil x/2 \rceil) + \min(a_2, \lceil x/2 \rceil) + \min(a_3, \lceil x/2 \rceil) \ge x,

First, if a_3 \ge \lceil x/2 \rceil, then we start with a list of size x, place \lceil x/2 \rceil type 3 problems on the odd-numbered positions, and place the type 1 and 2 problems in the even-numbered ones. Then since

a_1 + a_2 \ge \min(a_1, \lceil x/2 \rceil) + \min(a_2, \lceil x/2 \rceil) \ge x - \min(a_3, \lceil x/2 \rceil) = x - \lceil x/2 \rceil,

there are enough problems of type 1 and 2 to fill in the voids in between. Thus, we have shown a valid arrangement.

Now, let’s assume a_3 < \lceil x/2 \rceil. This also means that a_1 \le a_2 \le a_3 < \lceil x/2 \rceil, and the following is true:

a_1 + a_2 + a_3 \ge x.

The following is also true:

a_1 + a_2 > a_3,

otherwise a_1 + a_2 + a_3 \le a_3 + a_3 = 2a_3 < x. Let’s consider the value a_1 + a_2 - a_3 (which is positive). Also, whenever we place a problem in our arrangement, we update the corresponding value a_1, a_2 or a_3.

If a_1 + a_2 - a_3 \ge 2, then we place a type 2 and then type 1 problem, reducing a_1 and a_2 by 1, and thus reducing a_1 + a_2 - a_3 by two. We can repeat this until “a_1 + a_2 - a_3 \ge 2” becomes false. Thus, a_1 + a_2 - a_3 is now either 1 or 0.

If a_1 + a_2 - a_3 = 1, then we place another type 2 problem so that a_1 + a_2 - a_3 becomes 0. Since a_1 \le a_2 and they can’t be both zero (otherwise a_1 + a_2 - a_3 would not equal 1), a_2 must be > 0, so there exists at least one type 2 problem. Note that we can’t place a type 1 problem because the previous problem is also of type 1.

Finally, if a_1 + a_2 - a_3 = 0, then there are as many type 3 problems as there are type 1 and type 2 combined. In that case, we start with a list of size 2a_3, place the type 3 problems on the odd-numbered positions, and place the type 1 and 2 problems in the even-numbered ones. This gives us a valid arrangement!

Thus, we now have a simple check to see whether it is possible to conduct x contests:

\min(e-x, \lceil x/2 \rceil) + \min(m-x, \lceil x/2 \rceil) + \min(h, \lceil x/2 \rceil) \ge x

Since this check runs in O(1), our running time is O(m) in the worst case, so our algorithm passes the time limit!

Faster solution

A much faster solution exists. Problems like this are amenable to binary search if it satisfies some form of monotonicity. In our case, the following is true:

If you can conduct x contests, then you can conduct x-1 contests.

This is a trivial observation, nonetheless this is what makes binary search valid. The following is a pseudocode:

let L = 0 and R = m+1

// we will maintain the invariant that:
// - it is possible to conduct 'L' contests
// - it is impossible to conduct 'R' contests
while R - L > 1:
    M = floor((L + R) / 2)
    if can_conduct_x_contests(M):
        L = M
    else:
        R = M

// at this point, R = L+1, so the answer is L
print L

Using this, our algorithm runs in a much faster O(\log m) time.

Finally, we note that an O(1) solution exists, though it’s very tedious to describe and implement, so we will leave it up to the reader to find :stuck_out_tongue:

Time Complexity:

O(m) or O(\log m)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter: Will be uploaded soon.
Tester: Will be uploaded soon.
Editorialist: Will be uploaded soon.