notes.html

problem 85 · 77 lines

<article>
<h3>Problem Analysis</h3>
<p>
The heart of this problem is a counting question: how many distinct sub-rectangles fit inside an
<code>H x W</code> grid? The naive mental model is to slide every possible smaller rectangle across
every position, but there is a far cleaner way to see it. A grid of height <code>H</code> and width
<code>W</code> is bounded by <code>H + 1</code> horizontal lines and <code>W + 1</code> vertical
lines. Any rectangle is uniquely determined by choosing two of the horizontal lines (its top and
bottom edges) and two of the vertical lines (its left and right edges). Because the choice along
each axis is completely independent of the other, the total count factors into a product. This is
the structural insight that turns a two-dimensional search into something far smaller.
</p>
<p>
The number of ways to choose 2 items from <code>n</code> is the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Binomial_coefficient" rel="noopener noreferrer" target="_blank">binomial coefficient</a>
<code>C(n, 2) = n*(n-1)/2</code>. Choosing 2 lines from <code>H + 1</code> lines therefore gives
<code>(H+1)*H/2</code>, which is exactly the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Triangular_number" rel="noopener noreferrer" target="_blank">triangular number</a>
<code>T(H) = H*(H+1)/2</code> - the running sum <code>1 + 2 + ... + H</code>. So the total rectangle
count for an <code>H x W</code> grid is <code>T(H) * T(W)</code>. With <code>3 x 2</code> this gives
<code>T(3) * T(2) = 6 * 3 = 18</code>, matching the worked example. This factored form is the key
observation: instead of enumerating all rectangles, we only need to find the pair of triangular
numbers whose product is closest to two million. Since the triangular numbers form a strictly
increasing sequence, we can iterate over one axis and use a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Binary_search_algorithm" rel="noopener noreferrer" target="_blank">binary search</a>
on the other, giving an <code>O(max_side * log(max_side))</code> algorithm. The brute-force
alternative that literally sums over every sub-rectangle position is <code>O(max_side^2)</code>
in the outer loop with an additional <code>O(H*W)</code> inner cost per pair - correct, but far
slower, and useful mainly for illustrating the definition.
</p>
<h3>Solution Approach</h3>
<h4>Algorithm 0 - Brute-Force Position Counting (s0)</h4>
<p>
This approach counts rectangles exactly as the definition suggests. In
<code>num_rectangles(height, width)</code> I sum <code>(height - h + 1) * (width - w + 1)</code>
over every sub-rectangle dimension <code>(h, w)</code>. The term <code>(height - h + 1)</code> is
the number of vertical positions a sub-rectangle of height <code>h</code> can occupy, and likewise
for width; multiplying and summing over all <code>(h, w)</code> yields the total. I then iterate
over every grid shape <code>(height, width)</code> and track the count closest to the target.
</p>
<p>
The Python version (<code>p0085_s0.py</code>) uses <code>itertools.product</code> to generate the
grid shapes and stores every result in a dictionary keyed by count, then selects the global best
with a single <code>min(..., key=delta)</code> call. The C version (<code>p0085_s0.c</code>)
performs the same nested summation but keeps only a running <code>best_area</code> and
<code>best_delta</code>, avoiding the memory overhead of a dictionary. Both versions break out
early once a count falls within <code>max_error</code> of the target; in C this early exit uses
<code>goto done</code> to escape both loops cleanly. This algorithm is instructive but expensive -
the inner double loop recomputes the count from scratch for every grid shape.
</p>
<h4>Algorithm 1 - Triangular-Number Binary Search (s1)</h4>
<p>
This approach exploits the factored formula <code>count(H, W) = T(H) * T(W)</code>. I precompute
an array <code>numbers</code> where <code>numbers[i] = T(i+1)</code> for lengths from 1 up to
<code>max_side - 1</code>. Because
<a class="reference-source" href="https://en.wikipedia.org/wiki/Triangular_number" rel="noopener noreferrer" target="_blank">triangular numbers</a>
increase monotonically, this array is sorted and supports
<a class="reference-source" href="https://en.wikipedia.org/wiki/Binary_search_algorithm" rel="noopener noreferrer" target="_blank">binary search</a>.
In the Python version <code>num_rectangles_along_axis</code> computes <code>T(length)</code> by the
explicit running sum, while the C version uses the closed form <code>length*(length+1)/2</code>;
both yield the same sequence.
</p>
<p>
For each width <code>w</code> I read off <code>num_width = T(w)</code> and ask: what height
<code>H</code> makes <code>T(H) * num_width</code> closest to the target? That ideal satisfies
<code>T(H) ~= target / num_width</code>. I locate the insertion point of <code>target /
num_width</code> in the sorted array using <code>bisect.bisect_left</code> in Python or a hand-rolled
<code>bisect_left</code> in C. The closest triangular number must be one of the two neighbours of
that insertion point, so I evaluate both candidates, compute their products with
<code>num_width</code>, and update the running best. The same early-exit on <code>max_error</code>
applies, but now it triggers far sooner because each inner step is <code>O(log n)</code> rather
than a linear scan. The C version frees its allocated array before returning, and uses integer
division for <code>target / num_width</code> - acceptable here because the array neighbours bracket
the true closest value regardless of the small rounding from truncation.
</p>
</article>