MINIONS - Editorial

Did you try this proof-

Q- Given a sorted array C[] such that C1≤C2≤C3≤…≤Ck, prove that C1 ≤(C1+C2)/2≤(C1+C2+C3)/3.

Because of the inequality given in the question. In my approach ,I fixed the size of the subset ( let it be k ) and current minimum to be pow. Then pow >= (b1 + b2 + … bk) / k which is nothing but pow * k >= (b1 + b2 + … bk) . Therefore using greedy approach it makes sense to take the minimum k values of B array. Hope it helps. Let me know if something is unclear.

Yes, I tried that proof. When searching for appropriate subset, why does popping minimum element in array B work ?

You want fit in as many balls in a bag of weight W. What do you chose? Lighter balls or heavy balls? We only have to maximise number of balls in bag.

Then apply the logic to current scenario. Thanks @tihorsharma123 for helping me :slight_smile:

complexity O(nlogn)
Nice Approach @tihorsharma… got Ac in java
https://www.codechef.com/viewsolution/18943916

No problem :slight_smile: @vijju123

1 Like

Thank you :slight_smile:

1 Like

i do agree with you that it would be so appreciable if setter has added comments in his code , that would make it lot easier.

All the test cases were maximal, so official cases wont help. I will try to add few more cases.

issue solved i was using int instead of long long .

Will inform him that his solution got hacked xD. Nice job. The setter’s solution (used to make TC) is correct. The idea is also correct, he made a minor bug in implementation, so no major problem. Thanks :slight_smile:

Good job dear. Hope you liked the editorial :slight_smile: