Tile Cutting

first we have to figure out how to calculate the are of the parallelogram...if you try to use trig to get the base and height....you'll end up in a world of hurt...It'll work of course, but it's a bit of a pain. If you instead consider the area of the bounding rectangle, and subtracting OUT the 4 triangles, the formula pops out quite easily.

(a+b)(c+d) = area of bounding rectangle
ac/2, bd/2 = area of the two triangles (each duplicated twice
ac + bc + ad + bd - ac - bd = area of parallelogram
= ad + bc

So now what the heck do we do? can't just iterate over all sizes of tile...too many. But we have an area formula (A=ad + bc) and want to know what value of A in a given range gives the most integer solutions. To find the solution for a fixed A, we have to iterate over all possible values for the product ad (we'll call this x), and find the number of ways you can factor it, then check the number of ways we can factor bc = A-ad (we'll call this y). Multiplying x and y should give the total number of different tiles we can make.

So we're done, right? Just iterate from the min to the max, and do the above computation? Yeah no.

The range can be 500,000 and that means the possible value for the product AD can go up to 499,999....(which is not prime by the way)...too long obviously.

And this doesn't include calculating the number of factors of a number....well...turns out we can calculate all the prime factors of all numbers up to N in constant time...code's in the notebook, I think. The total number of factors is a quick extension of that.

So anyway, we do that first and then just have a lookup.

So that doesn't solve the other problem of how to find the max of sum(1,A,factors(i)*factors(A-i))

Solution 1: Precomputation. We can't precompute and store every answer...it would exceed the code size. Instead store the solution for fixed size ranges, say 50 or something. Store those, and then we only have to compute values at run time if the input range doesn't end on a multiple of 5000, in which case we STILL only need to calculate anything at the endpoints of the range, which limits our total number of explicit calculations to 100.

Note: this technique of dividing the whole range into segments and computing a max of those segments, and reevaluating all the points for extrema of an input range is generally done in divisions of square-root N, which limits the total number of lookups to 2*root(n), which is optimal. In our case, we have different constraints so use more segments of smaller size. In either case, I call this the "Square Root Split".

Solutoin 2: if you look at the above summation that we have to compute, we see that it looks strikingly like a convolution....The normal way of calculating a convolution is applying the FFT. In the process of calculating the convolution up to some A which is the max of our range, you incidently also calculate the values of all the values of A up until that value....then you just have to take the max. This happens in O(nlogn) where n is the size of the range. Details are left to the reader.