notes.html

problem 15 · 82 lines

<article>
<h3>Problem Analysis</h3>
<p>
The problem asks how many monotone
<a class="reference-source" href="https://en.wikipedia.org/wiki/Lattice_path" rel="noopener noreferrer" target="_blank">lattice paths</a>
exist from the top-left corner to the bottom-right corner of an n x n grid, where each step can
only move right or down. The crucial observation is that the geometry of the grid is irrelevant to
the count: any valid path consists of exactly 2n unit steps, of which n must go right and n must go
down. A path is fully determined by the order in which we interleave these two kinds of moves.
Counting paths therefore reduces to counting the ways to choose which n of the 2n positions in the
move sequence are "right" moves (the remaining n are automatically "down" moves). That count is
precisely the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Binomial_coefficient" rel="noopener noreferrer" target="_blank">binomial coefficient</a>
C(2n, n) = (2n)! / (n! * n!), known here as the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Central_binomial_coefficient" rel="noopener noreferrer" target="_blank">central binomial coefficient</a>.
For n = 20 the answer is C(40, 20) = 137,846,528,820, which fits in a signed 64-bit integer; for the
extra test case n = 200 the answer is a 120-digit number, which forces us to use
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision</a>
("big integer") arithmetic.
</p>
<p>
This reframing - from "simulate or enumerate paths" to "evaluate one closed-form expression" - is
what makes the problem trivial. There is no need for
<a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a>
over the grid, no recursion, no path-counting table. The remaining concern is purely arithmetic:
how to compute the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Central_binomial_coefficient" rel="noopener noreferrer" target="_blank">central binomial coefficient</a>
without producing absurdly large intermediate values. Computing (2n)! and (n!)^2 separately works
but creates enormous factorials. A better route is the incremental product form
C(2n, n) = product over i from 1 to n of (n + i) / i, which interleaves multiplication and division
to keep partial values small. Either way the cost is O(n) arithmetic operations on integers whose
size grows as O(n log n) bits, giving an overall bit-complexity of about O(n^2 log n) - entirely
negligible for the sizes here.
</p>
<h3>Solution Approach</h3>
<h4>Central Binomial Coefficient (Python and C)</h4>
<p>
Both the Python and C solutions compute the same quantity, the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Central_binomial_coefficient" rel="noopener noreferrer" target="_blank">central binomial coefficient</a>
C(2n, n), and differ only in how they manage
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision</a>
arithmetic.
</p>
<p>
<strong>Python (p0015_s0.py):</strong> I wrote the answer in a single line,
<code>math.factorial(2 * lattice_size) // math.factorial(lattice_size) ** 2</code>.
Python integers are
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision</a>
by default, so there is no overflow to worry about and no custom arithmetic to implement. I used
floor division (<code>//</code>) rather than true division (<code>/</code>) because the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Binomial_coefficient" rel="noopener noreferrer" target="_blank">binomial coefficient</a>
is always an exact integer and I want to avoid floating-point rounding entirely.
<code>math.factorial</code> is implemented in C inside the interpreter, so even for n = 200 this is
effectively instantaneous. This is the simplest correct solution available in the language.
</p>
<p>
<strong>C (p0015_s0.c):</strong> C has no native big integers, so I implemented a minimal
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision</a>
integer type and used the product form rather than factorials. The <code>BigInt</code> struct
stores the number as an array of base-10^9 "limbs" in
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
order (index 0 holds the least significant chunk). I chose base 10^9 because a limb fits inside a
32-bit value, yet I store each limb in a 64-bit <code>unsigned long long</code>, leaving ample
headroom for the intermediate product <code>limb * multiplier + carry</code> in a multiply step
- the multiplier is at most 2n = 400, far below the 64-bit overflow threshold.
</p>
<p>
The <code>solve</code> function initialises the result to 1 with <code>bi_set</code>, then loops
i from 1 to n, calling <code>bi_mul_ll(&amp;result, n + i)</code> followed by
<code>bi_div_ll(&amp;result, i)</code>. The ordering is deliberate: the running value after step k
equals C(n + k, k), which is always an integer, so each division by i is exact and never discards a
remainder. <code>bi_mul_ll</code> propagates a carry upward through the limbs (natural for
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
storage), and <code>bi_div_ll</code> sweeps from the top limb downward, carrying a remainder into
lower limbs - the standard
<a class="reference-source" href="https://en.wikipedia.org/wiki/Long_division" rel="noopener noreferrer" target="_blank">long division</a>
direction. Finally <code>bi_to_str</code> prints the most significant limb with no leading zeros
and every subsequent limb as exactly nine zero-padded decimal digits, which reconstructs the full
decimal number directly from the base-10^9 representation.
</p>
</article>