Facebook Hacker Cup

This is one problem which I could not solve during the contest. (Well, I could not solve any problem)...
You have to command an army of Guards and Warriors in a RTS game to beat Sauron.
Each Guard adds '1' second of game-play to your army, it costs 'G' coins.
Each Warrior deals '1' damage for every second of its existence and costs 'W' coins. All Warriors die when the time given by your Guards runs out.

You have 'M' coins.
Give an approximate answer stating how many Warriors will you buy. Write the answer for the following triplets of(G,W,M).

(15,12,123124423423)
(23,43,234234232489)
(34,24,234879)
(432,25,435354)

16 comments:

  1. ShivankerJanuary 16, 2011 at 12:21 PM

    is it..

    1. 5130184309
    2. 2723653866
    3. 4893
    4. 8707

    ??

    ReplyDelete
  2. Sambhav GuptaJanuary 16, 2011 at 8:55 PM

    agree to shivanker, just what we do when we have to maximise satisfaction from two products given the total income...(my fifth subject is economics, and though only the theory is in our syllabus, they still teach that the hyperbola and the straight line must be tangential)

    ReplyDelete
  3. AnujJanuary 16, 2011 at 9:45 PM

    What if I say that your answer is wrong?

    ReplyDelete
  4. Sambhav GuptaJanuary 16, 2011 at 9:55 PM

    i have to spend more time on school studies :P

    ReplyDelete
  5. Sambhav GuptaJanuary 16, 2011 at 10:02 PM

    i don't know, there is a catch then, and the question isn't straight forward

    ReplyDelete
  6. akash rupelaJanuary 18, 2011 at 7:21 AM

    This comment has been removed by the author.

    ReplyDelete
  7. AnujJanuary 18, 2011 at 5:51 PM

    Hey..i guess the number of warriors is coming out to be M/2G.

    Your answers correspond to M/2W..I may be wrong though..

    ReplyDelete
  8. ShivankerJanuary 18, 2011 at 7:41 PM

    that's what i posted bhaiya.. :D

    ReplyDelete
  9. Sambhav GuptaJanuary 18, 2011 at 8:45 PM

    hey M/2W he to hoga ?
    let x be the number of warriors, so xy has to be maximised, means dy/dx=-y/x

    also, Wx+Gy=M, for condition of tangency, dy/dx=-y/x=-W/G, which means y=Wx/G, which means Wx+Wx=M

    ReplyDelete
  10. AnujJanuary 18, 2011 at 9:19 PM

    All right...I'm wrong..xx1+yy1=2C is NOT the tangent's equation..

    This was one blunder on facebook's part though..their sample output was for the number of guards (though it was written that its for warriors).

    Moral of the story is that fb can't organize a coding contest.

    ReplyDelete
  11. AnujJanuary 18, 2011 at 9:21 PM

    This bit was easy anyways..the real problem is that this is an 'approximate' solution..

    Can you tell me why?

    ReplyDelete
  12. Sambhav GuptaJanuary 18, 2011 at 10:20 PM

    because the warriors/soldiers are not perfectly divisible to all real numbers, it is meaningless to say that i have 2.3 soldiers or e or pi soldiers

    ReplyDelete
  13. akash rupelaJanuary 19, 2011 at 1:00 AM

    Shudnt we consider that Wx+Gy<=M and while maximising xy, we have to consider x and y as integers

    That does give the answer of 4th question as 8705, and of 3rd as 4892, (more damage than 8707 and 4893 (Similarly 1st and 2nd can be done)

    ReplyDelete
  14. akash rupelaJanuary 19, 2011 at 7:20 AM

    I mean its possible to reach an exact solution than an approximate one with little reasoning and some uneasy calculations

    ReplyDelete
  15. AnujJanuary 19, 2011 at 12:48 PM

    Thats possible...but its 'N-P complete'...which means that in real life, you can't always compute the exact solution..

    for eg...if M=1123148234979328749283749623472638452098720217868768767657, it would take years for your computer to arrive at the answer!

    An approximate solution would be easy.

    ReplyDelete
  16. akash rupelaJanuary 19, 2011 at 1:12 PM

    right, i just got too emotional on reading the fact at first that the answer is wrong !

    ReplyDelete

Subscribe to: Post Comments (Atom)