The question goes something like: "You are to inflict mazimum damage to the zerg army. There are two types of units - Warrior and Sheild. Warriors do damage every second, while a sheild protects your entire army for one second. Your army is instantly overrun after the sheild generators expire. Given G cost to build a sheild, W cost to build a warrior and total money M, how many sheilds would you build?"
Let X and Y be the optimal number of generators and number of warriors to be built respectively. Lets take a simple example. Suppose sheilds and warriors both cost 1 unit and you have total money of 5 units. What is the optimum value of X and Y? It'd be optimum if you can inflict maximum damage. With 5 units of money, you can buy sheilds/warriors in the following combinations.
Assuming that a warrior does D damage per second, with 4 warriors and 1 shield, they do 4D damage. With 2 shields and 3 warriors they do 3 + 3 = 6D damage. So in general, with X generators and Y warriors, the damage inflicted is X * Y * D. Therefore our goal is to maximize the product X * Y.
The cost to buy X generators is X * G. Similarly, the cost to buy Y warriors is Y * W. Since we are limited by M amount of money, X and Y must satisfy X * G + Y * W <= M. This can be represented as a line and the inequality encapsulates a region, both of which are shown in fig 1.
 |
| Fig 1. Geometric representation |
For X + Y <= 5, the optimal points are (2,3) and (3,2). You can also try other examples, but you'll eventually notice that X*Y is maximum at the mid-point of the given line. G*X + W*Y <= M is just a general representation of the line. Putting Y=0, we get the intersection with X axis as M/G. Similarly, with X = 0 we get Y = M/W. The mid point is given by (M/2G, M/2W). Therefore optimal number of shields is given by M/2G. However, M/2G must be an integer. Taking floor(M/2G) should suffice as it always ensures that the given region falls within the shaded region.
However, I didn't upload this solution as i was confused with the incorrect test cases :(
Wasted my 2.5 hours.
Good work mate, best wishes for the next sub-round.
ReplyDeleteWhat about the other condition specified? That if there is more than one case that does the same amount of damage, the case with more warriors must be chosen. Where have you accounted for that?
ReplyDeleteWell, that happens if there are two mid points on the line...just as for the case where M = 5 and G = W = 1. For example, mid point for X + Y <= 5 is (2.5, 2.5) so floor(2.5) = 2 is a valid value for the number of shields. If mid-point is already an integer, then there is only one point.
ReplyDelete15 10 6320
ReplyDeleteyour solution is floor(6320/2/15)=210
corect solution is 212. rethink it!
@jiri: Thanks..I came to the conclusion of M/2G based on observation, while yours is based on proper math theory.
ReplyDeleteI ddidnt understand what you meant by "Does it really matter that the function is in fact discrete and not continuous?". Can you elaborate?
@drealecs: Yea,rounding off isnt the right approach. But i am sure the optimal solution will lie very close to M/2G...Just not sure how to compute it accurately...any tips?
I believe drealecs is wrong in the answer he provided:
ReplyDeleteG = 15
W = 10
M = 6320
w = 212, my application shows that 210 is indeed the correct answer for the optimum number of generator shields.
Given that the total damage inflicted is given by g x w (generators x warriors), if we make g = 212 then w = 314. Multiplying these two values yields a total damage of 59360.
Making g = 210 and w = 317, g x w = 66570. 59360 < 66570 thus 210 generators is a much better choice in terms of damage inflicted.
Huh..wonder how i missed that. Can anyone confirm if rounding off would ALWAYS work?
ReplyDeleteUpon further reading, it is not a Diophantine equation after all. Diophantine is looking for integer solutions on the line ax + by = c, but we are looking for a solution that satisfies the inequality ax + by <= c, so below the line.
ReplyDelete