The sequence is defined by
$$s_1=102022661,\qquad s_{k+1}\equiv s_k^2 \pmod{998388889}.$$
From it we take
$$a_i=s_{2i-1},\qquad b_i=s_{2i},$$
so the cost of cell \((i,j)\) is
$$c_{i,j}=a_i+b_j.$$
The goal is to minimize the sum of the visited cell values along a path from \((1,1)\) to \((n,n)\) using only right and down moves. A direct grid dynamic program would use \(n^2\) states, which is hopeless for the actual value \(n=10^7\). The implementations therefore exploit the additive form \(a_i+b_j\), rewrite the path by the columns where the downward moves occur, and then compress the remaining one-dimensional states with a geometric lower-hull argument.
The solution has three layers. First, separate the part of the cost that every monotone path must pay. Second, encode a path by a nondecreasing sequence of column choices. Third, observe that the resulting dynamic program only needs the columns lying on the lower hull of the sampled graph \(t \mapsto b_{t+1}\).
Let \(P(i,j)\) denote the minimum total cost of a path ending at \((i,j)\), including the value of that cell itself. The usual recurrence is
$$P(1,1)=a_1+b_1,$$
$$P(i,j)=a_i+b_j+\min\bigl(P(i,j-1),P(i-1,j)\bigr).$$
Every monotone path from the top-left corner to the bottom-right corner visits each row at least once and each column at least once. That means the sum
$$A_i=\sum_{r=1}^{i} a_r,\qquad B_j=\sum_{c=1}^{j} b_c$$
contains an unavoidable one-time contribution from every visited row and column. Subtract it by defining
$$D(i,j)=P(i,j)-A_i-B_j.$$
Then \(D(1,1)=0\), and the recurrence becomes
$$D(i,j)=\min\bigl(D(i,j-1)+a_i,\ D(i-1,j)+b_j\bigr).$$
This form is important because it shows what is really being optimized. Moving right in row \(i\) repeats the row cost \(a_i\). Moving down in column \(j\) repeats the column cost \(b_j\). The final answer is therefore
$$P(n,n)=A_n+B_n+D(n,n).$$
A path from \((1,1)\) to \((n,n)\) uses exactly \(n-1\) downward moves. Let \(t_i\) be the number of right moves already performed before the \(i\)-th downward move. Then
$$0\le t_1\le t_2\le \cdots \le t_{n-1}\le n-1.$$
This nondecreasing sequence determines the whole path. The \(i\)-th downward move occurs in column \(t_i+1\), so it contributes \(b_{t_i+1}\). If \(r_i\) is the number of right moves made in row \(i\), then
$$r_1=t_1,\qquad r_i=t_i-t_{i-1}\quad(2\le i\le n-1),\qquad r_n=(n-1)-t_{n-1}.$$
The extra cost beyond the base term is therefore
$$D(n,n)=\sum_{i=1}^{n} r_i a_i+\sum_{i=1}^{n-1} b_{t_i+1}.$$
Now telescope the row part:
$$\sum_{i=1}^{n} r_i a_i=t_1a_1+\sum_{i=2}^{n-1}(t_i-t_{i-1})a_i+\bigl((n-1)-t_{n-1}\bigr)a_n,$$
so
$$\sum_{i=1}^{n} r_i a_i=(n-1)a_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})t_i.$$
Hence the optimization problem is exactly
$$D(n,n)=(n-1)a_n+\sum_{i=1}^{n-1}\Bigl((a_i-a_{i+1})t_i+b_{t_i+1}\Bigr).$$
The original grid problem has now been converted into a one-dimensional optimization over nondecreasing integer sequences.
Introduce
$$u_i=a_i-a_{i+1},\qquad g(t)=b_{t+1}.$$
Let \(F_i(t)\) be the minimum contribution of the first \(i\) downward moves under the condition that \(t_i=t\). Then
$$F_i(t)=u_i t+g(t)+\min_{0\le s\le t}F_{i-1}(s),$$
with the initial condition \(F_0(0)=0\) and \(F_0(t)=+\infty\) for \(t>0\). Once all \(n-1\) downward moves have been processed,
$$D(n,n)=(n-1)a_n+\min_{0\le t\le n-1}F_{n-1}(t).$$
The recurrence shows that the previous layer is needed only through the prefix-minimum function
$$M_{i-1}(t)=\min_{0\le s\le t}F_{i-1}(s).$$
If we evaluated this for every \(t\), we would still spend \(O(n^2)\) time. The crucial remaining question is why the implementations can keep only a much smaller subset of columns.
Consider the sampled points
$$\bigl(t,g(t)\bigr)=\bigl(t,b_{t+1}\bigr),\qquad 0\le t\le n-1.$$
Let the vertices of their lower hull be
$$0=h_0\lt h_1\lt \cdots \lt h_{m-1}\le n-1.$$
They are built by a monotone scan. If three consecutive candidates \(t_1\lt t_2\lt t_3\) satisfy
$$\bigl(t_2-t_1\bigr)\bigl(g(t_3)-g(t_1)\bigr)-\bigl(g(t_2)-g(t_1)\bigr)\bigl(t_3-t_1\bigr)\le 0,$$
then \(t_2\) is removed, because its point lies on or above the segment joining the other two.
This hull is exactly what the fast solver needs. If a column \(t\) is not on the lower hull, then there exist hull vertices \(p\lt t\lt q\) and a number \(\lambda\in(0,1)\) with \(t=\lambda p+(1-\lambda)q\) such that
$$g(t)\ge \lambda g(p)+(1-\lambda)g(q).$$
Therefore, for every slope \(u\),
$$u t+g(t)\ge \lambda\bigl(up+g(p)\bigr)+(1-\lambda)\bigl(uq+g(q)\bigr).$$
So a non-hull column can never beat both neighboring hull columns for the tilted cost \(u t+g(t)\). Adding the linear term \(u t\) is an affine shear of the point set, and affine shears preserve which sampled columns lie on the lower hull.
Now apply this to the dynamic program. The prefix-minimum function \(M_{i-1}(t)\) is piecewise constant: it only changes when a new record low appears. If those record lows occur at hull columns, then on each interval where \(M_{i-1}\) is constant, minimizing
$$F_i(t)=M_{i-1}(t)+u_i t+g(t)$$
is the same as minimizing a constant plus a tilted copy of \(g\), so the minimum on that interval is again attained at a hull column. This gives an induction: every prefix minimum, every layer minimum, and in particular the final optimum can be read from hull columns alone.
For \(n=2\), the generated values are
$$a_1=102022661,\quad b_1=864751430,\quad a_2=661600260,\quad b_2=328965239.$$
So the grid is
$$\begin{pmatrix} a_1+b_1 & a_1+b_2\\ a_2+b_1 & a_2+b_2 \end{pmatrix} = \begin{pmatrix} 966774091 & 430987900\\ 1526351690 & 990565499 \end{pmatrix}.$$
There is only one down-step parameter, \(t_1\). If \(t_1=0\), the path goes down first; if \(t_1=1\), it goes right first. The unavoidable base part is
$$a_1+a_2+b_1+b_2=1957339590.$$
The extra part is
$$D(2,2)=a_2+\min\bigl(b_1,\ a_1-a_2+b_2\bigr),$$
hence
$$D(2,2)=661600260+\min(864751430,-230612360)=430987900.$$
Therefore
$$P(2,2)=1957339590+430987900=2388327490.$$
This is the same checkpoint used by the implementations and it illustrates the full decomposition into base cost plus optimized extra cost.
The C++, Python, and Java implementations first generate the deterministic sequence by repeated modular squaring. From that stream they extract all \(a_i\) and \(b_i\), while simultaneously accumulating \(\sum a_i\) and \(\sum b_i\). If \(n=1\), the answer is just \(a_1+b_1\), so no hull or dynamic program is needed.
For \(n\ge 2\), the implementation scans the sampled points \((t,b_{t+1})\) for \(0\le t\le n-1\) and keeps only the lower-hull columns. The geometric test is the cross-product inequality written above. This preprocessing is independent of the dynamic-programming layer, because each layer differs only by adding a linear term \(u_i t\), and that does not change which sampled columns are hull vertices.
After the hull is known, the implementation stores the surviving column indices and their \(b\)-values, then runs the recurrence only on that compressed list. Each layer is processed from left to right while maintaining the running prefix minimum from the previous layer, so only two rolling arrays are needed. At the end, the best compressed state is combined with \((n-1)a_n\) and the base sum \(\sum a_i+\sum b_i\).
The C++ implementation also keeps the original quadratic grid DP for small-size validation. It checks explicit values for \(n=1\), \(n=2\), and \(n=10\), and it compares the fast and quadratic methods for all \(1\le n\le 120\). The Python and Java implementations keep only the fast solver, but they follow the same mathematics.
Generating the sequence and the base sums costs \(O(n)\) time. Building the lower hull is another \(O(n)\) pass. If the hull contains \(m\) surviving columns, the compressed dynamic program takes \(O(nm)\) time, because there are \(n-1\) layers and each layer scans those \(m\) states once.
The implementations store the full arrays of \(a_i\) and \(b_i\) together with two rolling DP rows, so the memory usage is \(O(n+m)\). For comparison, the validation DP on the full grid needs \(O(n^2)\) time and \(O(n)\) memory with rolling rows. The entire point of the final method is to replace an impossible \(n^2\) grid computation at \(n=10^7\) by an \(O(n)\) preprocessing phase followed by a compressed one-dimensional DP.
Die Folge wird definiert durch
$$s_1=102022661,\qquad s_{k+1}\equiv s_k^2 \pmod{998388889}.$$
Daraus werden
$$a_i=s_{2i-1},\qquad b_i=s_{2i}$$
entnommen, sodass die Kosten der Zelle \((i,j)\) gleich
$$c_{i,j}=a_i+b_j$$
sind. Gesucht ist die minimale Summe der besuchten Zellwerte auf einem Weg von \((1,1)\) nach \((n,n)\), wenn nur Schritte nach rechts und nach unten erlaubt sind. Ein gewöhnliches Gitter-DP hätte \(n^2\) Zustände und ist für die eigentliche Größe \(n=10^7\) ausgeschlossen. Deshalb nutzen die Implementierungen die additive Struktur \(a_i+b_j\), kodieren den Weg über die Spalten der Abwärtsschritte und komprimieren danach den eindimensionalen Zustandsraum mit einem geometrischen Argument über die untere Hülle.
Die Herleitung besteht aus drei Teilen. Zuerst wird der Kostenanteil isoliert, den jeder monotone Weg zwangsläufig bezahlen muss. Danach wird der Weg als nicht fallende Folge von Spaltenentscheidungen beschrieben. Zum Schluss zeigt man, dass für das resultierende DP nur die Spalten auf der unteren Hülle des Graphen \(t\mapsto b_{t+1}\) benötigt werden.
Sei \(P(i,j)\) die minimale Pfadsumme bis zur Zelle \((i,j)\), einschließlich des Werts dieser Zelle. Dann gilt
$$P(1,1)=a_1+b_1,$$
$$P(i,j)=a_i+b_j+\min\bigl(P(i,j-1),P(i-1,j)\bigr).$$
Jeder monotone Weg von links oben nach rechts unten besucht jede Zeile mindestens einmal und jede Spalte mindestens einmal. Daher enthält
$$A_i=\sum_{r=1}^{i} a_r,\qquad B_j=\sum_{c=1}^{j} b_c$$
genau den unvermeidlichen Einmalbeitrag aller besuchten Zeilen und Spalten. Wir definieren
$$D(i,j)=P(i,j)-A_i-B_j.$$
Damit ist \(D(1,1)=0\), und die Rekursion vereinfacht sich zu
$$D(i,j)=\min\bigl(D(i,j-1)+a_i,\ D(i-1,j)+b_j\bigr).$$
Diese Form zeigt den eigentlichen Optimierungskern: Ein Rechtsschritt in Zeile \(i\) wiederholt den Zeilenbeitrag \(a_i\), und ein Abwärtsschritt in Spalte \(j\) wiederholt den Spaltenbeitrag \(b_j\). Also lautet die Endformel
$$P(n,n)=A_n+B_n+D(n,n).$$
Ein Weg von \((1,1)\) nach \((n,n)\) enthält genau \(n-1\) Abwärtsschritte. Sei \(t_i\) die Anzahl der bereits ausgeführten Rechtsschritte vor dem \(i\)-ten Abwärtsschritt. Dann gilt
$$0\le t_1\le t_2\le \cdots \le t_{n-1}\le n-1.$$
Diese nicht fallende Folge bestimmt den gesamten Weg. Der \(i\)-te Abwärtsschritt findet in Spalte \(t_i+1\) statt und trägt daher \(b_{t_i+1}\) bei. Bezeichnet \(r_i\) die Zahl der Rechtsschritte in Zeile \(i\), so ist
$$r_1=t_1,\qquad r_i=t_i-t_{i-1}\quad(2\le i\le n-1),\qquad r_n=(n-1)-t_{n-1}.$$
Damit wird der Zusatzterm
$$D(n,n)=\sum_{i=1}^{n} r_i a_i+\sum_{i=1}^{n-1} b_{t_i+1}.$$
Nun teleskopiert der Zeilenanteil:
$$\sum_{i=1}^{n} r_i a_i=t_1a_1+\sum_{i=2}^{n-1}(t_i-t_{i-1})a_i+\bigl((n-1)-t_{n-1}\bigr)a_n,$$
also
$$\sum_{i=1}^{n} r_i a_i=(n-1)a_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})t_i.$$
Somit lautet das Problem exakt
$$D(n,n)=(n-1)a_n+\sum_{i=1}^{n-1}\Bigl((a_i-a_{i+1})t_i+b_{t_i+1}\Bigr).$$
Das zweidimensionale Gitterproblem ist damit zu einer eindimensionalen Optimierung über nicht fallende ganzzahlige Folgen geworden.
Setze
$$u_i=a_i-a_{i+1},\qquad g(t)=b_{t+1}.$$
Sei \(F_i(t)\) der minimale Beitrag der ersten \(i\) Abwärtsschritte unter der Bedingung \(t_i=t\). Dann gilt
$$F_i(t)=u_i t+g(t)+\min_{0\le s\le t}F_{i-1}(s),$$
mit der Anfangsbedingung \(F_0(0)=0\) und \(F_0(t)=+\infty\) für \(t>0\). Nach allen \(n-1\) Abwärtsschritten ist
$$D(n,n)=(n-1)a_n+\min_{0\le t\le n-1}F_{n-1}(t).$$
Die Rekursion zeigt, dass aus der vorherigen Schicht nur die Präfixminimum-Funktion benötigt wird:
$$M_{i-1}(t)=\min_{0\le s\le t}F_{i-1}(s).$$
Würde man dies für alle \(t\) auswerten, bliebe die Laufzeit quadratisch. Der entscheidende nächste Schritt ist deshalb die Zustandskompression.
Betrachte die abgetasteten Punkte
$$\bigl(t,g(t)\bigr)=\bigl(t,b_{t+1}\bigr),\qquad 0\le t\le n-1.$$
Ihre Ecken auf der unteren Hülle seien
$$0=h_0\lt h_1\lt \cdots \lt h_{m-1}\le n-1.$$
Sie werden mit einem monotonen Scan aufgebaut. Wenn drei aufeinanderfolgende Kandidaten \(t_1\lt t_2\lt t_3\) die Bedingung
$$\bigl(t_2-t_1\bigr)\bigl(g(t_3)-g(t_1)\bigr)-\bigl(g(t_2)-g(t_1)\bigr)\bigl(t_3-t_1\bigr)\le 0$$
erfüllen, wird \(t_2\) entfernt, weil sein Punkt auf oder über der Verbindungsstrecke der beiden anderen liegt.
Genau diese Hülle reicht für das schnelle Verfahren. Liegt eine Spalte \(t\) nicht auf der unteren Hülle, dann gibt es Hüllpunkte \(p\lt t\lt q\) und ein \(\lambda\in(0,1)\) mit \(t=\lambda p+(1-\lambda)q\), sodass
$$g(t)\ge \lambda g(p)+(1-\lambda)g(q).$$
Folglich gilt für jede Steigung \(u\)
$$u t+g(t)\ge \lambda\bigl(up+g(p)\bigr)+(1-\lambda)\bigl(uq+g(q)\bigr).$$
Eine Nicht-Hüllspalte kann also die benachbarten Hüllspalten für den geneigten Ausdruck \(u t+g(t)\) nicht beide schlagen. Das Hinzufügen des linearen Terms \(u t\) ist nur eine affine Scherung der Punktmenge, und affine Scherungen ändern nicht, welche abgetasteten Spalten zur unteren Hülle gehören.
Wendet man das auf das DP an, erhält man die zentrale Invariante. Die Präfixminimum-Funktion \(M_{i-1}(t)\) ist stückweise konstant; sie ändert sich nur dort, wo ein neues Rekordminimum erreicht wird. Wenn diese Rekordtiefs auf Hüllspalten liegen, dann minimieren wir auf jedem konstanten Intervall
$$F_i(t)=M_{i-1}(t)+u_i t+g(t),$$
also eine Konstante plus eine geneigte Kopie von \(g\). Das Minimum auf einem solchen Intervall liegt daher wieder auf einer Hüllspalte. Daraus folgt induktiv: Alle Präfixminima, alle Schichtminima und insbesondere das Endminimum können ausschließlich auf Hüllspalten gefunden werden.
Für \(n=2\) entstehen die Werte
$$a_1=102022661,\quad b_1=864751430,\quad a_2=661600260,\quad b_2=328965239.$$
Damit lautet das Gitter
$$\begin{pmatrix} a_1+b_1 & a_1+b_2\\ a_2+b_1 & a_2+b_2 \end{pmatrix} = \begin{pmatrix} 966774091 & 430987900\\ 1526351690 & 990565499 \end{pmatrix}.$$
Es gibt nur einen Parameter \(t_1\). Für \(t_1=0\) geht der Weg zuerst nach unten, für \(t_1=1\) zuerst nach rechts. Der unvermeidliche Grundterm ist
$$a_1+a_2+b_1+b_2=1957339590.$$
Der Zusatzterm ist
$$D(2,2)=a_2+\min\bigl(b_1,\ a_1-a_2+b_2\bigr),$$
also
$$D(2,2)=661600260+\min(864751430,-230612360)=430987900.$$
Daher
$$P(2,2)=1957339590+430987900=2388327490.$$
Genau dieser Wert dient auch als Kontrollpunkt in den Implementierungen.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst die deterministische Folge durch wiederholtes Quadrieren modulo \(998388889\). Daraus werden sämtliche \(a_i\) und \(b_i\) abgeleitet, während gleichzeitig \(\sum a_i\) und \(\sum b_i\) akkumuliert werden. Für \(n=1\) ist die Antwort sofort \(a_1+b_1\).
Für \(n\ge 2\) scannt die Implementierung die Punkte \((t,b_{t+1})\) für \(0\le t\le n-1\) und behält nur die Spalten auf der unteren Hülle. Die geometrische Entscheidung basiert genau auf der oben angegebenen Kreuzprodukt-Ungleichung. Diese Vorverarbeitung ist unabhängig von der jeweiligen DP-Schicht, weil sich die Schichten nur durch das Hinzufügen eines linearen Terms \(u_i t\) unterscheiden.
Nach dem Hüllenaufbau speichert die Implementierung die überlebenden Spaltenindizes und die zugehörigen \(b\)-Werte und führt die Rekursion nur noch auf dieser komprimierten Liste aus. Jede Schicht wird von links nach rechts verarbeitet, während das laufende Präfixminimum der vorherigen Schicht mitgeführt wird. Deshalb reichen zwei rollierende Arrays aus. Am Ende wird der beste komprimierte Zustand mit \((n-1)a_n\) und der Grundsumme \(\sum a_i+\sum b_i\) kombiniert.
Die C++-Implementierung enthält zusätzlich das ursprüngliche quadratische Gitter-DP für kleine Eingaben. Sie prüft explizite Werte für \(n=1\), \(n=2\) und \(n=10\) und vergleicht die schnelle und die quadratische Methode für alle \(1\le n\le 120\). Die Python- und Java-Implementierungen behalten nur den schnellen Weg, folgen aber derselben Herleitung.
Die Erzeugung der Folge und der Grundsummen kostet \(O(n)\) Zeit. Der Aufbau der unteren Hülle ist ein weiterer \(O(n)\)-Durchlauf. Bleiben auf der Hülle \(m\) Spalten übrig, dann benötigt das komprimierte DP \(O(nm)\) Zeit, denn es gibt \(n-1\) Schichten und jede Schicht scannt diese \(m\) Zustände genau einmal.
Die Implementierungen speichern die vollständigen Arrays \(a_i\) und \(b_i\) sowie zwei rollierende DP-Zeilen, sodass der Speicherverbrauch \(O(n+m)\) ist. Zum Vergleich: Das Validierungs-DP auf dem vollen Gitter benötigt \(O(n^2)\) Zeit und mit rollierenden Zeilen \(O(n)\) Speicher. Der Gewinn der endgültigen Methode besteht also darin, die unbrauchbare \(n^2\)-Struktur bei \(n=10^7\) durch eine lineare Vorverarbeitung und ein komprimiertes eindimensionales DP zu ersetzen.
Dizi şu şekilde tanımlanır:
$$s_1=102022661,\qquad s_{k+1}\equiv s_k^2 \pmod{998388889}.$$
Buradan
$$a_i=s_{2i-1},\qquad b_i=s_{2i}$$
alınır; dolayısıyla \((i,j)\) hücresinin maliyeti
$$c_{i,j}=a_i+b_j$$
olur. Amaç, yalnızca sağa ve aşağı giderek \((1,1)\)'den \((n,n)\)'ye ulaşan bir yol üzerindeki hücre değerleri toplamını en küçük yapmaktır. Klasik bir ızgara dinamik programı \(n^2\) durum gerektirir ve gerçek boyut olan \(n=10^7\) için imkansızdır. Bu yüzden uygulamalar \(a_i+b_j\) biçimindeki toplamsal yapıyı kullanır, yolu aşağı inişlerin hangi sütunlarda gerçekleştiğiyle yeniden tanımlar ve sonra kalan tek boyutlu durumu alt zarf argümanıyla sıkıştırır.
Çözüm üç katmandan oluşur. Önce her monoton yolun mutlaka ödediği kısım ayrılır. Sonra yol, sütun seçimlerinden oluşan artmayan değil artan bir diziyle kodlanır. Son adımda ise ortaya çıkan DP'de yalnızca \(t\mapsto b_{t+1}\) örnekli grafiğinin alt dışbükey zarfı üzerindeki sütunların gerektiği gösterilir.
\(P(i,j)\), \((i,j)\) hücresine kadar gelen en küçük yol toplamı olsun; bu değer o hücrenin kendi maliyetini de içersin. O zaman temel bağıntı
$$P(1,1)=a_1+b_1,$$
$$P(i,j)=a_i+b_j+\min\bigl(P(i,j-1),P(i-1,j)\bigr)$$
şeklindedir. Sol üstten sağ alta giden her monoton yol, her satırı en az bir kez ve her sütunu en az bir kez ziyaret eder. Bu yüzden
$$A_i=\sum_{r=1}^{i} a_r,\qquad B_j=\sum_{c=1}^{j} b_c$$
toplamları, ziyaret edilen her satır ve sütunun zorunlu tek seferlik katkısını içerir. Şimdi
$$D(i,j)=P(i,j)-A_i-B_j$$
tanımını yapalım. Böylece \(D(1,1)=0\) olur ve geçiş
$$D(i,j)=\min\bigl(D(i,j-1)+a_i,\ D(i-1,j)+b_j\bigr)$$
haline gelir. Bu formül aslında neyin optimize edildiğini açıkça gösterir: satır \(i\) içinde sağa gitmek, \(a_i\) satır maliyetini tekrar ödetir; sütun \(j\) içinde aşağı inmek ise \(b_j\) sütun maliyetini tekrar ödetir. Sonuç dolayısıyla
$$P(n,n)=A_n+B_n+D(n,n)$$
şeklindedir.
\((1,1)\)'den \((n,n)\)'ye giden bir yol tam olarak \(n-1\) kez aşağı iner. \(t_i\), \(i\). aşağı inişten önce yapılmış sağ hareket sayısı olsun. O halde
$$0\le t_1\le t_2\le \cdots \le t_{n-1}\le n-1.$$
Bu artmayan değil artan dizi, yolun tamamını belirler. \(i\). aşağı iniş \(t_i+1\). sütunda gerçekleşir ve bu yüzden \(b_{t_i+1}\) katkısını getirir. Eğer \(r_i\), \(i\). satırda yapılan sağ hareket sayısıysa
$$r_1=t_1,\qquad r_i=t_i-t_{i-1}\quad(2\le i\le n-1),\qquad r_n=(n-1)-t_{n-1}.$$
Böylece taban terimin üzerindeki ek maliyet
$$D(n,n)=\sum_{i=1}^{n} r_i a_i+\sum_{i=1}^{n-1} b_{t_i+1}$$
olur. Satır terimini teleskopik biçimde açarsak
$$\sum_{i=1}^{n} r_i a_i=t_1a_1+\sum_{i=2}^{n-1}(t_i-t_{i-1})a_i+\bigl((n-1)-t_{n-1}\bigr)a_n,$$
ve buradan
$$\sum_{i=1}^{n} r_i a_i=(n-1)a_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})t_i$$
çıkar. Dolayısıyla problem tam olarak
$$D(n,n)=(n-1)a_n+\sum_{i=1}^{n-1}\Bigl((a_i-a_{i+1})t_i+b_{t_i+1}\Bigr)$$
biçimine iner. İki boyutlu ızgara problemi artık artan tamsayı dizileri üzerinde tek boyutlu bir optimizasyon problemidir.
Şu kısaltmaları kullanalım:
$$u_i=a_i-a_{i+1},\qquad g(t)=b_{t+1}.$$
\(F_i(t)\), ilk \(i\) aşağı inişin en küçük katkısı ve son seçimin \(t_i=t\) olduğu durum olsun. O zaman
$$F_i(t)=u_i t+g(t)+\min_{0\le s\le t}F_{i-1}(s)$$
bağıntısı elde edilir. Başlangıç koşulu \(F_0(0)=0\) ve \(t>0\) için \(F_0(t)=+\infty\)'dir. Tüm \(n-1\) iniş işlendiğinde
$$D(n,n)=(n-1)a_n+\min_{0\le t\le n-1}F_{n-1}(t)$$
olur. Bu bağıntı, bir önceki katmandan yalnızca şu ön-ek minimum fonksiyonunun gerektiğini gösterir:
$$M_{i-1}(t)=\min_{0\le s\le t}F_{i-1}(s).$$
Tüm \(t\) değerleri üzerinde çalışılırsa zaman maliyeti yine karesel kalır. Hız kazandıran fikir, durumların büyük kısmını tamamen atmaktır.
Şu örneklenmiş noktalara bakalım:
$$\bigl(t,g(t)\bigr)=\bigl(t,b_{t+1}\bigr),\qquad 0\le t\le n-1.$$
Bu noktaların alt zarf köşelerini
$$0=h_0\lt h_1\lt \cdots \lt h_{m-1}\le n-1$$
diye gösterelim. Bunlar tek yönlü bir taramayla kurulur. Arka arkaya gelen üç aday \(t_1\lt t_2\lt t_3\) için
$$\bigl(t_2-t_1\bigr)\bigl(g(t_3)-g(t_1)\bigr)-\bigl(g(t_2)-g(t_1)\bigr)\bigl(t_3-t_1\bigr)\le 0$$
ise orta nokta \(t_2\) atılır; çünkü noktası, diğer ikisini birleştiren doğru parçasının üzerinde ya da üstündedir.
Hızlı çözümün tam olarak ihtiyaç duyduğu nesne budur. Eğer bir \(t\) sütunu alt zarf üzerinde değilse, \(p\lt t\lt q\) olacak şekilde iki zarf köşesi ve \(t=\lambda p+(1-\lambda)q\) sağlayan bir \(\lambda\in(0,1)\) vardır ve
$$g(t)\ge \lambda g(p)+(1-\lambda)g(q)$$
eşitsizliği geçerlidir. Bu yüzden her \(u\) eğimi için
$$u t+g(t)\ge \lambda\bigl(up+g(p)\bigr)+(1-\lambda)\bigl(uq+g(q)\bigr)$$
olur. Yani zarf dışında kalan bir sütun, eğilmiş maliyet \(u t+g(t)\) için iki komşu zarf köşesini aynı anda yenemez. Lineer \(u t\) terimini eklemek, nokta kümesine yalnızca afin bir kaydırma uygular; bu da hangi örnek sütunların alt zarf üzerinde kaldığını değiştirmez.
Şimdi bunu DP'ye uygularız. \(M_{i-1}(t)\) fonksiyonu parçalı sabittir; yalnızca yeni bir rekor minimum oluştuğunda değişir. Eğer bu rekor minimumlar zarf köşelerinde oluşuyorsa, sabit kaldığı her aralıkta
$$F_i(t)=M_{i-1}(t)+u_i t+g(t)$$
ifadesini minimize ederiz. Bu da sabit bir sayı artı eğilmiş bir \(g\) kopyasıdır; dolayısıyla minimum yine zarf üzerindeki bir sütunda elde edilir. Böylece tümevarımla şu sonuç çıkar: tüm ön-ek minimumları, tüm katman minimumlarını ve nihai optimumu yalnızca zarf sütunlarından okumak yeterlidir.
\(n=2\) için üretilen değerler şunlardır:
$$a_1=102022661,\quad b_1=864751430,\quad a_2=661600260,\quad b_2=328965239.$$
Buna karşılık gelen ızgara
$$\begin{pmatrix} a_1+b_1 & a_1+b_2\\ a_2+b_1 & a_2+b_2 \end{pmatrix} = \begin{pmatrix} 966774091 & 430987900\\ 1526351690 & 990565499 \end{pmatrix}$$
olur. Burada yalnızca bir parametre vardır: \(t_1\). \(t_1=0\) ise yol önce aşağı iner; \(t_1=1\) ise önce sağa gider. Kaçınılmaz taban kısım
$$a_1+a_2+b_1+b_2=1957339590$$
değerindedir. Ek kısım ise
$$D(2,2)=a_2+\min\bigl(b_1,\ a_1-a_2+b_2\bigr),$$
yani
$$D(2,2)=661600260+\min(864751430,-230612360)=430987900$$
çıkar. Sonuç olarak
$$P(2,2)=1957339590+430987900=2388327490$$
elde edilir. Bu, uygulamaların kullandığı küçük doğrulama değeridir ve taban maliyet artı optimize edilen ek maliyet ayrımını açıkça gösterir.
C++, Python ve Java uygulamaları önce sabit mod altında tekrar tekrar kare alma işlemiyle diziyi üretir. Bu akıştan tüm \(a_i\) ve \(b_i\) değerleri çıkarılırken \(\sum a_i\) ve \(\sum b_i\) de aynı anda biriktirilir. \(n=1\) için cevap doğrudan \(a_1+b_1\) olduğundan zarf ve DP aşamalarına gerek kalmaz.
\(n\ge 2\) olduğunda uygulama \(0\le t\le n-1\) için \((t,b_{t+1})\) noktalarını tarar ve yalnızca alt zarf üzerinde kalan sütunları saklar. Geometrik eleme tam olarak yukarıdaki çapraz çarpım eşitsizliğine dayanır. Bu ön işlem, DP katmanından bağımsızdır; çünkü her katmanda değişen tek şey lineer \(u_i t\) terimidir.
Zarf kurulduktan sonra uygulama hayatta kalan sütun indislerini ve bunlara karşılık gelen \(b\) değerlerini saklar ve bağıntıyı yalnızca bu sıkıştırılmış liste üzerinde yürütür. Her katman soldan sağa tek geçişte işlenir ve bir önceki katmanın koşan ön-ek minimumu tutulur. Bu yüzden iki dönen dizi yeterlidir. En sonunda en iyi sıkıştırılmış durum, \((n-1)a_n\) ve \(\sum a_i+\sum b_i\) ile birleştirilir.
C++ uygulaması ayrıca küçük boyutlar için özgün karesel ızgara DP'sini de saklar. \(n=1\), \(n=2\) ve \(n=10\) için açık doğrulamalar yapar; ayrıca hızlı yöntem ile karesel yöntemi tüm \(1\le n\le 120\) değerlerinde karşılaştırır. Python ve Java sürümleri yalnızca hızlı çözümü içerir, fakat aynı matematiği uygular.
Dizinin ve taban toplamların üretilmesi \(O(n)\) zaman alır. Alt zarfın oluşturulması da ayrı bir \(O(n)\) taramadır. Zarf üzerinde \(m\) sütun kalıyorsa sıkıştırılmış DP'nin maliyeti \(O(nm)\) olur; çünkü \(n-1\) katmanın her biri bu \(m\) durumu tam bir kez dolaşır.
Uygulamalar tam uzunlukta \(a_i\) ve \(b_i\) dizilerini ve iki adet DP satırını tuttuğu için bellek kullanımı \(O(n+m)\)'dir. Karşılaştırma amacıyla kullanılan doğrulama DP'si ise dönen satırlarla \(O(n)\) bellek ve \(O(n^2)\) zaman kullanır. Nihai yöntem, asıl olarak \(n=10^7\) için kullanılamaz olan \(n^2\) ızgara yapısını, doğrusal bir ön işleme ve sıkıştırılmış tek boyutlu bir DP'ye çevirmiş olur.
La sucesión se define por
$$s_1=102022661,\qquad s_{k+1}\equiv s_k^2 \pmod{998388889}.$$
De ella se toman
$$a_i=s_{2i-1},\qquad b_i=s_{2i},$$
de modo que el costo de la celda \((i,j)\) es
$$c_{i,j}=a_i+b_j.$$
Hay que minimizar la suma de los valores visitados a lo largo de un camino desde \((1,1)\) hasta \((n,n)\) usando solo movimientos a la derecha y hacia abajo. Un DP clásico sobre toda la rejilla tendría \(n^2\) estados y es inviable para el tamaño real \(n=10^7\). Por eso las implementaciones aprovechan la forma aditiva \(a_i+b_j\), reescriben el camino mediante las columnas donde se producen los descensos y luego comprimen el espacio de estados unidimensional restante con un argumento geométrico sobre la envolvente inferior.
La derivación tiene tres niveles. Primero se separa la parte del costo que cualquier camino monótono paga inevitablemente. Después se codifica el camino mediante una sucesión no decreciente de elecciones de columna. Finalmente se demuestra que, en el DP resultante, solo hacen falta las columnas situadas en la envolvente inferior del gráfico muestreado \(t\mapsto b_{t+1}\).
Sea \(P(i,j)\) el costo mínimo de un camino que termina en \((i,j)\), incluyendo el valor de esa celda. Entonces
$$P(1,1)=a_1+b_1,$$
$$P(i,j)=a_i+b_j+\min\bigl(P(i,j-1),P(i-1,j)\bigr).$$
Todo camino monótono desde la esquina superior izquierda hasta la inferior derecha visita cada fila al menos una vez y cada columna al menos una vez. Por eso
$$A_i=\sum_{r=1}^{i} a_r,\qquad B_j=\sum_{c=1}^{j} b_c$$
recoge exactamente la contribución obligatoria, pagada una sola vez, de cada fila y columna visitadas. Definimos
$$D(i,j)=P(i,j)-A_i-B_j.$$
Así \(D(1,1)=0\) y la recurrencia se simplifica a
$$D(i,j)=\min\bigl(D(i,j-1)+a_i,\ D(i-1,j)+b_j\bigr).$$
Esta forma deja claro qué se está optimizando de verdad: moverse a la derecha en la fila \(i\) vuelve a pagar el costo de fila \(a_i\), mientras que bajar en la columna \(j\) vuelve a pagar el costo de columna \(b_j\). Por lo tanto,
$$P(n,n)=A_n+B_n+D(n,n).$$
Un camino desde \((1,1)\) hasta \((n,n)\) contiene exactamente \(n-1\) movimientos hacia abajo. Sea \(t_i\) el número de movimientos a la derecha ya realizados antes del \(i\)-ésimo descenso. Entonces
$$0\le t_1\le t_2\le \cdots \le t_{n-1}\le n-1.$$
Esta sucesión no decreciente determina el camino completo. El \(i\)-ésimo descenso ocurre en la columna \(t_i+1\), así que aporta \(b_{t_i+1}\). Si \(r_i\) es el número de movimientos a la derecha ejecutados en la fila \(i\), entonces
$$r_1=t_1,\qquad r_i=t_i-t_{i-1}\quad(2\le i\le n-1),\qquad r_n=(n-1)-t_{n-1}.$$
El costo extra sobre la base común es por tanto
$$D(n,n)=\sum_{i=1}^{n} r_i a_i+\sum_{i=1}^{n-1} b_{t_i+1}.$$
Ahora la parte de filas telescopa:
$$\sum_{i=1}^{n} r_i a_i=t_1a_1+\sum_{i=2}^{n-1}(t_i-t_{i-1})a_i+\bigl((n-1)-t_{n-1}\bigr)a_n,$$
de modo que
$$\sum_{i=1}^{n} r_i a_i=(n-1)a_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})t_i.$$
Así, el problema se reduce exactamente a
$$D(n,n)=(n-1)a_n+\sum_{i=1}^{n-1}\Bigl((a_i-a_{i+1})t_i+b_{t_i+1}\Bigr).$$
El problema bidimensional de la rejilla se ha convertido en una optimización unidimensional sobre sucesiones enteras no decrecientes.
Introducimos
$$u_i=a_i-a_{i+1},\qquad g(t)=b_{t+1}.$$
Sea \(F_i(t)\) la contribución mínima de los primeros \(i\) descensos bajo la condición \(t_i=t\). Entonces
$$F_i(t)=u_i t+g(t)+\min_{0\le s\le t}F_{i-1}(s),$$
con condición inicial \(F_0(0)=0\) y \(F_0(t)=+\infty\) para \(t>0\). Después de procesar los \(n-1\) descensos,
$$D(n,n)=(n-1)a_n+\min_{0\le t\le n-1}F_{n-1}(t).$$
La recurrencia muestra que de la capa anterior solo se necesita la función de mínimo prefijo
$$M_{i-1}(t)=\min_{0\le s\le t}F_{i-1}(s).$$
Si se evaluara esta fórmula para todos los \(t\), el tiempo seguiría siendo cuadrático. La mejora decisiva viene de descartar la mayoría de las columnas.
Consideremos los puntos muestreados
$$\bigl(t,g(t)\bigr)=\bigl(t,b_{t+1}\bigr),\qquad 0\le t\le n-1.$$
Sus vértices sobre la envolvente inferior serán
$$0=h_0\lt h_1\lt \cdots \lt h_{m-1}\le n-1.$$
Se construyen con un barrido monótono. Si tres candidatos consecutivos \(t_1\lt t_2\lt t_3\) cumplen
$$\bigl(t_2-t_1\bigr)\bigl(g(t_3)-g(t_1)\bigr)-\bigl(g(t_2)-g(t_1)\bigr)\bigl(t_3-t_1\bigr)\le 0,$$
entonces \(t_2\) se descarta porque su punto queda sobre o por encima del segmento que une a los otros dos.
Esa es exactamente la estructura que necesita el solver rápido. Si una columna \(t\) no pertenece a la envolvente inferior, existen vértices \(p\lt t\lt q\) y un \(\lambda\in(0,1)\) con \(t=\lambda p+(1-\lambda)q\) tales que
$$g(t)\ge \lambda g(p)+(1-\lambda)g(q).$$
Por lo tanto, para cualquier pendiente \(u\),
$$u t+g(t)\ge \lambda\bigl(up+g(p)\bigr)+(1-\lambda)\bigl(uq+g(q)\bigr).$$
Eso significa que una columna fuera de la envolvente nunca puede superar simultáneamente a sus dos vecinos de la envolvente para el costo inclinado \(u t+g(t)\). Añadir el término lineal \(u t\) es una cizalla afín del conjunto de puntos, y una cizalla afín no cambia qué columnas muestreadas forman parte de la envolvente inferior.
Llevado al DP, esto produce la invariante central. La función \(M_{i-1}(t)\) es constante por tramos; solo cambia cuando aparece un nuevo mínimo récord. Si esos récords se alcanzan en columnas de la envolvente, entonces en cada tramo donde \(M_{i-1}\) es constante estamos minimizando
$$F_i(t)=M_{i-1}(t)+u_i t+g(t),$$
es decir, una constante más una copia inclinada de \(g\). El mínimo de ese tramo vuelve a estar en una columna de la envolvente. Por inducción, todos los mínimos prefijo, todos los mínimos de capa y el óptimo final se pueden leer exclusivamente en las columnas de la envolvente inferior.
Para \(n=2\), los valores generados son
$$a_1=102022661,\quad b_1=864751430,\quad a_2=661600260,\quad b_2=328965239.$$
La rejilla resultante es
$$\begin{pmatrix} a_1+b_1 & a_1+b_2\\ a_2+b_1 & a_2+b_2 \end{pmatrix} = \begin{pmatrix} 966774091 & 430987900\\ 1526351690 & 990565499 \end{pmatrix}.$$
Aquí solo existe un parámetro, \(t_1\). Si \(t_1=0\), el camino baja primero; si \(t_1=1\), va primero a la derecha. La parte base inevitable es
$$a_1+a_2+b_1+b_2=1957339590.$$
La parte extra vale
$$D(2,2)=a_2+\min\bigl(b_1,\ a_1-a_2+b_2\bigr),$$
así que
$$D(2,2)=661600260+\min(864751430,-230612360)=430987900.$$
Por consiguiente,
$$P(2,2)=1957339590+430987900=2388327490.$$
Este es el mismo valor de control que usan las implementaciones y resume perfectamente la descomposición en costo base más costo extra optimizado.
Las implementaciones en C++, Python y Java generan primero la sucesión determinista mediante cuadrados modulares repetidos. De ese flujo extraen todos los \(a_i\) y \(b_i\), acumulando a la vez \(\sum a_i\) y \(\sum b_i\). Cuando \(n=1\), la respuesta ya es simplemente \(a_1+b_1\).
Para \(n\ge 2\), la implementación recorre los puntos \((t,b_{t+1})\) con \(0\le t\le n-1\) y conserva únicamente las columnas que quedan en la envolvente inferior. La decisión geométrica usa exactamente la desigualdad de producto cruzado escrita antes. Este preprocesamiento no depende de la capa del DP, porque cada capa solo añade un término lineal \(u_i t\).
Una vez conocida la envolvente, la implementación guarda los índices de columna que sobreviven y sus valores de \(b\), y ejecuta la recurrencia solo sobre esa lista comprimida. Cada capa se procesa de izquierda a derecha manteniendo el mínimo prefijo de la capa anterior, por lo que bastan dos arreglos rodantes. Al final, el mejor estado comprimido se combina con \((n-1)a_n\) y con la suma base \(\sum a_i+\sum b_i\).
La implementación en C++ conserva además el DP cuadrático original sobre la rejilla para validar tamaños pequeños. Comprueba valores explícitos para \(n=1\), \(n=2\) y \(n=10\), y compara el método rápido con el cuadrático para todos los \(1\le n\le 120\). Las versiones de Python y Java se quedan solo con el solver rápido, pero siguen la misma derivación.
Generar la sucesión y las sumas base cuesta \(O(n)\) tiempo. Construir la envolvente inferior es otro recorrido \(O(n)\). Si la envolvente contiene \(m\) columnas supervivientes, el DP comprimido tarda \(O(nm)\), ya que hay \(n-1\) capas y cada una recorre una sola vez esos \(m\) estados.
Las implementaciones almacenan los arreglos completos de \(a_i\) y \(b_i\), junto con dos filas rodantes del DP, de modo que el uso de memoria es \(O(n+m)\). En comparación, el DP de validación sobre toda la rejilla requiere \(O(n^2)\) tiempo y \(O(n)\) memoria con filas rodantes. El beneficio del método final es precisamente sustituir la estructura cuadrática imposible para \(n=10^7\) por un preprocesamiento lineal y un DP unidimensional comprimido.
数列按下式定义：
$$s_1=102022661,\qquad s_{k+1}\equiv s_k^2 \pmod{998388889}.$$
然后取
$$a_i=s_{2i-1},\qquad b_i=s_{2i},$$
于是单元格 \((i,j)\) 的代价就是
$$c_{i,j}=a_i+b_j.$$
题目要求在只允许向右或向下移动的条件下，从 \((1,1)\) 走到 \((n,n)\)，使经过单元格的权值和最小。如果直接对整个网格做动态规划，就需要 \(n^2\) 个状态；当真实规模是 \(n=10^7\) 时，这当然不可能。三份实现真正利用的是 \(a_i+b_j\) 这种可分离结构：先把路径改写成“每一次下移发生在哪一列”的一维对象，再用下凸包把一维状态压缩掉绝大部分。
整个推导可以分成三个层次。第一步，把所有单调路径必然支付的那一部分单独拆出来。第二步，把路径编码成一个非降整数序列。第三步，证明在得到的一维动态规划中，只需要保留采样图像 \(t\mapsto b_{t+1}\) 的下凸包顶点即可。
记 \(P(i,j)\) 为到达单元格 \((i,j)\) 的最小路径和，并且它已经包含该单元格本身的权值。标准递推是
$$P(1,1)=a_1+b_1,$$
$$P(i,j)=a_i+b_j+\min\bigl(P(i,j-1),P(i-1,j)\bigr).$$
任何一条从左上走到右下的单调路径，都会至少访问一次每一行，也都会至少访问一次每一列。因此
$$A_i=\sum_{r=1}^{i} a_r,\qquad B_j=\sum_{c=1}^{j} b_c$$
正好描述了这些被访问行、列各付一次的必选成本。定义
$$D(i,j)=P(i,j)-A_i-B_j.$$
这样 \(D(1,1)=0\)，而递推会化简成
$$D(i,j)=\min\bigl(D(i,j-1)+a_i,\ D(i-1,j)+b_j\bigr).$$
这个形式非常关键，因为它把“真正需要优化的部分”直接暴露出来了：在第 \(i\) 行里继续向右，会重复支付行代价 \(a_i\)；在第 \(j\) 列里继续向下，会重复支付列代价 \(b_j\)。因此最终答案就是
$$P(n,n)=A_n+B_n+D(n,n).$$
从 \((1,1)\) 到 \((n,n)\) 的路径恰好包含 \(n-1\) 次向下移动。设 \(t_i\) 表示第 \(i\) 次向下之前已经完成了多少次向右移动，那么必然有
$$0\le t_1\le t_2\le \cdots \le t_{n-1}\le n-1.$$
这条非降序列已经唯一决定了整条路径。第 \(i\) 次下移发生在第 \(t_i+1\) 列，所以带来一项 \(b_{t_i+1}\)。如果记 \(r_i\) 为第 \(i\) 行里执行的向右步数，那么
$$r_1=t_1,\qquad r_i=t_i-t_{i-1}\quad(2\le i\le n-1),\qquad r_n=(n-1)-t_{n-1}.$$
于是基础代价以外的额外部分满足
$$D(n,n)=\sum_{i=1}^{n} r_i a_i+\sum_{i=1}^{n-1} b_{t_i+1}.$$
现在把行部分做一次望远镜化简：
$$\sum_{i=1}^{n} r_i a_i=t_1a_1+\sum_{i=2}^{n-1}(t_i-t_{i-1})a_i+\bigl((n-1)-t_{n-1}\bigr)a_n,$$
因此
$$\sum_{i=1}^{n} r_i a_i=(n-1)a_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})t_i.$$
从而整个优化问题可以准确写成
$$D(n,n)=(n-1)a_n+\sum_{i=1}^{n-1}\Bigl((a_i-a_{i+1})t_i+b_{t_i+1}\Bigr).$$
至此，二维网格最短路已经完全变成了“在非降整数序列上最小化一个和式”的一维问题。
记
$$u_i=a_i-a_{i+1},\qquad g(t)=b_{t+1}.$$
再令 \(F_i(t)\) 表示“前 \(i\) 次下移都已经安排好，且第 \(i\) 次下移前共做了 \(t\) 次右移”时的最小贡献。那么有递推
$$F_i(t)=u_i t+g(t)+\min_{0\le s\le t}F_{i-1}(s).$$
初始条件是 \(F_0(0)=0\)，并且对 \(t>0\) 有 \(F_0(t)=+\infty\)。当全部 \(n-1\) 次下移都处理完以后，
$$D(n,n)=(n-1)a_n+\min_{0\le t\le n-1}F_{n-1}(t).$$
这个递推说明，上一层传下来的信息并不是完整的一行状态，而只是前缀最小函数
$$M_{i-1}(t)=\min_{0\le s\le t}F_{i-1}(s).$$
如果对每个 \(t\) 都显式计算，复杂度仍然是平方级。真正的压缩发生在下一步的几何观察里。
考虑采样点
$$\bigl(t,g(t)\bigr)=\bigl(t,b_{t+1}\bigr),\qquad 0\le t\le n-1.$$
把它们的下凸包顶点记为
$$0=h_0\lt h_1\lt \cdots \lt h_{m-1}\le n-1.$$
这些顶点可以用单调扫描构造出来。若三个连续候选点 \(t_1\lt t_2\lt t_3\) 满足
$$\bigl(t_2-t_1\bigr)\bigl(g(t_3)-g(t_1)\bigr)-\bigl(g(t_2)-g(t_1)\bigr)\bigl(t_3-t_1\bigr)\le 0,$$
那么中间点 \(t_2\) 就会被删去，因为它位于另外两点连线之上或线上，不可能成为下凸包的转折点。
为什么这正好对应快速算法？如果某个整数列 \(t\) 不在下凸包上，那么存在相邻的凸包顶点 \(p\lt t\lt q\) 与某个 \(\lambda\in(0,1)\)，使得 \(t=\lambda p+(1-\lambda)q\) 且
$$g(t)\ge \lambda g(p)+(1-\lambda)g(q).$$
于是对任意斜率 \(u\)，都有
$$u t+g(t)\ge \lambda\bigl(up+g(p)\bigr)+(1-\lambda)\bigl(uq+g(q)\bigr).$$
也就是说，在“给 \(g\) 加上一条线性倾斜”以后，非凸包点不可能同时优于它左右两侧的凸包顶点。加上 \(u t\) 其实只是对点集做了一次仿射剪切，而仿射剪切不会改变哪些采样列属于下凸包。
把这个事实带回动态规划，就得到核心不变量。函数 \(M_{i-1}(t)\) 是分段常数函数，它只会在出现新的历史最小值时发生变化。如果这些新的最小值都发生在凸包列上，那么在任何一个常值区间里，我们最小化的都是
$$F_i(t)=M_{i-1}(t)+u_i t+g(t),$$
也就是“常数 + 倾斜后的 \(g\)”。而这种最小值仍然必然落在下凸包列上。于是可以归纳得到：每一层的前缀最小值、每一层的全局最小值以及最后的最优答案，都可以完全从下凸包顶点中读出。
当 \(n=2\) 时，生成出的数为
$$a_1=102022661,\quad b_1=864751430,\quad a_2=661600260,\quad b_2=328965239.$$
对应网格是
$$\begin{pmatrix} a_1+b_1 & a_1+b_2\\ a_2+b_1 & a_2+b_2 \end{pmatrix} = \begin{pmatrix} 966774091 & 430987900\\ 1526351690 & 990565499 \end{pmatrix}.$$
这里只有一个参数 \(t_1\)。若 \(t_1=0\)，路径先下后右；若 \(t_1=1\)，路径先右后下。所有路径共有的基础部分是
$$a_1+a_2+b_1+b_2=1957339590.$$
额外部分则是
$$D(2,2)=a_2+\min\bigl(b_1,\ a_1-a_2+b_2\bigr),$$
因此
$$D(2,2)=661600260+\min(864751430,-230612360)=430987900.$$
最终得到
$$P(2,2)=1957339590+430987900=2388327490.$$
这正是实现里用于小规模校验的数值，也很好地展示了“基础部分 + 可优化额外部分”的分解。
C++、Python 和 Java 实现都会先通过重复模平方生成整条确定性序列，再从中提取全部 \(a_i\) 和 \(b_i\)，同时累加 \(\sum a_i\) 与 \(\sum b_i\)。如果 \(n=1\)，答案直接就是 \(a_1+b_1\)，不需要后续步骤。
当 \(n\ge 2\) 时，程序扫描所有点 \((t,b_{t+1})\)，其中 \(0\le t\le n-1\)，并且只保留下凸包上的列。几何判断正是上面那条叉积不等式。因为每一层 DP 只是在 \(g(t)\) 上加一个线性项 \(u_i t\)，所以下凸包可以预先统一构造一次。
下凸包建好之后，实现会保存这些幸存列的下标及其对应的 \(b\) 值，然后只在这张压缩后的状态表上运行递推。每一层都从左到右扫描，并维护上一层的前缀最小值，因此只需要两行滚动数组。最后再把最佳压缩状态与 \((n-1)a_n\) 以及基础和 \(\sum a_i+\sum b_i\) 合并起来。
C++ 实现还保留了原始的二维平方级网格 DP，用于小规模验证。它不仅检查 \(n=1\)、\(n=2\)、\(n=10\) 的明确数值，还会把快速方法与平方方法在全部 \(1\le n\le 120\) 的情形下一一比对。Python 与 Java 版本只保留快速算法，但数学内容完全相同。
生成序列并计算基础和需要 \(O(n)\) 时间。构造下凸包再花一个 \(O(n)\) 线性扫描。若下凸包上总共有 \(m\) 个保留下来的列，那么压缩 DP 的时间复杂度是 \(O(nm)\)，因为一共有 \(n-1\) 层，而每一层只扫描这 \(m\) 个状态一次。
当前实现会保存完整的 \(a_i\) 数组、完整的 \(b_i\) 数组以及两行滚动 DP，因此空间复杂度是 \(O(n+m)\)。相比之下，用于验证的小规模原始网格 DP 需要 \(O(n^2)\) 时间和 \(O(n)\) 空间。最终方法的意义就在于：把 \(n=10^7\) 时完全无法承受的平方级网格问题，转化成线性预处理加压缩一维 DP。
Последовательность задается формулами
$$s_1=102022661,\qquad s_{k+1}\equiv s_k^2 \pmod{998388889}.$$
Из нее берутся
$$a_i=s_{2i-1},\qquad b_i=s_{2i},$$
так что стоимость клетки \((i,j)\) равна
$$c_{i,j}=a_i+b_j.$$
Нужно минимизировать сумму значений клеток на пути из \((1,1)\) в \((n,n)\), если разрешены только шаги вправо и вниз. Обычный DP по всей таблице имеет \(n^2\) состояний и для реального размера \(n=10^7\) не подходит. Поэтому реализации используют аддитивную структуру \(a_i+b_j\), переписывают путь через столбцы, в которых происходят переходы вниз, а затем геометрически сжимают оставшееся одномерное пространство состояний.
Вывод состоит из трех шагов. Сначала выделяется та часть стоимости, которую любой монотонный путь платит неизбежно. Затем путь кодируется неубывающей последовательностью целых чисел. После этого доказывается, что в получившемся DP достаточно хранить только те столбцы, которые лежат на нижней оболочке дискретного графика \(t\mapsto b_{t+1}\).
Пусть \(P(i,j)\) обозначает минимальную стоимость пути до клетки \((i,j)\), включая стоимость этой клетки. Тогда
$$P(1,1)=a_1+b_1,$$
$$P(i,j)=a_i+b_j+\min\bigl(P(i,j-1),P(i-1,j)\bigr).$$
Любой монотонный путь из левого верхнего угла в правый нижний посещает каждую строку хотя бы один раз и каждый столбец хотя бы один раз. Поэтому
$$A_i=\sum_{r=1}^{i} a_r,\qquad B_j=\sum_{c=1}^{j} b_c$$
содержат ровно тот одноразовый вклад, который обязателен для любой такой траектории. Определим
$$D(i,j)=P(i,j)-A_i-B_j.$$
Тогда \(D(1,1)=0\), а рекурсия упрощается до
$$D(i,j)=\min\bigl(D(i,j-1)+a_i,\ D(i-1,j)+b_j\bigr).$$
Эта запись показывает, что именно оптимизируется: шаг вправо в строке \(i\) повторно платит строковую стоимость \(a_i\), а шаг вниз в столбце \(j\) повторно платит столбцовую стоимость \(b_j\). Следовательно,
$$P(n,n)=A_n+B_n+D(n,n).$$
Путь из \((1,1)\) в \((n,n)\) содержит ровно \(n-1\) переходов вниз. Пусть \(t_i\) - количество шагов вправо, уже сделанных перед \(i\)-м шагом вниз. Тогда обязательно
$$0\le t_1\le t_2\le \cdots \le t_{n-1}\le n-1.$$
Эта неубывающая последовательность полностью задает путь. \(i\)-й шаг вниз происходит в столбце \(t_i+1\), поэтому дает вклад \(b_{t_i+1}\). Если \(r_i\) - число шагов вправо в строке \(i\), то
$$r_1=t_1,\qquad r_i=t_i-t_{i-1}\quad(2\le i\le n-1),\qquad r_n=(n-1)-t_{n-1}.$$
Отсюда дополнительная часть стоимости равна
$$D(n,n)=\sum_{i=1}^{n} r_i a_i+\sum_{i=1}^{n-1} b_{t_i+1}.$$
Теперь сумма по строкам телескопируется:
$$\sum_{i=1}^{n} r_i a_i=t_1a_1+\sum_{i=2}^{n-1}(t_i-t_{i-1})a_i+\bigl((n-1)-t_{n-1}\bigr)a_n,$$
поэтому
$$\sum_{i=1}^{n} r_i a_i=(n-1)a_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})t_i.$$
Тем самым задача точно переписывается как
$$D(n,n)=(n-1)a_n+\sum_{i=1}^{n-1}\Bigl((a_i-a_{i+1})t_i+b_{t_i+1}\Bigr).$$
Двумерная задача о пути по сетке сведена к одномерной оптимизации по неубывающим целочисленным последовательностям.
Введем обозначения
$$u_i=a_i-a_{i+1},\qquad g(t)=b_{t+1}.$$
Пусть \(F_i(t)\) - минимальный вклад первых \(i\) шагов вниз при условии \(t_i=t\). Тогда
$$F_i(t)=u_i t+g(t)+\min_{0\le s\le t}F_{i-1}(s),$$
с начальными условиями \(F_0(0)=0\) и \(F_0(t)=+\infty\) при \(t>0\). После обработки всех \(n-1\) шагов вниз получаем
$$D(n,n)=(n-1)a_n+\min_{0\le t\le n-1}F_{n-1}(t).$$
Из рекурсии видно, что от предыдущего слоя нужна только функция префиксного минимума
$$M_{i-1}(t)=\min_{0\le s\le t}F_{i-1}(s).$$
Если вычислять это для всех \(t\), сложность останется квадратичной. Решающий шаг состоит в том, чтобы выбросить почти все столбцы.
Рассмотрим точки
$$\bigl(t,g(t)\bigr)=\bigl(t,b_{t+1}\bigr),\qquad 0\le t\le n-1.$$
Их вершины на нижней оболочке обозначим через
$$0=h_0\lt h_1\lt \cdots \lt h_{m-1}\le n-1.$$
Они строятся монотонным проходом. Если для трех последовательных кандидатов \(t_1\lt t_2\lt t_3\) выполнено
$$\bigl(t_2-t_1\bigr)\bigl(g(t_3)-g(t_1)\bigr)-\bigl(g(t_2)-g(t_1)\bigr)\bigl(t_3-t_1\bigr)\le 0,$$
то точка \(t_2\) удаляется, потому что она лежит на или над отрезком между двумя другими.
Именно эта оболочка нужна быстрому алгоритму. Если некоторое значение \(t\) не лежит на нижней оболочке, то существуют соседние вершины оболочки \(p\lt t\lt q\) и число \(\lambda\in(0,1)\) такие, что \(t=\lambda p+(1-\lambda)q\) и
$$g(t)\ge \lambda g(p)+(1-\lambda)g(q).$$
Следовательно, для любого наклона \(u\)
$$u t+g(t)\ge \lambda\bigl(up+g(p)\bigr)+(1-\lambda)\bigl(uq+g(q)\bigr).$$
Значит, внекорпусная колонка не может одновременно быть лучше обеих соседних колонок оболочки для наклоненной функции \(u t+g(t)\). Добавление линейного члена \(u t\) - это всего лишь аффинный сдвиг-срез плоскости, а такой срез не меняет набор выборок, лежащих на нижней оболочке.
Теперь перенесем это в динамику. Функция \(M_{i-1}(t)\) кусочно постоянна: она меняется только там, где возникает новый рекордно малый уровень. Если эти рекордные минимумы достигаются на колонках оболочки, то на каждом интервале постоянства мы минимизируем
$$F_i(t)=M_{i-1}(t)+u_i t+g(t),$$
то есть константу плюс наклоненную копию \(g\). Минимум на таком интервале снова достигается на колонке оболочки. Индукция дает центральную инварианту: все префиксные минимумы, минимумы слоев и конечный оптимум можно считывать исключительно по колонкам нижней оболочки.
При \(n=2\) получаются значения
$$a_1=102022661,\quad b_1=864751430,\quad a_2=661600260,\quad b_2=328965239.$$
Соответствующая матрица имеет вид
$$\begin{pmatrix} a_1+b_1 & a_1+b_2\\ a_2+b_1 & a_2+b_2 \end{pmatrix} = \begin{pmatrix} 966774091 & 430987900\\ 1526351690 & 990565499 \end{pmatrix}.$$
Здесь есть только один параметр \(t_1\). При \(t_1=0\) путь сначала идет вниз, при \(t_1=1\) сначала вправо. Общая базовая часть равна
$$a_1+a_2+b_1+b_2=1957339590.$$
Дополнительная часть равна
$$D(2,2)=a_2+\min\bigl(b_1,\ a_1-a_2+b_2\bigr),$$
следовательно,
$$D(2,2)=661600260+\min(864751430,-230612360)=430987900.$$
Итак,
$$P(2,2)=1957339590+430987900=2388327490.$$
Это тот же контрольный результат, который используют реализации, и он наглядно показывает разложение на базовую и дополнительную части.
Реализации на C++, Python и Java сначала порождают детерминированную последовательность повторным возведением по модулю в квадрат. Из этого потока извлекаются все \(a_i\) и \(b_i\), а одновременно накапливаются \(\sum a_i\) и \(\sum b_i\). Если \(n=1\), ответ сразу равен \(a_1+b_1\).
Для \(n\ge 2\) программа сканирует точки \((t,b_{t+1})\) при \(0\le t\le n-1\) и оставляет только колонки на нижней оболочке. Геометрическое решение основывается ровно на приведенном выше неравенстве с векторным произведением. Это предвычисление не зависит от номера слоя DP, потому что каждый слой отличается лишь добавлением линейного члена \(u_i t\).
После построения оболочки реализация хранит выжившие индексы столбцов и соответствующие им значения \(b\), а затем запускает рекурсию только по этому сжатому набору состояний. Каждый слой обрабатывается слева направо с поддержкой текущего префиксного минимума предыдущего слоя, поэтому хватает двух роллирующих массивов. В конце лучший сжатый результат складывается с \((n-1)a_n\) и базовой суммой \(\sum a_i+\sum b_i\).
В версии на C++ дополнительно сохранен исходный квадратичный DP по полной сетке для проверки на малых размерах. Он тестирует явные значения для \(n=1\), \(n=2\) и \(n=10\), а также сравнивает быстрый и квадратичный методы на всех \(1\le n\le 120\). В реализациях на Python и Java оставлен только быстрый путь, но математика у них та же.
Порождение последовательности и вычисление базовых сумм требуют \(O(n)\) времени. Построение нижней оболочки - еще один линейный проход \(O(n)\). Если на оболочке осталось \(m\) столбцов, то сжатое DP работает за \(O(nm)\), потому что имеется \(n-1\) слоев и в каждом слое все \(m\) состояний просматриваются ровно один раз.
Реализации хранят полные массивы \(a_i\) и \(b_i\), а также две роллирующие строки DP, поэтому память равна \(O(n+m)\). Для сравнения, проверочный DP по полной сетке имеет сложность \(O(n^2)\) по времени и \(O(n)\) по памяти при использовании роллирующих строк. Вся сила окончательного метода в том, что он заменяет невозможную квадратную сетку при \(n=10^7\) линейным предвычислением и сжатым одномерным DP.
تُعرَّف المتتالية بالعلاقة
$$s_1=102022661,\qquad s_{k+1}\equiv s_k^2 \pmod{998388889}.$$
ومنها نأخذ
$$a_i=s_{2i-1},\qquad b_i=s_{2i},$$
فتصبح كلفة الخلية \((i,j)\) مساوية لـ
$$c_{i,j}=a_i+b_j.$$
المطلوب هو تصغير مجموع قيم الخلايا التي يمر بها مسار من \((1,1)\) إلى \((n,n)\) إذا كانت الحركات المسموحة هي يمينًا وأسفل فقط. أي برمجة ديناميكية مباشرة على الشبكة تحتاج إلى \(n^2\) حالة، وهذا غير ممكن عند الحجم الحقيقي \(n=10^7\). لذلك تستفيد التطبيقات من البنية القابلة للفصل \(a_i+b_j\)، ثم تعيد تمثيل المسار بواسطة الأعمدة التي يحدث فيها النزول، وبعد ذلك تضغط فضاء الحالات الأحادي البعد باستعمال حجة هندسية مبنية على الغلاف السفلي.
الاشتقاق يمر عبر ثلاث طبقات. أولًا نفصل الجزء من الكلفة الذي لا بد أن تدفعه كل مسار أحادي. ثانيًا نمثل المسار بمتتالية صحيحة غير متناقصة. ثالثًا نثبت أن البرمجة الديناميكية الناتجة لا تحتاج إلا إلى الأعمدة الواقعة على الغلاف السفلي للرسم المتقطع \(t\mapsto b_{t+1}\).
لنرمز بـ \(P(i,j)\) إلى أقل كلفة لمسار ينتهي عند الخلية \((i,j)\)، مع احتساب قيمة تلك الخلية نفسها. عندئذ تكون العلاقة الأساسية
$$P(1,1)=a_1+b_1,$$
$$P(i,j)=a_i+b_j+\min\bigl(P(i,j-1),P(i-1,j)\bigr).$$
أي مسار أحادي من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى يزور كل صف مرة واحدة على الأقل، ويزور كل عمود مرة واحدة على الأقل. لذلك فإن
$$A_i=\sum_{r=1}^{i} a_r,\qquad B_j=\sum_{c=1}^{j} b_c$$
يمثلان تمامًا المساهمة الأساسية التي تُدفع مرة واحدة لكل صف وكل عمود مزور. نعرّف الآن
$$D(i,j)=P(i,j)-A_i-B_j.$$
وبذلك يصبح \(D(1,1)=0\)، وتتبسط العلاقة إلى
$$D(i,j)=\min\bigl(D(i,j-1)+a_i,\ D(i-1,j)+b_j\bigr).$$
هذه الصيغة تكشف لبّ المسألة: الحركة يمينًا داخل الصف \(i\) تعني دفع \(a_i\) مرة إضافية، والحركة نزولًا داخل العمود \(j\) تعني دفع \(b_j\) مرة إضافية. لذا فإن الجواب النهائي هو
$$P(n,n)=A_n+B_n+D(n,n).$$
المسار من \((1,1)\) إلى \((n,n)\) يحتوي بالضبط على \(n-1\) حركة نزول. لتكن \(t_i\) عدد الحركات إلى اليمين المنجزة قبل حركة النزول رقم \(i\). عندئذ يجب أن يكون
$$0\le t_1\le t_2\le \cdots \le t_{n-1}\le n-1.$$
هذه المتتالية غير المتناقصة تحدد المسار كله. حركة النزول رقم \(i\) تقع في العمود \(t_i+1\)، ولذلك تضيف الكلفة \(b_{t_i+1}\). وإذا رمزنا بـ \(r_i\) إلى عدد الحركات يمينًا المنفذة في الصف \(i\)، فإن
$$r_1=t_1,\qquad r_i=t_i-t_{i-1}\quad(2\le i\le n-1),\qquad r_n=(n-1)-t_{n-1}.$$
وعليه فإن الجزء الإضافي فوق الكلفة الأساسية يساوي
$$D(n,n)=\sum_{i=1}^{n} r_i a_i+\sum_{i=1}^{n-1} b_{t_i+1}.$$
الآن نجمع الجزء الصفّي بطريقة متسلسلة:
$$\sum_{i=1}^{n} r_i a_i=t_1a_1+\sum_{i=2}^{n-1}(t_i-t_{i-1})a_i+\bigl((n-1)-t_{n-1}\bigr)a_n,$$
ومن ثم
$$\sum_{i=1}^{n} r_i a_i=(n-1)a_n+\sum_{i=1}^{n-1}(a_i-a_{i+1})t_i.$$
فتصبح المسألة مكافئة تمامًا للصيغة
$$D(n,n)=(n-1)a_n+\sum_{i=1}^{n-1}\Bigl((a_i-a_{i+1})t_i+b_{t_i+1}\Bigr).$$
وهكذا تحولت مسألة المسار على شبكة ثنائية الأبعاد إلى مسألة تحسين أحادية البعد على متتالية صحيحة غير متناقصة.
لنضع
$$u_i=a_i-a_{i+1},\qquad g(t)=b_{t+1}.$$
ولنعرّف \(F_i(t)\) بأنه أقل مساهمة ممكنة لأول \(i\) حركات نزول تحت الشرط \(t_i=t\). عندها نحصل على
$$F_i(t)=u_i t+g(t)+\min_{0\le s\le t}F_{i-1}(s).$$
والشرط الابتدائي هو \(F_0(0)=0\) و\(F_0(t)=+\infty\) عندما \(t>0\). وبعد إنهاء جميع حركات النزول نحصل على
$$D(n,n)=(n-1)a_n+\min_{0\le t\le n-1}F_{n-1}(t).$$
هذه العلاقة تُظهر أن الطبقة السابقة لا يلزم منها إلا دالة الحد الأدنى على البادئات
$$M_{i-1}(t)=\min_{0\le s\le t}F_{i-1}(s).$$
ولو حُسبت هذه القيم لكل \(t\) على حدة لبقي التعقيد تربيعيًا. الفكرة الحاسمة هي أن أغلب الأعمدة يمكن حذفها نهائيًا.
لننظر إلى النقاط المتقطعة
$$\bigl(t,g(t)\bigr)=\bigl(t,b_{t+1}\bigr),\qquad 0\le t\le n-1.$$
ولتكن رؤوس غلافها السفلي
$$0=h_0\lt h_1\lt \cdots \lt h_{m-1}\le n-1.$$
تُبنى هذه الرؤوس بمسح أحادي الاتجاه. فإذا كانت ثلاث نقاط متتالية \(t_1\lt t_2\lt t_3\) تحقق
$$\bigl(t_2-t_1\bigr)\bigl(g(t_3)-g(t_1)\bigr)-\bigl(g(t_2)-g(t_1)\bigr)\bigl(t_3-t_1\bigr)\le 0,$$
فإن النقطة الوسطى \(t_2\) تُزال لأنها تقع على القطعة الواصلة بين الأخريين أو فوقها، وبالتالي لا يمكن أن تكون نقطة انكسار حقيقية على الغلاف السفلي.
وهذا هو بالضبط ما يحتاجه الحل السريع. فإذا كان عمود ما \(t\) خارج الغلاف السفلي، فهناك رأسان \(p\lt t\lt q\) على الغلاف وعدد \(\lambda\in(0,1)\) بحيث \(t=\lambda p+(1-\lambda)q\) و
$$g(t)\ge \lambda g(p)+(1-\lambda)g(q).$$
وعليه، لأي ميل \(u\) نحصل على
$$u t+g(t)\ge \lambda\bigl(up+g(p)\bigr)+(1-\lambda)\bigl(uq+g(q)\bigr).$$
أي إن العمود غير الواقع على الغلاف لا يستطيع أن يتفوق في الكلفة المائلة \(u t+g(t)\) على رأسي الغلاف المجاورين له معًا. وإضافة الحد الخطي \(u t\) ليست إلا قصًا أفينيًا لمجموعة النقاط، والقص الأفيني لا يغير أي الأعمدة المأخوذة بالعينة تبقى على الغلاف السفلي.
وعند إدخال هذه الحقيقة في البرمجة الديناميكية تظهر اللازمية الأساسية. فالدالة \(M_{i-1}(t)\) ثابتة على فترات، ولا تتغير إلا عند ظهور حد أدنى قياسي جديد. وإذا كانت هذه القيَم القياسية تتحقق على أعمدة الغلاف، فإننا على كل فترة ثابتة نكون بصدد تصغير
$$F_i(t)=M_{i-1}(t)+u_i t+g(t),$$
أي ثابتًا مضافًا إلى نسخة مائلة من \(g\). ومن ثم يكون أصغر عنصر في تلك الفترة واقعًا مرة أخرى على عمود من أعمدة الغلاف. وبالاستقراء نحصل على النتيجة: كل حدود البادئات الدنيا، وكل حدود الطبقات الدنيا، والجواب الأمثل النهائي، يمكن قراءتها من أعمدة الغلاف السفلي وحدها.
عندما \(n=2\) تكون القيم المتولدة
$$a_1=102022661,\quad b_1=864751430,\quad a_2=661600260,\quad b_2=328965239.$$
فتصبح الشبكة
$$\begin{pmatrix} a_1+b_1 & a_1+b_2\\ a_2+b_1 & a_2+b_2 \end{pmatrix} = \begin{pmatrix} 966774091 & 430987900\\ 1526351690 & 990565499 \end{pmatrix}.$$
هنا يوجد متغير واحد فقط هو \(t_1\). إذا كان \(t_1=0\) فالمسار يهبط أولًا، وإذا كان \(t_1=1\) فالمسار يتحرك يمينًا أولًا. الجزء الأساسي المشترك بين جميع المسارات هو
$$a_1+a_2+b_1+b_2=1957339590.$$
أما الجزء الإضافي فهو
$$D(2,2)=a_2+\min\bigl(b_1,\ a_1-a_2+b_2\bigr),$$
ومن ثم
$$D(2,2)=661600260+\min(864751430,-230612360)=430987900.$$
إذًا
$$P(2,2)=1957339590+430987900=2388327490.$$
وهذه هي نفس قيمة التحقق الصغيرة التي تستعملها التطبيقات، كما أنها توضح بجلاء تفكيك الكلفة إلى جزء أساسي وجزء إضافي قابل للتحسين.
تبدأ تطبيقات C++ وPython وJava بتوليد المتتالية الحتمية عبر التربيع المتكرر بترديد ثابت. ومن هذا التيار تستخرج جميع قيم \(a_i\) و\(b_i\)، مع تجميع \(\sum a_i\) و\(\sum b_i\) في الوقت نفسه. وإذا كان \(n=1\) فإن الجواب مباشرة هو \(a_1+b_1\).
عندما \(n\ge 2\)، يمسح التنفيذ جميع النقاط \((t,b_{t+1})\) حيث \(0\le t\le n-1\)، ولا يحتفظ إلا بالأعمدة الواقعة على الغلاف السفلي. القرار الهندسي يعتمد على متباينة حاصل الضرب الاتجاهي المكتوبة أعلاه. وهذه المعالجة المسبقة لا تعتمد على طبقة DP نفسها، لأن الاختلاف بين الطبقات يقتصر على إضافة الحد الخطي \(u_i t\).
بعد معرفة الغلاف، تحفظ الشيفرة فهارس الأعمدة الباقية وقيم \(b\) الموافقة لها، ثم تنفذ العلاقة التراجعية فقط على هذه القائمة المضغوطة. كل طبقة تُعالَج من اليسار إلى اليمين مع الاحتفاظ بالحد الأدنى الجاري من الطبقة السابقة، ولذلك تكفي مصفوفتان دائريتان. وفي النهاية يُدمَج أفضل وضع مضغوط مع \((n-1)a_n\) ومع المجموع الأساسي \(\sum a_i+\sum b_i\).
تتضمن نسخة C++ أيضًا البرمجة الديناميكية التربيعية الأصلية على الشبكة كاملة للتحقق على الأحجام الصغيرة. فهي تفحص القيم الصريحة عند \(n=1\) و\(n=2\) و\(n=10\)، وتقارن بين الطريقة السريعة والطريقة التربيعية لكل \(1\le n\le 120\). أما نسختا Python وJava فتكتفيان بالحل السريع، لكنهما تعتمدان الاشتقاق الرياضي نفسه.
توليد المتتالية وحساب المجاميع الأساسية يكلف \(O(n)\) زمنًا. وبناء الغلاف السفلي يحتاج إلى مرور خطي آخر \(O(n)\). وإذا بقي على الغلاف \(m\) عمودًا، فإن البرمجة الديناميكية المضغوطة تعمل في \(O(nm)\) زمنًا، لأن هناك \(n-1\) طبقات، وكل طبقة تمر مرة واحدة فقط على هذه الحالات \(m\).
التطبيقات تخزن المصفوفتين الكاملتين \(a_i\) و\(b_i\) مع صفين دوّارين للـ DP، ولذلك يكون استهلاك الذاكرة \(O(n+m)\). وللمقارنة، فإن DP التحققي على الشبكة الكاملة يحتاج إلى \(O(n^2)\) زمنًا و\(O(n)\) ذاكرة عند استعمال الصفوف الدوّارة. فجوهر الطريقة النهائية هو استبدال البنية التربيعية المستحيلة عند \(n=10^7\) بمرحلة تحضير خطية ثم DP أحادي البعد مضغوط.