CHEFPARTY - Editorial

chefparty
cook103
easy
editorial
sorting

#1

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Michael Nematollahi
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy

PREREQUISITES:

sorting

PROBLEM:

Chef is holding a party. He wants to invite N friends. However, his friends are demanding. The i_{th} friend states that if he arrives at Chef’s house and there are less than A_i people in the house (excluding Chef) he would just leave and never return back. Chef is wondering what’s the maximum number of friends that will attend the party. Chef is able to schedule the order of his friends’ arrivals. So you must help him to decide the best order of arrivals.

N \, \leq \, 10^5

EXPLANATION:

If we think a little bit, the best strategy is to invite friends sorted by their A values in ascending order. (Why?)

Suppose we have the x_{th} friend and the y_{th} friend such that A_x \, < A_y. It’s always better to invite the x_{th} one before. Because if we do the opposite, since A_x \, < A_y there’s a chance that the demand of y is not met and he leaves immediately. If we invite x before and he joins the party, we increase the number of people at the party getting close to y demand. On top of that, If we invite y before and he joins the party then x will join the party for sure (and this doesn’t make sense) so better to invite him before.

After we sort them according to A values, we iterate through friends list inviting them one by one. If the current friend can join the party, he’s welcome :slight_smile: . Otherwise, we should just break and we have our answer (because all upcoming friends have larger demands so they would never be able to enter).

Since N may reach 10^5 we must use a fast sorting algorithm (merge sort, quick sort… etc).

You can use standard sort function in C++ or Java which runs in O(N \, log \, N).

Check implementations for more details.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution


#2

Admin look into this:
https://www.codechef.com/viewsolution/23180064
The above link is using quick sort&it gives time limit exceeded.
https://www.codechef.com/viewsolution/23180071
This is using sort() function in c++.It gives correct answer.Only difference is I have replaced Quicksort() with sort().This means that you don’t get correct solution using quick sort.
Am i correct?


#3

Anti quick sort cases are possible.


#4

Thank you.With merge sort the answer is correct.I tried randomised quick sort.https://www.codechef.com/viewsolution/23183538 (taken from geeksforgeeks)
It still gives TLE.Does it mean that one of the input in test case is worst case of quick sort O(N^2)&that this problem is unsolvable using quick sort?


#5

Please do reply to my query.Tell me if I am wrong.