2403. Minimum Time to Kill All Monsters

HardBit ManipulationArrayDynamic ProgrammingBitmask

Problem Description

In this problem, you are tasked with defeating all the monsters in an array power, where power[i] represents the power level of the i-th monster. You start with 0 mana points, and each day, you gain more mana points. Initially, you gain 1 mana point per day, and each day this amount increases by 1 after you defeat a monster.

However, you can only defeat a monster on a given day if your current mana points exceed or are equal to that monster's power. If you defeat a monster, your mana points reset to 0, and the daily mana gain (gain) increases by 1. The goal is to find the minimum number of days required to defeat all monsters in the array.

To put it simply, the problem asks you to optimize the order of defeating monsters while considering the growth of your mana points so that all monsters can be defeated in the least number of days possible.

Intuition

The solution approach for this problem can be understood in terms of a depth-first search (DFS) through all possible scenarios. Since each day you can choose to defeat any monster whose power level is less than or equal to your current mana, there could be multiple choices, and thus multiple possible futures, to consider.

Given that each time you defeat a monster, your mana resets, the number of days needed depends on the order in which you choose to defeat the monsters. Using a bit-mask to represent which monsters have been defeated, we can systematically explore each choice. A bit-mask is a binary representation where each bit corresponds to a monster; if the bit is 1, the monster is defeated, and if it's 0, the monster remains.

The function dfs(mask) explores all possible choices from the current state defined by mask. If all monsters are defeated (the base case), it returns 0 since no additional days are needed. Otherwise, for each undefeated monster, it calculates the days needed to defeat it plus the days from defeating the remaining monsters and takes the minimum over all these possibilities.

The @cache decorator is utilized to memorize results of subproblems making the algorithm more efficient by avoiding redundant calculations. mask.bit_count() is used to count how many bits are set to 1 (how many monsters have been defeated) which determines the day's gain. (v + cnt) // (cnt + 1) calculates the number of days needed to accumulate enough mana to defeat the monster i with power v.

Essentially, this approach applies recursion to simulate the passage of days, defeat monsters, and track mana gain, recording the minimum days taken to reach the condition where all monsters are defeated.

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

The implementation employs a recursive function dfs(mask) to walk through all possible ways one could defeat the monsters. Here is the step-by-step explanation of the algorithm:

