COOLING - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

The following greedy algorithm always finds the optimum answer:

  • Choose the lightest pie not yet on a rack

  • If none of the remaining racks can hold this pie, stop

  • Of all the racks that can hold this pie, place the pie on the rack with the smallest weight limit

  • If there are no more pies, stop. Otherwise, go back to step 1

TESTER’S SOLUTION

Can be found here.

5 Likes

alt text

http://codepad.org/MuvFppO6

plz help me. I cannot find what is wrong in this code.

As the value of the number of pies and also the number of racks is equal to N.
So answer will never be greater than N so we can only check for number of pies fit into the racks
and print it.So that their is no need of checking of end of pies.If in case number of pies equals to N then all the racks get finished and answer will be N.

Means Simply as only one pies can be put in the rack if pies get finished rank will definitely get finished. So simply check for the end of racks and not about end of pies.

I don’t know greedy algorithm yet,I have a slightly simpler approach but I’m not able to get the correct answer, please give it read:

I take in the values of weights of pies in an array and weight limit in another.

I sort both the arrays using sort()

I run a loop from first to last, and if weight of pie>weight limit, counter++

I display (n-counter)

1 Like

@rohandtuse Your logic Fails in this case
4
8 8 10 11
7 7 9 9

2 Likes

may i know what’s wrong with code??

@rohanndtuse
See why the logic is wrong.
Let the pies be 5 10.
Let the weight be 4 8.
Here, your code will return 0 but answer is 1.
5 can go in 8

@rohanndtuse
See why the logic is wrong.
Let the pies be 5 10.
Let the weight be 4 8.
Here, your code will return 0 but answer is 1.
5 can go in 8

Hi
I had one query. Here you take the pies one by one and solve it via greedy algorithm. What if one takes it rack by rack. That is, i choose the first rack, see how many pies can be positioned on it and choose the one with the highest weight, and iterate over it. I could not think of a case where it should not work. But i wanted your take on it too?

That should work too

The answer is 2?

If I use the approach in reverse . First find rack for highest one? should it work?