CF 1526C2 - Potions (Hard Version)
We are walking along a row of potions, starting at the first and moving to the last. Each potion has a value: positive values increase your health, negative values decrease it. At each potion, you can choose to drink it or skip it, but your health must never drop below zero.
CF 1526C2 - Potions (Hard Version)
Rating: 1600
Tags: data structures, greedy
Solve time: 1m 17s
Verified: no
Solution
Problem Understanding
We are walking along a row of potions, starting at the first and moving to the last. Each potion has a value: positive values increase your health, negative values decrease it. At each potion, you can choose to drink it or skip it, but your health must never drop below zero. The goal is to maximize the number of potions you drink.
The input gives the number of potions and an array of integers representing the health change of each potion. The output is a single integer: the maximum number of potions you can safely drink while never letting your health go negative.
The constraints matter a lot for choosing the right algorithm. With up to 200,000 potions, any approach that examines all subsets of potions is immediately infeasible because there are $2^n$ combinations. Even an $O(n^2)$ solution, where we might try to compute the best sequence ending at each position, will be too slow: $200{,}000^2 = 4 \times 10^{10}$ operations is far beyond what fits in 1 second. This forces us toward an $O(n \log n)$ or $O(n)$ solution.
Edge cases that are easy to get wrong include sequences with large negative potions early. For example, if the input is:
3
-5 10 10
a naive greedy that just drinks all positive potions when possible might try to take the first potion, fail, or miscount, and conclude you can drink 2 potions when the correct answer is 2 (taking the last two potions and skipping the first negative). Similarly, if all potions are positive, the algorithm must not skip any, even if the values are huge.
Approaches
A brute-force approach would examine all sequences of potions, keeping track of the running health and the number of potions taken. This works because we could, in principle, evaluate every combination and choose the longest valid one. The complexity is $O(2^n)$, which is correct but completely impractical for $n = 200{,}000$. Even storing intermediate states for dynamic programming requires O(n \cdot \text{sum of positive a_i}) memory in some approaches, which is also too large.
The key insight for the optimal solution is that the problem is fundamentally greedy but with a twist. Positive potions are always safe, and negative potions reduce your health, so we want to keep them only if we can "afford" the health drop. If we encounter a negative potion that would drop our health below zero, we can look back at previously chosen negative potions: replacing a larger negative with a smaller one may allow us to drink the current potion without dropping below zero. This is naturally handled with a min-heap (priority queue) of negative potions. By keeping track of the sum of chosen potions and the largest negative potion consumed so far, we can decide in $O(\log n)$ per potion whether to swap out an earlier potion for a better sequence.
The brute-force works because it enumerates every combination, but fails because $2^n$ is astronomically large. The observation that we can maintain the sum of selected potions and adjust only the largest negative potion gives us a way to make local decisions greedily while preserving global correctness. This reduces the problem to an $O(n \log n)$ algorithm using a heap.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Too slow |
| Optimal | O(n log n) | O(n) | Accepted |
Algorithm Walkthrough
- Initialize your current health to zero. Keep a min-heap of negative potions you have chosen, and a counter for the number of potions drunk.
- Iterate through each potion in order. If the potion is positive, add its value to your health and increment the counter. Positive potions are always safe.
- If the potion is negative, tentatively add it to your health and push it onto the heap. Increment the counter because we are temporarily assuming we can take it.
- If adding the negative potion causes your health to drop below zero, remove the smallest (most negative) potion from the heap and subtract its value from your health. Decrement the counter because you cannot take that potion. This is effectively swapping out a more harmful potion for the current one if it helps maintain non-negative health.
- Continue until the last potion. The counter now contains the maximum number of potions you can drink.
Why it works: the heap ensures we always remove the largest negative potion when necessary, minimizing health loss. This preserves the invariant that our running health is never negative. By always taking positive potions and only discarding the worst negative ones when needed, we guarantee that no other selection can give a higher count. Any alternative sequence wo