You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFPARTY - Editorial

Tester: Michael Nematollahi
Editorialist: Hussain Kara Fallah

Easy

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 :) . 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:

TESTER's solution

This question is marked "community wiki".

asked 17 Feb, 19:16

1181234
accept rate: 0%

19.8k350498541

 0 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? answered 22 Feb, 15:21 2★roha2 127●1●4 accept rate: 20% 2 Anti quick sort cases are possible. (22 Feb, 15:35) 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? (22 Feb, 23:28) roha22★ Please do reply to my query.Tell me if I am wrong. (23 Feb, 22:26) roha22★
 toggle preview community wiki:
Preview

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×801
×43
×7

question asked: 17 Feb, 19:16

question was seen: 442 times

last updated: 13 Mar, 14:29