You are to inflict maximum damage to the zerg army. There are two types of units - Warrior and Shield. Warriors do damage every second, while a shield protects your entire army for one second. Your army is instantly overrun after the shield generators expire. Given $$G$$ cost to build a shield, $$W$$ cost to build a warrior and total money $$M$$, how many shields would you build?

### Solution

Let $$X$$ and $$Y$$ be the optimal number of generators and number of warriors to be built, respectively. Let’s start with a simple concrete example. Suppose shields and warriors both cost 1 unit and you have total money of 5 units. Also assume 1 unit of damage per warrior. What is the optimum value of $$X$$ and $$Y$$? It would be optimum if you can inflict maximum damage. With 5 units of money, you can buy shields/warriors in the following combinations.

Table 1. Combinations of $$X, Y$$
X Y Damage

1

4

4

2

3

6

3

2

6

4

1

4

In this case, the optimal choice of $$X, Y$$ seem to be $$(2, 3)$$ and $$(3, 4)$$ respectively, both of which maximize the product $$XY$$. In the general case, the cost to buy $$X$$ generators is $$XG$$, cost to buy $$Y$$ warriors is $$YW$$. Since we are limited by $$M$$ amount of money, $$X, Y$$ must satisfy $$XG + YW \le M$$. This can be represented as a line and the inequality encapsulates a region for candidate $$(X, Y)$$ values.

Figure 1. Candidate solution region

We want $$X, Y \mid \arg\max{XY}$$. Geometrically, $$XY$$ represents the area of the rectangle shaded in blue.

Figure 2. The area to be maximized

We need to find integer values of $$X, Y$$ that maximize this area.

How do we go about doing that? We know that the line will intersect X and Y axis at $$\frac{M}{G}, \frac{M}{W}$$. We also know that the optimal rectangle touches the line. If it doesn’t, the area can be trivially increased by increasing either/both $$X, Y$$ values until it touches the line.

The boring calculus way for figuring this out is as follows:

$$Area(A) = XY \\ A = \frac{M - YW}{G}Y \\ \\ \frac{\partial A}{\partial Y} = \frac{Y(M - WY)}{G} \\ \arg\max{A} \scriptstyle \implies \frac{Y(M - WY)}{G} = 0 \\ Y = \frac{M}{2W}$$

This gives corresponding $$X = \frac{M}{2G}$$

A more interesting way to arrive at the same conclusion would be to think as follows:

• The shaded triangle increases its area as long as X and Y increase.

• Start with $$(0, 0)$$ and increase both $$X, Y$$ by 1. This gives us a small rectangle with bottom left $$(0, 0)$$ and top right $$(1, 1)$$.

• If the straight line was X + Y = 1, it would be a right angled isosceles triangle. The $$X, Y$$ value would always increase in the direction of line $$Y = X$$, which would cut the line in middle at $$(\frac{X}{2}, \frac{Y}{2})$$

• Generalizing this, the value of $$X. Y$$ will increase as long as we go on the direction of line that joins $$(0, 0)$$ to midpoint of the line $$XG + YW = M$$. The mid point of this line is, unsurprisingly, $$(\frac{M}{2G}, \frac{M}{2W})$$

There are other ways to arrive at this. Perhaps I should write a post that exclusively deals with this problem.

Coming back to our original question, the optimal number of shields must be $$\frac{M}{2G}$$. If, $$\frac{M}{2G}$$ is not an integer, we go towards the origin on the line that joins $$(0, 0)$$ and $$(\frac{M}{2G}, \frac{M}{2W})$$. However, I was able to get away by taking $$\lfloor\frac{M}{2G} \rfloor$$.