Problem context and objectives
Mission briefing
Signal rescue operator · A beacon is hidden inside an ordered frequency band
Lock onto the signal without testing every frequency: The Cargo Capacity.
Each probe costs precious time; searching the wrong half moves the rescue team farther away.
How you win
- 1Recognize when Greedy feasibility plus answer search matches the clues
- 2Keep this true after every move: left excludes every impossible capacity and right remains sufficient
- 3Reach the result within O(n log sum weights)
Rules and pressure
- Target cost: O(n log sum weights)
- State rule: left excludes every impossible capacity and right remains sufficient
Lesson 1 of 3
Live algorithm trace
Greedy feasibility plus answer search
Complete execution1 of 8
Capacity cannot be below the heaviest package or above the total weight.
1
left, right = max(weights), sum(weights)2
capacity = midpoint3
greedily count required days4
if required <= days: right = capacity5
otherwise left = capacity + 16
return leftdays = 5left = 10right = 55
Truth to preserve / Cost target
Truth to preserve
left excludes every impossible capacity and right remains sufficient
Cost target
O(n log sum weights)
For a proposed capacity, greedily fill each day in order and start a new day only when the next package would overflow. Feasibility is monotonic as capacity increases.
Your call · What should guide every step of this algorithm?