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.

Continue reading

GCJ – Template Code

I’ve been participating in the Google Code Jam since last year, and I’ve been having a good time with it.  The problems have a common format, and instead of spending a lot of time rewriting the same code to read in data from a file, write it out with the correct formatting, and so forth, I went ahead and wrote a template for new problems in Python that can handle all of that by itself.

It first runs the precalculate() function to prepare anything (e.g. lookup tables and such) that I want to have before I start the main calculations. Then it reads in the input file from the command line, parses the number of cases to calculate, and uses the read_input() function to parse data for a single case.  It then passes the input data to the solve_case() function, which should solve the problem, and writes the result to the output file in the correct format.

Then to solve a new problem, I need only rewrite these three functions to do what I need. There’s a couple of other helpful things: read_input() has a bunch of parser functions inside it to quickly pull out specific types of data, and there’s a memoize decorator that I can use to give helper functions a cache if needed for efficiency.

Continue reading