Minimum Time to Kill All Monsters

Minimum Time to Kill All Monsters

What is this problem about?

The Minimum Time to Kill All Monsters problem gives you monsters, each requiring a certain number of attacks to kill. You accumulate attack power over time (starting from 1 and gaining +1 per day), and each monster costs a fixed number of attacks. When you kill a monster, your daily attack power gain increases by 1. Find the minimum number of days to kill all monsters. This Minimum Time to Kill All Monsters coding problem uses bitmask DP to optimize kill order.

Why is this asked in interviews?

Trilogy asks this hard problem to test bitmask DP with state-dependent transitions — specifically, the order in which monsters are killed changes your power gain rate, affecting how long subsequent kills take. The array, bitmask, bit manipulation, and dynamic programming interview pattern is central. It's a smaller-scale TSP-like problem where order matters for total cost.

Algorithmic pattern used

Bitmask DP. State: dp[mask] = minimum days to kill exactly the set of monsters in mask. The number of monsters killed so far (popcount(mask)) determines the current daily power gain (= gain + popcount(mask)). For each mask, try killing each unkilled monster next: dp[mask | (1<<i)] = min(dp[mask | (1<<i)], dp[mask] + ceil(health[i] / current_gain)). Final answer: dp[(1<<n)-1].

Example explanation

Monsters: health = [3, 4, 5]. Base gain = 1.

• Kill monster 0 first: days = ceil(3/1) = 3. Now gain = 2.
• Kill monster 1 next: days = ceil(4/2) = 2. Now gain = 3.
• Kill monster 2 last: days = ceil(5/3) = 2. Total = 3+2+2 = 7.

Try other orders via bitmask DP to find the minimum.

Common mistakes candidates make

• Using gain = 1 throughout instead of base_gain + popcount(mask).
• Not memoizing DP states (pure recursive backtracking is too slow for n=20+).
• Forgetting that the gain updates immediately after each kill.
• Integer division instead of ceiling division for days per kill.

Interview preparation tip

Bitmask DP problems where "the cost depends on how many items have been processed so far" are common in combinatorial optimization interviews. The pattern: popcount(mask) gives the count of processed items, which determines the current state parameter (here: daily gain). Practice computing popcount efficiently and building masks bit by bit. After this problem, try variations where the cost depends on the specific items chosen (not just the count) — those require tracking accumulated state differently in the DP.