Bullseye, Round 1A 2013

This is a largely mathematical problem: the first ring will use units of paint, the second units, and so forth, so that the ring will require

, or

units of paint. I.e., each ring will take a constant amount of paint () plus some varying amount depending on how far out it is (). That second sequence is 1, 5, 9, 13, 17, 21, etc. But the question we want to answer is not how much paint *each* ring will take, but how many rings we can paint with a given amount of paint.

One way to solve this problem would be to simply add up the paint as we paint each ring until we don’t have enough paint to go on, then report the number of the last complete ring. This solution will work for the small problem, but will fail on the large problem as it is linear in , and in the large problem can be very very large.

We can resolve this by finding a closed form solution for the sum of all from 1 to k. We first note that there is a constant amount of paint for each ring, so we can sum up that part simply as . The first few variable sums are 1, 6, 15, 28, 45…, which we can recognize as the sequence of hexagonal numbers with closed form solution . This gives us:

Now that we have a closed form solution, we can try to substitute in , the total amount of paint we have, for , solve for , and round down to obtain the maximum number of complete rings we can draw, in constant time, much better than linear! This is a quadratic, and we obtain the (positive) solution

We’re done, right? Well, this solution will work fine for the small input, and in constant time. But it will fail dramatically on the large input. Why? Because we’re taking square roots of very large integers, which transforms them from integers (which are stored with perfect precision) to floating point numbers (which are stored with limited precision), and with the limits we’re given, the precision of floating points isn’t sufficient to give us the right answer this way.

So we need to use a different method. Again, what we want to do is find such that while . Simply walking through increasing values of is too slow for the large input. So instead we can do a binary search. We’re guaranteed in the problem statement that . So let’s start a lower limit for our search at . We’ll start an upper limit at . It’s probably not an upper limit yet, but we’ll make it so by iteratively doubling both our limits until it is: find the first power of 2 where . Then is somewhere in the interval . We can find its exact value by repeatedly subdividing this interval until it is narrowed down to a single value.

Here’s the final code, as built around my Google Code Jam template.

def how_much_paint(r, k): """How much paint is needed to paint k black rings starting at radius r? """ return 2 * r * k + k * (2 * k - 1) def solve_case(case): """Take the input data (structured in case) and perform any necessary calculations to obtain the desired output, formatted as the appropriate string. """ r, t = case #Do a one-sided binary search on k to find the maximum number of rings #possible with how much paint we have #Initialize the number of rings to 1 k_lo = 0 k_hi = 1 #First we find the interval by incremental doubling while how_much_paint(r, k_hi) <= t: k_lo = k_hi k_hi *= 2 #Then we binary search in that interval while k_hi - k_lo > 1: k_mid = k_lo + (k_hi - k_lo) / 2 #N.B. integer division if how_much_paint(r, k_mid) > t: k_hi = k_mid elif how_much_paint(r, k_mid) <= t: k_lo = k_mid return k_lo

Pingback: Google Code Jam – Summary | Reflections of Dusk