Facebook Hacker Cup: Power Overwhelming

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) ≤ 1000000开发者_开发百科000000 (10¹²)

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).

If you build g generators, and w warriors, you can do a total damage of w (damage per time) × g (time until game-over).

The funds constraint restricts the value of g and w to W × w + G × g ≤ M.

If you build g generators, you can build at most (M - g × G)/W warriors, and do g × (M - g × G)/W damage.

This function has a maximum at g = M / (2 G), which results in M² / (4 G W) damage.

Summary:

• Build M / (2 G) shield generators.
• Build M / (2 G) warriors.
• Do M² / (4 G W) damage.

Since you can only build integer amounts of any of the two units, this reduces to the optimization problem:

maximize g × w
with respect to g × G + w × W ≤ M and g, w ∈ ℤ⁺

The general problem of Integer Programming is NP-complete, so the best algorithm for this is to check all integer values close to the real-valued solution above.

If you find some pair (g_i, w_i), with total damage d_i, you only have to check values where g_j × w_j ≥ d_i. This and the original condition W × w + G × g ≤ M constrains the search-space with each item found.

F#-code:

let findBestSetup (G : int) (W : int) (M : int) =
    let mutable bestG = int (float M / (2.0 * float G))
    let mutable bestW = int (float M / (2.0 * float W))
    let mutable bestScore = bestG * bestW
    let maxW = (M + isqrt (M*M - 4 * bestScore * G * W)) / (2*G)
    let minW = (M - isqrt (M*M - 4 * bestScore * G * W)) / (2*G)
    for w = minW to maxW do
        // ceiling of (bestScore / w)
        let minG = (bestScore + w - 1) / w
        let maxG = (M - W*w)/G
        for g = minG to maxG do
            let score = g * w
            if score > bestScore || score = bestScore && w > bestW then
                bestG <- g
                bestW <- w
                bestScore <- score
    bestG, bestW, bestScore

This assumed W and G were the counts and the cost of each was equal to 1. So it's obsolete with the updated question.

Damage = LifeTime*DamagePerSecond = W * G

So you need to maximize W*G with the constraint G+W <= M. Since both Generators and Warriors are always good we can use G+W = M.

Thus the function we want to maximize becomes W*(M-W).
Now we set the derivative = 0:
M-2W=0
W = M/2

But since we need the solution to the discrete case(You can't have x.5 warriors and x.5 generators) we use the values closest to the continuous solution(this is optimal due to the properties of a parabel).

If M is even than the continuous solution is identical to the discrete solution. If M is odd then we have two closest solutions, one with one warrior more than generators, and one the other way round. And the OP said we should choose more warriors.

So the final solution is:
G = W = M/2 for even M
and G+1 = W = (M+1)/2 for odd M.

g = total generators gc = generator cost w = warriors wc = warrior cost m = money d = total damage

g = (m - (w*wc))/gc w = (m - (g*gc))/wc

d = g * w d = ((m - (w*wc))/gc) * ((m - (g*gc))/wc) d = ((m - (w*wc))/gc) * ((m - (((m - (w*wc))/gc)*gc))/wc) damage as a function of warriors

I then tried to compute an array of all damages then find max but of course it'd not complete in 6 mins with m in the trillions.

To find the max you'd have to differentiate that equation and find when it equals zero, which I forgotten how to do seing I haven't done math in about 6 years

Not a really a solution but here goes.

The assumption is that you already get a high value of damage when the number of shields equals 1 (cannot equal zero or no damage will be done) and the number of warriors equals (m-g)/w. Iterating up should (again an assumption) reach the point of compromise between the number of shields and warriors where damage is maximized. This is handled by the bestDamage > calc branch.

There is almost likely a flaw in this reasoning and it'd be preferable to understand the maths behind the problem. As I haven't practised mathematics for a while I'll just guess that this requires deriving a function.

        long bestDamage = 0;
        long numShields = 0;
        long numWarriors = 0;

        for( int k = 1;; k++ ){
            // Should move declaration outside of loop
            long calc = m / ( k * g ); // k = number of shields

            if( bestDamage < calc ) {
                bestDamage = calc;
            }

            if( bestDamage > calc ) {
                numShields = k;
                numWarriors = (m - (numShields*g))/w;
                break;
            }
        }

        System.out.println( "numShields:" + numShields );
        System.out.println( "numWarriors:" + numWarriors );
        System.out.println( bestDamage );

Since I solved this last night, I thought I'd post my C++ solution. The algorithm starts with an initial guess, located at the global maximum of the continuous case. Then it searches 'little' to the left/right of the initial guess, terminating early when continuous case dips below an already established maximum. Interestingly, the 5 example answers posted by the FB contained 3 wrong answers:

Case #1
  ours:   21964379805 dmg: 723650970382348706550
  theirs: 21964393379 dmg: 723650970382072360271 Wrong
Case #2
  ours:   1652611083 dmg: 6790901372732348715
  theirs: 1652611083 dmg: 6790901372732348715 
Case #3
  ours:   12472139015 dmg: 60666158566094902765
  theirs: 12472102915 dmg: 60666158565585381950 Wrong
Case #4
  ours:   6386438607 dmg: 10998633262062635721
  theirs: 6386403897 dmg: 10998633261737360511 Wrong
Case #5
  ours:   1991050385 dmg: 15857126540443542515
  theirs: 1991050385 dmg: 15857126540443542515

Finally the code (it uses libgmpxx for large numbers). I doubt the code is optimal, but it does complete in 0.280ms on my personal computer for the example input given by FB....

#include <iostream>
#include <gmpxx.h>

using namespace std;

typedef mpz_class Integer;
typedef mpf_class Real;

static Integer getDamage( Integer g, Integer G, Integer W, Integer M)
{
    Integer w = (M - g * G) / W;
    return g * w;
}

static Integer optimize( Integer G, Integer W, Integer M)
{
    Integer initialNg = M / ( 2 * G);
    Integer bestNg = initialNg;
    Integer bestDamage = getDamage ( initialNg, G, W, M);

    // search left
    for( Integer gg = initialNg - 1 ; ; gg -- ) {
        Real bestTheoreticalDamage = gg * (M - gg * G) / (Real(W));
        if( bestTheoreticalDamage < bestDamage) break;
        Integer dd = getDamage ( gg, G, W, M);
        if( dd >= bestDamage) {
            bestDamage = dd;
            bestNg = gg;
        }
    }

    // search right
    for( Integer gg = initialNg + 1 ; ; gg ++ ) {
        Real bestTheoreticalDamage = gg * (M - gg * G) / (Real(W));
        if( bestTheoreticalDamage < bestDamage) break;
        Integer dd = getDamage ( gg, G, W, M);
        if( dd > bestDamage) {
            bestDamage = dd;
            bestNg = gg;
        }
    }

    return bestNg;
}

int main( int, char **)
{
    Integer N;

    cin >> N;
    for( int i = 0 ; i < N ; i ++ ) {
        cout << "Case #" << i << "\n";
        Integer G, W, M, FB;
        cin >> G >> W >> M >> FB;

        Integer g = optimize( G, W, M);

        Integer ourDamage = getDamage( g, G, W, M);
        Integer fbDamage = getDamage( FB, G, W, M);

        cout << "  ours:   " << g << " dmg: " << ourDamage << "\n"
             << "  theirs: " << FB << " dmg: " << fbDamage << " "
             << (ourDamage > fbDamage ? "Wrong" : "") << "\n";
    }
}