Problem Link:
Difficulty:
CAKEWALK
Pre-requisites:
ad-hoc
Problem:
You have N plates of meatballs, the ith having Pi meatballs. What is the minimum number of plates you need to choose so that you have atleast M meatballs in total.
Explanation:
Sort the plates in descending order of meatballs. Then keep adding plates until you cross the threshold M. This number is your answer.
Proof of Correctness:
This is a greedy way of choosing your plates. Most greedy algorithms are proved using some kind of switching method - by converting an optimal solution to your greedy solution. We use this method here too.
After sorting, we know that greedy has chosen p1, p2, p3, …, pg. Let us assume an optimal solution chooses plates pi1, pi2, …, piOPT. We wish to transform the optimal solution to greedy. We know that:
p1 + p2 + … +
pg >= M,
p1
- p2 + … + pg-1 < M, and
pi1 +
pi2 + … +
piOPT >= M.
Let j be the first index from i1, i2, i3, …, iOPT that does not match the greedy choice. That is, i1 = 1, i2 = 2, …, ij-1 = j-1. Now, pj >= pij, and so the choice (i1, i2, i3, …, ij-1, j, ij+1, …, iOPT) also satisfies sum of number of meatballs >= M.
By repeating this switching, we have transformed this OPT into Greedy. But since OPT has the optimal number, thus greedy must also have the optimal number (since p1 + p2 + … + pg-1 < M).
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
