notes.html

problem 53 · 18 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem sits squarely in <a class="reference-source" href="https://en.wikipedia.org/wiki/Combinatorics" rel="noopener noreferrer" target="_blank">combinatorics</a>, and its difficulty is not conceptual but arithmetic. The object of interest is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Binomial_coefficient" rel="noopener noreferrer" target="_blank">binomial coefficient</a> C(n, r) = n! / (r!(n-r)!), which counts how many ways one can choose r items from n distinct items without regard to order. The naive route - computing the three factorials and dividing - is a trap: 100! has more than 150 decimal digits, so building it explicitly forces big-integer arithmetic and burns time dividing enormous numbers. The real skill here is finding a way to obtain the coefficients without ever touching a factorial.
</p>
<p>
Two structural facts about <a class="reference-source" href="https://en.wikipedia.org/wiki/Pascal%27s_triangle" rel="noopener noreferrer" target="_blank">Pascal's triangle</a> make this clean. First, each row - the values C(n, 0), C(n, 1), ..., C(n, n) - is symmetric, since C(n, r) = C(n, n-r), and it is unimodal: it rises monotonically to a single peak near r = n/2 and then falls. A unimodal sequence is one that increases up to one maximum and then decreases, so once a value crosses a threshold on the way up it stays above it until the peak. This means that as soon as I find the first r whose coefficient exceeds one-million, every entry from r through n-r also exceeds it, and I can count them all with a formula instead of evaluating them. Second, neighbouring coefficients in a row are related by the multiplicative recurrence C(n, r+1) = C(n, r) * (n - r) / (r + 1), so I can walk along a row one cell at a time using only modest-sized multiplications and an exact division. The worst-case complexity is O(max_n^2) - every row scanned to its midpoint - but the early exit trims most rows to a handful of steps, and with max_n capped at 100 the total work is trivial.
</p>
<h3>Solution Approach</h3>
<h4>Incremental Row Traversal with Symmetry Early-Exit</h4>
<p>
Both the C and Python files implement one and the same algorithm. I iterate over each row n from 1 to max_n. Within a row I initialise the running coefficient <code>c</code> to C(n, 0) = 1 and step r from 0 up to n/2 - only the left half, because symmetry will account for the right. At each step I test whether <code>c</code> already exceeds the threshold. If it does, I know from unimodality that every coefficient from index r up to the midpoint qualifies, and by symmetry their mirror images from the midpoint to n-r qualify too. The number of qualifying entries is therefore exactly n - 2*r + 1, the count of integers from r to n-r inclusive. I add that and break out of the inner loop immediately. If <code>c</code> has not yet crossed the threshold, I advance to the next cell with <code>c = c * (n - r) / (r + 1)</code> and continue.
</p>
<p>
The crucial arithmetic decision is multiplying before dividing in the recurrence. Because every binomial coefficient is a whole number, the product <code>c * (n - r)</code> is always exactly divisible by <code>(r + 1)</code>, so doing the multiplication first guarantees the integer division is exact and loses nothing. The two implementations differ only in language detail. The C version reads max_n and threshold from the command line via <code>parse_int</code>, and accumulates the running coefficient in a <code>long long</code> so the intermediate values - which grow large as n approaches 100 - do not overflow. The Python version takes the same two inputs and relies on Python's arbitrary-precision integers, so overflow is simply impossible; it uses floor division <code>//</code> where C uses truncating <code>/</code>, but since the division is always exact the distinction never bites.
</p>
</article>