I attempted the second problem, which took all the time irrespective of my confidence in my logic. I mean I tested my algorithm with the samples given in the problem page and was able to get answers correct to the last decimal. However, when I used their input and produced the output, Google Code Jam didn't accept my outputs. I'm totally at loss where the problem was... And I posted the problem in Stack Exchange, where many seems to agree with my logic.
Losing the qualification round is painful, but I would be worth it if I could know where I went wrong... Here is the logic I came with... (with some algebra...): Let us assume, n as the minimum number of Farms to buy to win in the shortest time. n is a non-negative integer value. a is the number of cookies one gets per second, a=2; n is the minimum number of farms to buy to win, if and only if the following equation is satisfied... i.e time taken to buy n−1 farms + time to reach goal with (n−1) Farms > time taken to buy n farms + time to reach goal with n Farms However, time taken to buy n Farms =∑C/(a+(i−1)F); i = 1,...,n Therefore LHS becomes: (∑C/(a+(i−1)F))+(X/(a+(n−1)F)) RHS becomes (∑C/(a+(i−1)F))+(X/(a+nF))+C/(a+(n−1)F) by rearranging the equations, (X/(a+(n−1)F))>(X/(a+nF))+(C/(a+(n−1)F))(eq.1) (X/(a+(n−1)F))−(X/(a+nF))>(C/(a+(n−1)F)) After some rearrangements, it becomes: XF/(a+nF)>C XF>C(a+nF) XF/C>a+nF (XF/C)−a>nF (1/F)((XF/C)−a)>n (X/C)−(a/F)>n or n <(X/C)−(a/F) --- by ensuring that n is an non-negative integer, this equation would give the minimum number of farms,n, to buy. Assuming it is not possible to buy fraction of farms With n Farms, the total time taken to reach the goal would be given by RHS of (eq.1) Could anyone tell me, where I went wrong? As I sample, I tried with the samples and produced results correct to the last decimal...! -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/5d9cb132-96d9-43df-9a82-3705895148d4%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
