• Posts

Problem 3207 Maximum Points After Enemy Battles

Problem Statement

Link - Problem 3207

Question

You are given an integer array enemyEnergies denoting the energy values of various enemies.

You are also given an integer currentEnergy denoting the amount of energy you have initially.

You start with 0 points, and all the enemies are unmarked initially.

You can perform either of the following operations zero or multiple times to gain points:

• Choose an unmarked enemy, i, such that currentEnergy >= enemyEnergies[i]. By choosing this option:
  • You gain 1 point.
  • Your energy is reduced by the enemy's energy, i.e. currentEnergy = currentEnergy - enemyEnergies[i].
• If you have at least 1 point, you can choose an unmarked enemy, i. By choosing this option:
  • Your energy increases by the enemy's energy, i.e. currentEnergy = currentEnergy + enemyEnergies[i].
  • The enemy i is marked.

Return an integer denoting the maximum points you can get in the end by optimally performing operations.

Example 1:

Example 2:

Constraints:

• 1 <= enemyEnergies.length <= 105
• 1 <= enemyEnergies[i] <= 109
• 0 <= currentEnergy <= 109

Solution

class Solution {
public:
   long long maximumPoints(std::vector<int>& arr, int currentEnergy) {
        sort(arr.begin(), arr.end());

        long long total = 0;
        total = std::accumulate(arr.begin(), arr.end(), 0LL);
        total -= arr[0];

        long long points = 0;
        if (currentEnergy >= arr[0]) {
            points++;
            currentEnergy -= arr[0];
        }

        if (points >= 1) {
            total += currentEnergy;
            points += total / arr[0];
        }

        return points;
    }
};

Complexity Analysis

| Algorithm             | Time Complexity | Space Complexity |
| --------------------- | --------------- | ---------------- |
| Modified Accumulation | O(n log n)      | O(1)             |

Explanation

Intial Thoughts

Sort the enemy energies array to prioritize the enemy with the least energy. Initialize points to 0. Consider the trade-off between scoring points and increasing energy by choosing the most energy-efficient enemy. Think about the benefit of marking an enemy and the potential loss of energy from fighting them.

Intuitive Analysis

Imagine you’re playing a game where you can choose to fight or boost your energy. You want to fight the enemies that require the least energy to beat and then use their energy to boost your own. The initial energy requirement is the lowest energy enemy, and then you can use the remaining enemies to boost your energy. This creates a snowball effect where you can fight and boost your energy repeatedly to maximize points.

1. Intuition

• The problem can be solved by first sorting the enemy energies in ascending order.
• The goal is to maximize the points by choosing the enemies with the lowest energy first.
• If we have enough energy to defeat the first enemy, we can defeat it and gain a point.
• After defeating the first enemy, we can use the second operation to increase our energy by the energy of the first enemy.
• We can then use this increased energy to defeat more enemies and gain more points.
• The key insight is to use the second operation to increase our energy after defeating the first enemy.
• This allows us to defeat more enemies and gain more points.
• The time complexity of this solution is O(n log n) due to the sorting operation.

2. Implementation

• The sort(arr.begin(), arr.end()) line sorts the enemy energies in ascending order.
• The total = std::accumulate(arr.begin(), arr.end(), 0LL) line calculates the total energy of all enemies.
• The total -= arr[0] line subtracts the energy of the first enemy from the total energy.
• The if (currentEnergy >= arr[0]) line checks if we have enough energy to defeat the first enemy.
• The points++ and currentEnergy -= arr[0] lines increment the points and decrement the energy after defeating the first enemy.
• The if (points >= 1) line checks if we have at least one point.
• The total += currentEnergy line adds the current energy to the total energy.
• The points += total / arr[0] line calculates the maximum points we can gain by defeating the remaining enemies.

Complexity Analysis

Time Complexity:

• The algorithm performs a sort operation sort(arr.begin(), arr.end()); which takes O(n log n) time complexity. This is the most significant operation in the algorithm and thus determines its overall time complexity.
• Other operations in the algorithm like accumulation total = std::accumulate(arr.begin(), arr.end(), 0LL); and arithmetic operations take linear time, but they are dominated by the sorting operation.
• Since n is the number of elements in the input array arr, and sorting has a time complexity of O(n log n), the time complexity of this algorithm can be classified as O(n log n) due to the log-linear time complexity of the sorting operation.

Space Complexity:

• No additional space is used to store the input elements, and thus the memory usage does not grow with the input size. However, additional variables for accumulation and indexing are used, resulting in a constant space usage.
• The input array arr is sorted in-place, meaning that the sorting operation does not allocate additional space that scales with the input size.
• Since the algorithm does not use any data structures that allocate additional memory based on the input size, the space complexity is classified as O(1), indicating constant space usage.

Footnote

This question is rated as Medium difficulty.

Hints

The problem can be solved greedily.

Mark all the others except the smallest one first.

Use the smallest one to increase the energy.

Note that the initial energy should be no less than the smallest enemy.