Editorial for TLE '16 Contest 4 P1 - Stack of Presents
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
We can solve this problem using a greedy algorithm. First, sort the presents in non-decreasing order of weight. Then, iterate through the presents while keeping track of the cumulative weight so far. If the current present's weight is not less than the cumulative weight, add it to the stack.
The proof of the greedy algorithm is as follows:
For the sake of contradiction, assume that the greedy solution is not optimal.
The greedy solution selects presents
The optimal solution selects the lightest presents
There is a maximal value of
Since
Time complexity:
Comments