We want a binary prefix code for \(10^9\) symbols. One branch adds cost \(1\) and the other adds cost \(4\), so the cost of a codeword is the sum of the edge costs along its root-to-leaf path. If \(\text{Cost}(n)\) denotes the minimum possible total cost of all codewords for \(n\) symbols, then Problem 219 asks for \(\text{Cost}(10^9)\).
A direct greedy simulation with an explicit priority queue works for tiny values of \(n\), but not for \(n=10^9\). The implementations therefore replace the evolving leaf set by a counting argument on how many nodes exist at each possible cost.
The right model is an infinite binary tree rooted at cost \(0\). From any node of cost \(c\), its two children have costs \(c+1\) and \(c+4\). A finite prefix-free code is obtained by choosing a finite full subtree and taking its leaves as the codewords.
In an optimal code tree, every internal node has exactly two children. A node with only one child would add positive cost without helping the prefix condition, so it can be contracted away. Therefore a code with \(n\) leaves has exactly \(n-1\) internal nodes.
Now start from a single leaf of cost \(0\) and expand leaves until \(n\) leaves exist. Expanding a leaf of cost \(c\) removes that leaf and creates two new leaves of costs \(c+1\) and \(c+4\). The total leaf-cost sum therefore changes by
$$\Delta=(c+1)+(c+4)-c=c+5.$$
If the internal-node costs, listed in the order they are expanded, are \(c_1,c_2,\dots,c_{n-1}\), then
$$\text{Cost}(n)=\sum_{k=1}^{n-1}(c_k+5)=5(n-1)+\sum_{k=1}^{n-1}c_k.$$
So the whole problem is reduced to finding the smallest possible sum of the \(n-1\) internal-node costs.
Every descendant of a node is strictly more expensive than the node itself, because each edge adds a positive amount. That means any feasible set of internal nodes is automatically prefix-closed: if a node is internal, then every ancestor on the path from the root must also be internal.
Consequently, the minimum possible value of \(\sum c_k\) is obtained by taking the \(n-1\) cheapest nodes in the infinite skew-cost tree. This is exactly the same rule as repeatedly expanding the currently cheapest available leaf. The greedy process is therefore not just a heuristic; it is the canonical order in which internal nodes appear in the optimum.
Let \(f(c)\) be the number of nodes in the infinite tree whose path cost is exactly \(c\). We have \(f(0)=1\) for the root and \(f(c)=0\) for negative \(c\). For \(c\ge 1\), any node of cost \(c\) must end either with a \(1\)-cost edge from a node of cost \(c-1\) or with a \(4\)-cost edge from a node of cost \(c-4\). These two cases are disjoint, so
$$f(c)=f(c-1)+f(c-4),\qquad f(0)=1,\qquad f(c)=0\text{ for }c<0.$$
This recurrence is the core object used by all three implementations. It tells us the multiplicity of each cost level without ever constructing the code tree explicitly.
There is also a combinatorial interpretation used as an independent check. If a node has cost \(c\), and exactly \(a\) of its edges are the \(4\)-cost kind, then the remaining number of \(1\)-cost edges is \(c-4a\). The total path length is therefore \(c-3a\), and the number of such words is \(\binom{c-3a}{a}\). Summing over all admissible \(a\) gives
$$f(c)=\sum_{a=0}^{\lfloor c/4\rfloor}\binom{c-3a}{a}.$$
The C++ implementation checks that this binomial-count formula matches the recurrence on small cost levels, which confirms that the state space has been modeled correctly.
Set \(m=n-1\), because that is the number of internal nodes we must choose. If we scan cost levels in increasing order, then at level \(c\) there are exactly \(f(c)\) nodes of that cost available to become internal nodes. Let
$$A(C)=\sum_{c=0}^{C}f(c),\qquad B(C)=\sum_{c=0}^{C}c\,f(c).$$
Let \(C_\star\) be the first cost level with \(A(C_\star)\ge m\). Then all nodes with cost below \(C_\star\) are taken completely, while the last layer is only partially used. Therefore
$$\sum_{k=1}^{m}c_k=B(C_\star-1)+C_\star\bigl(m-A(C_\star-1)\bigr),$$
and the final answer is
$$\boxed{\text{Cost}(n)=5(n-1)+B(C_\star-1)+C_\star\bigl((n-1)-A(C_\star-1)\bigr).}$$
The implementations compute this same quantity incrementally: they keep a running count of how many internal nodes have already been consumed and a running sum of their costs, and they stop as soon as the quota \(n-1\) is filled.
The checkpoint \(\text{Cost}(6)=35\) is built into the main implementation. Here \(m=n-1=5\), so we need the five cheapest internal-node costs. The recurrence begins
$$f(0)=1,\quad f(1)=1,\quad f(2)=1,\quad f(3)=1,\quad f(4)=2.$$
Thus the first five internal nodes have costs \(0,1,2,3,4\), whose sum is \(10\). Plugging that into the master formula gives
$$\text{Cost}(6)=5\cdot 5+(0+1+2+3+4)=25+10=35.$$
The same example can be seen directly through leaf expansions: \(0\to(1,4)\to(2,4,5)\to(3,4,5,6)\to(4,4,5,6,7)\to(4,5,5,6,7,8)\), and the final leaf-cost sum is indeed \(35\).
The C++, Python, and Java implementations all follow the same production method. They treat \(n-1\) as the number of internal nodes that must be selected, generate the multiplicities \(f(c)\) level by level from the recurrence \(f(c)=f(c-1)+f(c-4)\), and accumulate the sum of the cheapest internal-node costs.
At each cost level \(c\), the implementation takes
$$\min\bigl(f(c),\text{remaining internal nodes}\bigr)$$
nodes from that layer, adds \(c\) times that amount to the running total of internal-node costs, and advances to the next level. Once the required \(n-1\) nodes have been consumed, it adds the constant term \(5(n-1)\) and prints the result.
The arithmetic is intentionally wide. Python uses built-in arbitrary-precision integers, Java uses arbitrary-precision integer objects, and the C++ implementation uses a wider integer type because both multiplicities and totals quickly outgrow ordinary 32-bit arithmetic. The C++ implementation also includes validation logic: it checks the known value \(\text{Cost}(6)=35\), compares the recurrence against the binomial formula for \(f(c)\), and matches the formula-based solver against a direct greedy priority-queue simulation on small inputs.
Let \(C_\star\) be the largest cost level that must be visited before the first \(n-1\) internal nodes have been collected. The main solver performs a single forward pass through costs \(0,1,\dots,C_\star\), so its running time is \(O(C_\star)\).
The table of multiplicities also has size \(C_\star+1\), so the memory usage is \(O(C_\star)\). This is far smaller than an explicit greedy heap simulation up to \(n=10^9\), which would require maintaining an enormous frontier and would scale like \(O(n\log n)\). The priority-queue approach appears only in the small checkpoint code, not in the real computation.
Gesucht ist ein binärer Präfixcode für \(10^9\) Symbole. Ein Zweig kostet \(1\), der andere \(4\), also ist die Kosten eines Codeworts die Summe der Kantenkosten auf dem Pfad von der Wurzel zum Blatt. Bezeichnet \(\text{Cost}(n)\) die kleinstmögliche Summe aller Codewortkosten für \(n\) Symbole, dann verlangt Problem 219 den Wert \(\text{Cost}(10^9)\).
Eine direkte greedy Simulation mit einer Prioritätswarteschlange funktioniert nur für sehr kleine \(n\). Deshalb zählen die Implementierungen nicht einzelne Blätter aus, sondern bestimmen, wie viele Knoten auf jeder möglichen Kostenstufe existieren.
Das passende Modell ist ein unendlicher binärer Baum mit Wurzelkosten \(0\). Aus jedem Knoten mit Kosten \(c\) entstehen zwei Kinder mit Kosten \(c+1\) und \(c+4\). Ein endlicher präfixfreier Code entsteht, indem man einen endlichen vollen Teilbaum wählt und seine Blätter als Codewörter nimmt.
In einem optimalen Codebaum hat jeder innere Knoten genau zwei Kinder. Ein Knoten mit nur einem Kind würde ausschließlich positive Zusatzkosten erzeugen und könnte kontrahiert werden, ohne die Präfixeigenschaft zu verlieren. Also besitzt ein Code mit \(n\) Blättern genau \(n-1\) innere Knoten.
Beginnt man mit einem einzigen Blatt der Kosten \(0\) und erweitert dann Blätter, bis \(n\) Blätter vorhanden sind, so ersetzt eine Erweiterung eines Blatts der Kosten \(c\) dieses Blatt durch zwei neue Blätter der Kosten \(c+1\) und \(c+4\). Die Summe aller Blattkosten ändert sich daher um
$$\Delta=(c+1)+(c+4)-c=c+5.$$
Wenn die Kosten der inneren Knoten in der Reihenfolge ihrer Erweiterung \(c_1,c_2,\dots,c_{n-1}\) sind, dann gilt
$$\text{Cost}(n)=\sum_{k=1}^{n-1}(c_k+5)=5(n-1)+\sum_{k=1}^{n-1}c_k.$$
Das Problem reduziert sich also darauf, die kleinstmögliche Summe der \(n-1\) Kosten innerer Knoten zu finden.
Jeder Nachkomme eines Knotens ist strikt teurer als der Knoten selbst, denn jede Kante fügt einen positiven Wert hinzu. Deshalb ist jede zulässige Menge innerer Knoten automatisch präfixabgeschlossen: Wenn ein Knoten innerer Knoten ist, müssen auch alle seine Vorfahren auf dem Weg zur Wurzel innere Knoten sein.
Folglich erhält man das Minimum von \(\sum c_k\), indem man einfach die \(n-1\) billigsten Knoten im unendlichen skew-cost Baum auswählt. Das ist genau dieselbe Regel wie: Erweitere immer das aktuell billigste Blatt. Der greedy Prozess ist also nicht bloß plausibel, sondern genau die optimale Reihenfolge.
Sei \(f(c)\) die Anzahl der Knoten im unendlichen Baum mit Pfadkosten genau \(c\). Für die Wurzel gilt \(f(0)=1\), und für negative \(c\) gilt \(f(c)=0\). Für \(c\ge 1\) muss ein Knoten der Kosten \(c\) entweder mit einer \(1\)-Kante von einem Knoten der Kosten \(c-1\) kommen oder mit einer \(4\)-Kante von einem Knoten der Kosten \(c-4\). Diese Fälle sind disjunkt, also
$$f(c)=f(c-1)+f(c-4),\qquad f(0)=1,\qquad f(c)=0\text{ für }c<0.$$
Diese Rekurrenz ist das zentrale Zählobjekt aller drei Implementierungen. Sie liefert die Multiplizität jeder Kostenstufe, ohne den Baum explizit zu erzeugen.
Zusätzlich gibt es eine kombinatorische Interpretation als unabhängige Kontrolle. Hat ein Knoten Gesamtkosten \(c\) und genau \(a\) Kanten vom Kostenwert \(4\), dann bleiben \(c-4a\) Kanten vom Kostenwert \(1\). Die Pfadlänge ist also \(c-3a\), und die Anzahl solcher Wörter beträgt \(\binom{c-3a}{a}\). Summiert man über alle zulässigen \(a\), erhält man
$$f(c)=\sum_{a=0}^{\lfloor c/4\rfloor}\binom{c-3a}{a}.$$
Die C++-Implementierung prüft auf kleinen Kostenstufen, dass diese Binomialformel mit der Rekurrenz übereinstimmt. Damit wird das mathematische Modell zusätzlich verifiziert.
Setze \(m=n-1\), denn so viele innere Knoten müssen gewählt werden. Läuft man die Kostenstufen in aufsteigender Reihenfolge durch, dann stehen auf Stufe \(c\) genau \(f(c)\) Knoten dieser Kosten zur Verfügung. Definiere
$$A(C)=\sum_{c=0}^{C}f(c),\qquad B(C)=\sum_{c=0}^{C}c\,f(c).$$
Sei \(C_\star\) die erste Kostenstufe mit \(A(C_\star)\ge m\). Dann werden alle Knoten unterhalb von \(C_\star\) vollständig genommen, während die letzte Stufe nur teilweise benutzt wird. Daher
$$\sum_{k=1}^{m}c_k=B(C_\star-1)+C_\star\bigl(m-A(C_\star-1)\bigr),$$
und damit
$$\boxed{\text{Cost}(n)=5(n-1)+B(C_\star-1)+C_\star\bigl((n-1)-A(C_\star-1)\bigr).}$$
Genau diese Größe akkumulieren die Implementierungen schrittweise: Sie führen mit, wie viele innere Knoten bereits verbraucht sind und welche Kostensumme dazu gehört, und stoppen, sobald die Quote \(n-1\) erreicht ist.
Der Kontrollwert \(\text{Cost}(6)=35\) ist fest in der Hauptimplementierung eingebaut. Hier ist \(m=n-1=5\), also benötigen wir die fünf billigsten inneren Knoten. Die Rekurrenz beginnt mit
$$f(0)=1,\quad f(1)=1,\quad f(2)=1,\quad f(3)=1,\quad f(4)=2.$$
Also sind die ersten fünf Kosten innerer Knoten \(0,1,2,3,4\), ihre Summe ist \(10\). Damit folgt
$$\text{Cost}(6)=5\cdot 5+(0+1+2+3+4)=25+10=35.$$
Man sieht dasselbe auch direkt an den Blattexpansionen: \(0\to(1,4)\to(2,4,5)\to(3,4,5,6)\to(4,4,5,6,7)\to(4,5,5,6,7,8)\). Die Summe der Blattkosten am Ende ist tatsächlich \(35\).
Die Implementierungen in C++, Python und Java benutzen alle denselben Produktionsalgorithmus. Sie interpretieren \(n-1\) als die Anzahl innerer Knoten, die ausgewählt werden müssen, erzeugen die Multiplizitäten \(f(c)\) stufenweise aus der Rekurrenz \(f(c)=f(c-1)+f(c-4)\) und summieren die Kosten der billigsten inneren Knoten auf.
Auf jeder Kostenstufe \(c\) nimmt die Implementierung
$$\min\bigl(f(c),\text{verbleibende innere Knoten}\bigr)$$
Knoten aus dieser Schicht, addiert \(c\) mal diese Anzahl zur laufenden Summe der inneren Knotenkosten und geht dann zur nächsten Stufe weiter. Sobald insgesamt \(n-1\) Knoten verbraucht wurden, wird der konstante Anteil \(5(n-1)\) addiert und das Resultat ausgegeben.
Die Arithmetik ist bewusst breit gewählt. Python nutzt eingebaute Ganzzahlen beliebiger Größe, Java verwendet Ganzzahlen mit beliebiger Präzision, und die C++-Implementierung benutzt einen breiteren Ganzzahltyp, weil sowohl Multiplizitäten als auch Summen schnell über gewöhnliche 32-Bit-Arithmetik hinauswachsen. Zusätzlich enthält die C++-Version Validierungen: Sie prüft den bekannten Wert \(\text{Cost}(6)=35\), vergleicht die Rekurrenz mit der Binomialformel für \(f(c)\) und testet den formelbasierten Solver auf kleinen Eingaben gegen eine direkte greedy Prioritätswarteschlangen-Simulation.
Sei \(C_\star\) die größte Kostenstufe, die besucht werden muss, bevor die ersten \(n-1\) inneren Knoten vollständig gesammelt sind. Der Hauptsolver macht genau einen Vorwärtsdurchlauf über die Kosten \(0,1,\dots,C_\star\), also beträgt die Laufzeit \(O(C_\star)\).
Auch die Tabelle der Multiplizitäten hat nur Länge \(C_\star+1\), also beträgt der Speicherbedarf \(O(C_\star)\). Das ist wesentlich kleiner als eine explizite greedy Heap-Simulation bis \(n=10^9\), die eine riesige Front verwalten müsste und in \(O(n\log n)\) läge. Die Prioritätswarteschlange erscheint nur in den kleinen Checkpoints, nicht in der eigentlichen Rechnung.
\(10^9\) sembol için ikili bir prefix kod aranıyor. Dallardan biri \(1\), diğeri \(4\) maliyet ekliyor; dolayısıyla bir kod sözcüğünün maliyeti, kökten yaprağa giden yol üzerindeki kenar maliyetlerinin toplamıdır. \(\text{Cost}(n)\), \(n\) sembol için mümkün olan en küçük toplam kod maliyetini göstersin. Problem 219, \(\text{Cost}(10^9)\) değerini ister.
Açık bir öncelik kuyruğu ile doğrudan greedy simülasyon küçük \(n\) için işe yarar, fakat \(n=10^9\) için pratik değildir. Bu yüzden uygulamalar yaprak kümesini tek tek izlemek yerine, her maliyet seviyesinde kaç düğüm bulunduğunu sayan bir yönteme geçer.
Doğru model, kök maliyeti \(0\) olan sonsuz bir ikili ağaçtır. Maliyeti \(c\) olan her düğümün iki çocuğu vardır ve bunların maliyetleri \(c+1\) ile \(c+4\) olur. Sonlu bir prefix-free kod, bu ağacın sonlu ve tam bir alt ağacını seçip yapraklarını kod sözcükleri olarak almakla elde edilir.
Optimal bir kod ağacında her iç düğümün tam iki çocuğu vardır. Tek çocuklu bir iç düğüm, prefix koşuluna katkı yapmadan yalnızca pozitif maliyet ekler; bu yüzden daraltılıp kaldırılabilir. Dolayısıyla \(n\) yapraklı bir kod ağacının tam \(n-1\) iç düğümü vardır.
Şimdi maliyeti \(0\) olan tek bir yaprakla başlayıp \(n\) yaprağa ulaşıncaya kadar yaprak genişlettiğimizi düşünelim. Maliyeti \(c\) olan bir yaprağı genişletmek, o yaprağı kaldırıp maliyetleri \(c+1\) ve \(c+4\) olan iki yeni yaprak üretir. Toplam yaprak maliyeti bu yüzden
$$\Delta=(c+1)+(c+4)-c=c+5$$
kadar değişir. İç düğüm maliyetleri genişletilme sırasıyla \(c_1,c_2,\dots,c_{n-1}\) ise
$$\text{Cost}(n)=\sum_{k=1}^{n-1}(c_k+5)=5(n-1)+\sum_{k=1}^{n-1}c_k$$
olur. Böylece problem, \(n-1\) iç düğüm maliyetinin mümkün olan en küçük toplamını bulmaya indirgenir.
Her çocuk düğüm, atasından daha pahalıdır; çünkü her kenar pozitif bir miktar ekler. Bu nedenle geçerli herhangi bir iç düğüm kümesi otomatik olarak prefix-closed olur: bir düğüm iç düğümse, kökten ona kadar olan tüm ataları da iç düğüm olmak zorundadır.
Sonuç olarak \(\sum c_k\) toplamını minimize etmek için sonsuz skew-cost ağacındaki en ucuz \(n-1\) düğümü seçmek yeterlidir. Bu da tam olarak “o anda mevcut olan en ucuz yaprağı genişlet” kuralıdır. Yani greedy süreç yalnızca sezgisel değil, doğrudan optimal yapının kendisidir.
\(f(c)\), sonsuz ağaçta yol maliyeti tam olarak \(c\) olan düğüm sayısı olsun. Kök için \(f(0)=1\), negatif maliyetler içinse \(f(c)=0\) alınır. \(c\ge 1\) olduğunda, maliyeti \(c\) olan her düğüm ya maliyeti \(c-1\) olan bir düğümden gelen \(1\) maliyetli bir son kenarla ya da maliyeti \(c-4\) olan bir düğümden gelen \(4\) maliyetli bir son kenarla oluşur. Bu iki durum ayrık olduğundan
$$f(c)=f(c-1)+f(c-4),\qquad f(0)=1,\qquad f(c)=0\text{ if }c<0$$
bağıntısı elde edilir. Üç uygulamanın da merkezindeki nesne bu yinelemedir. Kod ağacını açıkça kurmadan her maliyet seviyesinin çokluğunu verir.
Ayrıca bağımsız bir doğrulama olarak kombinatoryal bir yorum da vardır. Bir düğümün toplam maliyeti \(c\) ise ve yolunda tam \(a\) tane \(4\)-maliyetli kenar varsa, geriye \(c-4a\) tane \(1\)-maliyetli kenar kalır. O halde yol uzunluğu \(c-3a\) olur ve böyle sözcüklerin sayısı \(\binom{c-3a}{a}\) kadardır. Bütün uygun \(a\) değerleri toplanınca
$$f(c)=\sum_{a=0}^{\lfloor c/4\rfloor}\binom{c-3a}{a}$$
elde edilir. C++ uygulaması, küçük maliyet seviyelerinde bu binom formülünün yineleme ile uyuştuğunu kontrol eder; böylece model ikinci bir yoldan doğrulanmış olur.
\(m=n-1\) yazalım; çünkü seçmemiz gereken iç düğüm sayısı budur. Maliyet seviyelerini artan sırada tararsak, seviye \(c\)'de iç düğüm olarak seçilebilecek tam \(f(c)\) adet düğüm vardır. Şimdi
$$A(C)=\sum_{c=0}^{C}f(c),\qquad B(C)=\sum_{c=0}^{C}c\,f(c)$$
tanımlarını yapalım. \(A(C_\star)\ge m\) koşulunu sağlayan ilk maliyet seviyesi \(C_\star\) olsun. O zaman \(C_\star\)'dan düşük bütün seviyeler tamamen alınır; yalnız son seviye kısmen kullanılır. Bu yüzden
$$\sum_{k=1}^{m}c_k=B(C_\star-1)+C_\star\bigl(m-A(C_\star-1)\bigr)$$
ve dolayısıyla
$$\boxed{\text{Cost}(n)=5(n-1)+B(C_\star-1)+C_\star\bigl((n-1)-A(C_\star-1)\bigr).}$$
Uygulamalar aynı niceliği artımlı olarak hesaplar: kaç iç düğümün tüketildiğini ve bu düğümlerin maliyet toplamını birlikte taşır, \(n-1\) kotası dolunca durur.
\(\text{Cost}(6)=35\) kontrolü ana uygulamaya gömülüdür. Burada \(m=n-1=5\) olduğundan en ucuz beş iç düğüm maliyetine ihtiyacımız var. Yinelemenin ilk değerleri
$$f(0)=1,\quad f(1)=1,\quad f(2)=1,\quad f(3)=1,\quad f(4)=2$$
şeklindedir. Demek ki ilk beş iç düğüm maliyeti \(0,1,2,3,4\) olur ve toplamları \(10\)'dur. Ana formüle yerleştirince
$$\text{Cost}(6)=5\cdot 5+(0+1+2+3+4)=25+10=35$$
çıkar. Aynı durum yaprak genişletmeleriyle de görülebilir: \(0\to(1,4)\to(2,4,5)\to(3,4,5,6)\to(4,4,5,6,7)\to(4,5,5,6,7,8)\). Son yaprak maliyeti toplamı gerçekten \(35\)'tir.
C++, Python ve Java uygulamalarının üretim mantığı aynıdır. Hepsi \(n-1\)'i seçilmesi gereken iç düğüm sayısı olarak görür, \(f(c)=f(c-1)+f(c-4)\) yinelemesiyle \(f(c)\) çokluklarını seviye seviye üretir ve en ucuz iç düğüm maliyetlerinin toplamını biriktirir.
Her maliyet seviyesi \(c\) için uygulama
$$\min\bigl(f(c),\text{kalan iç düğüm sayısı}\bigr)$$
kadar düğüm alır, bunu \(c\) ile çarpıp iç düğüm maliyetleri toplamına ekler ve sonra bir sonraki seviyeye geçer. Gerekli \(n-1\) düğüm tamamlanınca sabit terim \(5(n-1)\) eklenir ve sonuç yazdırılır.
Sayı aritmetiği bilinçli olarak geniş tutulur. Python yerleşik büyük tamsayılar kullanır, Java keyfi hassasiyetli tamsayı sınıfına dayanır, C++ uygulaması ise hem çokluklar hem de toplamlar sıradan 32-bit aralığı hızla aştığı için daha geniş bir tamsayı türü kullanır. C++ sürümünde ayrıca doğrulamalar vardır: bilinen \(\text{Cost}(6)=35\) değeri kontrol edilir, \(f(c)\) için yineleme ile binom formülü karşılaştırılır ve formül tabanlı çözücü küçük girdilerde doğrudan greedy öncelik kuyruğu simülasyonuyla eşleştirilir.
\(C_\star\), ilk \(n-1\) iç düğüm toplanmadan önce ziyaret edilmesi gereken en büyük maliyet seviyesi olsun. Ana çözücü maliyetler üzerinde \(0,1,\dots,C_\star\) şeklinde tek bir ileri tarama yapar; dolayısıyla zaman karmaşıklığı \(O(C_\star)\) olur.
Çokluk tablosunun uzunluğu da yalnızca \(C_\star+1\) olduğu için bellek karmaşıklığı \(O(C_\star)\)'dir. Bu, \(n=10^9\) için açık greedy heap simülasyonundan çok daha küçüktür; çünkü o yaklaşım devasa bir sınır kümesini taşımak zorunda kalır ve \(O(n\log n)\) ölçeğinde büyür. Öncelik kuyruğu burada yalnızca küçük kontrol testlerinde kullanılır, asıl hesaplamada değil.
Buscamos un código prefijo binario para \(10^9\) símbolos. Una rama añade coste \(1\) y la otra añade coste \(4\), de modo que el coste de una palabra código es la suma de los costes de las aristas a lo largo de su camino desde la raíz hasta una hoja. Si \(\text{Cost}(n)\) denota el coste total mínimo posible de todas las palabras código para \(n\) símbolos, el Problema 219 pide \(\text{Cost}(10^9)\).
Una simulación greedy directa con una cola de prioridad explícita sirve para valores muy pequeños de \(n\), pero no para \(n=10^9\). Por eso las implementaciones reemplazan el seguimiento hoja por hoja por un argumento de conteo sobre cuántos nodos existen en cada nivel de coste.
El modelo correcto es un árbol binario infinito con coste \(0\) en la raíz. Desde cualquier nodo de coste \(c\), sus dos hijos tienen costes \(c+1\) y \(c+4\). Un código prefijo finito se obtiene eligiendo un subárbol lleno finito y tomando sus hojas como palabras código.
En un árbol óptimo, cada nodo interno tiene exactamente dos hijos. Un nodo interno con un solo hijo añadiría coste positivo sin aportar nada a la condición de prefijo, así que puede contraerse. Por tanto, un código con \(n\) hojas tiene exactamente \(n-1\) nodos internos.
Partamos ahora de una sola hoja de coste \(0\) y vayamos expandiendo hojas hasta obtener \(n\) hojas. Expandir una hoja de coste \(c\) elimina esa hoja y crea dos nuevas hojas de costes \(c+1\) y \(c+4\). El cambio en la suma total de costes de las hojas es entonces
$$\Delta=(c+1)+(c+4)-c=c+5.$$
Si los costes de los nodos internos, en el orden en que se expanden, son \(c_1,c_2,\dots,c_{n-1}\), entonces
$$\text{Cost}(n)=\sum_{k=1}^{n-1}(c_k+5)=5(n-1)+\sum_{k=1}^{n-1}c_k.$$
Así, todo el problema queda reducido a minimizar la suma de los \(n-1\) costes de los nodos internos.
Cada descendiente de un nodo es estrictamente más caro que el propio nodo, porque cada arista añade una cantidad positiva. Eso implica que cualquier conjunto factible de nodos internos es automáticamente cerrado por prefijos: si un nodo es interno, todos sus antepasados hasta la raíz también deben ser internos.
En consecuencia, el valor mínimo de \(\sum c_k\) se obtiene tomando simplemente los \(n-1\) nodos más baratos del árbol infinito de coste sesgado. Esa es exactamente la misma regla que “expandir siempre la hoja disponible más barata”. El procedimiento greedy no es solo intuitivo: coincide con la estructura óptima.
Sea \(f(c)\) el número de nodos del árbol infinito cuyo coste de camino es exactamente \(c\). Para la raíz tenemos \(f(0)=1\), y para costes negativos tomamos \(f(c)=0\). Si \(c\ge 1\), cualquier nodo de coste \(c\) debe terminar o bien con una arista de coste \(1\) desde un nodo de coste \(c-1\), o bien con una arista de coste \(4\) desde un nodo de coste \(c-4\). Como ambos casos son disjuntos, se obtiene
$$f(c)=f(c-1)+f(c-4),\qquad f(0)=1,\qquad f(c)=0\text{ para }c<0.$$
Esta recurrencia es el objeto central de las tres implementaciones. Da la multiplicidad de cada nivel de coste sin construir el árbol de manera explícita.
Además hay una interpretación combinatoria que se usa como comprobación independiente. Si un nodo tiene coste total \(c\) y exactamente \(a\) aristas del tipo de coste \(4\), entonces le quedan \(c-4a\) aristas del tipo de coste \(1\). La longitud total del camino es \(c-3a\), y el número de palabras de ese tipo es \(\binom{c-3a}{a}\). Sumando sobre todos los valores admisibles de \(a\), obtenemos
$$f(c)=\sum_{a=0}^{\lfloor c/4\rfloor}\binom{c-3a}{a}.$$
La implementación en C++ comprueba en niveles pequeños de coste que esta fórmula binomial coincide con la recurrencia, lo cual valida el modelo desde un segundo punto de vista.
Escribamos \(m=n-1\), porque ese es el número de nodos internos que debemos seleccionar. Si recorremos los niveles de coste en orden creciente, en el nivel \(c\) hay exactamente \(f(c)\) nodos de ese coste disponibles para convertirse en nodos internos. Definimos
$$A(C)=\sum_{c=0}^{C}f(c),\qquad B(C)=\sum_{c=0}^{C}c\,f(c).$$
Sea \(C_\star\) el primer nivel de coste tal que \(A(C_\star)\ge m\). Entonces todos los nodos con coste inferior a \(C_\star\) se toman por completo, mientras que la última capa solo se usa parcialmente. Por tanto,
$$\sum_{k=1}^{m}c_k=B(C_\star-1)+C_\star\bigl(m-A(C_\star-1)\bigr),$$
y en consecuencia
$$\boxed{\text{Cost}(n)=5(n-1)+B(C_\star-1)+C_\star\bigl((n-1)-A(C_\star-1)\bigr).}$$
Las implementaciones calculan esta misma cantidad de forma incremental: llevan la cuenta de cuántos nodos internos ya se han consumido y cuál es la suma de sus costes, y se detienen justo cuando se completa la cuota \(n-1\).
El valor de control \(\text{Cost}(6)=35\) está incorporado en la implementación principal. Aquí \(m=n-1=5\), así que necesitamos los cinco costes internos más pequeños. La recurrencia empieza como
$$f(0)=1,\quad f(1)=1,\quad f(2)=1,\quad f(3)=1,\quad f(4)=2.$$
Por tanto, los cinco primeros costes internos son \(0,1,2,3,4\), cuya suma es \(10\). Sustituyendo en la fórmula principal se obtiene
$$\text{Cost}(6)=5\cdot 5+(0+1+2+3+4)=25+10=35.$$
El mismo ejemplo también puede verse siguiendo las expansiones de hojas: \(0\to(1,4)\to(2,4,5)\to(3,4,5,6)\to(4,4,5,6,7)\to(4,5,5,6,7,8)\). La suma final de costes de las hojas es efectivamente \(35\).
Las implementaciones en C++, Python y Java siguen el mismo método de producción. Interpretan \(n-1\) como el número de nodos internos que hay que seleccionar, generan las multiplicidades \(f(c)\) nivel por nivel a partir de la recurrencia \(f(c)=f(c-1)+f(c-4)\) y acumulan la suma de los costes internos más baratos.
En cada nivel de coste \(c\), la implementación toma
$$\min\bigl(f(c),\text{nodos internos restantes}\bigr)$$
nodos de esa capa, añade \(c\) multiplicado por esa cantidad a la suma acumulada de costes internos y pasa al siguiente nivel. Una vez consumidos los \(n-1\) nodos requeridos, añade el término constante \(5(n-1)\) y produce la respuesta.
La aritmética se maneja con tipos amplios. Python usa enteros grandes nativos, Java usa enteros de precisión arbitraria y la implementación en C++ usa un tipo entero más ancho porque tanto las multiplicidades como las sumas superan enseguida la aritmética ordinaria de 32 bits. La versión en C++ también incorpora validaciones: verifica el valor conocido \(\text{Cost}(6)=35\), compara la recurrencia con la fórmula binomial de \(f(c)\) y contrasta el solucionador basado en la fórmula con una simulación greedy directa mediante cola de prioridad en entradas pequeñas.
Sea \(C_\star\) el mayor nivel de coste que debe visitarse antes de reunir por completo los primeros \(n-1\) nodos internos. El solucionador principal hace una sola pasada hacia delante por los costes \(0,1,\dots,C_\star\), así que su tiempo de ejecución es \(O(C_\star)\).
La tabla de multiplicidades también tiene longitud \(C_\star+1\), por lo que el uso de memoria es \(O(C_\star)\). Esto es muchísimo menor que una simulación greedy explícita con heap hasta \(n=10^9\), que tendría que mantener una frontera enorme y escalaría como \(O(n\log n)\). La cola de prioridad solo aparece en las comprobaciones pequeñas, no en el cálculo real.
题目要求为 \(10^9\) 个符号构造一个二叉前缀码。两条分支的代价并不对称，其中一条边增加 \(1\)，另一条边增加 \(4\)。因此，一个码字的代价就是从根到对应叶子的路径总代价。记 \(\text{Cost}(n)\) 为 \(n\) 个符号时所有码字总代价的最小值，那么 Problem 219 要求的就是 \(\text{Cost}(10^9)\)。
如果直接用优先队列做贪心模拟，那么对很小的 \(n\) 当然可行，但对 \(n=10^9\) 完全不现实。真正的解法不再显式维护“当前有哪些叶子”，而是改为统计“代价恰好等于 \(c\) 的节点一共有多少个”。
最合适的数学模型是一棵根节点代价为 \(0\) 的无限二叉树。任何一个代价为 \(c\) 的节点都会生成两个孩子，它们的代价分别是 \(c+1\) 和 \(c+4\)。一个有限的前缀码，对应于这棵无限树中的一个有限满二叉子树，而它的所有叶子正好就是码字。
在最优码树中，每个内部节点都必须恰好有两个孩子。若某个内部节点只有一个孩子，那么它只会额外增加正代价，却不会对前缀约束带来任何好处，因此完全可以把它收缩掉。于是，一个有 \(n\) 个叶子的最优码树一定有恰好 \(n-1\) 个内部节点。
现在从一个代价为 \(0\) 的单叶开始，不断扩展叶子，直到树中有 \(n\) 个叶子。若扩展的是一个代价为 \(c\) 的叶子，那么这个叶子会消失，并被两个新叶子取代，它们的代价分别为 \(c+1\) 与 \(c+4\)。因此叶子总代价的变化量为
$$\Delta=(c+1)+(c+4)-c=c+5.$$
如果按扩展顺序把所有内部节点的代价记为 \(c_1,c_2,\dots,c_{n-1}\)，那么就有
$$\text{Cost}(n)=\sum_{k=1}^{n-1}(c_k+5)=5(n-1)+\sum_{k=1}^{n-1}c_k.$$
这一步非常关键，因为它把原问题从“找最优码树”改写成了“找出代价最小的 \(n-1\) 个内部节点”。
每条边的代价都是正的，所以任何节点的后代都一定比它本身更贵。这意味着：如果某个节点被选作内部节点，那么从根到它路径上的所有祖先节点也都必须已经是内部节点。换句话说，任何可行的内部节点集合天然都是前缀闭合的。
因此，要最小化 \(\sum c_k\)，最优策略就是直接取这棵无限 skew-cost 树里代价最小的 \(n-1\) 个节点。这与“每次总是扩展当前代价最小的叶子”完全等价。也就是说，贪心顺序不是经验规则，而是最优结构本身。
设 \(f(c)\) 表示无限树中路径代价恰好为 \(c\) 的节点数。根节点给出 \(f(0)=1\)，而负代价下没有节点，所以 \(f(c)=0\)（当 \(c<0\) 时）。对任意 \(c\ge 1\)，一个总代价为 \(c\) 的节点，最后一步只能来自两种互斥情况之一：要么它的父节点代价是 \(c-1\)，最后一条边代价为 \(1\)；要么它的父节点代价是 \(c-4\)，最后一条边代价为 \(4\)。因此满足递推关系
$$f(c)=f(c-1)+f(c-4),\qquad f(0)=1,\qquad f(c)=0\text{ 当 }c<0.$$
这就是三个实现共同依赖的核心计数对象。它直接给出了每一个代价层的节点重数，而完全不需要显式构造整棵编码树。
同一个量还有一个组合解释，可作为独立校验。若一个总代价为 \(c\) 的节点路径中恰好有 \(a\) 条代价为 \(4\) 的边，那么剩下的代价为 \(1\) 的边数就是 \(c-4a\)。于是路径总长度为 \(c-3a\)，而这种路径的排列数为 \(\binom{c-3a}{a}\)。对所有允许的 \(a\) 求和，得到
$$f(c)=\sum_{a=0}^{\lfloor c/4\rfloor}\binom{c-3a}{a}.$$
C++ 实现会在若干小代价层上验证这个二项式计数公式与递推公式完全一致，从而确认状态空间建模没有偏差。
记 \(m=n-1\)，因为我们必须选出 \(m\) 个内部节点。如果按代价从小到大扫描，那么在层 \(c\) 上恰好有 \(f(c)\) 个代价等于 \(c\) 的候选节点。定义累计计数与累计加权和
$$A(C)=\sum_{c=0}^{C}f(c),\qquad B(C)=\sum_{c=0}^{C}c\,f(c).$$
设 \(C_\star\) 是第一个满足 \(A(C_\star)\ge m\) 的代价层。那么所有小于 \(C_\star\) 的层都必须整层取完，而最后一层 \(C_\star\) 只取其中一部分。因此
$$\sum_{k=1}^{m}c_k=B(C_\star-1)+C_\star\bigl(m-A(C_\star-1)\bigr),$$
于是最终答案为
$$\boxed{\text{Cost}(n)=5(n-1)+B(C_\star-1)+C_\star\bigl((n-1)-A(C_\star-1)\bigr).}$$
实际实现虽然没有显式写成 \(A\) 和 \(B\) 这两个函数，但做的正是同一件事：一边扫描代价层，一边累计已经取走了多少个内部节点，以及这些节点的总代价，直到配额 \(n-1\) 被填满为止。
主实现中内置了一个重要校验值：\(\text{Cost}(6)=35\)。此时 \(m=n-1=5\)，所以只需要最便宜的五个内部节点代价。由递推可得前几项
$$f(0)=1,\quad f(1)=1,\quad f(2)=1,\quad f(3)=1,\quad f(4)=2.$$
因此前五个内部节点代价就是 \(0,1,2,3,4\)，它们的和为 \(10\)。代回主公式得到
$$\text{Cost}(6)=5\cdot 5+(0+1+2+3+4)=25+10=35.$$
如果从叶子扩展的角度看，同样能得到这个结果：\(0\to(1,4)\to(2,4,5)\to(3,4,5,6)\to(4,4,5,6,7)\to(4,5,5,6,7,8)\)。最终六个叶子的总代价确实就是 \(35\)。这个例子同时说明了贪心顺序和“按代价层计数”这两种视角其实完全一致。
C++、Python 和 Java 三个实现都采用同一个核心思路。它们把 \(n-1\) 视为必须选出的内部节点个数，利用递推 \(f(c)=f(c-1)+f(c-4)\) 逐层生成每个代价层的节点数，然后把最小的那些内部节点代价累加起来。
在每个代价层 \(c\)，实现都会取出
$$\min\bigl(f(c),\text{尚未补足的内部节点数}\bigr)$$
个节点，把这部分节点的总代价 \(c\times\text{数量}\) 加入运行中的和，然后继续扫描下一层。一旦总共取满 \(n-1\) 个内部节点，就再加上固定项 \(5(n-1)\)，得到最终答案。
实现中的整数类型都刻意选得足够宽。Python 直接使用内建大整数，Java 使用任意精度整数，而 C++ 使用更宽的整数类型，因为无论是层重数还是最终总和，都很快会超出普通 32 位整数范围。C++ 实现还带有几层校验：先验证已知值 \(\text{Cost}(6)=35\)，再检查递推式与二项式计数公式在小代价区间上一致，最后把正式公式解与小规模的直接贪心优先队列模拟逐项比对。
设 \(C_\star\) 为在收集前 \(n-1\) 个内部节点之前必须访问到的最大代价层。主求解器只会对代价 \(0,1,\dots,C_\star\) 做一次线性前向扫描，因此时间复杂度为 \(O(C_\star)\)。
重数表同样只需要存到 \(C_\star\) 为止，所以空间复杂度也是 \(O(C_\star)\)。这比显式使用堆来模拟直到 \(n=10^9\) 的贪心过程小得多；后者不仅需要维护一个极大的前沿，还会带来 \(O(n\log n)\) 级别的工作量。优先队列在这里仅用于小规模校验，不属于真正的生产计算。
Нужно построить двоичный префиксный код для \(10^9\) символов. Одна ветвь добавляет стоимость \(1\), другая добавляет стоимость \(4\), поэтому стоимость кодового слова равна сумме стоимостей ребер на пути от корня к листу. Пусть \(\text{Cost}(n)\) обозначает минимально возможную суммарную стоимость всех кодовых слов для \(n\) символов. Тогда в Problem 219 требуется вычислить \(\text{Cost}(10^9)\).
Прямая greedy симуляция с явной приоритетной очередью работает только на очень малых \(n\), но не на \(n=10^9\). Поэтому реализации отказываются от явного отслеживания множества листьев и переходят к подсчету того, сколько узлов существует на каждом уровне стоимости.
Удобнее всего рассматривать бесконечное двоичное дерево с корнем стоимости \(0\). У любого узла стоимости \(c\) два потомка имеют стоимости \(c+1\) и \(c+4\). Конечный префиксный код получается из конечного полного поддерева этой бесконечной конструкции, а листья поддерева и есть кодовые слова.
В оптимальном кодовом дереве каждый внутренний узел имеет ровно двух детей. Внутренний узел с одним ребенком лишь добавлял бы положительную стоимость и не улучшал бы префиксное условие, так что его можно было бы стянуть. Следовательно, у кода с \(n\) листьями ровно \(n-1\) внутренних узлов.
Начнем с одного листа стоимости \(0\) и будем расширять листья, пока не получим \(n\) листьев. Если расширяется лист стоимости \(c\), то этот лист исчезает и заменяется двумя новыми листьями стоимостей \(c+1\) и \(c+4\). Поэтому сумма стоимостей листьев изменяется на
$$\Delta=(c+1)+(c+4)-c=c+5.$$
Если стоимости внутренних узлов в порядке расширения равны \(c_1,c_2,\dots,c_{n-1}\), то
$$\text{Cost}(n)=\sum_{k=1}^{n-1}(c_k+5)=5(n-1)+\sum_{k=1}^{n-1}c_k.$$
Значит, задача целиком сводится к минимизации суммы стоимостей \(n-1\) внутренних узлов.
Любой потомок узла строго дороже самого узла, потому что каждое ребро добавляет положительное число. Поэтому любое допустимое множество внутренних узлов автоматически замкнуто по префиксу: если узел внутренний, то все его предки до корня тоже обязаны быть внутренними.
Отсюда следует, что минимальное значение \(\sum c_k\) достигается просто выбором \(n-1\) самых дешевых узлов в бесконечном skew-cost дереве. Это в точности совпадает с правилом «всегда расширять самый дешевый доступный лист». То есть greedy порядок здесь не эвристика, а точное описание оптимальной структуры.
Пусть \(f(c)\) обозначает число узлов бесконечного дерева, чья стоимость пути равна ровно \(c\). Для корня имеем \(f(0)=1\), а для отрицательных \(c\) полагаем \(f(c)=0\). При \(c\ge 1\) любой узел стоимости \(c\) может возникнуть ровно одним из двух взаимоисключающих способов: либо его родитель имеет стоимость \(c-1\), а последнее ребро стоит \(1\); либо его родитель имеет стоимость \(c-4\), а последнее ребро стоит \(4\). Поэтому
$$f(c)=f(c-1)+f(c-4),\qquad f(0)=1,\qquad f(c)=0\text{ при }c<0.$$
Именно эта рекуррентная формула лежит в центре всех трех реализаций. Она дает кратность каждого уровня стоимости без явного построения кодового дерева.
Существует и комбинаторная интерпретация, используемая как независимая проверка. Если у узла полной стоимости \(c\) ровно \(a\) ребер стоимости \(4\), то ребер стоимости \(1\) остается \(c-4a\). Общая длина пути тогда равна \(c-3a\), а число слов такого вида равно \(\binom{c-3a}{a}\). Суммируя по всем допустимым \(a\), получаем
$$f(c)=\sum_{a=0}^{\lfloor c/4\rfloor}\binom{c-3a}{a}.$$
Реализация на C++ сравнивает эту биномиальную формулу с рекуррентной на малых уровнях стоимости, что служит дополнительным подтверждением корректности модели.
Положим \(m=n-1\), поскольку именно столько внутренних узлов нужно выбрать. Если идти по уровням стоимости в возрастающем порядке, то на уровне \(c\) имеется ровно \(f(c)\) узлов с этой стоимостью, годящихся в внутренние. Введем
$$A(C)=\sum_{c=0}^{C}f(c),\qquad B(C)=\sum_{c=0}^{C}c\,f(c).$$
Пусть \(C_\star\) является первым уровнем стоимости, для которого \(A(C_\star)\ge m\). Тогда все узлы со стоимостью меньше \(C_\star\) берутся целиком, а последний слой используется лишь частично. Поэтому
$$\sum_{k=1}^{m}c_k=B(C_\star-1)+C_\star\bigl(m-A(C_\star-1)\bigr),$$
а значит
$$\boxed{\text{Cost}(n)=5(n-1)+B(C_\star-1)+C_\star\bigl((n-1)-A(C_\star-1)\bigr).}$$
Именно эту величину реализации и считают по шагам: они держат число уже выбранных внутренних узлов и сумму их стоимостей, продвигаясь вперед по уровням до тех пор, пока квота \(n-1\) не заполнена.
Контрольное значение \(\text{Cost}(6)=35\) встроено в основную реализацию. Здесь \(m=n-1=5\), так что нужны пять самых дешевых внутренних узлов. Начало рекуррентной последовательности таково:
$$f(0)=1,\quad f(1)=1,\quad f(2)=1,\quad f(3)=1,\quad f(4)=2.$$
Следовательно, первые пять стоимостей внутренних узлов равны \(0,1,2,3,4\), а их сумма равна \(10\). Подстановка в общую формулу дает
$$\text{Cost}(6)=5\cdot 5+(0+1+2+3+4)=25+10=35.$$
То же самое видно и на уровне расширений листьев: \(0\to(1,4)\to(2,4,5)\to(3,4,5,6)\to(4,4,5,6,7)\to(4,5,5,6,7,8)\). Итоговая сумма стоимостей листьев действительно равна \(35\).
Реализации на C++, Python и Java используют один и тот же рабочий метод. Они интерпретируют \(n-1\) как количество внутренних узлов, которые нужно выбрать, по рекуррентной формуле \(f(c)=f(c-1)+f(c-4)\) строят кратности уровней стоимости и суммируют стоимости самых дешевых внутренних узлов.
На каждом уровне стоимости \(c\) реализация берет
$$\min\bigl(f(c),\text{оставшиеся внутренние узлы}\bigr)$$
узлов из этого слоя, прибавляет \(c\), умноженное на это количество, к текущей сумме стоимостей внутренних узлов и переходит к следующему уровню. Как только набраны все \(n-1\) узлов, добавляется постоянный вклад \(5(n-1)\), после чего печатается ответ.
Используемая арифметика намеренно выбрана широкой. Python опирается на встроенные длинные целые, Java использует объекты произвольной точности, а C++ берет более широкий целочисленный тип, потому что и кратности, и итоговые суммы быстро выходят за пределы обычной 32-битной арифметики. Реализация на C++ также содержит проверки: она подтверждает известное значение \(\text{Cost}(6)=35\), сравнивает рекуррентную формулу с биномиальной формулой для \(f(c)\) и сверяет формульный решатель с прямой greedy симуляцией через приоритетную очередь на малых входах.
Пусть \(C_\star\) обозначает наибольший уровень стоимости, который нужно посетить, прежде чем будут полностью собраны первые \(n-1\) внутренних узлов. Основной решатель делает один линейный проход по стоимостям \(0,1,\dots,C_\star\), поэтому его временная сложность равна \(O(C_\star)\).
Таблица кратностей тоже имеет длину всего \(C_\star+1\), так что затраты памяти составляют \(O(C_\star)\). Это радикально меньше, чем у явной greedy симуляции с кучей до \(n=10^9\), где пришлось бы хранить огромный фронт и платить \(O(n\log n)\). Приоритетная очередь здесь используется только в небольших проверках, а не в реальном вычислении.
نريد بناء ترميز بادئي ثنائي لعدد \(10^9\) من الرموز. أحد الفرعين يضيف كلفة مقدارها \(1\) والآخر يضيف كلفة مقدارها \(4\)، ولذلك فإن كلفة أي كلمة ترميز هي مجموع كلف الحواف على المسار من الجذر إلى الورقة. إذا رمزنا بأصغر كلفة كلية ممكنة لجميع الكلمات عند وجود \(n\) رموز بالرمز \(\text{Cost}(n)\)، فإن المطلوب في Problem 219 هو حساب \(\text{Cost}(10^9)\).
المحاكاة الجشعة المباشرة باستخدام طابور أولوية صريح تصلح فقط للقيم الصغيرة جدًا من \(n\)، لكنها غير عملية إطلاقًا عندما يكون \(n=10^9\). لذلك تستبدل التطبيقات تتبّع الأوراق واحدةً واحدةً بحجة عدّية تحدد كم عقدة توجد في كل مستوى كلفة.
النموذج المناسب هو شجرة ثنائية لا نهائية تكون كلفة جذرها \(0\). وكل عقدة كلفتها \(c\) لها ابنان بكلفتين \(c+1\) و\(c+4\). أمّا الترميز البادئي المنتهي فينتج من اختيار شجرة فرعية ممتلئة منتهية من هذه الشجرة اللانهائية، ثم أخذ أوراقها على أنها كلمات الترميز.
في الشجرة المثلى يجب أن تمتلك كل عقدة داخلية ولدين بالضبط. فالعقدة الداخلية ذات الابن الوحيد تضيف كلفة موجبة من غير أي فائدة حقيقية لشرط البادئة، ولذلك يمكن ضغطها وحذفها. ومن ثم فإن أي شجرة ترميز لها \(n\) ورقة تحتوي بالضبط على \(n-1\) عقدة داخلية.
لنبدأ بورقة واحدة كلفتها \(0\)، ثم نتابع توسيع الأوراق حتى نحصل على \(n\) أوراق. إذا وسّعنا ورقة كلفتها \(c\)، فإننا نحذف تلك الورقة ونستبدل بها ورقتين جديدتين كلفتاهما \(c+1\) و\(c+4\). لهذا يتغير مجموع كلف الأوراق بمقدار
$$\Delta=(c+1)+(c+4)-c=c+5.$$
وإذا كانت كلف العقد الداخلية وفق ترتيب التوسيع هي \(c_1,c_2,\dots,c_{n-1}\)، فإن
$$\text{Cost}(n)=\sum_{k=1}^{n-1}(c_k+5)=5(n-1)+\sum_{k=1}^{n-1}c_k.$$
وهكذا تتحول المسألة كلها إلى إيجاد أصغر مجموع ممكن لكلف \(n-1\) عقدة داخلية.
كل حفيد لعقدة ما يكون أغلى من تلك العقدة نفسها، لأن كل حافة تضيف مقدارًا موجبًا. وهذا يعني أن أي مجموعة صالحة من العقد الداخلية تكون مغلقة بادئيًا تلقائيًا: فإذا كانت عقدة ما داخلية، فلا بد أن تكون كل أسلافها على الطريق إلى الجذر داخلية أيضًا.
وبالتالي فإن أصغر قيمة ممكنة للمجموع \(\sum c_k\) تتحقق بمجرد أخذ أرخص \(n-1\) عقدة في شجرة skew-cost اللانهائية. وهذا مكافئ تمامًا للقاعدة الجشعة التي تقول: وسّع دائمًا الورقة الأرخص المتاحة حاليًا. إذن فالترتيب الجشع هنا ليس حدسًا فقط، بل هو الوصف الدقيق للبنية المثلى.
لنعرّف \(f(c)\) بأنه عدد العقد في الشجرة اللانهائية التي تساوي كلفة مسارها تمامًا \(c\). لدينا \(f(0)=1\) للجذر، ونأخذ \(f(c)=0\) عندما تكون \(c\) سالبة. ولكل \(c\ge 1\)، فإن أي عقدة كلفتها \(c\) لا بد أن تنتهي بإحدى حالتين متنافيتين: إما حافة أخيرة كلفتها \(1\) قادمة من عقدة كلفتها \(c-1\)، أو حافة أخيرة كلفتها \(4\) قادمة من عقدة كلفتها \(c-4\). لذلك نحصل على العلاقة
$$f(c)=f(c-1)+f(c-4),\qquad f(0)=1,\qquad f(c)=0\text{ for }c<0.$$
هذه العلاقة التراجعية هي الكائن المركزي الذي تعتمد عليه التطبيقات الثلاثة. فهي تعطينا تعددية كل مستوى كلفة من غير الحاجة إلى بناء شجرة الترميز صراحة.
وهناك أيضًا تفسير توافقي يُستخدم باعتباره فحصًا مستقلاً. فإذا كانت كلفة عقدة ما تساوي \(c\)، وكان في مسارها بالضبط \(a\) من الحواف ذات الكلفة \(4\)، فإن عدد الحواف ذات الكلفة \(1\) يساوي \(c-4a\). وعندئذ يكون طول المسار كله \(c-3a\)، وعدد الكلمات من هذا النوع يساوي \(\binom{c-3a}{a}\). وبجمع جميع القيم المسموح بها لـ \(a\) نحصل على
$$f(c)=\sum_{a=0}^{\lfloor c/4\rfloor}\binom{c-3a}{a}.$$
وتتحقق نسخة C++ على مستويات كلفة صغيرة من أن هذه الصيغة ذات المعاملات الثنائية تطابق العلاقة التراجعية تمامًا، وهو ما يؤكد صحة النموذج من زاوية مستقلة.
لنكتب \(m=n-1\)، لأن هذا هو عدد العقد الداخلية التي يجب اختيارها. إذا مسحنا مستويات الكلفة تصاعديًا، فإن المستوى \(c\) يحتوي بالضبط على \(f(c)\) عقدة من هذه الكلفة يمكن أن تصبح عقدًا داخلية. لنعرّف الآن
$$A(C)=\sum_{c=0}^{C}f(c),\qquad B(C)=\sum_{c=0}^{C}c\,f(c).$$
وليكن \(C_\star\) أول مستوى يحقق \(A(C_\star)\ge m\). عندها تؤخذ جميع العقد التي كلفتها أقل من \(C_\star\) كاملةً، بينما يُستخدم المستوى الأخير جزئيًا فقط. لذلك
$$\sum_{k=1}^{m}c_k=B(C_\star-1)+C_\star\bigl(m-A(C_\star-1)\bigr),$$
ومن ثم يكون الجواب النهائي
$$\boxed{\text{Cost}(n)=5(n-1)+B(C_\star-1)+C_\star\bigl((n-1)-A(C_\star-1)\bigr).}$$
والتطبيقات تحسب هذه الكمية نفسها بشكل تزايدي: فهي تحتفظ بعدد العقد الداخلية التي استُهلكت حتى الآن، وبمجموع كلفها، وتتوقف عندما يكتمل الحد المطلوب وهو \(n-1\).
القيمة الاختبارية \(\text{Cost}(6)=35\) مضمنة في التطبيق الرئيسي. هنا \(m=n-1=5\)، ولذلك نحتاج إلى أرخص خمس كلف للعقد الداخلية. بداية العلاقة التراجعية هي
$$f(0)=1,\quad f(1)=1,\quad f(2)=1,\quad f(3)=1,\quad f(4)=2.$$
إذن فإن أول خمس كلف داخلية هي \(0,1,2,3,4\)، ومجموعها \(10\). وبالتعويض في الصيغة الأساسية نحصل على
$$\text{Cost}(6)=5\cdot 5+(0+1+2+3+4)=25+10=35.$$
ويمكن رؤية المثال نفسه مباشرة عبر توسعات الأوراق: \(0\to(1,4)\to(2,4,5)\to(3,4,5,6)\to(4,4,5,6,7)\to(4,5,5,6,7,8)\). ومجموع كلف الأوراق في النهاية يساوي فعلًا \(35\).
تتبع تطبيقات C++ وPython وJava الفكرة الإنتاجية نفسها. فهي تتعامل مع \(n-1\) على أنه عدد العقد الداخلية التي يجب اختيارها، وتولد القيم \(f(c)\) مستوىً بعد مستوى من العلاقة \(f(c)=f(c-1)+f(c-4)\)، ثم تجمع كلف أرخص العقد الداخلية.
وعند كل مستوى كلفة \(c\)، إذا رمزنا بعدد العقد الداخلية المتبقية بالرمز \(r\)، فإن التنفيذ يأخذ
$$\min\bigl(f(c),r\bigr)$$
عقدًا من تلك الطبقة، ويضيف \(c\) مضروبًا في هذا العدد إلى المجموع الجاري لكلف العقد الداخلية، ثم ينتقل إلى المستوى التالي. وما إن تكتمل حصة \(n-1\) حتى يضيف الحد الثابت \(5(n-1)\) ويخرج النتيجة النهائية.
ولهذا الغرض تُستخدم أنماط عددية واسعة عمدًا. Python تستفيد من الأعداد الصحيحة كبيرة الدقة المضمنة، وJava تعتمد على أعداد صحيحة ذات دقة اعتباطية، أما تنفيذ C++ فيستخدم نوعًا عدديًا أوسع لأن كلًا من التعدادات والمجاميع يتجاوز سريعًا حدود الحساب الصحيح المعتاد ذي 32 بت. كما تتضمن نسخة C++ طبقات تحقق إضافية: فهي تتأكد من القيمة المعروفة \(\text{Cost}(6)=35\)، وتقارن العلاقة التراجعية بالصيغة الثنائية لـ \(f(c)\)، ثم تطابق الحل الصيغوي مع محاكاة جشعة مباشرة بطابور أولوية على القيم الصغيرة.
لنرمز بـ \(C_\star\) إلى أكبر مستوى كلفة يجب الوصول إليه قبل جمع أول \(n-1\) عقدة داخلية كاملة. إن الحل الأساسي ينفذ مرورًا خطيًا وحيدًا على القيم \(0,1,\dots,C_\star\)، ولهذا يكون تعقيده الزمني \(O(C_\star)\).
أما جدول التعدديات فطوله أيضًا لا يتجاوز \(C_\star+1\)، ولذلك يكون التعقيد المكاني \(O(C_\star)\). وهذا أصغر بكثير من محاكاة جشعة صريحة باستخدام كومة حتى \(n=10^9\)، لأن تلك الطريقة تحتاج إلى جبهة ضخمة وتؤدي عملًا من رتبة \(O(n\log n)\). وهنا لا يُستخدم طابور الأولوية إلا في اختبارات التحقق الصغيرة، وليس في الحساب الفعلي.