Problem 1A in Code Jam 2013 involved finding the maximum number of rings that could be drawn when creating an archery target; the starting radius r
and paint supply t
vary.
I cranked out a naive implementation for the small problem set which looped through the formula for calculating paint used for each ring, summing it up along the way and comparing against the max paint supply. Since 1 mL of paint conveniently covers exactly pi cm^{2}, pi was omitted. Given radius r
, the paint required for the k
^{th} ring is found by:
This was also the first time I’d used Mozilla Research’s Rust, though I did gear up for the contest by preparing a vanilla template. As with any new language, the syntax isn’t completely cast in iron, and if you google around, you’ll see some examples with slight differences. All code samples are relevant for version 0.6:
1 2 3 4 5 6 7 8 9 10 11 12 

Complexity is O(N) with N dependent upon tr
. This took care of the small dataset fine. However, for a small radius and lots of paint  up to 10^^{18}  this could take long. Indeed, my first test with largedatasettype numbers crawled. I immediately looked for the fastest solution I could think of, which involved arithmetic series:
computing total paint for j
rings
and solving for the positive root using the quadratic equation, given p
as paint used:
And in code:
1 2 3 4 5 6 7 8 9 

No built in BigInt sqrt
, had to use Newton’s method:
1 2 3 4 5 6 7 8 9 10 11 12 

The good news was that the solution was constant time, O(1). The bad news was computation, debugging and BigInt wrangling ate up too much time so I failed to submit before the contest ended.
Turns out there’s a better approach here. Part of an earlier calculation yielded the formula for computing how much total paint would be used for j
number of rings. This could be used to approach the paint available t
in faster than linear time. In fact, a binary search did occur to me at one point. It’s orders of magnitude faster, but given how slowly the O(N) solution was executing, I figured O(log N) wouldn’t make much difference. Sucker ran nearly as fast as the O(1) solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

Given the time constraints in Code Jam, sometimes it’s difficult to stop and guage what’s going to be fast enough. Then again, I should be able to adapt binary search into any solution fast enough by now, that a quick check shouldn’t cost much more than a few minutes.
The Rust templates for all the code above are on github: Rust Code Jam templates