Bullseye (Google Code Jam 2013, round 1A, problem A)
I only solved one problem in GCJ 2013 round 1A, and that's problem A, Bullseye. I really liked my solution to this problem (written in Racket):
(define (rings r t) (quotient (- (integer-sqrt (+ (* 4 r r) (* -4 r) (* 8 t) 1)) r r -1) 4))
Is the problem really that simple? Why, yes! It's much simpler than many other entries I've seen, so I wanted to explain my solution approach.
So, let's look at the problem step by step:
You are given t units of paint, and each unit of paint fills in a circle of radius 1.
This means that it takes 4 units of paint to fill in a circle of radius 2, 9 units for radius 3, etc., and generally, n² units to fill in a circle of radius n.
For a black ring with inner boundary r, and outer boundary r + 1, the total units used is, thus, (r + 1)² - r², or fully expanded as 2r + 1.
The next black ring has inner boundary r + 2, and outer boundary r + 3. More generally, for ring i, the inner boundary is r + 2i - 2, and the outer boundary is r + 2i - 1.
The total paint used for the first k rings is thus (2r + 1) + (2r + 5) + (2r + 9) + … + (2r + 4k - 3).
This is the same as k(2r - 3) + 4(1 + 2 + … + k), or in other words, k(2r - 3) + 2k(k + 1), which then becomes 2k² + (2r - 1)k.
You want to find the largest k is that satisfies 2k² + (2r - 1)k ≤ t, or in other words, 2k² + (2r - 1)k - t ≤ 0.
Solving this is easy: just use the quadratic formula! In this case, the factors used are a = 2, b = 2r - 1, and c = -t. Plugging this into the quadratic formula gives ((1 - 2r) ± sqrt((2r - 1)² + 8t)) / 4.
We only care about the positive (you can't have a negative number of rings), so this simplifies to (sqrt(4r² - 4r + 8t + 1) - 2r + 1) / 4, which is almost exactly the code you see.
Finally, we are asked to disregard partial rings, so we simply floor the result. Done.
