# GCJ – Bullseye

Bullseye, Round 1A 2013

This is a largely mathematical problem: the first ring will use $(r + 1)^2 - r^2$ units of paint, the second $(r + 3)^2 - (r + 2)^2$ units, and so forth, so that the $k^{th}$ ring will require
$P(k) = (r + 2k - 1)^2 - (r + 2k - 2)^2$, or
$P(k) = 2r + (4k - 3)$
units of paint. I.e., each ring will take a constant amount of paint ($2r$) plus some varying amount depending on how far out it is ($4k - 3$). 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 $k$, and $k$ in the large problem can be very very large.

We can resolve this by finding a closed form solution for the sum of all $P(k)$ 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 $2rk$. 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 $k(2k - 1)$. This gives us:
$P_{total}(k) = 2rk + k(2k-1)$

Now that we have a closed form solution, we can try to substitute in $t$, the total amount of paint we have, for $P_{total}$, solve for $k$, 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
$k = \lfloor \sqrt{4r^2 - 4r + 8t + 1} - \frac{2r - 1}{4} \rfloor$

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 $k$ such that $P_{total}(k) \le t$ while $P_{total}(k+1) > t$. Simply walking through increasing values of $k$ is too slow for the large input. So instead we can do a binary search. We’re guaranteed in the problem statement that $k \ge 1$. So let’s start a lower limit for our search at $k_{low} = 1$. We’ll start an upper limit at $k_{hi} = 2$. 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 $P_{total}(2^i) > t$. Then $k$ is somewhere in the interval $[k_{low}, k_{hi})$. 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