PROBLEM LINKSAuthor: Constantine Sokol DIFFICULTY:simple PREREQUISITES:Greedy Algorithms HINTSort the array and see if you can figure out some property which will allow you to compute the solution in a greedy manner. EXPLANATIONWe will solve this in a greedy manner. The key idea is to have as many nonfailed packages as possible for this we have to just have maximum number of halfsolved (+1 for odd numbers) packages which is possible only if pick up the packages with smaller number of tasks first. Hence we will sort array first and start seeing how many packages can we halfsolve without crossing our limit of X. At this moment it is possible that we have not exceeded the quota of X tasks. So we will again start from package will smallest number of tasks and see how many packages we can completely solve. Here is a complete algorithm. Sort the array A in ascending order.
Let the value of successfulPackages be 0 initially Now traverse the array A from left to right (you would not need to go beyond the point where you broke out in the previous iteration), for each array entry (denoting a package),
Report the values failedPackages and successfulPackages Comments on subtasks: subtask1: Since A1 + A2 + ... + AN ≤ X we can solve all the tasks. So the the number of failed packages will be 0 and the number of successful packages will be N. So the answer is “0 N” for this subtask. subtask2,3,4: Not sure of any elegant solutions which are worse than our greedy solution in time complexity. If somebody solves this by alternate means we will make a mention here. SOLUTIONSSetter's Solution: MIKE2.cpp
This question is marked "community wiki".
asked 29 Dec '13, 15:35

Can anyone tell me which case am I missing in this
answered 29 Dec '13, 15:51
1
well your breaking condition seems to be faulty... i removed some unecessary conditions and got ac.. here is the link of AC code http://www.codechef.com/viewsolution/3146808 i just changed the conditions 1) while(i<n&&x>0) to while(i<N) 2) removed the else block
(31 Dec '13, 18:06)

Sorry to be opening an old thread again. But i am not sure about the solution given in the editorial. Consider the example 3 8 4 4 20 Now, what i am able to understand is that the correct answer is 0 2 (0 failed 2 successsful). But with the testers solution, i am getting 1 2. what is the expected answer for this case?
link
This answer is marked "community wiki".
answered 12 Apr '14, 00:24
Tester's solution gives the correct answer: we shall solve first two packages and that's it. We cannot solve the halves of all given packages since 2 + 2 + 10 = 14 is greater than 8.
(12 Apr '14, 19:49)

Can someone please explain how the solution to this test case is 0 3 (0 failed 3 passed) as per setter and testers solution by I am getting 0 4 as the solution.
My Explanation : Remaining tasks after allotment of 9 tasks. 2 0 0 0 0 . Success appears to be 4 instead of 3. answered 23 Oct '16, 15:29
