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

×

CHEFPARTY - Editorial

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

This question is marked "community wiki".

asked 17 Feb, 19:16

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 13 Mar, 14:29

admin's gravatar image

0★admin ♦♦
19.8k350498541


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?

link

answered 22 Feb, 15:21

roha2's gravatar image

2★roha2
12714
accept rate: 20%

2

Anti quick sort cases are possible.

(22 Feb, 15:35) vijju123 ♦♦5★

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
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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