Recursion and Bitmask: The primary technique used is recursion combined with bitmasking. Each bit in the mask corresponds to a monster. If the bit is set (1), the monster is already defeated; else (0), the monster is yet to be defeated.
Base Case: The base case for the recursion is when all monsters have been defeated, which is when the bit_count of the mask is equal to the length of the power array. In this case, dfs returns 0 because no additional days are required.
Exploring Paths: For each undefeated monster (those bits that are 0), the algorithm explores what would happen if you were to defeat this monster next. It does so by calculating the number of days needed to defeat the monster ((v + cnt) // (cnt + 1)) added to the result of a recursive call to dfs with the monster defeated (mask | (1 << i)). The calculation considers the current count of defeated monsters (cnt) to determine the daily gain in mana points.
Minimum Days: The dfs function looks for the minimum number of days across all such recursive calls for different monsters. The variable ans stores the minimum number of days found so far and is updated whenever a smaller value is found.
Memoization: The algorithm uses memoization with the @cache decorator to store results of subproblems. This means that once the number of days required to defeat a certain set of monsters (i.e., a particular mask) has been calculated, it won't be recalculated again if encountered in the future.
Inf: The value inf from the Python math module (which represents "infinity") is used to initialize the ans variable. This ensures that the first comparison will always favor the first actual computed number of days over inf.
The Initial Recursive Call: The function dfs(0) kicks off the recursion with all monsters undefeated.

In summary, this is a classic brute-force search with optimization. The bitmask acts as a state representation for the set of monsters defeated, and the minimum number of days is computed recursively with memoization to speed up the search process by not recalculating already known states.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's consider an example. Suppose we have the following array of monster powers: power = [2, 4, 2].

This means we have three monsters with power levels 2, 4, and 2, respectively.

Day 1: We start with 0 mana points and a gain of 1 mana point per day. We cannot defeat any monsters on day 1 because our mana is less than the power of any monster.

Day 2: We now have 1 (from Day 1) + 2 mana (since our gain increases daily) = 3 mana points total. We can defeat the first or the third monster (both with power 2), but not the second (with power 4). Let's defeat the first monster. Our mana resets to 0, but now our mana gain increases to 2 mana points per day.

Mask 1: 001, meaning the first monster has been defeated, and two are left.

Day 3: No mana from previous days since it reset, so you only gain 2 mana points this day. With only 2 mana points, we cannot defeat any remaining monsters, since the next weakest has a power of 2 and we would need to start the day with at least 3 mana points to defeat it (2 required + 1 since we have already defeated one monster, which is our additional mana gain per day).

Day 4: We carry over 2 mana points from Day 3 and gain 3 more (since our gain increases daily), giving us 5 mana points total. Now we can defeat either the second or third monster. Let's choose the third monster. Our mana resets again.

Mask 2: 011, indicating that the first and third monsters are defeated, and only one monster, with power 4, is left.

Day 5: We start again with 0 mana.

Day 6: We gain 3 mana points.

Day 7: We gain 4 mana points (since we defeated 2 monsters already, our gain is 2 and increases daily by 1), totaling 7 mana points, and now we can defeat the second monster with power 4.

At the end of day 7, we have defeated all monsters.

Mask 3: 111. This means all monsters are defeated and the recursion base case is met.

To calculate the minimum number of days needed, we must consider all the permutation ways to defeat the monsters, which means not only the path we walked through above. The algorithm does just that, by exploring all possibilities and caching the results for efficiency. We end up with:

dfs(0) -> minimum of {dfs(001), dfs(010), dfs(100)} -- these represent defeating each monster first.

Each of these calls will traverse further with their respective masks, accounting for the increasing mana gain and resetting after each defeat. In this simple example, it took us 7 days, but in a different order of defeating monsters, or a different power array, it might take fewer or more days to figure out the least number of days needed. The dfs function handles these comparisons and finds the optimal solution.

Solution Implementation

1from functools import lru_cache
2from math import inf
3
4class Solution:
5    def minimumTime(self, powers: List[int]) -> int:
6        # This function uses depth-first search to calculate the minimum time
7        # to accumulate powers from list 'powers'. It uses memoization to 
8        # store results of subproblems for efficiency.
9        @lru_cache(maxsize=None)  # Using LRU cache for memoization
10        def dfs(mask):
11            # Count the number of bits set to 1 in 'mask' — this represents
12            # the number of powers acquired so far.
13            count = mask.bit_count()  
14          
15            # If all powers are acquired, no additional time is needed.
16            if count == len(powers):
17                return 0
18          
19            # Initialize the answer for this subproblem to infinity.
20            answer = inf
21          
22            # Iterate through each power.
23            for i, power_value in enumerate(powers):
24                # Check if the power represented by the current index 'i' 
25                # has already been acquired using the mask.
26                if mask & (1 << i):
27                    continue
28              
29                # Recursive call to explore further by including the current index's power.
30                # The time to acquire this power is (power_value + count) divided by (count + 1),
31                # representing the efficient use of acquired powers to reduce the time.
32                answer = min(answer, dfs(mask | 1 << i) + (power_value + count) // (count + 1))
33          
34            return answer
35
36        # Start DFS with an initial mask of 0 (no powers acquired)
37        return dfs(0)
38

1class Solution {
2    private int taskCount;          // Number of tasks
3    private long[] memoization;     // Array to store results of subproblems
4    private int[] taskPower;        // Array to hold the power of each task
5
6    /**
7     * Calculates the minimum time required to complete all tasks.
8     *
9     * @param power Array representing the power of each task
10     * @return Minimum time to complete all tasks
11     */
12    public long minimumTime(int[] power) {
13        taskCount = power.length;   // Initialize the number of tasks
14        memoization = new long[1 << taskCount]; // Initialize memoization array to store intermediate results
15        Arrays.fill(memoization, -1L); // Fill the array with -1 to denote uncalculated states
16        taskPower = power; // Reference to power of tasks
17        return dfs(0); // Begin the dfs with an empty mask (no tasks completed)
18    }
19
20    /**
21     * Performs depth-first search to find the minimum time needed to complete the remaining tasks.
22     *
23     * @param mask A bitmask representing the state of tasks completion
24     * @return Minimum time to complete the tasks represented by the current mask
25     */
26    private long dfs(int mask) {
27        // If we have already computed the answer for this state, return it
28        if (memoization[mask] != -1) {
29            return memoization[mask];
30        }
31        int completedTasks = Integer.bitCount(mask); // Count how many tasks have been completed so far
32        if (completedTasks == taskCount) { // If all tasks are completed, return 0 as no more time is needed
33            return 0;
34        }
35
36        long minTime = Long.MAX_VALUE; // Initialize the minimum time to a very large number
37        for (int i = 0; i < taskCount; ++i) {
38            // If the task 'i' is not completed yet
39            if (((mask >> i) & 1) == 0) {
40                // Calculate time required if we choose to complete task 'i' next
41                long time = dfs(mask | (1 << i)) + (long) Math.ceil((double)taskPower[i] / (completedTasks + 1));
42                // Update the minimum time
43                minTime = Math.min(minTime, time);
44            }
45        }
46
47        memoization[mask] = minTime; // Store the computed minimum time for this state
48        return minTime; // Return the computed minimum time
49    }
50}
51

1using ll = long long;
2
3class Solution {
4public:
5    // f stores the minimum time for each subset of power-ups used
6    vector<ll> minTimeMemo;
7    // store the input power values
8    vector<int> heroPowers;
9    // the number of heroes
10    int n;
11
12    // The function to calculate the minimum time to beat all the monsters
13    long long minimumTime(vector<int>& power) {
14        n = power.size();
15      
16        // Initialize memoization vector for each possible combination of heroes (2^n)
17        minTimeMemo.assign(1 << n, -1);
18      
19        // Assign the hero powers to a member variable for easy access
20        this->heroPowers = power;
21      
22        // Start solving the problem using Depth-First Search Approach from an empty mask (no hero used)
23        return dfs(0);
24    }
25
26    // Recursive function to find the minimum time using Depth-First Search
27    ll dfs(int mask) {
28        // If we have already calculated the minimum time for this mask, return it to avoid recomputation
29        if (minTimeMemo[mask] != -1) return minTimeMemo[mask];
30      
31        // Count the number of bits set in the mask (number of heroes that have already fought)
32        int cnt = __builtin_popcount(mask);
33      
34        // Base case: if cnt == n, all heroes have been used, no time needed beyond this point
35        if (cnt == n) return 0;
36      
37        // Initialize the answer to maximum possible value to effectively find the minimum
38        ll ans = LONG_MAX;
39      
40        // Loop through each hero
41        for (int i = 0; i < n; ++i) {
42            // Check to make sure the hero hasn't already been used (bit not set in mask)
43            if ((mask >> i) & 1) continue;
44          
45            // Recur to get the minimum time if we use this hero as the next one
46            ll timeIfHeroIUsed = dfs(mask | (1 << i)) + (heroPowers[i] + cnt) / (cnt + 1);
47          
48            // Compare with the best(minimum) answer so far
49            ans = min(ans, timeIfHeroIUsed);
50        }
51      
52        // Store the calculated minimum time for this mask for future reference
53        minTimeMemo[mask] = ans;
54        return ans;
55    }
56};
57

1function minimumTime(power: number[]): number {
2    // The length of the power array.
3    const numTasks = power.length;
4    // An array to memoize the minimum time for each state.
5    const memo = new Array(1 << numTasks).fill(-1);
6
7    // Depth-first search to find the minimum time for a given mask of tasks.
8    function dfs(currentMask: number): number {
9        // If this state has already been computed, return the memoized result.
10        if (memo[currentMask] !== -1) {
11            return memo[currentMask];
12        }
13      
14        // Base case: if all tasks are turned on (i.e., mask has all bits set), return 0.
15        const numBitsSet = bitCount(currentMask);
16        if (numBitsSet === numTasks) {
17            return 0;
18        }
19      
20        // Set initial minimum time as infinite to ensure it will be replaced by any valid time.
21        let minTime = Infinity;
22
23        // Iterate through all tasks.
24        for (let i = 0; i < numTasks; ++i) {
25            // Skip if the task is already included in the currentMask.
26            if ((currentMask >> i) & 1) {
27                continue;
28            }
29            // Make recursive call by including the new task i and calculate the total time.
30            // Here we use Math.ceil to divide the power by the number of active tasks.
31            const timeWithNewTask = dfs(currentMask | (1 << i)) + Math.ceil(power[i] / (numBitsSet + 1));
32            // Update minTime if the new calculated time is less than the current minimum.
33            minTime = Math.min(minTime, timeWithNewTask);
34        }
35      
36        // Memoize and return the minimum time for the current mask.
37        memo[currentMask] = minTime;
38        return minTime;
39    }
40
41    // Begin recursion starting with an empty task mask.
42    return dfs(0);
43}
44
45// Helper function to count the number of bits set to 1 in an integer.
46function bitCount(x: number): number {
47    let count = 0;
48    // Iterate over each bit position.
49    for (let i = 0; i < 32; ++i) {
50        if ((x >> i) & 1) {
51            count++;
52        }
53    }
54    return count;
55}
56

Time and Space Complexity

The given Python code defines a function minimumTime which finds the minimum time required to reduce a given list of powers to zero by deactivating machines in sequence, with the speed of deactivation increasing with each machine that is turned off.

Time Complexity

The time complexity of the code can be determined by analyzing the dfs function, which is a depth-first search with memoization. The recursion explores each possible state represented by mask, which has a length of n where n is the number of elements in power. There are 2^n possible states given that each element can be either active (1) or inactive (0). For every state, the function iterates over all n elements to check which machines can be turned off next. Therefore, the total number of operations is O(n * 2^n).

Memoization is used to ensure that each state is computed only once. This is important because without memoization, the algorithm would have to recompute the same states exponentially more times. With memoization, each state's result is stored and reused, so the total number of distinct function calls matches the number of distinct states, which is 2^n.

Space Complexity

The space complexity is determined by the space required for memoization and the recursion call stack. The memoization stores results for each of the 2^n possible states, so the space complexity for memoization is O(2^n).

The recursion stack's maximum depth would be n, since it represents turning off each machine exactly once. Thus, in terms of space complexity, the recursion stack contributes O(n).

However, as the space used for memoization dominates the space required for the call stack as n grows, the overall space complexity is O(2^n) for storing the results of each of the unique states.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following array represent a max heap?

20 12 16 1 2 3 4

20 30 10 5 6 7 18

30 20 11 2 3 4 12

50 30 40 10 20 30 40

I don’t know