Practice

Contest

CAKEWALK

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

2 Likes

my program give wrong answer just I forgot “at least M meatballs in total” .this happen second time first time I forgot to write “\n” after every output and know just “==” always my program give wrong answer and I lost 1 point

1 Like

The editorial solution is faster and a little easier to code than mine (considering a sorting algorithm is at reach). I have a lot to improve in short contests, the pressure always gets to me. I take more time than usual and a lot of times I make stupid mistakes. Although my solution wasn’t so bad I should have tought about this solution first (I solved a reasonable amount of problems similar to this one). I used bitmasks instead since the constraints were low. BTW any suggestions for handling the pressure in this type of contest would be higly appreciated.

I know that pressure thing very very well. Maybe there will be a better advice, but my experience tells, that you have to compete in contests to get confidence, that’s all

Before I was switching the division often because of that pressure, it seems that I’m ready to stay blue - http://community.topcoder.com/tc?module=MemberProfile&cr=22101631

As I always say, contest is the best practice.

2 Likes

@junior94 >> Not suggestion, but I would like to share some things to stay cool during these cook-offs. First, start with thinking that you have to solve only 2 questions in 2.5 hours, that translates to 1.25 hours per question! Thats it. It will relieve a lot of stress. And I saw it helped me, I did one problem in 15 minutes, another in 10 minutes, but just forgot to check for one special case where I failed and then I dint want to think over more problems and was disappointed and crashed. But, wish you better luck for next cook-offs.

1 Like

I did the same thing but sorted the plates in ascending order and then traversed the array in backward direction till sum of the no of meat balls >=m, but it gave wrong ans again and again…

shouldn’t it be pj >= pi(j-1) instead of pj >= pij ??

http://www.codechef.com/viewsolution/2070019

1 Like

For input

``````2
1 1
1
1 1
1
``````

your code returns 11 - see http://ideone.com/ABww3A

The j’th largest plate globally is atleast as large as the j’th largest plate of the optimal solution.

http://www.codechef.com/viewsolution/2070449
Plz help…cannot find the mistake.

http://www.codechef.com/viewsolution/2167470 plz help find the mistake,

WOW I don’t understand this at all! So lost…

What does “converting an optimal solution to your greedy solution” mean? Why to convert an “optimal solution”??

1 Like