Code Jam 2014 Qualification
Posted on 8th April 2015
While on holiday, what better way to unwind than solve some old Code Jam puzzles?
As ever, the Official Analysis is very good, and similar to my approaches. Some code on GitHub.
Problem A: Trivial.
Problem B: The official writeup draws some graphs, but you can argue quite algebraically.
- Once you have C cookies, it doesn't make sense to delay upgrading.
- So the optimal strategy is to keep getting to C cookies, upgrade, and then eventually decide to stop and just generate the needed X cookies.
- What to stop?
- If you stop after n=0,1,2,... upgrades then the time taken is
\[ T_n = \frac{C}{2} + \frac{C}{2+F} + \frac{C}{2+2F} + \cdots + \frac{C}{C+(n-1)F} + \frac{X}{2+nF} \]
Then we can check that \( T_{n+1} < T_n \) if and only if \( n+1 < \frac{X}{C} - \frac{2}{F} \). It follows from this if and only if that the sequence \( (T_n) \) will decrease, bottom out, and then forever increase. So \( T_N \) is minimal if \( N \) is maximal with \( N < \frac{X}{C} - \frac{2}{F} \) or equivalently \( N = \lceil \frac{X}{C} - \frac{2}{F} \rceil - 1 \).
- So we simply compute \( T_N \) for this value; I went to the effort of summing from the least to greatest values to reduce round-off errors.
Problem C: Just draw a lot of pictures!
Problem D: I worked out Ken's optimal strategy, and it seemed intuitively clear that Naomi couldn't change this, but I couldn't find a formal proof (the official writeup has a very nice one). The optimal strategy in Deceitful War is also reasonably clear, once you draw a few arrangements of weights.