Kill Monsters in C++

You are a hero in a game, initially having HP health points and K magic potions.

You have to fight N monsters in the order they are given, knowing the damage each monster deals to you.

damage[i] represents the damage the monster deals to you when you fight them. If the damage is negative, it means your HP increases by that amount.

If you use a magic potion on a monster, it will kill the monster without you fighting or losing health points.

If you reach zero HP, you die. Therefore you can't win agains a monster that has damage[i] >= HP

Find the maximum number of monsters you can kill, considering you are playing optimally.

Example

Input: K = 2, HP = 10,
       damage = [-3, 2, 3, -2, 8, 8, 6, 4, 3, 3]
Output: 8
Explanation: You kill the first 8 monsters by using the two potions on the 6^th and 7^th monsters

Understanding the Problem

The core challenge of this problem is to maximize the number of monsters you can kill while managing your health points (HP) and the limited number of magic potions (K). The damage array can have both positive and negative values, where positive values decrease your HP and negative values increase it. The key is to use the potions optimally to bypass the most damaging monsters.

Approach

To solve this problem, we need to consider the following steps:

Iterate through the list of monsters and keep track of your current HP.
Use a priority queue (max-heap) to keep track of the most damaging monsters you have encountered so far.
If your HP drops below zero, use a potion on the most damaging monster encountered so far (i.e., the root of the max-heap).
Continue this process until you either run out of potions or can no longer survive the next monster's attack.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize a max-heap to keep track of the most damaging monsters.
Iterate through the damage array and update your HP accordingly.
If the damage is positive, add it to the max-heap.
If your HP drops below zero, use a potion on the most damaging monster (pop from the max-heap) and increase your HP by that amount.
Keep track of the number of monsters you have killed.
Stop if you run out of potions or can no longer survive the next attack.

Code Implementation


#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int maxMonstersKilled(int K, int HP, vector<int>& damage) {
    priority_queue<int> maxHeap;
    int monstersKilled = 0;

    for (int i = 0; i < damage.size(); ++i) {
        if (damage[i] > 0) {
            maxHeap.push(damage[i]);
        }
        HP -= damage[i];
        monstersKilled++;

        // If HP drops below zero, use a potion
        if (HP < 0) {
            if (K > 0 && !maxHeap.empty()) {
                HP += maxHeap.top();
                maxHeap.pop();
                K--;
            } else {
                break;
            }
        }
    }

    return monstersKilled;
}

int main() {
    int K = 2;
    int HP = 10;
    vector<int> damage = {-3, 2, 3, -2, 8, 8, 6, 4, 3, 3};

    cout << "Maximum monsters killed: " << maxMonstersKilled(K, HP, damage) << endl;

    return 0;
}

Complexity Analysis

The time complexity of this approach is O(N log K), where N is the number of monsters and K is the number of potions. This is because we are using a max-heap to keep track of the most damaging monsters, and each insertion and deletion operation in the heap takes O(log K) time.

The space complexity is O(K) due to the storage required for the max-heap.

Edge Cases

Consider the following edge cases:

All damage values are negative: The hero's HP will keep increasing, and no potions will be needed.
All damage values are positive and greater than the initial HP: The hero will need to use potions immediately.
Number of potions (K) is zero: The hero can only rely on their initial HP to survive.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small arrays and few potions.
Cases with a mix of positive and negative damage values.
Edge cases as mentioned above.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Think about the constraints and how they affect your solution.
Use data structures like heaps to optimize your solution.
Test your solution with a variety of test cases to ensure its correctness.

Conclusion

In this blog post, we discussed how to solve the "Kill Monsters" problem using a max-heap to keep track of the most damaging monsters. We provided a detailed explanation of the algorithm, its implementation in C++, and analyzed its complexity. By understanding and practicing such problems, you can improve your problem-solving skills and prepare for coding interviews.

Additional Resources

For further reading and practice, consider the following resources:

LeetCode - A platform for practicing coding problems.
GeeksforGeeks - A comprehensive resource for learning algorithms and data structures.
C++ Reference - Documentation and tutorials for C++ programming.

Kill Monsters - Time Complexity: O(N log K) - C++ Solution