2013 Google Code Jam Round 1A

Well that was a bust.  I figured out how to do the first problem within the first 15 minutes, and spent the rest of my time screwing it up.  The problem is as follows...

Problem

Maria has been hired by the Ghastly Chemicals Junkies (GCJ) company to help them manufacture bullseyes. A bullseye consists of a number of concentric rings (rings that are centered at the same point), and it usually represents an archery target. GCJ is interested in manufacturing black-and-white bullseyes.



Maria starts with t millilitres of black paint, which she will use to draw rings of thickness 1cm (one centimetre). A ring of thickness 1cm is the space between two concentric circles whose radii differ by 1cm.

Maria draws the first black ring around a white circle of radius r cm. Then she repeats the following process for as long as she has enough paint to do so:

1. Maria imagines a white ring of thickness 1cm around the last black ring.
2. Then she draws a new black ring of thickness 1cm around that white ring.

Note that each "white ring" is simply the space between two black rings.

The area of a disk with radius 1cm is π cm². One millilitre of paint is required to cover area π cm². What is the maximum number of black rings that Maria can draw? Please note that:

• Maria only draws complete rings. If the remaining paint is not enough to draw a complete black ring, she stops painting immediately.
• There will always be enough paint to draw at least one black ring.

My Solution

The key here is writing a generalized expression relating area to number of rings...  Lets start with the area for the ith ring... this will be the area of the circle with a radius going to the outside of the black paint, minus the area of the paint just inside the black line...

Equation 1: Area of ring #i

Here, R is the radius just at the inside of the ith ring, and we know that the ring radius will be one centimeter larger.  Next, lets formalize the radius with respect to the ring number...

Equation 2: Incorporating formalized Ri

Now all we need to do is sum all N of our rings... which means summing from 0 to N-1, the way we formulated our answer...

Equation 3: Total Area of paint as a function of N rings

Equation 3 gives us a total area... and the problem specifies that 1 ml of paint covers an area of pi... we get a final answer as follows...

Equation 4: Quadratic equation for number of rings that can be painted

So this is where I made my big mistake... I have a quadratic equation that I can stuff into the Quadratic Formula... so that is what I did.  Convert everything to double precision and solve.  Then the number of rings would be the floor of the solution to this equation.  But double precision runs into rounding errors... I'd get answers that would be correct MOST of the time, and then fail for edge cases where rounding matters, and you can bet Google checks for rounding.

However, I was convinced that I had made an algebra mistake, and so I went through this math several times, trying to figure out if I had an off by one error.  I was left with only a few minutes to work through the rest of this problem, when it occurred to me that left in the final form in equation 4, I could use a binary search to finish the search in a way that wouldn't induce round-off errors.

Unfortunately, my first attempt at the binary search for the small set didn't pass, and at this point, the round ended.  I'm pretty much convinced that my approach was correct, but I got caught in the technical details of the solution, which killed me.  I'll be back next week, trying to get through to Round 2.  But I'll have to do a lot better than this.  None the less, Google Code Jam is always my favorite programming event of the year, and this is no exception.  Cheers, Google!