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.
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)\).
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.
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.
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.
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.
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.
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.
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.
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.
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.
Das Problem erzeugt ein nach unten gerichtetes Zahlendreieck mit \(n=1000\) Zeilen und damit insgesamt \(1+2+\cdots+1000=500{,}500\) Einträgen. Die Werte werden zeilenweise durch die lineare Kongruenzfolge \(t_0=0\), \(t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}\) und \(s_k=t_k-2^{19}\) erzeugt. Gesucht ist das Unterdreieck mit der kleinsten möglichen Summe.
Wenn man jede Kandidatensumme von Grund auf neu berechnen würde, wäre die Laufzeit viel zu groß. Der entscheidende Gedanke ist, dass ein Unterdreieck beim Vergrößern seiner Höhe genau ein zusammenhängendes Segment in der nächsten Zeile hinzubekommt. Mit Zeilenpräfixsummen wird jeder solche Schritt zu einem \(O(1)\)-Update.
Bezeichne den erzeugten Dreieckseintrag in Zeile \(r\) und Spalte \(c\) mit \(a_{r,c}\), wobei \(0\le c\le r<n\) gilt. Ein Unterdreieck wird durch seine Spitze \((r,c)\) und seine Höhe \(h\ge 1\) bestimmt. Seine Summe ist
$$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.$$
Zu minimieren ist also \(T(r,c,h)\) über alle zulässigen Tripel \((r,c,h)\).
Der Pseudozufallsgenerator gehört hier zur eigentlichen Problemstruktur, weil die Datenmenge allein durch diese Rekursion festgelegt wird. Nach der Erzeugung von \(s_1,s_2,\dots\) werden die Werte zeilenweise eingetragen: ein Wert in die erste Zeile, zwei in die zweite, drei in die dritte und so weiter bis zur tausendsten Zeile.
Wegen des Modulus \(2^{20}\) liegt jeder Rohwert \(t_k\) in \(\{0,1,\dots,2^{20}-1\}\). Durch die Verschiebung um \(2^{19}\) erhält man Werte im Bereich \([-2^{19},2^{19}-1]\). Da viele Einträge negativ sind, muss das Minimum nicht bei einem einzelnen Feld liegen; auch ein größeres Gebiet kann insgesamt stärker negativ werden.
Ein nach unten gerichtetes Unterdreieck ist kein Rechteck. In der Zeile \(r+i\) umfasst es genau den zusammenhängenden Block \(a_{r+i,c},a_{r+i,c+1},\dots,a_{r+i,c+i}\). Deshalb sind Präfixsummen pro Zeile das natürliche Werkzeug. Definiere
$$P_r(m)=\sum_{j=0}^{m-1} a_{r,j},\qquad P_r(0)=0.$$
Dann hat jedes zusammenhängende Segment in Zeile \(r\), das bei Spalte \(c\) beginnt und Länge \(\ell\) besitzt, die Summe
$$\sum_{j=0}^{\ell-1} a_{r,c+j}=P_r(c+\ell)-P_r(c).$$
Setzt man für die \(i\)-te Zeile des Unterdreiecks die korrekte Länge \(\ell=i+1\) ein, erhält man
$$T(r,c,h)=\sum_{i=0}^{h-1}\bigl(P_{r+i}(c+i+1)-P_{r+i}(c)\bigr).$$
Genau diese Formel macht das Problem beherrschbar: Jeder Zeilenbeitrag reduziert sich auf die Differenz zweier Präfixwerte.
Ist die Spitze \((r,c)\) fest, dann verändert der Übergang von Höhe \(h\) zu Höhe \(h+1\) die bereits gezählten Zeilen nicht. Hinzu kommt nur das neue untere Segment in Zeile \(r+h\). Daher gilt
$$T(r,c,h+1)=T(r,c,h)+P_{r+h}(c+h+1)-P_{r+h}(c).$$
Das ist die zentrale Rekurrenz aller drei Implementierungen. Sobald die erste Zeile bekannt ist, kostet jede weitere Höhenstufe konstante Zeit, weil der obere Teil des Dreiecks nie noch einmal summiert werden muss.
Das in den Implementierungen verwendete Kontrollbeispiel lautet
$$\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}$$
Das Minimum wird vom Unterdreieck mit Spitze in der zweiten Zeile an zweiter Stelle und Höhe \(4\) erreicht. Die vier Zeilenbeiträge sind
$$-7,\qquad (-13)+(-5)=-18,\qquad 8+23-26=5,\qquad -4-5-18+5=-22,$$
also insgesamt
$$-7-18+5-22=-42.$$
Die obige Rekurrenz bildet das exakt nach: Man startet mit dem Spitzenwert \(-7\) und addiert dann jeweils das nächste verbreiterte Zeilensegment.
Die Schleifen lassen sich auf zwei äquivalente Arten organisieren. Man kann eine feste Spitze \((r,c)\) wählen und die Höhe schrittweise vergrößern, oder man fixiert eine obere Zeile \(r\) und aktualisiert gleichzeitig die laufenden Summen aller Spitzen in dieser Zeile, während die untere Zeile nach unten wandert. Beide Sichtweisen beruhen auf derselben Größe:
$$A_{r,b}(c)=\sum_{i=r}^{b}\bigl(P_i(c+i-r+1)-P_i(c)\bigr),$$
also genau der Summe des Unterdreiecks mit Spitze \((r,c)\) und unterster Zeile \(b\). Erhöht sich \(b\) um \(1\), kommt genau ein neues Zeilensegment hinzu, sonst ändert sich nichts.
Die Anzahl aller Kandidaten beträgt
$$\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)=\frac{n(n+1)(n+2)}{6}.$$
Für \(n=1000\) sind das \(167{,}167{,}000\) Unterdreiecke. Das ist groß, aber praktikabel, weil jede neue Höhe nur per Konstantzeit-Update aus der vorherigen entsteht.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst das vollständige Pseudozufallsdreieck im Speicher. Danach oder zugleich wird für jede Zeile eine Präfixtabelle mit führender Null aufgebaut, sodass jedes Zeilensegment als Differenz zweier Präfixeinträge gelesen werden kann.
Die laufenden Summen und das globale Minimum werden in 64-Bit-Ganzzahltypen gehalten. Das ist wichtig, denn obwohl jedes einzelne Feld in 32 Bit passt, kann ein großes Unterdreieck Hunderttausende Summanden enthalten, und Zwischensummen können den sicheren 32-Bit-Bereich überschreiten.
Die Java-Implementierung folgt direkt der Rekurrenz mit fester Spitze: Spitze wählen, laufende Summe halten, nächstes unteres Segment hinzufügen und nach jeder Erweiterung das Minimum prüfen.
Die C++- und Python-Implementierungen bündeln dieselbe Rekurrenz zeilenweise. Für eine feste obere Zeile halten sie für jede mögliche Spitzenspalte eine laufende Summe. Wenn die untere Zeile nach unten rückt, bekommt jede dieser Summen ihr neues Segment, sodass alle Unterdreiecke mit derselben oberen Zeile parallel wachsen. Mathematisch ist das identisch; nur die Schleifenanordnung ist anders.
Nach jedem Erweiterungsschritt wird die aktuelle Summe mit dem globalen Minimum verglichen. Da jedes zulässige \((r,c,h)\) genau einmal besucht wird, ist das am Ende gespeicherte Minimum genau die gesuchte Antwort.
Das Erzeugen des Dreiecks und der Aufbau der Zeilenpräfixsummen benötigen jeweils \(O(n^2)\) Zeit und \(O(n^2)\) Speicher. Die dominante Phase ist die Aufzählung aller Unterdreiecke mit Aufwand
$$O\!\left(\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)\right)=O(n^3).$$
Für \(n=1000\) sind das exakt \(167{,}167{,}000\) Kandidaten. Entscheidend ist der kleine konstante Faktor: Jede Erweiterung braucht nur eine Präfixdifferenz, eine Addition und einen Vergleich. Die gebündelte Variante nach oberer Zeile benötigt zusätzlich lediglich \(O(n)\) Arbeitspeicher neben dem gespeicherten Dreieck und den Präfixtabellen.
Problem, \(n=1000\) satırlı aşağı bakan bir sayı üçgeni kurar; dolayısıyla toplam eleman sayısı \(1+2+\cdots+1000=500{,}500\) olur. Değerler satır satır şu lineer eşlenik üreteç ile oluşturulur: \(t_0=0\), \(t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}\), ardından \(s_k=t_k-2^{19}\). Amaç, toplamı en küçük olan aşağı yönlü alt üçgeni bulmaktır.
Her aday alt üçgenin toplamı baştan hesaplanırsa çözüm çok yavaş olur. Temel fikir şudur: bir alt üçgenin yüksekliğini bir artırmak, yalnızca alttaki bir sonraki satırdan tek bir bitişik parçayı ekler. Bu yüzden satır bazlı önek toplamları her büyütme adımını \(O(1)\) maliyete indirir.
Üretilen üçgendeki değeri \(a_{r,c}\) ile gösterelim; burada \(0\le c\le r<n\). Bir alt üçgen, tepe noktası \((r,c)\) ve yüksekliği \(h\ge 1\) ile belirlenir. Toplamı
$$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$$
şeklindedir. Dolayısıyla yapılması gereken şey, geçerli tüm \((r,c,h)\) üçlüleri üzerinde \(T(r,c,h)\) değerini minimize etmektir.
Sözde rastgele üreteç burada yalnızca veri hazırlama ayrıntısı değildir; problemdeki tüm üçgen bu yineleme ile tanımlanır. \(s_1,s_2,\dots\) değerleri elde edildikten sonra satır satır yerleştirilir: ilk satıra 1 sayı, ikinci satıra 2 sayı, üçüncü satıra 3 sayı ve bu böyle devam eder.
Modül \(2^{20}\) olduğu için her ham durum \(t_k\), \(\{0,1,\dots,2^{20}-1\}\) kümesindedir. \(2^{19}\) çıkarılınca değerler \([-2^{19},2^{19}-1]\) aralığına kayar. Bu yüzden çok sayıda negatif terim vardır ve minimum toplam mutlaka tek bir hücrede ortaya çıkmak zorunda değildir; daha büyük bir bölge daha da negatif olabilir.
Aşağı yönlü alt üçgen dikdörtgen değildir. \(r+i\) satırında tam olarak \(a_{r+i,c},a_{r+i,c+1},\dots,a_{r+i,c+i}\) blokunu kapsar. Bu geometri satır başına önek toplamlarla doğal biçimde eşleşir. Şöyle tanımlayalım:
$$P_r(m)=\sum_{j=0}^{m-1} a_{r,j},\qquad P_r(0)=0.$$
O halde \(r\) satırında \(c\) sütunundan başlayan ve uzunluğu \(\ell\) olan bitişik parçanın toplamı
$$\sum_{j=0}^{\ell-1} a_{r,c+j}=P_r(c+\ell)-P_r(c)$$
olur. Alt üçgenin \(i\). satırında uzunluk tam olarak \(i+1\) olduğundan
$$T(r,c,h)=\sum_{i=0}^{h-1}\bigl(P_{r+i}(c+i+1)-P_{r+i}(c)\bigr)$$
elde edilir. Problemi çözülebilir yapan kimlik tam olarak budur: her satır katkısı iki önek değerinin farkına indirgenir.
Tepe \((r,c)\) sabitlendikten sonra yüksekliği \(h\) değerinden \(h+1\) değerine çıkarmak, daha önce sayılmış satırları değiştirmez. Sadece \(r+h\) satırındaki yeni alt parça eklenir. Bu nedenle
$$T(r,c,h+1)=T(r,c,h)+P_{r+h}(c+h+1)-P_{r+h}(c)$$
bağıntısı geçerlidir. Üç çözümün de kullandığı temel değişmez budur. İlk satır bilindikten sonra her yeni yükseklik adımı sabit zamanda işlenir; üst kısmı tekrar toplamaya gerek kalmaz.
Uygulamaların doğrulama için kullandığı küçük üçgen şudur:
$$\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}$$
Minimum toplam, ikinci satırdaki ikinci elemandan başlayan ve yüksekliği \(4\) olan alt üçgende elde edilir. Satır katkıları
$$-7,\qquad (-13)+(-5)=-18,\qquad 8+23-26=5,\qquad -4-5-18+5=-22$$
olduğu için toplam
$$-7-18+5-22=-42$$
çıkar. Yukarıdaki bağıntı bunu adım adım yeniden üretir: önce \(-7\) ile başlanır, sonra her adımda bir alt satır parçası eklenir.
Döngüler iki eşdeğer şekilde kurulabilir. Bir yol, sabit bir tepe \((r,c)\) seçip yüksekliği birer birer büyütmektir. Diğer yol, üst satırı \(r\) olarak sabitleyip o satırdaki tüm olası tepelerin güncel toplamlarını alt satır aşağı inerken aynı anda güncellemektir. Her iki bakış açısı da şu niceliğe dayanır:
$$A_{r,b}(c)=\sum_{i=r}^{b}\bigl(P_i(c+i-r+1)-P_i(c)\bigr).$$
Bu ifade, tepesi \((r,c)\) ve alt satırı \(b\) olan alt üçgenin toplamıdır. \(b\) bir artırıldığında yalnızca tek bir yeni satır parçası eklenir; başka hiçbir şey değişmez.
Aday sayısı
$$\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)=\frac{n(n+1)(n+2)}{6}$$
olur. \(n=1000\) için bu tam olarak \(167{,}167{,}000\) alt üçgendir. Sayı büyük görünse de her biri bir önceki yükseklikten sabit zamanlı güncelleme ile elde edildiği için uygulanabilir kalır.
C++, Python ve Java uygulamaları önce tüm sözde rastgele üçgeni bellekte yeniden üretir. Ardından her satır için başında sıfır bulunan bir önek toplam tablosu oluşturulur; böylece herhangi bir satır parçası iki önek değerin farkı olarak okunabilir.
Çalışan toplamlar ve en iyi değer 64 bit tamsayı türlerinde tutulur. Bu önemlidir; çünkü tek tek hücreler 32 bite sığsa da büyük bir alt üçgen yüzbinlerce terim içerebilir ve ara toplamlar 32 bit işaretli aralığı aşabilir.
Java uygulaması sabit tepe bağıntısını doğrudan izler: bir tepe seçilir, kümülatif toplam tutulur, bir sonraki alt satır parçası eklenir ve her genişlemeden sonra minimum güncellenir.
C++ ve Python uygulamaları aynı hesabı üst satır bazında toplu yapar. Sabit bir üst satır için, o satırdaki her olası tepe sütunu adına bir çalışan toplam tutulur. Alt satır aşağı indikçe her toplama kendi yeni parçası eklenir; böylece aynı üst satıra sahip bütün alt üçgenler paralel biçimde büyür. Matematik aynıdır; değişen yalnızca döngülerin düzenidir.
Her büyütme adımından sonra güncel toplam küresel minimum ile karşılaştırılır. Geçerli her \((r,c,h)\) tam bir kez ziyaret edildiği için, en sonda tutulan minimum problemde istenen cevaptır.
Üçgeni üretmek ve satır önek toplamlarını kurmak \(O(n^2)\) zaman ve \(O(n^2)\) bellek ister. Baskın aşama, tüm alt üçgenleri saymaktır ve maliyeti
$$O\!\left(\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)\right)=O(n^3)$$
şeklindedir. \(n=1000\) olduğunda bu tam olarak \(167{,}167{,}000\) aday demektir. Kritik nokta sabit katsayının küçük kalmasıdır: her genişleme bir önek farkı, bir toplama işlemi ve bir karşılaştırmadan ibarettir. Üst satır bazında toplu sürüm, saklanan üçgen ve önek tablolarının üzerine yalnızca \(O(n)\) ek çalışma belleği kullanır.
El problema construye un arreglo triangular orientado hacia abajo con \(n=1000\) filas, de modo que el número total de entradas es \(1+2+\cdots+1000=500{,}500\). Los valores se generan fila por fila mediante la recurrencia congruencial lineal \(t_0=0\), \(t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}\), y \(s_k=t_k-2^{19}\). Hay que encontrar el subtriángulo descendente cuya suma total sea la menor posible.
Si se recalculara desde cero la suma de cada candidato, el tiempo sería excesivo. La observación matemática decisiva es que aumentar la altura de un subtriángulo solo añade un segmento contiguo en la fila siguiente, así que las sumas prefijas por fila convierten cada extensión en una actualización de costo \(O(1)\).
Denotemos por \(a_{r,c}\) la entrada situada en la fila \(r\) y la columna \(c\), con \(0\le c\le r<n\). Un subtriángulo queda determinado por su vértice superior \((r,c)\) y su altura \(h\ge 1\). Su suma es
$$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.$$
Por tanto, el objetivo es minimizar \(T(r,c,h)\) sobre todos los triples válidos \((r,c,h)\).
El generador pseudoaleatorio forma parte del contenido matemático del problema, porque el conjunto de datos está definido exclusivamente por esa recurrencia. Después de producir \(s_1,s_2,\dots\), los valores se colocan por filas: un valor en la primera fila, dos en la segunda, tres en la tercera y así sucesivamente hasta completar la fila 1000.
Como el módulo es \(2^{20}\), cada estado bruto \(t_k\) pertenece a \(\{0,1,\dots,2^{20}-1\}\). Restar \(2^{19}\) desplaza los valores al intervalo con signo \([-2^{19},2^{19}-1]\). Debido a que aparecen muchos términos negativos, la suma mínima no tiene por qué corresponder a una sola celda; un bloque triangular más grande puede resultar todavía más negativo.
Un subtriángulo descendente no es un rectángulo. En la fila \(r+i\) cubre exactamente el bloque contiguo \(a_{r+i,c},a_{r+i,c+1},\dots,a_{r+i,c+i}\). Por eso las sumas prefijas por fila son la herramienta natural. Definimos
$$P_r(m)=\sum_{j=0}^{m-1} a_{r,j},\qquad P_r(0)=0.$$
Entonces cualquier segmento contiguo de la fila \(r\), que empieza en la columna \(c\) y tiene longitud \(\ell\), satisface
$$\sum_{j=0}^{\ell-1} a_{r,c+j}=P_r(c+\ell)-P_r(c).$$
Al sustituir la longitud correcta \(\ell=i+1\) en cada fila del subtriángulo, obtenemos
$$T(r,c,h)=\sum_{i=0}^{h-1}\bigl(P_{r+i}(c+i+1)-P_{r+i}(c)\bigr).$$
Esa identidad es la razón por la que el problema se vuelve manejable: cada contribución de fila queda reducida a una diferencia de dos prefijos.
Una vez fijado el vértice \((r,c)\), pasar de altura \(h\) a altura \(h+1\) no altera las filas ya contadas. Solo se añade el nuevo segmento inferior de la fila \(r+h\). Por ello
$$T(r,c,h+1)=T(r,c,h)+P_{r+h}(c+h+1)-P_{r+h}(c).$$
Esta es la recurrencia central empleada por las tres implementaciones. Después de contar la primera fila, cada incremento adicional de altura cuesta tiempo constante, porque la parte superior del subtriángulo nunca se vuelve a sumar.
El triángulo de comprobación utilizado por las implementaciones es
$$\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}$$
El mínimo se alcanza en el subtriángulo cuyo vértice está en la segunda fila, segunda entrada, y cuya altura es \(4\). Las contribuciones de sus filas son
$$-7,\qquad (-13)+(-5)=-18,\qquad 8+23-26=5,\qquad -4-5-18+5=-22,$$
de modo que la suma total vale
$$-7-18+5-22=-42.$$
La recurrencia anterior reproduce exactamente este proceso: se empieza con el valor del vértice \(-7\) y en cada paso se añade un segmento inferior un poco más ancho.
Los bucles pueden organizarse de dos maneras equivalentes. Una posibilidad es fijar un vértice \((r,c)\) y aumentar la altura fila a fila. La otra es fijar una fila superior \(r\) y mantener simultáneamente las sumas actuales de todos los vértices de esa fila mientras la fila inferior desciende. Ambas visiones usan la misma cantidad:
$$A_{r,b}(c)=\sum_{i=r}^{b}\bigl(P_i(c+i-r+1)-P_i(c)\bigr),$$
que es precisamente la suma del subtriángulo con vértice \((r,c)\) y fila inferior \(b\). Cuando \(b\) aumenta en \(1\), solo se añade un nuevo segmento de fila y nada más cambia.
El número total de candidatos es
$$\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)=\frac{n(n+1)(n+2)}{6}.$$
Para \(n=1000\), esto da \(167{,}167{,}000\) subtriángulos. Es una cantidad grande, pero resulta viable porque cada uno se obtiene mediante una actualización constante a partir de la altura anterior.
Las implementaciones en C++, Python y Java reconstruyen primero el triángulo pseudoaleatorio completo en memoria. Además, preparan para cada fila una tabla de sumas prefijas con un cero inicial, de forma que cualquier segmento de fila se obtiene restando dos entradas de esa tabla.
Las sumas acumuladas y el mejor valor encontrado se guardan en enteros de 64 bits. Eso es importante porque, aunque cada celda individual cabe en 32 bits, un subtriángulo grande puede contener cientos de miles de términos y las sumas intermedias pueden superar el rango seguro de 32 bits con signo.
La implementación en Java sigue la recurrencia de vértice fijo de manera directa: elige un vértice, mantiene una suma acumulada, añade el siguiente segmento inferior y comprueba si el mínimo mejora.
Las implementaciones en C++ y Python agrupan el mismo cálculo por fila superior. Para una fila superior fija, mantienen una suma en curso para cada posible columna de vértice en esa fila. A medida que la fila inferior baja, cada suma recibe su nuevo segmento, así que todos los subtriángulos con esa misma fila superior crecen en paralelo. Las matemáticas son exactamente las mismas; solo cambia la organización de los bucles.
Tras cada paso de extensión, la suma actual se compara con el mínimo global. Como cada triple válido \((r,c,h)\) aparece exactamente una vez, el mínimo final almacenado es la respuesta pedida.
Generar el triángulo y construir las sumas prefijas por fila cuesta \(O(n^2)\) tiempo y \(O(n^2)\) memoria. La fase dominante es la enumeración de todos los subtriángulos, con coste
$$O\!\left(\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)\right)=O(n^3).$$
Para \(n=1000\), eso significa exactamente \(167{,}167{,}000\) candidatos. Lo esencial es que el factor constante se mantiene pequeño: cada extensión utiliza una resta de prefijos, una suma y una comparación. La versión agrupada por fila superior solo necesita \(O(n)\) memoria auxiliar adicional, aparte del triángulo almacenado y de sus tablas de prefijos.
本题构造一个向下展开的三角形数组，行数为 \(n=1000\)，因此元素总数是 \(1+2+\cdots+1000=500{,}500\)。这些数不是输入给出的，而是按行依次由线性同余递推生成：\(t_0=0\)，\(t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}\)，再令 \(s_k=t_k-2^{19}\)。要求在所有向下的子三角形中，找出元素和最小的那个。
如果对每个候选子三角形都从头累加，它的代价会高得不可接受。真正的数学关键是：把一个子三角形的高度增加 1 时，只会在下一行新增一个连续区间，因此按行做前缀和以后，每次扩展都可以在 \(O(1)\) 时间内完成。
记生成出的三角形元素为 \(a_{r,c}\)，其中 \(0\le c\le r<n\)。一个子三角形由顶点 \((r,c)\) 和高度 \(h\ge 1\) 唯一确定，它的和为
$$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.$$
因此，问题就是在所有合法的 \((r,c,h)\) 三元组上最小化 \(T(r,c,h)\)。
这里的伪随机生成器本身就是题目定义的一部分，因为整个数据集完全由这条递推式决定。得到 \(s_1,s_2,\dots\) 之后，数值按行填入三角形：第一行放 1 个，第二行放 2 个，第三行放 3 个，依此类推，直到第 1000 行结束。
由于模数是 \(2^{20}\)，每个原始状态 \(t_k\) 都落在 \(\{0,1,\dots,2^{20}-1\}\) 中。减去 \(2^{19}\) 之后，数值区间平移为 \([-2^{19},2^{19}-1]\)。这意味着数组中会出现大量负数，所以最小值未必来自某个单独元素；当若干行的负贡献叠加时，较大的子三角形反而可能更小。
向下子三角形不是矩形。在第 \(r+i\) 行中，它恰好覆盖连续的一段：\(a_{r+i,c},a_{r+i,c+1},\dots,a_{r+i,c+i}\)。这种“每向下一行就向右多伸出一个元素”的几何结构，与逐行前缀和完全吻合。定义
$$P_r(m)=\sum_{j=0}^{m-1} a_{r,j},\qquad P_r(0)=0.$$
那么，第 \(r\) 行从第 \(c\) 列开始、长度为 \(\ell\) 的任意连续区间，其和都可以写成
$$\sum_{j=0}^{\ell-1} a_{r,c+j}=P_r(c+\ell)-P_r(c).$$
对子三角形来说，第 \(i\) 个向下层级对应的区间长度正好是 \(\ell=i+1\)，于是有
$$T(r,c,h)=\sum_{i=0}^{h-1}\bigl(P_{r+i}(c+i+1)-P_{r+i}(c)\bigr).$$
这就是整个算法的核心转换：每一层的贡献都变成了两个前缀值的差。
一旦顶点 \((r,c)\) 固定，把高度从 \(h\) 扩展到 \(h+1\) 时，之前已经计算过的那些行完全不需要改动。新增的只有底部那一层，也就是第 \(r+h\) 行上的一个连续区间。因此
$$T(r,c,h+1)=T(r,c,h)+P_{r+h}(c+h+1)-P_{r+h}(c).$$
这正是三个实现共同依赖的关键不变量。已知第一个高度之后，每再增加一层都只需要常数时间，因为上面的部分永远不会被重复求和。
实现中用于校验的六行样例如下：
$$\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}$$
最小和来自这样一个子三角形：顶点在第二行第二个元素，高度为 \(4\)。它四层的行贡献分别是
$$-7,\qquad (-13)+(-5)=-18,\qquad 8+23-26=5,\qquad -4-5-18+5=-22,$$
于是总和为
$$-7-18+5-22=-42.$$
上面的递推式会精确地重现这个过程：先从顶点值 \(-7\) 开始，然后每一步把下一行更宽的那段区间加进去。
代码中的循环可以有两种等价组织方式。第一种是固定一个顶点 \((r,c)\)，再把高度一层一层向下扩展。第二种是固定顶行 \(r\)，同时维护这一顶行上所有可能顶点的当前子三角形和，并让底行逐步下移。无论哪种写法，本质上都在维护同一个量：
$$A_{r,b}(c)=\sum_{i=r}^{b}\bigl(P_i(c+i-r+1)-P_i(c)\bigr).$$
这里 \(A_{r,b}(c)\) 恰好就是“顶点为 \((r,c)\)、底行是 \(b\)”的子三角形总和。当 \(b\) 增加 1 时，只会多出一个新的行区间，其余部分完全不变。
候选子三角形的总数为
$$\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)=\frac{n(n+1)(n+2)}{6}.$$
当 \(n=1000\) 时，这个数字是 \(167{,}167{,}000\)。看起来很多，但因为每个候选都是从上一个高度做常数时间更新得到的，所以整体仍然可行。
C++、Python 和 Java 实现都会先在内存中重建完整的伪随机三角形。随后为每一行建立一张前缀和表，并在最前面放一个 0，这样任意连续区间都可以通过两个前缀值相减得到。
运行中的累计和以及全局最优值都使用 64 位整数保存。这一点很重要：虽然单个单元格远小于 32 位整数上限，但大子三角形可能含有数十万项，中间总和可能超出 32 位有符号整数的安全范围。
Java 实现直接按照“固定顶点”的递推来做：选定一个顶点，维护当前和，不断追加新的底层区间，并在每次扩展后更新答案。
C++ 和 Python 实现则按“固定顶行”批量处理。对于同一顶行上的每个可能顶点列，都维护一个当前和；随着底行下移，这些当前和同时接收各自的新行区间，于是同一顶行的所有子三角形一起向下增长。数学内容完全一样，只是循环结构不同。
每次扩展之后，当前子三角形和都会与全局最小值比较一次。因为每个合法的 \((r,c,h)\) 恰好出现一次，所以最终保留下来的最小值就是题目要求的答案。
生成三角形以及建立所有行前缀和都需要 \(O(n^2)\) 时间和 \(O(n^2)\) 空间。主导成本来自枚举全部子三角形，其复杂度为
$$O\!\left(\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)\right)=O(n^3).$$
当 \(n=1000\) 时，候选数恰好是 \(167{,}167{,}000\)。真正让它可行的原因在于常数因子很小：每次扩展只涉及一次前缀差、一次加法和一次比较。按顶行批量更新的写法，在保存三角形和前缀表之外只需要 \(O(n)\) 的额外工作空间。
В задаче строится направленный вниз числовой треугольник из \(n=1000\) строк, поэтому общее число элементов равно \(1+2+\cdots+1000=500{,}500\). Значения не подаются на вход, а порождаются построчно линейным конгруэнтным соотношением \(t_0=0\), \(t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}\), после чего берётся \(s_k=t_k-2^{19}\). Нужно найти такой подтреугольник, ориентированный вниз, у которого сумма элементов минимальна.
Если для каждого кандидата пересчитывать сумму с нуля, решение будет слишком медленным. Ключевое наблюдение состоит в том, что при увеличении высоты подтреугольника добавляется ровно один непрерывный отрезок на следующей строке. Поэтому префиксные суммы по строкам позволяют выполнять каждый шаг расширения за \(O(1)\).
Обозначим элемент в строке \(r\) и столбце \(c\) через \(a_{r,c}\), где \(0\le c\le r<n\). Подтреугольник задаётся вершиной \((r,c)\) и высотой \(h\ge 1\). Его сумма равна
$$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.$$
Следовательно, требуется минимизировать \(T(r,c,h)\) по всем допустимым тройкам \((r,c,h)\).
Псевдослучайный генератор здесь является частью самой математической постановки, потому что весь набор данных определяется именно этой рекурсией. После получения значений \(s_1,s_2,\dots\) они раскладываются по строкам: одно число в первую строку, два во вторую, три в третью и так далее, пока не будет заполнена тысячная строка.
Поскольку модуль равен \(2^{20}\), каждое промежуточное состояние \(t_k\) лежит в множестве \(\{0,1,\dots,2^{20}-1\}\). Вычитание \(2^{19}\) сдвигает значения в знаковый диапазон \([-2^{19},2^{19}-1]\). Из-за большого количества отрицательных элементов минимум может достигаться не в одной клетке, а на более крупной треугольной области.
Подтреугольник, направленный вниз, не является прямоугольником. На строке \(r+i\) он покрывает ровно непрерывный блок \(a_{r+i,c},a_{r+i,c+1},\dots,a_{r+i,c+i}\). Поэтому естественный инструмент здесь - префиксные суммы отдельно для каждой строки. Определим
$$P_r(m)=\sum_{j=0}^{m-1} a_{r,j},\qquad P_r(0)=0.$$
Тогда сумма любого непрерывного отрезка строки \(r\), начинающегося в столбце \(c\) и имеющего длину \(\ell\), равна
$$\sum_{j=0}^{\ell-1} a_{r,c+j}=P_r(c+\ell)-P_r(c).$$
Для \(i\)-й строки подтреугольника длина такого отрезка равна \(\ell=i+1\), поэтому
$$T(r,c,h)=\sum_{i=0}^{h-1}\bigl(P_{r+i}(c+i+1)-P_{r+i}(c)\bigr).$$
Именно эта формула делает задачу вычислимо удобной: вклад каждой строки выражается разностью двух значений префиксной суммы.
Если вершина \((r,c)\) фиксирована, то переход от высоты \(h\) к высоте \(h+1\) не меняет уже учтённые строки. Добавляется только новый нижний отрезок на строке \(r+h\). Поэтому
$$T(r,c,h+1)=T(r,c,h)+P_{r+h}(c+h+1)-P_{r+h}(c).$$
Это и есть главный инвариант, на котором основаны все три реализации. После того как первый уровень уже учтён, каждое дальнейшее расширение требует постоянного времени и не пересчитывает верхнюю часть подтреугольника.
Контрольный треугольник, используемый реализациями, выглядит так:
$$\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}$$
Минимум достигается у подтреугольника с вершиной во второй строке, во втором элементе, и высотой \(4\). Его построчные вклады равны
$$-7,\qquad (-13)+(-5)=-18,\qquad 8+23-26=5,\qquad -4-5-18+5=-22,$$
поэтому общая сумма равна
$$-7-18+5-22=-42.$$
Рекуррентная формула выше воспроизводит это буквально: стартуем с вершины \(-7\), затем на каждом шаге прибавляем очередной расширенный нижний сегмент.
Циклы можно организовать двумя эквивалентными способами. Можно фиксировать вершину \((r,c)\) и увеличивать высоту на одну строку за шаг. А можно фиксировать верхнюю строку \(r\) и одновременно поддерживать текущие суммы для всех вершин этой строки, пока нижняя граница опускается вниз. Обе организации основаны на одной и той же величине:
$$A_{r,b}(c)=\sum_{i=r}^{b}\bigl(P_i(c+i-r+1)-P_i(c)\bigr).$$
Это в точности сумма подтреугольника с вершиной \((r,c)\) и нижней строкой \(b\). При увеличении \(b\) на \(1\) добавляется лишь один новый строковый сегмент, а всё остальное остаётся без изменений.
Число всех кандидатов равно
$$\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)=\frac{n(n+1)(n+2)}{6}.$$
При \(n=1000\) это \(167{,}167{,}000\) подтреугольников. Число большое, но вычислимо приемлемое, потому что каждый новый кандидат получается из предыдущего по высоте за постоянное время.
Реализации на C++, Python и Java сначала полностью восстанавливают псевдослучайный треугольник в памяти. Затем для каждой строки строится таблица префиксных сумм с начальным нулём, чтобы любой непрерывный отрезок строки можно было получить вычитанием двух значений.
Промежуточные суммы и глобальный минимум хранятся в 64-битных целых типах. Это необходимо, потому что хотя отдельная клетка легко помещается в 32 бита, крупный подтреугольник может содержать сотни тысяч элементов, и промежуточные суммы выходят за безопасный диапазон 32-битного знакового типа.
Java-реализация напрямую следует рекуррентному правилу для фиксированной вершины: выбирается вершина, поддерживается накопленная сумма, добавляется следующий нижний сегмент, после чего обновляется лучший ответ.
Реализации на C++ и Python группируют тот же процесс по верхней строке. Для фиксированной верхней строки они держат по одной текущей сумме для каждой возможной вершины в этой строке. Когда нижняя строка опускается, каждая текущая сумма получает свой новый сегмент, и все подтреугольники с этой верхней строкой растут одновременно. Математика та же самая; отличается только структура циклов.
После каждого шага расширения текущая сумма сравнивается с глобальным минимумом. Так как каждый допустимый набор \((r,c,h)\) рассматривается ровно один раз, итоговый сохранённый минимум и есть искомый ответ.
Порождение треугольника и построение префиксов по строкам требуют \(O(n^2)\) времени и \(O(n^2)\) памяти. Доминирующая часть - перебор всех подтреугольников, который стоит
$$O\!\left(\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)\right)=O(n^3).$$
Для \(n=1000\) это ровно \(167{,}167{,}000\) кандидатов. Важнейшее обстоятельство состоит в малом постоянном множителе: каждое расширение использует одну разность префиксов, одно сложение и одно сравнение. Пакетная версия по верхней строке требует всего \(O(n)\) дополнительной рабочей памяти сверх сохранённого треугольника и его таблиц префиксов.
تُنشئ المسألة مصفوفة مثلثة متجهة إلى الأسفل بعدد صفوف \(n=1000\)، ولذلك فإن عدد العناصر الكلي هو \(1+2+\cdots+1000=500{,}500\). القيم لا تُعطى مباشرة، بل تُولَّد صفًا بعد صف بواسطة العلاقة التوافقية الخطية \(t_0=0\)، و\(t_k=(615949\,t_{k-1}+797807)\bmod 2^{20}\)، ثم \(s_k=t_k-2^{19}\). المطلوب هو إيجاد المثلث الفرعي الهابط الذي يملك أصغر مجموع ممكن.
لو أُعيد حساب مجموع كل مثلث فرعي من البداية، فسيصبح الحل بطيئًا جدًا. الفكرة الرياضية الحاسمة هي أن زيادة ارتفاع مثلث فرعي بمقدار واحد تضيف فقط قطعة متصلة واحدة من الصف التالي، ولذلك فإن مجاميع البادئة لكل صف تجعل كل عملية تمديد تتم في زمن \(O(1)\).
لنرمز إلى العنصر الموجود في الصف \(r\) والعمود \(c\) بـ \(a_{r,c}\)، حيث \(0\le c\le r<n\). يتحدد كل مثلث فرعي برأسه \((r,c)\) وارتفاعه \(h\ge 1\)، ويكون مجموعه
$$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.$$
إذن الهدف هو تصغير \(T(r,c,h)\) على جميع الثلاثيات المسموح بها \((r,c,h)\).
مولد الأعداد شبه العشوائية ليس مجرد تفصيل برمجي هنا، بل هو جزء من البنية الرياضية نفسها، لأن البيانات كلها تُعرَّف بالكامل بهذه العلاقة. بعد توليد \(s_1,s_2,\dots\)، توضع القيم سطرًا بعد سطر: قيمة واحدة في الصف الأول، قيمتان في الصف الثاني، ثلاث قيم في الصف الثالث، وهكذا حتى يكتمل الصف الألف.
بما أن المودولو هو \(2^{20}\)، فإن كل حالة خام \(t_k\) تقع في المجموعة \(\{0,1,\dots,2^{20}-1\}\). وعند طرح \(2^{19}\) تنتقل القيم إلى المجال الموقع \([-2^{19},2^{19}-1]\). ولأن هناك الكثير من القيم السالبة، فليس من الضروري أن يتحقق الحد الأدنى في خلية واحدة فقط؛ فقد يصبح مثلث فرعي أكبر أكثر سلبية عندما تتراكم عدة صفوف غير مواتية.
المثلث الفرعي الهابط ليس مستطيلًا. ففي الصف \(r+i\) يغطي بالضبط الكتلة المتصلة \(a_{r+i,c},a_{r+i,c+1},\dots,a_{r+i,c+i}\). ولهذا تكون مجاميع البادئة على مستوى الصفوف هي الأداة الطبيعية. نعرّف
$$P_r(m)=\sum_{j=0}^{m-1} a_{r,j},\qquad P_r(0)=0.$$
وعندئذ يكون مجموع أي قطعة متصلة في الصف \(r\)، تبدأ عند العمود \(c\) وطولها \(\ell\)، مساويًا لـ
$$\sum_{j=0}^{\ell-1} a_{r,c+j}=P_r(c+\ell)-P_r(c).$$
وبما أن طول القطعة في المستوى \(i\) من المثلث الفرعي يساوي تمامًا \(\ell=i+1\)، نحصل على
$$T(r,c,h)=\sum_{i=0}^{h-1}\bigl(P_{r+i}(c+i+1)-P_{r+i}(c)\bigr).$$
هذه الصيغة هي التي تجعل المسألة عملية حسابيًا، لأن مساهمة كل صف تختزل إلى فرق بين قيمتين من جدول البادئة.
بعد تثبيت الرأس \((r,c)\)، فإن الانتقال من ارتفاع \(h\) إلى ارتفاع \(h+1\) لا يغيّر الصفوف التي حُسبت من قبل. الشيء الجديد الوحيد هو القطعة السفلية في الصف \(r+h\). ولذلك
$$T(r,c,h+1)=T(r,c,h)+P_{r+h}(c+h+1)-P_{r+h}(c).$$
هذه هي العلاقة الأساسية التي تعتمد عليها التطبيقات الثلاثة. فبعد حساب الصف الأول، تصبح كل زيادة إضافية في الارتفاع عملية ذات كلفة ثابتة، لأن الجزء العلوي من المثلث لا يُجمع مرة أخرى.
المثلث الصغير المستخدم للتحقق في التطبيقات هو
$$\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}$$
أصغر مجموع يتحقق في مثلث فرعي رأسه في الصف الثاني والعنصر الثاني، وارتفاعه \(4\). مساهمات صفوفه الأربع هي
$$-7,\qquad (-13)+(-5)=-18,\qquad 8+23-26=5,\qquad -4-5-18+5=-22,$$
ومن ثم يكون المجموع الكلي
$$-7-18+5-22=-42.$$
العلاقة السابقة تعيد إنتاج هذا المثال حرفيًا: نبدأ من قيمة الرأس \(-7\)، ثم نضيف في كل خطوة قطعة أوسع من الصف التالي.
يمكن تنظيم الحلقات بطريقتين متكافئتين. الطريقة الأولى هي تثبيت رأس واحد \((r,c)\) ثم زيادة الارتفاع صفًا بعد صف. والطريقة الثانية هي تثبيت الصف العلوي \(r\) ثم الاحتفاظ في الوقت نفسه بالمجاميع الحالية لجميع الرؤوس الممكنة في ذلك الصف بينما يتحرك الصف السفلي إلى الأسفل. كلتا الطريقتين تعتمدان على الكمية نفسها:
$$A_{r,b}(c)=\sum_{i=r}^{b}\bigl(P_i(c+i-r+1)-P_i(c)\bigr).$$
وهذه الكمية هي بالضبط مجموع المثلث الفرعي الذي رأسه \((r,c)\) وآخر صف فيه هو \(b\). وعندما يزداد \(b\) بمقدار \(1\)، تُضاف قطعة صف جديدة واحدة فقط ولا يتغير أي شيء آخر.
عدد جميع المرشحين يساوي
$$\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)=\frac{n(n+1)(n+2)}{6}.$$
وعند \(n=1000\) نحصل على \(167{,}167{,}000\) مثلث فرعي. هذا عدد كبير، لكنه يظل ممكنًا لأن كل مرشح جديد ينتج من تحديث ثابت الزمن انطلاقًا من الارتفاع السابق.
تعيد تطبيقات C++ وPython وJava بناء المثلث شبه العشوائي كاملًا في الذاكرة أولًا. ثم تنشئ لكل صف جدول مجاميع بادئة يبدأ بصفر أولي، بحيث يمكن الحصول على أي قطعة متصلة من الصف بطرح قيمتين من هذا الجدول.
تُخزَّن المجاميع الجارية وأفضل قيمة معروفة في أنواع أعداد صحيحة ذات 64 بت. وهذا ضروري، لأن الخلية الواحدة وإن كانت صغيرة نسبيًا، فإن مثلثًا فرعيًا كبيرًا قد يحتوي على مئات الآلاف من الحدود، وقد تتجاوز المجاميع الوسيطة المجال الآمن لـ 32 بت.
تسير نسخة Java مباشرة وفق علاقة الرأس الثابت: تختار رأسًا، وتحافظ على مجموع تراكمي، ثم تضيف القطعة السفلية التالية، وبعد كل تمديد تختبر إن كان الحد الأدنى قد تحسن.
أما نسختا C++ وPython فتنجزان الحساب نفسه على مستوى الصف العلوي دفعة واحدة. فلكل صف علوي ثابت تحتفظان بمجموع جارٍ لكل عمود يمكن أن يكون رأسًا في ذلك الصف. وعندما يهبط الصف السفلي، تتلقى كل قيمة جارية قطعتها الجديدة، وبذلك تنمو جميع المثلثات الفرعية ذات الصف العلوي نفسه بالتوازي. الرياضيات واحدة تمامًا؛ والاختلاف فقط في ترتيب الحلقات.
بعد كل خطوة تمديد، يُقارن المجموع الحالي بالحد الأدنى العالمي. وبما أن كل ثلاثية صحيحة \((r,c,h)\) تُزار مرة واحدة بالضبط، فإن أصغر قيمة محفوظة في النهاية هي الجواب المطلوب.
إن توليد المثلث وبناء مجاميع البادئة لكل الصفوف يكلفان \(O(n^2)\) زمنًا و\(O(n^2)\) ذاكرة. أما المرحلة المهيمنة فهي تعداد جميع المثلثات الفرعية، وكلفتها
$$O\!\left(\sum_{r=0}^{n-1}\sum_{c=0}^{r}(n-r)\right)=O(n^3).$$
وعندما يكون \(n=1000\)، فهذا يعني بالضبط \(167{,}167{,}000\) مرشحًا. والنقطة المهمة أن العامل الثابت صغير: كل تمديد يحتاج إلى فرق بادئة واحد، وعملية جمع واحدة، ومقارنة واحدة. كما أن النسخة التي تجمع العمل حسب الصف العلوي تحتاج فقط إلى \(O(n)\) من الذاكرة العاملة الإضافية فوق تخزين المثلث نفسه وجداول البادئة الخاصة به.