Detailed mathematical approach

Problem Summary

The problem constructs a downward triangular array with \(n=1000\) rows, so the total number of entries is \(1+2+\cdots+1000=500{,}500\). The entries are generated in row-major order by the linear congruential recurrence \(t_0=0\), \(t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}\), and \(s_k=t_k-2^{19}\). We must find the downward-pointing sub-triangle whose total sum is as small as possible.

If every candidate sub-triangle were summed from scratch, the computation would be far too slow. The key mathematical observation is that increasing the height of a sub-triangle adds exactly one contiguous segment on the next row, so row prefix sums turn each extension into an \(O(1)\) update.

Mathematical Approach

Let the generated triangle be \(a_{r,c}\) with \(0\le c\le r<n\). A sub-triangle is determined by its apex \((r,c)\) and its height \(h\ge 1\). Its sum is

$T(r,c,h)=\sum_{i=0}^{h-1}\sum_{j=0}^{i} a_{r+i,c+j},\qquad 1\le h\le n-r.$

The problem is to minimize \(T(r,c,h)\) over all valid triples \((r,c,h)\).

Encoding the triangular array

The pseudo-random generator is part of the mathematics, not just an implementation detail, because the data set is defined by that recurrence alone. After generating \(s_1,s_2,\dots\), the values are placed row by row: one value in the first row, two in the second, three in the third, and so on until row 1000 is complete.

The modulus is \(2^{20}\), so every raw state \(t_k\) lies in \(\{0,1,\dots,2^{20}-1\}\). Subtracting \(2^{19}\) shifts the numbers into the signed range \([-2^{19},2^{19}-1]\). Since many entries are negative, the minimum is not forced to be a single entry; a larger region can become more negative when several adverse rows align.

Why row prefix sums fit the geometry

A downward sub-triangle is not rectangular. On row \(r+i\), it covers exactly the contiguous block \(a_{r+i,c},a_{r+i,c+1},\dots,a_{r+i,c+i}\). That makes row-wise prefix sums the natural coordinate system. Define

$P_r(m)=\sum_{j=0}^{m-1} a_{r,j},\qquad P_r(0)=0.$

Then any contiguous segment on row \(r\), starting at column \(c\) and having length \(\ell\), has sum

$\sum_{j=0}^{\ell-1} a_{r,c+j}=P_r(c+\ell)-P_r(c).$

Substituting the correct segment length \(\ell=i+1\) for each row of the sub-triangle gives

$T(r,c,h)=\sum_{i=0}^{h-1}\bigl(P_{r+i}(c+i+1)-P_{r+i}(c)\bigr).$

This identity is the reason the problem is tractable: each row contribution is reduced to the difference of two prefix values.

The fixed-apex growth recurrence

Once the apex \((r,c)\) is fixed, growing the triangle from height \(h\) to height \(h+1\) leaves all previously counted rows unchanged. The only new contribution is the bottom segment on row \(r+h\). Therefore

$T(r,c,h+1)=T(r,c,h)+P_{r+h}(c+h+1)-P_{r+h}(c).$

This recurrence is the core invariant used by all three implementations. After the first row is known, every extra height step costs constant time, because the upper part of the triangle never has to be recomputed.

Worked example on the six-row sample

The checkpoint triangle used by the implementations is

$\begin{array}{r} 15\\ -14\ -7\\ 20\ -13\ -5\\ -3\ 8\ 23\ -26\\ 1\ -4\ -5\ -18\ 5\\ -16\ 31\ 2\ 9\ 28\ 3 \end{array}$

Its minimum-sum sub-triangle has apex at the second row, second entry, and height \(4\). The four row contributions are

$-7,\qquad (-13)+(-5)=-18,\qquad 8+23-26=5,\qquad -4-5-18+5=-22,$

so the total is

$-7-18+5-22=-42.$

The recurrence above reproduces this exactly: start from the apex value \(-7\), then add one wider row segment at each step.

Enumerating every candidate without recomputation

There are two equivalent ways to organize the loops. One can fix an apex \((r,c)\) and extend its height one row at a time, or one can fix a top row \(r\) and update the current sums for every apex on that row simultaneously as the bottom row moves downward. Both viewpoints rely on the same quantity:

$A_{r,b}(c)=\sum_{i=r}^{b}\bigl(P_i(c+i-r+1)-P_i(c)\bigr),$

which is exactly the sum of the sub-triangle with apex \((r,c)\) and bottom row \(b\). When \(b\) increases by \(1\), one more row segment is added and nothing else changes.

The number of candidates is

$\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)=\frac{n(n+1)(n+2)}{6}.$

For \(n=1000\), this is \(167{,}167{,}000\) sub-triangles. That is large but still feasible because each one is obtained by a constant-time update from the previous height.

How the Code Works

Generating the data and prefix tables

The C++, Python, and Java implementations first rebuild the entire pseudo-random triangle in memory. They also prepare one prefix-sum table per row, with a leading zero so that every row segment can be read by subtracting two prefix entries.

The running totals and the best answer are stored in 64-bit integer types. That is necessary because a large sub-triangle can contain hundreds of thousands of terms, so intermediate sums can exceed the safe range of 32-bit signed arithmetic.

Two equivalent implementation patterns

The Java implementation follows the fixed-apex recurrence directly: choose an apex, keep a cumulative sum, append the next bottom segment, and test whether the minimum improved.

The C++ and Python implementations batch the same recurrence by top row. For a fixed top row, they maintain one running total for each possible apex column on that row. As the bottom row descends, every running total receives its new segment, so all sub-triangles with that top row grow in parallel. The mathematics is identical; only the loop structure differs.

Capturing the answer

After every extension step, the current sum is compared with the global minimum. Because every valid \((r,c,h)\) appears exactly once, the final recorded minimum is the required answer.

Complexity Analysis

Generating the triangle and building the row prefixes both take \(O(n^2)\) time and \(O(n^2)\) memory. The dominant phase is the enumeration of all sub-triangles, which costs

$O\!\left(\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)\right)=O(n^3).$

At \(n=1000\), that means exactly \(167{,}167{,}000\) candidates. The important point is that the constant factor stays small: each extension uses one prefix-sum subtraction, one addition, and one comparison. The batched top-row version needs only \(O(n)\) extra working memory on top of the stored triangle and prefix tables.

Footnotes and References

1. Problem page: Project Euler 150
2. Linear congruential generator: Wikipedia - Linear congruential generator
3. Prefix sum: Wikipedia - Prefix sum
4. Triangular number: Wikipedia - Triangular number