MIKE2 - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Contest

Practice

Author: Constantine Sokol

Tester: Roman Rubanenko

Editorialist: Praveen Reddy Vaka

DIFFICULTY:

simple

PREREQUISITES:

Greedy Algorithms

HINT

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

EXPLANATION

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.

SOLUTIONS

Setter’s Solution: MIKE2.cpp

Tester’s Solution: MIKE2.cpp

Editorialist’s Solution: MIKE2.java

2

Can anyone tell me which case am I missing in this

http://www.codechef.com/viewsolution/3138770
3

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
1 Like
4

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?

5

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.

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.