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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Amount of Damage Dealt to Bob

Number: 3531

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer power and two arrays damage and health of length n, each enemy i deals damage[i] per second to Bob while alive. Every second, after all surviving enemies deal damage, Bob can choose one enemy (that is still alive) to attack and deal power damage to it. Each enemy requires ceil(health[i] / power) attacks (seconds) to be killed. Determine the minimum total damage Bob will receive before all enemies are dead.

Key Insights

  • The problem can be modeled as a scheduling problem where each enemy requires a fixed number of rounds (processing time) and has a weight (its damage per second).
  • The total damage Bob takes is equivalent to the weighted sum of completion times if you view each enemy as a job.
  • To minimize total damage, enemies with a higher “damage rate” relative to the number of rounds required (i.e. a higher ratio of damage[i] to ceil(health[i]/power)) should be targeted first.
  • Smith’s rule applies: sort enemies in descending order of damage[i] / rounds (or equivalently, sort by increasing order of rounds[i] / damage[i]) to minimize the weighted sum of completion times.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the enemies. Space Complexity: O(n) to store the rounds for each enemy and sorting overhead.

Solution

First, compute for each enemy the number of rounds required to kill it using rounds = ceil(health[i] / power) which is implemented as (health[i] + power - 1) // power. Then, using a greedy strategy, sort the enemies using the comparator based on the ratio of damage to rounds. In essence, enemy i should come before enemy j if damage[i] / rounds[i] > damage[j] / rounds[j]. To avoid floating-point calculations, we can compare damage[i] * rounds[j] with damage[j] * rounds[i]. After sorting, simulate the killing process: as you process each enemy in order, maintain the cumulative rounds (which represents the time at which the enemy is killed) and add to the total damage Bob takes the enemy’s damage multiplied by the current cumulative rounds. This computation effectively sums the contribution of each enemy’s damage until it is removed from the battle.

Code Solutions

# Python solution
# Function to calculate minimum damage taken by Bob
def minimumDamage(power, damage, health):
    n = len(damage)
    # Compute rounds needed for each enemy: rounds = ceil(health / power)
    rounds = [(health[i] + power - 1) // power for i in range(n)]
    
    # Create list of indices for enemies
    enemies = list(range(n))
    
    # Custom sort: enemy i comes before enemy j if damage[i] * rounds[j] > damage[j] * rounds[i]
    enemies.sort(key=lambda i: (-damage[i] / rounds[i], rounds[i]))
    # Alternatively, sort using multiplication to avoid floating point:
    # enemies.sort(key=lambda i: ( -damage[i], rounds[i] ))
    # But using ratio is clearer considering both factors.
    
    total_damage = 0
    cumulative_time = 0
    # Process enemies in the sorted order
    for i in enemies:
        cumulative_time += rounds[i]  # Time when enemy i is killed
        total_damage += damage[i] * cumulative_time  # Damage contributed by enemy i while alive
    return total_damage

# Example usage:
if __name__ == "__main__":
    print(minimumDamage(4, [1,2,3,4], [4,5,6,8]))  # Expected output 39
    print(minimumDamage(1, [1,1,1,1], [1,2,3,4]))  # Expected output 20
    print(minimumDamage(8, [40], [59]))             # Expected output 320
← Back to All Questions