PROBLEM LINK:Author: Hasan Jaddouh 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 :) . 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:
This question is marked "community wiki".
asked 17 Feb, 19:16

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
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)
Please do reply to my query.Tell me if I am wrong.
(23 Feb, 22:26)
