photo by stevendepolo

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², 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

    let mut paint_used = 0;
    let mut rings_drawn = 0;

    loop {
      let current_r = 2 * rings_drawn + r;
      let paint_needed = 2 * current_r + 1;
      if (paint_needed + paint_used > t) {
        break;
      }
      paint_used += paint_needed;
      rings_drawn += 1;
    }

Complexity is O(N) with N dependent upon t-r. This took care of the small dataset fine. However, for a small radius and lots of paint - up to 10^¹⁸ - this could take long. Indeed, my first test with large-dataset-type 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

// Coefficient `b`.                                                         
let b: int = 2*r-1;
// BigInt `b`.                                                              
let bigb = ~bigint::BigInt::from_uint(b.to_uint());
// b^2 - 4ac                                                                
let bsquared_minus4ac = ~bigint::BigInt::from_uint(t.to_uint())
    .mul(~bigint::BigInt::from_uint(8)).add(~bigb.mul(bigb));
// -b + sqrt(b^2 - 4ac) / 2 * a                                             
let x = (bigroot(bsquared_minus4ac).to_uint().to_int() - b) / 4;

No built in BigInt sqrt, had to use Newton’s method:

1
2
3
4
5
6
7
8
9
10
11
12

fn bigroot(N: &bigint::BigInt) -> ~bigint::BigInt {
  // Any bigger than this is overflow.
  let mut x = ~bigint::BigInt::from_uint(10000000000000000000);
  let two = ~bigint::BigInt::from_uint(2);
  loop {
    let y = ~N.div(x).add(x).div(two);
    if y >= x {
      return x;
    }
    x = y;
  }
}

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

// Double the ring size till we surpass total paint.
while t > computeTotalPaint(r, high) {
  low = high;
  high *= 2;
}

let mut rings = 0;
// Answer now bounded between low/high. Binary search.
while low <= high {
  let mut mid = (high + low)/2;
  match (t, computeTotalPaint(r, mid)) {
    (x, y) if x > y => { low = mid+1; }
    (x, y) if x < y => { high = mid-1; }
    (_, _) => { rings = mid; break; }
  }
  rings = high;
}

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