CF 1526C1 - Potions (Easy Version)

CF 1526C1 - Potions (Easy Version)

Rating: 1500
Tags: brute force, data structures, dp, greedy
Solve time: 1m 43s
Verified: yes

Solution

Problem Understanding

We have a sequence of potions lined up, each changing our health by some integer value, which can be positive or negative. We start with zero health and move from the first potion to the last. At each step, we can choose to drink the potion or skip it, but our health must never go below zero. The goal is to maximize the number of potions we drink.

Because the input size in this easy version is limited to $n \le 2000$, we can consider solutions that are quadratic in $n$, but anything above that will likely exceed the time limit. Health values themselves can be very large (up to $10^9$ in magnitude), so we need to be careful with cumulative sums to avoid integer overflow in languages without automatic big integers, although Python handles this naturally.

Some edge cases can trick a naive implementation. If all potions are negative, the correct output is zero, because drinking any potion would immediately drop health below zero. Another subtle case is a sequence like [5, -10, 5]. A naive greedy approach of always drinking positive potions and skipping negatives may fail, because sometimes accepting a small negative allows drinking more potions later.

Approaches

A brute-force solution would try every subset of potions in order and track whether the health remains non-negative. For each potion, we branch into two possibilities: take it or skip it. This gives $2^n$ combinations. Even for $n = 20$ this is already over a million possibilities, and with $n = 2000$ it is completely infeasible. The brute force works because it enumerates all possibilities, but it fails for large $n$ because the operation count grows exponentially.

The key insight comes from observing that we only care about maintaining non-negative health and maximizing the number of potions. If we greedily try to drink potions in order, we only need to track which negative potions we’ve accepted and potentially replace larger negative ones with smaller ones if doing so keeps health non-negative. This can be efficiently implemented using a min-heap (priority queue). Each time we drink a potion, we add its value to our current health sum. If the sum ever drops below zero, we remove the most damaging potion we drank so far (the smallest value in the heap), which restores the health while keeping the count of potions maximal for that prefix. Positive potions never decrease health and can always be added.

This observation reduces the solution to $O(n \log n)$ because each insertion and deletion from the heap costs $O(\log n)$, and we only process each potion once. This is well within the limits for $n = 2000$.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(2^n)	O(n)	Too slow
Optimal (Heap-based Greedy)	O(n log n)	O(n)	Accepted

Algorithm Walkthrough

1. Initialize a variable health = 0 to track the current health and a min-heap taken to store the values of potions we decide to drink.
2. Iterate through the potion array. For each potion a[i], add it to health and push it into the heap. We always try to drink the current potion to maximize the count.
3. After adding a potion, check if health is negative. If so, pop the smallest potion from the heap and subtract its value from health. This effectively discards the most harmful potion we’ve drunk so far, keeping the health non-negative.
4. Continue until all potions are processed. The size of the heap at the end gives the maximum number of potions we can drink while maintaining non-negative health.

Why it works: The heap always keeps the potions we have committed to drinking in order of increasing health impact. By discarding the most negative potion whenever we risk dropping below zero, we maximize the number of potions without ever violating the health constraint. Positive potions are never removed, and negative potions are removed only if absolutely necessary, which ensures the final count is optimal.

Python Solution

import sys
import heapq
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

health = 0
taken = []

for potion in a:
    health += potion
    heapq.heappush(taken, potion)
    if health < 0:
        smallest = heapq.heappop(taken)
        health -= smallest

print(len(taken))

The solution initializes health and a min-heap taken. For each potion, we add it to health and push it into the heap. If health drops below zero, we remove the most harmful potion from taken, which restores non-negative health. The length of the heap at the end is exactly the maximum number of potions we can drink. Care must be taken to push negative values into the heap correctly and subtract them when removing from health.

Worked Examples

Sample 1:

Input: [4, -4, 1, -3, 1, -3]

Step	Potion	Health	Heap	Action
1	4	4	[4]	Drink
2	-4	0	[-4, 4]	Drink
3	1	1	[-4, 4, 1]	Drink
4	-3	-2	[-4, -3, 1, 4]	Health < 0, pop -4 → health = 2
5	1	3	[-3, 1, 1, 4]	Drink
6	-3	0	[-3, -3, 1, 4, 1]	Drink

Heap size = 5, matches output. This trace shows the heap correctly discarding the worst negative potion to maintain non-negative health.

Custom Input 2: [5, -10, 5]

Step	Potion	Health	Heap	Action
1	5	5	[5]	Drink
2	-10	-5	[-10, 5]	Health < 0, pop -10 → health = 5
3	5	10	[-10, 5, 5]	Drink

Heap size = 2, cannot drink all three without going negative.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each potion is pushed into a min-heap and potentially popped once, costing O(log n) per operation
Space	O(n)	The heap stores at most all n potions

For $n \le 2000$, $n \log n$ operations are under 20,000, which fits comfortably under 1 second, and the heap easily fits in 256 MB.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n = int(input())
    a = list(map(int, input().split()))
    import heapq
    health = 0
    taken = []
    for potion in a:
        health += potion
        heapq.heappush(taken, potion)
        if health < 0:
            health -= heapq.heappop(taken)
    return str(len(taken))

# provided sample
assert run("6\n4 -4 1 -3 1 -3\n") == "5", "sample 1"

# custom cases
assert run("3\n5 -10 5\n") == "2", "negative recovery"
assert run("5\n-1 -2 -3 -4 -5\n") == "0", "all negative"
assert run("4\n1 1 1 1\n") == "4", "all positive"
assert run("1\n-1000000000\n") == "0", "single huge negative"
assert run("5\n10 -1 -2 5 -3\n") == "5", "mixed positive and negative"

Test input	Expected output	What it validates
3\n5 -10 5	2	Handles negative that must be skipped to maintain health
5\n-1 -2 -3 -4 -5	0	Cannot drink any negative-only potions
4\n1 1 1 1	4	Drinks all positive potions
1\n-1000000000	0	Single large negative potion
5\n10 -1 -2 5 -3	5	Mixed sequence with selective negative removal

Edge Cases

For input [5, -10, 5], the heap starts with [5] after the first potion. Adding -10 drops health to -5, so we pop -10. Health returns to 5, and we can then safely drink the last potion, ending with health 10. Output is 2, exactly the maximum possible. This confirms that the algorithm correctly discards the most harmful potion in a running prefix to maximize count without violating the non