P1Z2S - Editorial

PROBLEM LINK:

Contest
Practice

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:

\left\lceil \frac{s}{2} \right\rceil = \left\lfloor \frac{s+1}{2} \right\rfloor

(take note that this only works for integers.)

Time Complexity:

O(n)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

1 Like

https://www.codechef.com/viewsolution/10148598
whats wrong with this solution

Hi @vishalrox as explained in editorial minimum number of tickets needed is not always if(sum is odd) { sum/2 +1 } else { sum/2}.
Answer can be minimum n, when each of the n chefs want just 1 visit.

To quote editorial which helped me, hope it helps you too.
"Thus, we now have a lower bound for the original problem: Let s=t1+t2+…+tns=t1+t2+…+tn. Then the answer is at least ⌈s/2⌉⌈s/2⌉. And you can also try some random cases and find that the answer ⌈s/2⌉⌈s/2⌉ is usually achievable. But not always! For example, suppose each ti=1ti=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 nn, which is greater than our lower bound in this case: ⌈s/2⌉=⌈n/2⌉⌈s/2⌉=⌈n/2⌉.

In fact, each Chef is required to buy at least one ticket, which gives us another lower bound: nn. Combining the lower bounds we have, we get the tighter lower bound of max(n,⌈s/2⌉)max(n,⌈s/2⌉)."

#include
#include
using namespace std;

int main() {
int n;
cin>>n;
long long s=0;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
s+=a;
}
if(s==n)
cout<<n;
else
cout<<ceil((s)/2.0);
}

I have used the same concept that if (s==n) when each chef wants one visit answer is n. else it is ceil(s/2.0).

2 Likes

ty @varunvyas got it.

https://www.codechef.com/viewsolution/10151041 could you please tell me what is wrong with this solution? I got every test case correct when I checked.

Could someone explain the case of s>2n in detail?

Alter native solution would have been, first count the number of people who want to visit exactly one(let count be variable assigned to it). Now we calculate the sum of number of times remaining people want to go (let variable assigned to it be sum).
Then the answer must be (sum/2)+count(sum is even) or (sum/2)+count+1 if sum is odd.
Here is my answer and according to me algorithm implemented by me is correct as all the test cases I thought(around 20) were working perfectly.
Some one please tell me the error.
https://www.codechef.com/viewsolution/10145673

@vishalrox …your program fails for testCase

5

1 1 1 1 1