The cards are labeled \(1,2,\dots,n\). Their initial left-to-right order is generated by
$$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n.$$
For the target case \(n=976\), this construction is treated as a permutation of the labels. The task is to combine all cards into one valid ordered stack with minimum total movement cost. Once the starting order is fixed, the optimization depends only on where each label appears, so the problem becomes an interval dynamic program on consecutive labels.
Let \(P(k)\) be the position of label \(k\) in the generated order. For every interval of labels \(l \le r\), define \(C(l,r)\) as the minimum cost needed to consolidate exactly the cards with labels \(l,l+1,\dots,r\) into one valid stack. The desired answer is \(C(1,n)\).
Starting from \(a_0=1\), each new card label is obtained by multiplying by \(3\) modulo \(n+1\). The implementations record, for every label \(k\), the unique position where \(k\) occurs. This produces the position map
$$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}.$$
No closed-form shortcut is required later; every cost is expressed directly in terms of these recorded positions.
Any valid final stack preserves the numerical order of the labels, so whenever we look at labels \(l,l+1,\dots,r\), they behave as one consecutive block in the final construction. That means a complete strategy can be represented by an ordered binary merge tree whose leaves are \(1,2,\dots,n\) from left to right.
Each internal node of that tree corresponds to some interval \([l,r]\), and its last split occurs at some \(m\) with
$$l \le m \lt r,$$
so the interval is formed by first solving \([l,m]\) and \([m+1,r]\), then merging those two completed sub-stacks.
For a single label there is nothing to merge, so
$$C(l,l)=0.$$
For longer intervals, \(C(l,r)\) stores the best possible cost over every legal merge order that produces one stack from the labels \(l,l+1,\dots,r\).
Assume that the last merge for \([l,r]\) splits at \(m\). Then the left subproblem contributes \(C(l,m)\), the right subproblem contributes \(C(m+1,r)\), and the final merge itself contributes the distance between the exposed card of the left block and the exposed card of the right block.
In this interval model, those exposed labels are \(m\) and \(r\), so the extra cost is
$$|P(m)-P(r)|.$$
Therefore
$$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$$
This is the full optimization rule used by the C++, Python, and Java implementations.
Once every interval cost is known, the whole problem is solved by
$$A(n)=C(1,n).$$
Because each state depends only on shorter intervals, the table can be filled in increasing order of interval length.
For \(n=6\), we work modulo \(7\) and obtain
$$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1.$$
So the position map is
$$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3.$$
Some short intervals are immediate:
$$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$$
For a length-three interval,
$$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$$
Likewise,
$$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$$
Continuing bottom-up gives
$$C(1,6)=\min(9,10,10,9,8)=8.$$
Hence the optimal total cost for the six-card test case is \(8\), matching the small checkpoint used by the implementations.
The C++, Python, and Java implementations first generate the permutation by repeated multiplication by \(3\) modulo \(n+1\). As they do so, they store the position of every label. The C++ and Java versions also verify that the sequence really is a permutation with no duplicate or missing label.
Next, the implementation allocates a two-dimensional table for interval costs. The diagonal is initialized to zero because intervals of length \(1\) need no merge.
The main dynamic program processes interval lengths \(2,3,\dots,n\). For each interval \([l,r]\), it tries every split point \(m\), evaluates
$$C(l,m)+C(m+1,r)+|P(m)-P(r)|,$$
and keeps the minimum. After all lengths are processed, the entry for \([1,n]\) is printed as the answer.
Building the permutation and the position map takes \(O(n)\) time and \(O(n)\) memory. The dynamic program considers every interval \([l,r]\) and, for each one, every split point \(m\). This gives
$$O(n^3)$$
time in total and
$$O(n^2)$$
memory for the interval table.
Die Karten tragen die Labels \(1,2,\dots,n\). Ihre anfängliche Reihenfolge von links nach rechts wird durch
$$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n$$
erzeugt. Für den Zielwert \(n=976\) wird diese Folge als Permutation der Labels behandelt. Gesucht ist eine gültige Endstapelung mit minimalen Gesamtkosten. Sobald die Startreihenfolge feststeht, hängt die Optimierung nur noch von den Positionen der Labels ab; damit wird das Problem zu einer Intervall-DP über aufeinanderfolgende Labels.
Sei \(P(k)\) die Position des Labels \(k\) in der erzeugten Reihenfolge. Für jedes Labelintervall \(l \le r\) bezeichne \(C(l,r)\) die minimalen Kosten, um genau die Karten mit Labels \(l,l+1,\dots,r\) zu einem gültigen Stapel zusammenzuführen. Gesucht ist also \(C(1,n)\).
Ausgehend von \(a_0=1\) entsteht jede neue Karte durch Multiplikation mit \(3\) modulo \(n+1\). Die Implementierungen speichern für jedes Label \(k\) die eindeutige Position seines Auftretens. So entsteht die Abbildung
$$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}.$$
Für die spätere Optimierung ist kein weiterer zahlentheoretischer Trick nötig; alle Kosten werden direkt über diese Positionen ausgedrückt.
Ein gültiger Endstapel respektiert die numerische Reihenfolge der Labels. Deshalb verhalten sich die Labels \(l,l+1,\dots,r\) in jeder vollständigen Lösung wie ein zusammenhängender Block. Jede Gesamtstrategie kann daher als geordneter binärer Merge-Baum mit Blättern \(1,2,\dots,n\) beschrieben werden.
Jeder innere Knoten dieses Baums entspricht einem Intervall \([l,r]\) und besitzt einen letzten Schnittpunkt \(m\) mit
$$l \le m \lt r.$$
Man löst also zuerst \([l,m]\) und \([m+1,r]\) und fügt anschließend diese beiden Teilstapel zusammen.
Für ein einzelnes Label muss nichts zusammengeführt werden, also gilt
$$C(l,l)=0.$$
Für längere Intervalle speichert \(C(l,r)\) die besten erreichbaren Kosten unter allen zulässigen Reihenfolgen von Zusammenführungen für die Labels \(l,l+1,\dots,r\).
Angenommen, der letzte Merge des Intervalls \([l,r]\) trennt bei \(m\). Dann liefert das linke Teilproblem \(C(l,m)\), das rechte Teilproblem \(C(m+1,r)\), und der letzte Merge selbst kostet den Abstand zwischen der exponierten Karte des linken Blocks und der exponierten Karte des rechten Blocks.
In diesem Intervallmodell sind diese exponierten Labels gerade \(m\) und \(r\). Der Zusatzterm ist also
$$|P(m)-P(r)|.$$
Daher erhält man die Rekurrenz
$$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$$
Genau diese Optimierungsregel verwenden die C++-, Python- und Java-Implementierungen.
Sind alle Intervallkosten bekannt, lautet die Gesamtlösung
$$A(n)=C(1,n).$$
Da jeder Zustand nur von kürzeren Intervallen abhängt, kann die Tabelle in aufsteigender Intervalllänge berechnet werden.
Für \(n=6\) arbeiten wir modulo \(7\) und erhalten
$$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1.$$
Daraus folgt die Positionsabbildung
$$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3.$$
Kurze Intervalle sind sofort klar:
$$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$$
Für ein Intervall der Länge \(3\) gilt
$$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$$
Ebenso
$$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$$
Führt man die DP weiter fort, ergibt sich
$$C(1,6)=\min(9,10,10,9,8)=8.$$
Damit ist die optimale Gesamtkosten für den Testfall mit sechs Karten gleich \(8\), genau wie im kleinen Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst die Permutation durch wiederholte Multiplikation mit \(3\) modulo \(n+1\). Dabei wird für jedes Label seine Position gespeichert. Die C++- und Java-Versionen prüfen zusätzlich, dass tatsächlich eine Permutation ohne doppelte oder fehlende Labels entsteht.
Anschließend reserviert die Implementierung eine zweidimensionale Tabelle für Intervallkosten. Die Diagonale wird mit \(0\) initialisiert, weil Intervalle der Länge \(1\) keinen Merge benötigen.
Dann verarbeitet das dynamische Programm die Intervalllängen \(2,3,\dots,n\). Für jedes Intervall \([l,r]\) werden alle Schnittpunkte \(m\) getestet, der Ausdruck
$$C(l,m)+C(m+1,r)+|P(m)-P(r)|$$
ausgewertet und das Minimum gespeichert. Nach Abschluss aller Längen liefert der Eintrag für \([1,n]\) die gesuchte Antwort.
Das Erzeugen der Permutation und der Positionsabbildung benötigt \(O(n)\) Zeit und \(O(n)\) Speicher. Das dynamische Programm betrachtet jedes Intervall \([l,r]\) und darin jeden Schnittpunkt \(m\). Insgesamt ergibt das
$$O(n^3)$$
Zeit und
$$O(n^2)$$
Speicher für die Intervalltabelle.
Kartlar \(1,2,\dots,n\) etiketlerini taşır. Soldan sağa başlangıç dizilimi
$$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n$$
ile üretilir. Hedef örnekte \(n=976\) için bu dizi etiketlerin bir permütasyonu olarak ele alınır. Amaç, bütün kartları geçerli bir sıralı destede en düşük toplam hareket maliyetiyle birleştirmektir. Başlangıç sırası belli olduktan sonra optimizasyon yalnızca etiketlerin hangi konumlarda bulunduğuna bağlıdır; böylece problem ardışık etiket aralıkları üzerinde bir interval DP haline gelir.
Üretilen sırada etiket \(k\)'nin bulunduğu konumu \(P(k)\) ile gösterelim. Her \(l \le r\) için \(C(l,r)\), tam olarak \(l,l+1,\dots,r\) etiketli kartları tek bir geçerli destede toplamanın minimum maliyeti olsun. O halde aranan değer \(C(1,n)\)'dir.
\(a_0=1\) ile başlayıp her adımda \(3\) ile çarpıp \(n+1\)'e göre mod alırız. Uygulamalar, her etiket \(k\) için onun geçtiği tek konumu kaydeder. Böylece
$$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$$
eşlemesi elde edilir. Sonraki maliyet hesabı için ayrı bir sayılar kuramı kısayoluna ihtiyaç yoktur; bütün maliyetler doğrudan bu konumlar üzerinden yazılır.
Geçerli bir son destede etiketlerin sayısal sırası korunur. Bu yüzden \(l,l+1,\dots,r\) etiketleri tam çözüm içinde doğal olarak tek bir ardışık blok gibi davranır. Dolayısıyla her tam strateji, yaprakları soldan sağa \(1,2,\dots,n\) olan sıralı bir ikili birleştirme ağacı olarak görülebilir.
Bu ağacın her iç düğümü \([l,r]\) aralığına karşılık gelir ve son bölünme noktası
$$l \le m \lt r$$
şeklindedir. Yani önce \([l,m]\) ve \([m+1,r]\) çözülür, sonra bu iki alt deste birleştirilir.
Tek etiketli bir aralıkta yapılacak birleştirme yoktur, dolayısıyla
$$C(l,l)=0.$$
Daha uzun aralıklarda \(C(l,r)\), \(l,l+1,\dots,r\) etiketlerini tek desteye dönüştüren bütün yasal birleştirme sıraları arasındaki en düşük maliyeti tutar.
\([l,r]\) aralığının son birleşmesinin \(m\) noktasında ayrıldığını varsayalım. Sol alt problem \(C(l,m)\), sağ alt problem \(C(m+1,r)\) katkısını verir. Son birleşmenin ek maliyeti ise sol bloğun dışarıya açık kartı ile sağ bloğun dışarıya açık kartı arasındaki uzaklıktır.
Bu interval modelinde bu iki açık etiket \(m\) ve \(r\) olur. Dolayısıyla ek terim
$$|P(m)-P(r)|$$
şeklindedir. Sonuç olarak
$$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$$
C++, Python ve Java uygulamalarının optimize ettiği tam bağıntı budur.
Bütün aralık maliyetleri hesaplandığında toplam çözüm
$$A(n)=C(1,n)$$
olur. Her durum yalnızca daha kısa aralıklara bağlı olduğu için tablo aralık uzunluğu artan sırayla doldurulabilir.
\(n=6\) için \(7\)'ye göre mod alırız ve
$$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1$$
dizisini elde ederiz. Buna karşılık gelen konumlar
$$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3$$
şeklindedir. Kısa aralıklarda
$$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$$
Uzunluğu \(3\) olan bir aralık için
$$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$$
Aynı şekilde
$$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$$
DP alt aralıklardan yukarı doğru tamamlandığında
$$C(1,6)=\min(9,10,10,9,8)=8$$
bulunur. Böylece altı kartlık test için en iyi toplam maliyet \(8\)'dir; bu değer uygulamalardaki küçük kontrol sonucu ile aynıdır.
C++, Python ve Java uygulamaları önce \(3\) ile ardışık çarpma yaparak ve her adımda \(n+1\)'e göre mod alarak permütasyonu üretir. Aynı anda her etiketin konumu saklanır. C++ ve Java sürümleri ayrıca dizinin gerçekten eksiksiz ve tekrarsız bir permütasyon olduğunu da denetler.
Daha sonra interval maliyetlerini tutan iki boyutlu bir tablo ayrılır. Uzunluğu \(1\) olan aralıkların birleşmeye ihtiyacı olmadığı için köşegen değerleri \(0\) olarak bırakılır.
Ana DP, aralık uzunluklarını \(2,3,\dots,n\) sırasıyla gezer. Her \([l,r]\) aralığı için tüm bölme noktaları \(m\) denenir,
$$C(l,m)+C(m+1,r)+|P(m)-P(r)|$$
hesaplanır ve minimum değer saklanır. Bütün uzunluklar bittikten sonra \([1,n]\) hücresi cevap olarak yazdırılır.
Permütasyonu ve konum eşlemesini oluşturmak \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. Dinamik program her \([l,r]\) aralığını ve her aralık için bütün bölme noktalarını inceler. Toplam çalışma süresi
$$O(n^3)$$
ve interval tablosu için bellek kullanımı
$$O(n^2)$$
olur.
Las cartas llevan las etiquetas \(1,2,\dots,n\). El orden inicial de izquierda a derecha se genera mediante
$$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n.$$
Para el caso objetivo \(n=976\), esta construcción se interpreta como una permutación de las etiquetas. La meta es reunir todas las cartas en una única pila válida con costo total mínimo. Una vez fijado el orden inicial, la optimización depende solo de la posición de cada etiqueta, así que el problema se convierte en una programación dinámica por intervalos sobre etiquetas consecutivas.
Sea \(P(k)\) la posición de la etiqueta \(k\) en el orden generado. Para cada intervalo \(l \le r\), definimos \(C(l,r)\) como el costo mínimo para consolidar exactamente las cartas con etiquetas \(l,l+1,\dots,r\) en una sola pila válida. Lo que se busca es \(C(1,n)\).
Partiendo de \(a_0=1\), cada nueva etiqueta se obtiene multiplicando por \(3\) módulo \(n+1\). Las implementaciones guardan, para cada etiqueta \(k\), la posición única en la que aparece. Así se obtiene la aplicación
$$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}.$$
Después no hace falta ningún atajo teórico adicional; todos los costos se expresan directamente con estas posiciones.
Una pila final válida respeta el orden numérico de las etiquetas. Por eso, las etiquetas \(l,l+1,\dots,r\) se comportan como un bloque consecutivo dentro de cualquier construcción completa. En consecuencia, una estrategia global puede verse como un árbol binario ordenado de fusiones cuyas hojas son \(1,2,\dots,n\) de izquierda a derecha.
Cada nodo interno representa un intervalo \([l,r]\) y su última partición ocurre en algún \(m\) con
$$l \le m \lt r.$$
Es decir, primero se resuelven \([l,m]\) y \([m+1,r]\), y solo al final se fusionan esas dos subpilas.
Si el intervalo contiene una sola etiqueta, no hay ninguna fusión que hacer, así que
$$C(l,l)=0.$$
Para intervalos más largos, \(C(l,r)\) almacena el mejor costo posible entre todas las secuencias legales de fusiones que producen una sola pila con las etiquetas \(l,l+1,\dots,r\).
Supongamos que la última fusión del intervalo \([l,r]\) corta en \(m\). Entonces el subproblema izquierdo aporta \(C(l,m)\), el derecho aporta \(C(m+1,r)\), y la fusión final añade la distancia entre la carta expuesta del bloque izquierdo y la carta expuesta del bloque derecho.
En este modelo por intervalos, esas etiquetas expuestas son \(m\) y \(r\), por lo que el costo adicional es
$$|P(m)-P(r)|.$$
Por tanto, la transición queda
$$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$$
Esta es exactamente la regla que optimizan las implementaciones en C++, Python y Java.
Una vez conocidos todos los costos por intervalos, la solución completa es
$$A(n)=C(1,n).$$
Como cada estado depende solo de intervalos más cortos, la tabla se puede rellenar en orden creciente de longitud.
Para \(n=6\), trabajamos módulo \(7\) y obtenemos
$$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1.$$
El mapa de posiciones es
$$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3.$$
Algunos intervalos cortos son inmediatos:
$$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$$
Para un intervalo de longitud \(3\),
$$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$$
De forma análoga,
$$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$$
Continuando la DP de abajo hacia arriba se obtiene
$$C(1,6)=\min(9,10,10,9,8)=8.$$
Por lo tanto, el costo óptimo total para el caso de seis cartas es \(8\), en concordancia con la comprobación pequeña usada por las implementaciones.
Las implementaciones en C++, Python y Java generan primero la permutación mediante multiplicaciones sucesivas por \(3\) módulo \(n+1\). Mientras lo hacen, guardan la posición de cada etiqueta. Las versiones en C++ y Java también verifican que la secuencia obtenida sea realmente una permutación, sin etiquetas repetidas ni ausentes.
Después, la implementación reserva una tabla bidimensional para los costos de intervalos. La diagonal se deja en cero porque los intervalos de longitud \(1\) no requieren ninguna fusión.
El núcleo de la programación dinámica recorre las longitudes \(2,3,\dots,n\). Para cada intervalo \([l,r]\), prueba todos los puntos de corte \(m\), evalúa
$$C(l,m)+C(m+1,r)+|P(m)-P(r)|,$$
y conserva el mínimo. Cuando todas las longitudes han sido procesadas, la entrada correspondiente a \([1,n]\) se imprime como respuesta final.
Construir la permutación y el mapa de posiciones cuesta \(O(n)\) tiempo y \(O(n)\) memoria. La programación dinámica examina cada intervalo \([l,r]\) y, dentro de él, cada punto de corte \(m\). En total, esto produce
$$O(n^3)$$
tiempo y
$$O(n^2)$$
memoria para la tabla de intervalos.
卡牌的标签为 \(1,2,\dots,n\)。初始从左到右的排列由
$$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n$$
生成。对目标实例 \(n=976\) 而言，这个序列被视为标签 \(1\) 到 \(n\) 的一个排列。问题要求以最小总代价把所有卡牌合并成一个满足顺序约束的最终牌堆。初始顺序一旦确定，后续优化只与每个标签出现的位置有关，因此整个问题可以改写成一个关于连续标签区间的区间动态规划。
记 \(P(k)\) 为标签 \(k\) 在生成序列中的位置。对任意区间 \(l \le r\)，定义 \(C(l,r)\) 为把恰好标签 \(l,l+1,\dots,r\) 这些牌合并成一个合法牌堆所需的最小代价。最终要求的就是 \(C(1,n)\)。
从 \(a_0=1\) 开始，每一步都乘以 \(3\)，再对 \(n+1\) 取模，就得到下一张牌的标签。实现会在生成过程中记录每个标签 \(k\) 出现的唯一位置，从而得到映射
$$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}.$$
后面的代价公式完全由这个位置映射给出，不需要再额外引入别的数论技巧。
合法的最终牌堆必须保持标签的数值顺序，因此标签 \(l,l+1,\dots,r\) 在完整解中会表现为一个连续块。于是，任意一种完整策略都可以看成一棵有序二叉合并树，它的叶子从左到右依次是 \(1,2,\dots,n\)。
树中的每个内部节点对应一个区间 \([l,r]\)，并且它的最后一次划分一定发生在某个
$$l \le m \lt r$$
处。也就是说，先分别完成 \([l,m]\) 和 \([m+1,r]\) 的内部合并，再把这两个已经完成的子牌堆做最后一次合并。
如果区间中只有一张牌，那么不需要做任何合并，所以
$$C(l,l)=0.$$
当区间更长时，\(C(l,r)\) 表示在所有合法合并顺序中，把标签 \(l,l+1,\dots,r\) 合并成一个牌堆的最小总代价。
设区间 \([l,r]\) 的最后一次合并在 \(m\) 处分开。这样左半部分贡献 \(C(l,m)\)，右半部分贡献 \(C(m+1,r)\)。最后一次合并本身还需要支付一个额外代价，它等于左块暴露出来的标签与右块暴露出来的标签在初始排列中的位置差。
在这个区间模型里，这两个暴露标签正好是 \(m\) 和 \(r\)，因此附加代价为
$$|P(m)-P(r)|.$$
于是得到递推式
$$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$$
这正是 C++、Python 和 Java 实现所计算的核心公式。
只要所有区间代价都已经求出，整个问题的答案就是
$$A(n)=C(1,n).$$
由于每个状态只依赖更短的区间，所以可以按区间长度从小到大填表。
当 \(n=6\) 时，模数为 \(7\)，生成序列是
$$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1.$$
因此位置映射为
$$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3.$$
长度为 \(2\) 的区间可以直接写出：
$$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$$
对长度为 \(3\) 的区间，
$$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$$
同理，
$$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$$
继续按长度递增完成整张表，最终得到
$$C(1,6)=\min(9,10,10,9,8)=8.$$
所以六张牌的小例子最优总代价是 \(8\)，这与实现中使用的小型校验值一致。
C++、Python 和 Java 实现首先通过不断乘以 \(3\) 并对 \(n+1\) 取模来生成排列，同时记录每个标签出现的位置。C++ 和 Java 版本还会额外检查生成结果是否真的是一个没有重复、也没有缺失标签的排列。
接着，实现分配一个二维表来存放区间代价。主对角线全部为 \(0\)，因为长度为 \(1\) 的区间不需要任何合并。
随后按照区间长度 \(2,3,\dots,n\) 进行动态规划。对每个区间 \([l,r]\)，程序枚举所有切分点 \(m\)，计算
$$C(l,m)+C(m+1,r)+|P(m)-P(r)|,$$
并保留其中最小的值。等所有长度都处理完以后，整题答案就是 \([1,n]\) 对应的表项。
构造排列和位置映射需要 \(O(n)\) 时间与 \(O(n)\) 额外空间。区间动态规划要枚举所有区间 \([l,r]\)，并对每个区间枚举所有分割点 \(m\)。因此总时间复杂度为
$$O(n^3)$$
而保存区间表需要
$$O(n^2)$$
空间。
Карты имеют метки \(1,2,\dots,n\). Их начальный порядок слева направо задается формулой
$$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n.$$
Для целевого случая \(n=976\) эта последовательность рассматривается как перестановка меток. Нужно собрать все карты в одну корректную упорядоченную стопку с минимальной суммарной стоимостью перемещений. После того как стартовый порядок построен, оптимизация зависит только от позиций меток, поэтому задача сводится к интервальному динамическому программированию по последовательным меткам.
Обозначим через \(P(k)\) позицию метки \(k\) в построенном порядке. Для каждого интервала \(l \le r\) определим \(C(l,r)\) как минимальную стоимость, необходимую для объединения ровно карт с метками \(l,l+1,\dots,r\) в одну корректную стопку. Тогда искомый ответ равен \(C(1,n)\).
Начиная с \(a_0=1\), каждая следующая метка получается умножением на \(3\) по модулю \(n+1\). Реализации запоминают для каждой метки \(k\) единственную позицию, на которой она встретилась. Так получается отображение
$$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}.$$
Дальше никакой дополнительный теоретический трюк не нужен: все стоимости выражаются напрямую через эти позиции.
Корректная конечная стопка сохраняет числовой порядок меток. Поэтому метки \(l,l+1,\dots,r\) в любой полной стратегии естественно образуют единый непрерывный блок. Значит, любую полную стратегию можно представить в виде упорядоченного бинарного дерева слияний, у которого листья слева направо равны \(1,2,\dots,n\).
Каждая внутренняя вершина такого дерева соответствует интервалу \([l,r]\) и имеет последнюю точку разбиения \(m\), где
$$l \le m \lt r.$$
То есть сначала полностью собираются интервалы \([l,m]\) и \([m+1,r]\), а затем эти две готовые подстопки объединяются последним действием.
Если в интервале одна метка, объединять нечего, поэтому
$$C(l,l)=0.$$
Для более длинных интервалов \(C(l,r)\) хранит наилучшую стоимость среди всех допустимых порядков слияния, которые превращают метки \(l,l+1,\dots,r\) в одну стопку.
Предположим, что последнее слияние для \([l,r]\) происходит после разреза в точке \(m\). Тогда левая часть дает вклад \(C(l,m)\), правая часть дает вклад \(C(m+1,r)\), а само последнее слияние добавляет расстояние между открытой картой левого блока и открытой картой правого блока.
В этой интервальной модели этими открытыми метками являются \(m\) и \(r\), значит дополнительная стоимость равна
$$|P(m)-P(r)|.$$
Следовательно,
$$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$$
Именно это соотношение оптимизируют реализации на C++, Python и Java.
Когда стоимости всех интервалов уже найдены, полный ответ равен
$$A(n)=C(1,n).$$
Поскольку каждое состояние зависит только от более коротких интервалов, таблицу удобно заполнять в порядке возрастания длины интервала.
При \(n=6\) работаем по модулю \(7\) и получаем последовательность
$$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1.$$
Отсюда позиции равны
$$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3.$$
Для коротких интервалов сразу имеем
$$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$$
Для интервала длины \(3\)
$$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$$
Аналогично
$$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$$
Продолжая заполнять таблицу снизу вверх, получаем
$$C(1,6)=\min(9,10,10,9,8)=8.$$
Следовательно, оптимальная суммарная стоимость для малого теста из шести карт равна \(8\), что совпадает с проверочным значением в реализациях.
Реализации на C++, Python и Java сначала строят перестановку последовательными умножениями на \(3\) по модулю \(n+1\). Одновременно сохраняется позиция каждой метки. Версии на C++ и Java дополнительно проверяют, что действительно получилась перестановка без пропусков и повторов.
После этого выделяется двумерная таблица для интервальных стоимостей. Диагональ заполняется нулями, потому что интервалы длины \(1\) не требуют слияния.
Основной цикл динамики идет по длинам \(2,3,\dots,n\). Для каждого интервала \([l,r]\) перебираются все точки разреза \(m\), вычисляется
$$C(l,m)+C(m+1,r)+|P(m)-P(r)|,$$
и сохраняется минимальное значение. После обработки всех длин ответом становится ячейка для интервала \([1,n]\).
Построение перестановки и таблицы позиций требует \(O(n)\) времени и \(O(n)\) памяти. Интервальная динамика перебирает все интервалы \([l,r]\) и все точки разреза \(m\) внутри каждого интервала. Итоговая сложность по времени равна
$$O(n^3),$$
а по памяти требуется
$$O(n^2)$$
для хранения таблицы интервалов.
البطاقات تحمل التسميات \(1,2,\dots,n\). والترتيب الابتدائي من اليسار إلى اليمين يُنشأ بواسطة
$$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n.$$
في الحالة المطلوبة \(n=976\) يُتعامل مع هذا التسلسل على أنه تبديل كامل للتسميات. المطلوب هو جمع جميع البطاقات في رزمة مرتبة واحدة بأقل كلفة حركة ممكنة. وبعد تثبيت الترتيب الابتدائي، لا يعود التحسين يعتمد إلا على مواضع التسميات، ولذلك تتحول المسألة إلى برمجة ديناميكية على فواصل من التسميات المتتالية.
لنرمز بـ \(P(k)\) إلى موضع التسمية \(k\) في الترتيب المتولد. ولكل فترة \(l \le r\)، نعرّف \(C(l,r)\) بأنها أقل كلفة لازمة لدمج البطاقات ذات التسميات \(l,l+1,\dots,r\) فقط في رزمة صحيحة واحدة. إذن الجواب النهائي هو \(C(1,n)\).
نبدأ من \(a_0=1\)، ثم نحصل على كل تسمية جديدة بضرب السابقة في \(3\) وأخذ الباقي modulo \(n+1\). تقوم التطبيقات بتسجيل الموضع الوحيد الذي تظهر فيه كل تسمية \(k\)، فنحصل على التطبيق
$$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}.$$
بعد ذلك لا نحتاج إلى حيلة عددية إضافية، لأن كل صيغة للكلفة تُكتب مباشرة بدلالة هذه المواضع.
الرزمة النهائية الصحيحة يجب أن تحافظ على الترتيب العددي للتسميات. لذلك فإن التسميات \(l,l+1,\dots,r\) تتصرف في أي حل كامل على أنها كتلة متجاورة واحدة. وبناء على ذلك يمكن تمثيل أي استراتيجية كاملة بشجرة دمج ثنائية مرتبة تكون أوراقها من اليسار إلى اليمين هي \(1,2,\dots,n\).
كل عقدة داخلية في هذه الشجرة تمثل الفترة \([l,r]\)، وآخر انقسام فيها يقع عند قيمة \(m\) تحقق
$$l \le m \lt r.$$
أي إننا نحل أولا الفترتين \([l,m]\) و\([m+1,r]\)، ثم ندمج الرزمتين الجزئيتين الناتجتين في الخطوة الأخيرة.
إذا احتوت الفترة على تسمية واحدة فقط فلا توجد عملية دمج، ولهذا
$$C(l,l)=0.$$
أما عندما تكون الفترة أطول، فإن \(C(l,r)\) تخزن أقل كلفة ممكنة بين جميع ترتيبات الدمج القانونية التي تحول التسميات \(l,l+1,\dots,r\) إلى رزمة واحدة.
افترض أن آخر دمج للفترة \([l,r]\) ينقسم عند \(m\). عندئذ تسهم الجهة اليسرى بالمقدار \(C(l,m)\)، وتسهم الجهة اليمنى بالمقدار \(C(m+1,r)\)، ثم تضيف عملية الدمج الأخيرة نفسها كلفة مساوية للمسافة بين البطاقة المكشوفة في الكتلة اليسرى والبطاقة المكشوفة في الكتلة اليمنى.
في هذا النموذج الفاصلي تكون هاتان التسميتان هما \(m\) و\(r\)، ولذلك تكون الكلفة الإضافية
$$|P(m)-P(r)|.$$
ومن ثم نحصل على العلاقة
$$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$$
وهذه هي بالضبط العلاقة التي تطبقها نسخ C++ وPython وJava.
بعد معرفة كلفة كل فترة، يصبح حل المسألة كلها
$$A(n)=C(1,n).$$
وبما أن كل حالة تعتمد فقط على فترات أقصر، فمن الممكن ملء الجدول بترتيب تصاعدي لطول الفترة.
عندما يكون \(n=6\) نعمل modulo \(7\)، فنحصل على
$$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1.$$
ومن ثم تكون خريطة المواضع
$$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3.$$
بعض الفترات القصيرة مباشرة:
$$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$$
ولفترة طولها \(3\)، نجد
$$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$$
وبالمثل
$$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$$
وعند إكمال الجدول من الفترات الأقصر إلى الأطول نحصل في النهاية على
$$C(1,6)=\min(9,10,10,9,8)=8.$$
إذن الكلفة المثلى للحالة الصغيرة ذات البطاقات الست هي \(8\)، وهذا يطابق قيمة التحقق الصغيرة المستخدمة في التطبيقات.
تقوم تطبيقات C++ وPython وJava أولا بتوليد التبديل عبر الضرب المتكرر في \(3\) ثم أخذ الباقي modulo \(n+1\). وخلال ذلك تُسجل مواضع جميع التسميات. كما أن نسختي C++ وJava تتحققان أيضا من أن التسلسل الناتج هو فعلا تبديل بلا تكرار ولا عناصر مفقودة.
بعد ذلك تُنشئ الشفرة جدولا ثنائيا لتخزين كلف الفترات. وتبقى قيم القطر مساوية للصفر لأن الفترات ذات الطول \(1\) لا تحتاج إلى أي دمج.
ثم تعالج البرمجة الديناميكية أطوال الفترات \(2,3,\dots,n\). ولكل فترة \([l,r]\) تجرّب جميع نقاط القطع \(m\)، وتحسب
$$C(l,m)+C(m+1,r)+|P(m)-P(r)|,$$
ثم تحتفظ بأصغر قيمة. وبعد الانتهاء من جميع الأطوال تكون الخانة الخاصة بالفترة \([1,n]\) هي الجواب النهائي.
بناء التبديل وخريطة المواضع يحتاج إلى زمن \(O(n)\) وذاكرة \(O(n)\). أما البرمجة الديناميكية فتفحص كل فترة \([l,r]\) وكل نقطة قطع \(m\) داخلها، ولذلك يكون التعقيد الزمني الكلي
$$O(n^3)$$
بينما يحتاج جدول الفترات إلى
$$O(n^2)$$
من الذاكرة.