# Problem Link:

# Difficulty:

CAKEWALK

# Pre-requisites:

ad-hoc

# Problem:

You have **N** plates of meatballs, the ith having **P _{i}** 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 p_{1}, p_{2}, p_{3}, …, p_{g}. Let us assume an optimal solution chooses plates p_{i1}, p_{i2}, …, p_{iOPT}. We wish to transform the optimal solution to greedy. We know that:

p

_{1}+ p_{2}+ … +

p_{g}>= M,

p_{1}

- p
_{2}+ … + p_{g-1}< M, and

p_{i1}+

p_{i2}+ … +

p_{iOPT}>= M.

Let j be the first index from i_{1}, i_{2}, i_{3}, …, i_{OPT} that does not match the greedy choice. That is, i_{1} = 1, i_{2} = 2, …, i_{j-1} = j-1. Now, p_{j} >= p_{ij}, and so the choice (i_{1}, i_{2}, i_{3}, …, i_{j-1}, *j*, i_{j+1}, …, i_{OPT}) 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 p_{1} + p_{2} + … + p_{g-1} < M).

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here