We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Kill All Monsters

Number: 2537

Difficulty: Hard

Paid? Yes

Companies: Trilogy

Problem Description

You are given an array power where power[i] is the power required to defeat the iᵗʰ monster. You start with 0 mana and a daily mana gain equal to 1. Every day, you gain mana equal to your current gain. When your accumulated mana reaches or exceeds a monster's power, you can defeat that monster. Defeating a monster resets your mana to 0 and increases your daily gain by 1. The goal is to determine the minimum number of days required to defeat all monsters.

Key Insights

  • There are at most 17 monsters, which permits using a bitmask dynamic programming (DP) solution that iterates over all subsets.
  • The order in which you defeat monsters is crucial; one effective strategy is to decide which monster to kill next given your current mana gain (which equals the number of monsters defeated so far plus one).
  • The days needed to defeat a monster with power P when your gain is g is computed as ceil(P / g). This represents waiting enough days until your accumulated mana becomes sufficient.
  • The DP state uses a bitmask where each bit indicates whether a monster has been defeated. The current gain is deduced from the number of defeated monsters.
  • Transition between states: from a state represented by mask and with current gain = (popcount(mask) + 1) try defeating any remaining monster and update the days accordingly.

Space and Time Complexity

Time Complexity: O(2ⁿ * n), where n is the number of monsters.
Space Complexity: O(2ⁿ), required for storing the DP state for each subset of monsters.

Solution

We use a bitmask dynamic programming approach where each state is represented by a bitmask, indicating which monsters have been defeated.

  • Define dp[mask] as the minimum number of days needed to defeat the monsters in the set represented by mask.
  • The starting condition is dp[0] = 0 (no monsters defeated, 0 days used).
  • For each dp[mask], determine the current gain g = count of defeated monsters + 1.
  • For each monster not yet defeated (i.e., corresponding bit is 0 in mask), calculate the minimum days needed to accumulate enough mana: days_needed = ceil(power[i] / g).
  • Transition to the new state (i.e., new_mask = mask OR (1 << i)) with dp[new_mask] = min(dp[new_mask], dp[mask] + days_needed).
  • The answer is dp[(1 << n) - 1], where all monsters have been defeated.

The challenge involves correctly computing the ceiling of the division and updating the DP states optimally.

Code Solutions

# Python solution using bitmask dynamic programming
import math

def minDays(power):
    n = len(power)
    max_mask = 1 << n
    dp = [float('inf')] * max_mask
    dp[0] = 0  # No monsters defeated requires 0 days
    
    # Iterate over all possible states (bitmask)
    for mask in range(max_mask):
        # current gain is number of defeated monsters + 1
        curr_gain = bin(mask).count("1") + 1
        
        # Try to defeat each monster that is not yet defeated in this state
        for i in range(n):
            if not (mask & (1 << i)):
                # Compute the days needed to acquire enough mana using the current gain
                days_needed = (power[i] + curr_gain - 1) // curr_gain  # equivalent to math.ceil(power[i] / curr_gain)
                new_mask = mask | (1 << i)
                dp[new_mask] = min(dp[new_mask], dp[mask] + days_needed)
    
    return dp[max_mask - 1]

# Example usage:
if __name__ == "__main__":
    print(minDays([3, 1, 4]))  # Output: 4
    print(minDays([1, 1, 4]))  # Output: 4
    print(minDays([1, 2, 4, 9]))  # Output: 6
← Back to All Questions