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


MIKE2 - Editorial



Author: Constantine Sokol
Tester: Roman Rubanenko
Editorialist: Praveen Reddy Vaka




Greedy Algorithms


Sort the array and see if you can figure out some property which will allow you to compute the solution in a greedy manner.


We will solve this in a greedy manner. The key idea is to have as many non-failed packages as possible for this we have to just have maximum number of half-solved (+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 half-solve 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 completedTasks be 0 initially
Let the value of failedPackages be N initially
Now traverse the array A from left to right, for each array entry (denoting a package)

  • taskCount = Number of tasks needed to be solved so that the package is not a failure
  • if (completedTasks + taskCount > X) break out of the for loop
  • increase the value of completedTasks by taskCount
  • decrease the value of failedPackages by 1

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),

  • taskCount = (Number of tasks in the package - Number of tasks needed to be solved so that the package is not a failure) //more tasks that need to be solved to mark the package successfully
  • if (completedTasks + taskCount > X) break out of the for loop
  • increase the value of completedTasks by taskCount
  • increase the value of successfulPackages by 1

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.


Setter's Solution: MIKE2.cpp
Tester's Solution: MIKE2.cpp
Editorialist's Solution:

This question is marked "community wiki".

asked 29 Dec '13, 15:35

vaka's gravatar image

2★vaka ♦♦
accept rate: 16%

edited 29 Dec '13, 16:10

Can anyone tell me which case am I missing in this

answered 29 Dec '13, 15:51

dush22's gravatar image

accept rate: 0%


well your breaking condition seems to be faulty... i removed some unecessary conditions and got ac.. here is the link of AC code 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) yagyank3★

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?

This answer is marked "community wiki".

answered 12 Apr '14, 00:24

anantkaushik89's gravatar image

accept rate: 0%

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) kostya_by ♦♦6★

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.

5 9 3 3 1 1 3

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

your_goru's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 29 Dec '13, 15:35

question was seen: 2,351 times

last updated: 23 Oct '16, 15:29