Google Code Jam's Cookie Clicker Program...

Question

Today, the Google Code Jam's cookie clicker problem was something like this.

Problem

In this problem, you start with 0 cookies. You gain cookies at a rate of 2
cookies per second, by clicking on a giant cookie. Any time you have at least C cookies, you can buy a cookie farm. Every time you buy a cookie farm, it costs
you C cookies and gives you an extra F cookies per second.

Once you have X cookies that you haven't spent on farms, you win! Figure out how long it will take you to win if you use the best possible strategy.

I approached the problem something like this:
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 $= \sum_{i=1}^{n-1}\frac{C}{a+(i-1)F}$

Therefore LHS becomes:
$$\sum_{i=1}^{n-1}\frac{C}{a+(i-1)F} + \frac{X}{a+(n-1)F}$$

RHS becomes
$$\sum_{i=1}^{n-1}\frac{C}{a+(i-1)F} + \frac{X}{a+nF} + \frac{C}{a+(n-1)F}$$

by rearranging the equations,

$\begin{align} \frac{X}{a+(n-1)F} > \frac{X}{a+nF} + \frac{C}{a+(n-1)F} \tag{eq.1}\\ \frac{X}{a+(n-1)F} - \frac{X}{a+nF} > \frac{C}{a+(n-1)F}\\ \end{align}$

After some rearrangements, it becomes:

$\begin{align} \frac{ XF}{a+nF} > C \\ XF > C(a+nF) \\ \frac{ XF}{C} > a + nF \\ \frac{ XF}{C} - a > nF \\ \frac{ 1}{F}\left(\frac{XF}{C}-a\right) > n \\ \frac{ X}{C} - \frac{a}{F} > n \\ \end{align}$

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.
With $n$ Farms, the total time taken to reach the goal would be given by RHS of (eq.1)

With this derivation, I checked the outputs for the examples they have given namely:

Input

4 ==> no of test cases
30.0 1.0 2.0
30.0 2.0 100.0
30.50000 3.14159 1999.19990
500.0 4.0 2000.0

Output
Case #1: 1.0000000
Case #2: 39.1666667
Case #3: 63.9680013
Case #4: 526.1904762

I used the equation and tested in it each of the samples and the answers were correct to the last of the decimal in all these four cases. However, when I produced the results using the same code based on the same equation for their problem input with 100 cases, google rejected my outputs.

Could anyone point me when my logic breaks or what could be the reason, google didn't accept my solution?

Answer 1

Here is a thought:

First, define $t_n(k)=$ time to win given $n$ farms and $k$ starting cookies (and never buying additional farms). Clearly, $t_n(k)=\frac{X-k}{nF+2}$.

Now, your idea was that there exists a number of farms that buying any more will result in a suboptimal strategy. Also, if we intend to buy a farm, we should purchase it as soon as we can (otherwise we lose out on cookie revenue). So, we should buy a farm when $t_{n+1}(0)\leq t_n(C)$, and when that no longer is satisfied, we should just keep clicking on the cookie.

Suppose we have the optimal $n$ farms and $C$ cookies. Then, $$ t_n(C) < t_{n+1}(0) \iff \frac{X-C}{nF+2} < \frac{X}{(n+1)F+2} \iff \frac{X}{C}-\frac{2}{F}-1 < n. $$ Thus, we pick the smallest such $n$ as the optimal value of farms.

This agrees remarkably well with your answer, with a little less algebra.

Answer 2

Here is my PHP code below that I used in this problem. I'm curious as to why your equations are so big?

My maths skills wouldnt be great but surely the equation can be smaller than above?

while(($goal/$cookies_per_sec) > (($cost_of_farm/$cookies_per_sec)+ ($goal/($cookies_per_sec+$factory_rate))))
{
    $time = $time + $cost_of_farm/$cookie_per_sec;
 $cookies_per_sec = $cookies_per_sec + $factory_rate; 
}
$answer = $time + ($goal/$cookies_per_sec);