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

×

MIKE2 - Editorial

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

This question is marked "community wiki".

asked 29 Dec '13, 15:35

vaka's gravatar image

2★vaka ♦♦
253131822
accept rate: 16%

edited 29 Dec '13, 16:10


Can anyone tell me which case am I missing in this

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

answered 29 Dec '13, 15:51

dush22's gravatar image

3★dush22
614
accept rate: 0%

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

link
This answer is marked "community wiki".

answered 12 Apr '14, 00:24

anantkaushik89's gravatar image

4★anantkaushik89
1116
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.

link

answered 23 Oct '16, 15:29

your_goru's gravatar image

2★your_goru
1
accept rate: 0%

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,482
×1,159
×982
×12
×3

question asked: 29 Dec '13, 15:35

question was seen: 2,351 times

last updated: 23 Oct '16, 15:29