Problem #29 MEDIUM
The Desert Stockpile
Amazon Microsoft Optimization Logic
Problem Statement
An explorer needs to cross a desert that is exactly 1,000 miles wide. She can carry at most 1,000 units of food at a time and consumes exactly 1 unit per mile traveled in any direction. She starts at the western edge with a stockpile of 3,000 units. Food can be cached anywhere in the desert and retrieved later. What is the maximum number of food units she can deliver to the eastern edge?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Approximately 533 food units delivered. Key: cache at mile 200 (cost drops from 5 to 3 units/mile) and mile 533⅓ (cost drops to 1 unit/mile). Each phase runs until exactly one load is consumed.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Think of the journey in phases. When you have k full loads, moving 1 mile of progress requires k forward trips and k−1 return trips, costing 2k−1 food units per net mile forward.
Step 1: Phase 1: Explorer has 3,000 units — exactly 3 full loads. Each net forward mile costs 2×3−1 = 5 units. She makes 3 forward trips and 2 return trips per segment.
Step 2: Run Phase 1 until one full load is consumed: 1,000 units used ÷ 5 units/mile = 200 miles. At mile 200, she has 2,000 units cached.
Step 3: Phase 2: 2,000 units at mile 200 — exactly 2 full loads. Each net forward mile costs 2×2−1 = 3 units.
Step 4: Run Phase 2 until another load is gone: 1,000 units ÷ 3 units/mile = 333⅓ miles. At mile 533⅓, she has 1,000 units.
Step 5: Phase 3: 1,000 units remain, 466⅔ miles left to travel. One load, cost = 1 unit/mile.
Step 6: Units delivered = 1,000 − 466⅔ = 533⅓ units. (Approximately 533 whole units in practice.)
Key Insight:
The cost per mile drops from 5 to 3 to 1 as the number of required loads decreases. The optimal breakpoints are where exactly one full load's worth of food has been consumed in each phase — these minimize total food spent on repositioning.