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
Advertisements

One thought on “GCJ – Bullseye

  1. Pingback: Google Code Jam – Summary | Reflections of Dusk

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s