PROBLEM LINK:
Author: Ke Bi
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
Contest Admin: Praveen Dhinwa
DIFFICULTY:
Cakewalk
PROBLEM:
There are n Chefs, and the i th Chef wants to visit Phantasialand t_i times.
The park offers a voucher which allows you to visit another time. The procedure for visiting the park and availing the offer is as follows.
- Buy a ticket at the entrance of the park, and possibly avail a voucher.
- Enter the theme park. While returning, sign your name in the voucher. Unsigned vouchers will not be allowed to be taken out of the park.
- After the visit, the ticket counter takes back your ticket.
- You can use vouchers signed with your name to visit the park again.
This procedure has a flaw: the Chefs can exchange unsigned vouchers inside the park.
Chefs thought of exploiting this flaw. What is the minimum number of tickets they should buy?
QUICK EXPLANATION:
Let s be the sum of the $t_i$s. Then the answer is \max(n, \lceil s/2 \rceil), where \lceil x \rceil denotes the ceiling function.
EXPLANATION:
Let’s weaken the restrictions of the problem a bit, and say we allow to exchange vouchers anywhere, anytime, even the signed ones. What is the minimum number of tickets they should buy? Obviously, the answer to this problem will not exceed the answer to the original problem. But this problem is easier to solve! Each ticket will provide one voucher, so it will provide for two visits by any two Chefs. Since there are t_1 + t_2 + \ldots + t_n visits all in all, you only need to buy k tickets such that 2k \ge t_1 + t_2 \ldots + t_n. In other words, k = \left\lceil \frac{t_1 + t_2 + \ldots + t_n}{2} \right\rceil, where \lceil x \rceil denotes the ceiling function.
Thus, we now have a lower bound for the original problem: Let s = t_1 + t_2 + \ldots + t_n. Then the answer is at least \lceil s/2 \rceil. And you can also try some random cases and find that the answer \lceil s/2 \rceil is usually achievable. But not always! For example, suppose each t_i = 1, i.e., each Chef wants to visit only once. Then each Chef will have to buy one ticket, because they can only exchange vouchers inside the park. But this means that the answer is already n, which is greater than our lower bound in this case: \lceil s/2 \rceil = \lceil n/2 \rceil.
In fact, each Chef is required to buy at least one ticket, which gives us another lower bound: n. Combining the lower bounds we have, we get the tighter lower bound of \max(n, \lceil s/2 \rceil).
We ask again this time: Is there still a case where the answer is greater than this bound? Amazingly, the answer is no this time! Here we’ll show an algorithm that uses exactly \max(n, \lceil s/2 \rceil) tickets:
-
If s \le 2n, we want to show that we can solve the problem with just \max(n, \lceil s/2 \rceil) = n tickets. First, all Chefs buy one ticket each, and then give their vouchers to the Chefs who want more visits. Because s \le 2n, there will be enough vouchers for everyone. Thus, we only need n tickets.
-
If s > 2n, we want to show that we can solve the problem with just \max(n, \lceil s/2 \rceil) = \lceil s/2 \rceil tickets. If s > 2n, there is at least one t_i that is \ge 3. (Why?) So, while s > 2n, take such a Chef with t_i \ge 3, have him/her buy a ticket, and have him/her consume the ticket and the voucher for himself/herself. Repeat this until the sum s becomes \le 2n, in which case s can only be 2n or 2n-1. In this case, we do the same procedure as in the first case, and we will need n tickets.
So how many tickets did we use? Suppose we repeated the first step k times. In other words, k is the smallest integer satisfying s - 2k \le 2n. Then we used up k + n tickets all in all. But the smallest integer k satisfying s - 2k \le 2n is k = \left\lceil \frac{s - 2n}{2} \right\rceil, which means the number of tickets we used is k + n = \left\lceil \frac{s - 2n}{2} \right\rceil + n = \left\lceil \frac{s}{2} \right\rceil!
Thus, the answer is \max(n, \lceil s/2 \rceil).
Implementation Detail: The answer requires ceiling division, but integer division in many programming languages is usually floor division. Thankfully, we can compute \lceil s/2 \rceil using floor using the following equality:
(take note that this only works for integers.)
Time Complexity:
O(n)