Facebook Hacker Cup: Power Overwhelming

Question

A lot of people at Facebook like to play Starcraft II™. Some of them have made a custom game using the Starcraft II™ map editor. In this game, you play as the noble Protoss defending your adopted homeworld of Shakuras from a massive Zerg army. You must do as much damage to the Zerg as possible before getting overwhelmed. You can only build two types of units, shield generators and warriors. Shield generators do no damage, but your army survives for one second per shield generator that you build. Warriors do one damage every second. Your army is instantly overrun after your shield generators expire. How many shield generators and how many warriors should you build to inflict the maximum amount of damage on the Zerg before your army is overrun? Because the Protoss value bravery, if there is more than one solution you should return the one that uses the most warriors.

Constraints

• 1 ≤ G (cost for one shield generator) ≤ 100
• 1 ≤ W (cost for one warrior) ≤ 100
• G + W ≤ M (available funds) ≤ 1000000000000 (10¹²)

Answer 1

Here's a solution whose complexity is O(W). Let g be the number of generators we build, and similarly let w be the number of warriors we build (and G, W be the corresponding prices per unit).

We note that we want to maximize w*g subject to w*W + g*G <= M.

First, we'll get rid of one of the variables. Note that if we choose a value for g, then obviously we should buy as many warriors as possible with the remaining amount of money M - g*G. In other words, w = floor((M-g*G)/W).

Now, the problem is to maximize g*floor((M-g*G)/W) subject to 0 <= g <= floor(M/G). We want to get rid of the floor, so let's consider W distinct cases. Let's write g = W*k + r, where 0 <= r < W is the remainder when dividing g by W.

The idea is now to fix r, and insert the expression for g and then let k be the variable in the equation. We'll get the following quadratic equation in k:

Let p = floor((M - r*G)/W), then the equation is (-GW) * k^2 + (Wp - rG)k + rp.

This is a quadratic equation which goes to negative infinity when x goes to infinity or negative infinity so it has a global maximum at k = -B/(2A). To find the maximum value for legal values of k, we'll try the minimum legal value of k, the maximum legal value of k and the two nearest integer points of the real maximum if they are within the legal range.

The overall maximum for all values of r is the one we are seeking. Since there are W values for r, and it takes O(1) to compute the maximum for a fixed value, the overall time is O(W).