Start from the source phrase "thereisasyetinsufficientdataforameaningfulanswer". Its letters form a multiset, and we consider every distinct word over the alphabet from a to z whose length is at most \(15\) and whose letter multiplicities do not exceed the available counts.
These words are ordered lexicographically, with the usual dictionary convention that a word comes before any longer word having it as a prefix. The task is to determine the ranks of five specified words, combine those ranks arithmetically, and then reconstruct the unique word at the resulting rank.
A brute-force list of all admissible words would be far too large. The successful approach is to count the size of every lexicographic subtree, then use those counts both for ranking and for unranking.
Let \(s_\ell\) be the multiplicity of letter \(\ell\) in the source phrase, and let \(L=15\) be the maximum allowed length. For any current prefix, write \(\mathbf c=(c_a,\dots,c_z)\) for the remaining letter counts and \(r\) for the number of positions still available.
Define \(F(\mathbf c,r)\) as the number of valid suffixes that can still be appended when the remaining stock is \(\mathbf c\) and at most \(r\) more letters may be used. The empty suffix is allowed, so it already contributes one possibility.
Therefore
$$F(\mathbf c,0)=1,$$
$$F(\mathbf c,r)=1+\sum_{\ell:\,c_\ell>0}F(\mathbf c-\mathbf e_\ell,r-1).$$
The leading \(1\) means “stop here”. Every term in the sum means “choose one available letter first, then count everything below that child”. This is exactly the size of the lexicographic subtree rooted at the current prefix.
The exact letter labels do not matter for subtree size; only the multiset of remaining multiplicities matters. If two states differ only by renaming letters, they generate isomorphic subtrees and must have the same count.
So the implementations replace \(\mathbf c\) by a canonical representative \(\lambda(\mathbf c)\): take the positive entries of \(\mathbf c\), sort them in nonincreasing order, and discard trailing zeros. The dynamic program is memoized on the pair \((\lambda(\mathbf c),r)\).
This is a major compression step. For example, the states \((2,1,1,0,\dots)\) and \((1,2,1,0,\dots)\) become the same canonical key \((2,1,1)\). If equal parts appear, they are still summed separately in the recurrence because they correspond to different actual letters with the same remaining multiplicity.
Let \(P_{\mathbf c,r}(w)\) denote the 1-based position of word \(w\) inside the subtree determined by \((\mathbf c,r)\). The empty word has position \(1\):
$$P_{\mathbf c,r}(\varepsilon)=1.$$
If \(w=w_1w_2\dots w_t\) is nonempty, then every legal first letter smaller than \(w_1\) contributes an entire subtree that lies before \(w\). Hence
$$P_{\mathbf c,r}(w)=1+\sum_{\ell\lt w_1,\ c_\ell>0}F(\lambda(\mathbf c-\mathbf e_\ell),r-1)+P_{\mathbf c-\mathbf e_{w_1},\,r-1}(w_2\dots w_t).$$
The ranking arithmetic in the implementations is performed with the 0-based value \(R(w)=P(w)-1\). Subtracting \(1\) removes the root empty word and makes addition and subtraction of ranks cleaner.
To recover a word from its 0-based rank \(R\), first switch to the 1-based position \(Q=R+1\). If \(Q=1\), the correct continuation is empty. Otherwise discard that empty option by replacing \(Q\leftarrow Q-1\).
Now scan letters in increasing order. For each candidate letter \(\ell\) with \(c_\ell>0\), compute
$$T_\ell=F(\lambda(\mathbf c-\mathbf e_\ell),r-1).$$
If \(Q>T_\ell\), the entire \(\ell\)-subtree lies before the target, so set \(Q\leftarrow Q-T_\ell\) and continue. Otherwise \(\ell\) is the next letter of the answer, and the same procedure recurses one level deeper. Because the subtree counts are exact, this reconstruction is unique.
The five words supplied by the problem are legionary, calorimeters, annihilate, orchestrated, and fluttering. If their 0-based ranks are \(R_1,R_2,R_3,R_4,R_5\), then the target rank is
$$T=R_1+R_2-R_3+R_4-R_5.$$
The final answer is the word obtained by unranking \(T\) in the full initial state defined by the source phrase and the depth limit \(15\).
Take a toy multiset with two a's, one b, and maximum length \(2\). The canonical state is \((2,1)\). Its subtree size satisfies
$$F((2,1),2)=1+F((1,1),1)+F((2),1).$$
Now \(F((1,1),1)=3\) because the admissible suffixes are \(\varepsilon\), a, and b, while \(F((2),1)=2\) because the admissible suffixes are \(\varepsilon\) and a. Therefore
$$F((2,1),2)=1+3+2=6.$$
The six words in order are
$$\varepsilon,\ a,\ aa,\ ab,\ b,\ ba.$$
So \(P(ab)=4\) and \(R(ab)=3\). Running the inverse procedure on rank \(3\) returns ab again. This miniature example mirrors the full solution: subtree counting first, then ranking or unranking by skipping whole branches at a time.
The C++, Python, and Java implementations begin by counting the source letters once and fixing the maximum depth at \(15\). They then memoize subtree sizes using the canonical sorted multiplicities together with the remaining depth.
Each ranking query processes its word from left to right. At every position it adds the sizes of all lexicographically earlier sibling branches, consumes the actual next letter, and continues on the smaller remaining state. This produces a 1-based tree position, which is converted to a 0-based rank for the final arithmetic.
The unranking phase performs the complementary search. It tests candidate letters in alphabetical order, subtracts whole subtree sizes when those branches lie entirely before the target, and descends into the first branch that contains the desired position.
All five rank queries and the final unranking call share the same memoized subtree counts, so the expensive combinatorial work is done once and then reused.
Let \(\mathcal S\) be the set of reachable canonical states \((\lambda,r)\). Each such state is evaluated once, and each evaluation inspects at most \(26\) letter slots, so the dynamic programming phase costs \(O(26|\mathcal S|)\) time and \(O(|\mathcal S|)\) memory. Since the sorting step is over at most \(26\) entries, it only affects the constant factor.
If a queried word has length \(m\le 15\), then one ranking or unranking operation examines at most \(26\) candidates at each of the \(m\) levels, so its cost is \(O(26m)\) after memoization. In practice, runtime is dominated by building the cache of subtree sizes, not by the final six queries.
Ausgangspunkt ist die Quellphrase "thereisasyetinsufficientdataforameaningfulanswer". Ihre Buchstaben bilden ein Multiset, und betrachtet werden alle verschiedenen Wörter über dem Alphabet von a bis z, deren Länge höchstens \(15\) ist und deren Buchstabenhäufigkeiten die verfügbaren Vorkommen nicht überschreiten.
Diese Wörter werden lexikographisch geordnet, wobei wie im Wörterbuch ein Wort vor jeder längeren Fortsetzung mit demselben Präfix steht. Gesucht ist nicht die vollständige Auflistung aller Wörter, sondern zunächst die Position von fünf vorgegebenen Wörtern, dann eine arithmetische Kombination dieser Positionen und schließlich das Wort an der so erhaltenen Zielposition.
Eine naive Enumeration wäre viel zu groß. Der funktionierende Weg besteht darin, für jedes Präfix die Größe seines lexikographischen Teilbaums zu zählen und dieselben Zählwerte sowohl für das Ranking als auch für das Unranking zu verwenden.
Sei \(s_\ell\) die Häufigkeit des Buchstabens \(\ell\) in der Quellphrase und \(L=15\) die maximale Wortlänge. Für ein beliebiges aktuelles Präfix bezeichne \(\mathbf c=(c_a,\dots,c_z)\) die verbleibenden Buchstabenzahlen und \(r\) die noch verfügbaren Positionen.
Definiere \(F(\mathbf c,r)\) als die Anzahl gültiger Suffixe, die noch angehängt werden können, wenn der verbleibende Vorrat \(\mathbf c\) ist und höchstens \(r\) weitere Buchstaben benutzt werden dürfen. Das leere Suffix ist erlaubt und liefert daher sofort eine Möglichkeit.
Also gilt
$$F(\mathbf c,0)=1,$$
$$F(\mathbf c,r)=1+\sum_{\ell:\,c_\ell>0}F(\mathbf c-\mathbf e_\ell,r-1).$$
Die führende \(1\) bedeutet „hier stoppen“. Jeder Summand bedeutet „einen verfügbaren Buchstaben zuerst wählen und dann alles unter dem entsprechenden Kindknoten zählen“. Genau das ist die Größe des lexikographischen Teilbaums des aktuellen Präfixes.
Für die Größe eines Teilbaums sind die konkreten Buchstabenbezeichnungen unwichtig; entscheidend ist nur das Multiset der verbleibenden Häufigkeiten. Zwei Zustände, die sich nur durch Umbenennung von Buchstaben unterscheiden, erzeugen isomorphe Teilbäume und müssen daher dieselbe Anzahl besitzen.
Deshalb ersetzen die Implementierungen \(\mathbf c\) durch einen kanonischen Repräsentanten \(\lambda(\mathbf c)\): Man nimmt die positiven Einträge von \(\mathbf c\), sortiert sie nichtzunehmend und entfernt die Nullen am Ende. Der DP-Cache wird auf dem Paar \((\lambda(\mathbf c),r)\) geführt.
Das reduziert die Zahl der Zustände drastisch. So werden etwa \((2,1,1,0,\dots)\) und \((1,2,1,0,\dots)\) beide zum selben Schlüssel \((2,1,1)\). Treten gleiche Teile mehrfach auf, werden sie in der Rekursion trotzdem getrennt aufsummiert, weil sie verschiedene reale Buchstaben mit derselben Resthäufigkeit repräsentieren.
Sei \(P_{\mathbf c,r}(w)\) die 1-basierte Position des Wortes \(w\) innerhalb des Teilbaums zum Zustand \((\mathbf c,r)\). Das leere Wort hat Position \(1\):
$$P_{\mathbf c,r}(\varepsilon)=1.$$
Ist \(w=w_1w_2\dots w_t\) nicht leer, dann trägt jeder zulässige erste Buchstabe kleiner als \(w_1\) einen ganzen Teilbaum bei, der vor \(w\) liegt. Daher
$$P_{\mathbf c,r}(w)=1+\sum_{\ell\lt w_1,\ c_\ell>0}F(\lambda(\mathbf c-\mathbf e_\ell),r-1)+P_{\mathbf c-\mathbf e_{w_1},\,r-1}(w_2\dots w_t).$$
Für die arithmetische Kombination benutzt die Implementierung den 0-basierten Rang \(R(w)=P(w)-1\). Das Subtrahieren von \(1\) entfernt das leere Wort an der Wurzel und macht die spätere Rechnung natürlicher.
Um aus einem 0-basierten Rang \(R\) wieder ein Wort zu gewinnen, wechselt man zunächst zur 1-basierten Position \(Q=R+1\). Ist \(Q=1\), dann ist die richtige Fortsetzung leer. Andernfalls wird diese leere Möglichkeit entfernt, also \(Q\leftarrow Q-1\) gesetzt.
Danach werden die Buchstaben in aufsteigender Reihenfolge geprüft. Für jeden Kandidaten \(\ell\) mit \(c_\ell>0\) berechnet man
$$T_\ell=F(\lambda(\mathbf c-\mathbf e_\ell),r-1).$$
Falls \(Q>T_\ell\), liegt der gesamte \(\ell\)-Teilbaum vor dem Ziel und man setzt \(Q\leftarrow Q-T_\ell\). Andernfalls ist \(\ell\) der nächste Buchstabe der Antwort, und dasselbe Verfahren wird eine Ebene tiefer fortgesetzt. Weil die Teilbaumgrößen exakt sind, ist die Rekonstruktion eindeutig.
Die fünf im Problem verwendeten Wörter sind legionary, calorimeters, annihilate, orchestrated und fluttering. Sind ihre 0-basierten Ränge \(R_1,R_2,R_3,R_4,R_5\), dann lautet der Zielrang
$$T=R_1+R_2-R_3+R_4-R_5.$$
Die endgültige Lösung ist also das Wort, das man durch Unranking von \(T\) im vollständigen Anfangszustand der Quellphrase mit Tiefengrenze \(15\) erhält.
Betrachte ein Spielzeugbeispiel mit zwei a, einem b und maximaler Länge \(2\). Der kanonische Zustand ist \((2,1)\). Seine Teilbaumgröße erfüllt
$$F((2,1),2)=1+F((1,1),1)+F((2),1).$$
Dabei ist \(F((1,1),1)=3\), weil die zulässigen Suffixe \(\varepsilon\), a und b sind, und \(F((2),1)=2\), weil dort nur \(\varepsilon\) und a möglich sind. Also
$$F((2,1),2)=1+3+2=6.$$
Die sechs Wörter in Reihenfolge sind
$$\varepsilon,\ a,\ aa,\ ab,\ b,\ ba.$$
Damit gilt \(P(ab)=4\) und \(R(ab)=3\). Führt man das inverse Verfahren mit Rang \(3\) aus, erhält man wieder ab. Genau dieses Zusammenspiel aus Teilbaumzählung, Ranking und Unranking verwendet auch die vollständige Lösung.
Die C++-, Python- und Java-Implementierungen zählen zuerst einmalig die Buchstaben der Quellphrase und fixieren die maximale Tiefe auf \(15\). Anschließend speichern sie Teilbaumgrößen memoisiert anhand der kanonisch sortierten Restmultiplizitäten zusammen mit der verbleibenden Tiefe.
Jede Ranking-Anfrage verarbeitet ihr Wort von links nach rechts. An jeder Stelle werden die Größen aller lexikographisch früheren Geschwisterzweige addiert, dann wird der tatsächliche nächste Buchstabe verbraucht, und der Prozess läuft im kleineren Restzustand weiter. Das liefert zunächst eine 1-basierte Baumposition, aus der der 0-basierte Rang für die Endrechnung gewonnen wird.
Das Unranking arbeitet komplementär dazu. Es testet Kandidatenbuchstaben in alphabetischer Reihenfolge, zieht ganze Teilbaumgrößen ab, solange diese vollständig vor dem Ziel liegen, und steigt in den ersten Zweig hinab, der die gesuchte Position enthält.
Alle fünf Rangabfragen und der abschließende Unranking-Schritt benutzen denselben Cache von Teilbaumgrößen. Der teure kombinatorische Teil wird also einmal aufgebaut und danach wiederverwendet.
Sei \(\mathcal S\) die Menge der erreichbaren kanonischen Zustände \((\lambda,r)\). Jeder dieser Zustände wird genau einmal ausgewertet, und jede Auswertung betrachtet höchstens \(26\) Buchstabenslots. Damit kostet die DP-Phase \(O(26|\mathcal S|)\) Zeit und \(O(|\mathcal S|)\) Speicher. Da das Sortieren über höchstens \(26\) Einträge läuft, beeinflusst es nur den konstanten Faktor.
Hat ein abgefragtes Wort Länge \(m\le 15\), dann untersucht ein Ranking- oder Unranking-Lauf an jeder der \(m\) Ebenen höchstens \(26\) Kandidaten. Nach der Memoisierung ergibt sich also \(O(26m)\). Praktisch wird die Laufzeit fast vollständig vom Aufbau des Caches dominiert, nicht von den sechs abschließenden Anfragen.
Başlangıç noktası "thereisasyetinsufficientdataforameaningfulanswer" ifadesidir. Bu ifadedeki harfler bir çoklu küme oluşturur; biz de uzunluğu en fazla \(15\) olan ve her harfi eldeki sayısından fazla kullanmayan tüm farklı kelimeleri inceleriz.
Bu kelimeler sözlük sırasına göre dizilir; yani bir kelime, kendi ön eki olduğu daha uzun tüm kelimelerden önce gelir. Amaç bütün kelimeleri tek tek üretmek değil, önce beş belirli kelimenin sırasını bulmak, sonra bu sıraları aritmetik olarak birleştirmek ve son olarak ortaya çıkan sıradaki kelimeyi geri kurmaktır.
Doğrudan listeleme çok büyük olur. Etkili yöntem, her ön ekin altında kaç kelime bulunduğunu saymak ve aynı sayımları hem sıralama hem de ters sıralama için kullanmaktır.
\(s_\ell\), kaynak ifadede \(\ell\) harfinin adedi olsun; ayrıca \(L=15\) azami kelime uzunluğudur. Herhangi bir mevcut ön ek için \(\mathbf c=(c_a,\dots,c_z)\) kalan harf sayılarını, \(r\) ise kullanılabilecek kalan konum sayısını göstersin.
\(F(\mathbf c,r)\), kalan stok \(\mathbf c\) iken ve en fazla \(r\) harf daha kullanılabiliyorken eklenebilecek geçerli son ek sayısı olsun. Boş son ek de izinli olduğu için baştan bir olasılık zaten vardır.
Dolayısıyla
$$F(\mathbf c,0)=1,$$
$$F(\mathbf c,r)=1+\sum_{\ell:\,c_\ell>0}F(\mathbf c-\mathbf e_\ell,r-1).$$
Baştaki \(1\), “burada dur” seçeneğidir. Toplamdaki her terim ise “önce uygun bir harf seç, sonra o çocuğun altındaki bütün devamları say” anlamına gelir. Bu değer tam olarak mevcut ön ekin sözlük ağacındaki alt ağacının boyudur.
Bir alt ağacın boyu için harflerin isimleri önemli değildir; önemli olan yalnızca kalan adetlerin çoklu kümesidir. Sadece harf isimleri değiştirilmiş iki durum izomorfik alt ağaçlar üretir ve aynı sayıya sahip olmalıdır.
Bu yüzden uygulamalar \(\mathbf c\) vektörünü kanonik bir gösterime dönüştürür: pozitif girişler alınır, azalmayan değil azalan sıraya dizilir ve sondaki sıfırlar atılır. Bu kanonik biçimi \(\lambda(\mathbf c)\) ile gösterelim. Dinamik programlama önbelleği \((\lambda(\mathbf c),r)\) çifti üzerinde tutulur.
Bu sıkıştırma çok etkilidir. Örneğin \((2,1,1,0,\dots)\) ile \((1,2,1,0,\dots)\) aynı anahtara, yani \((2,1,1)\)'e gider. Eşit parçalar varsa, yine de özyinelemede ayrı ayrı toplanırlar; çünkü bunlar aynı kalan sayıya sahip farklı gerçek harfleri temsil eder.
\(P_{\mathbf c,r}(w)\), \(w\) kelimesinin \((\mathbf c,r)\) durumundaki alt ağaç içindeki 1-bazlı konumu olsun. Boş kelimenin konumu \(1\)'dir:
$$P_{\mathbf c,r}(\varepsilon)=1.$$
Eğer \(w=w_1w_2\dots w_t\) boş değilse, \(w_1\)'den küçük her uygun ilk harf, \(w\)'den önce gelen tam bir alt ağaç katkısı yapar. Bu nedenle
$$P_{\mathbf c,r}(w)=1+\sum_{\ell\lt w_1,\ c_\ell>0}F(\lambda(\mathbf c-\mathbf e_\ell),r-1)+P_{\mathbf c-\mathbf e_{w_1},\,r-1}(w_2\dots w_t).$$
Uygulamalardaki aritmetik birleştirme 0-bazlı sıra değeriyle yapılır: \(R(w)=P(w)-1\). Böylece kökteki boş kelime çıkarılmış olur ve toplama-çıkarma daha doğal hale gelir.
0-bazlı bir sıra \(R\) verildiğinde önce 1-bazlı konuma geçilir: \(Q=R+1\). Eğer \(Q=1\) ise doğru devam boş dizidir. Aksi halde boş seçeneği atmak için \(Q\leftarrow Q-1\) yapılır.
Sonra harfler alfabetik sırayla taranır. \(c_\ell>0\) olan her aday harf \(\ell\) için
$$T_\ell=F(\lambda(\mathbf c-\mathbf e_\ell),r-1)$$
hesaplanır. Eğer \(Q>T_\ell\) ise hedef bu alt ağacın sonrasındadır; o zaman \(Q\leftarrow Q-T_\ell\) yapılıp sıradaki harfe geçilir. Aksi halde cevabın sıradaki harfi \(\ell\)'dir ve aynı işlem bir seviye aşağıda sürdürülür. Alt ağaç boyları tam olduğu için sonuç tektir.
Problemde verilen beş kelime legionary, calorimeters, annihilate, orchestrated ve fluttering'dir. Bunların 0-bazlı sıraları \(R_1,R_2,R_3,R_4,R_5\) ise hedef sıra
$$T=R_1+R_2-R_3+R_4-R_5$$
olur. Nihai cevap, kaynak ifadenin tam başlangıç durumunda ve derinlik sınırı \(15\) iken \(T\) için yapılan ters sıralama sonucunda elde edilen kelimedir.
Oyuncak bir örnek olarak iki tane a, bir tane b ve azami uzunluk \(2\) alalım. Kanonik durum \((2,1)\)'dir ve alt ağaç boyu
$$F((2,1),2)=1+F((1,1),1)+F((2),1)$$
eşitliğini sağlar. Burada \(F((1,1),1)=3\) çünkü izinli son ekler \(\varepsilon\), a ve b'dir; ayrıca \(F((2),1)=2\) çünkü sadece \(\varepsilon\) ve a mümkündür. Dolayısıyla
$$F((2,1),2)=1+3+2=6.$$
Sıralı altı kelime şunlardır:
$$\varepsilon,\ a,\ aa,\ ab,\ b,\ ba.$$
Buna göre \(P(ab)=4\) ve \(R(ab)=3\) olur. Ters işlem rank \(3\) için çalıştırıldığında yine ab elde edilir. Küçük örnek, tam çözümdeki temel fikri aynen gösterir: önce alt ağaç sayımı, sonra büyük dalları atlayarak sıralama veya ters sıralama.
C++, Python ve Java uygulamaları önce kaynak ifadedeki harfleri bir kez sayar ve azami derinliği \(15\) olarak sabitler. Daha sonra kanonik sıralı çokluklar ile kalan derinlik çiftine göre alt ağaç boylarını önbelleğe alırlar.
Her sıralama sorgusu kelimeyi soldan sağa işler. Her konumda, sözlükçe daha küçük kardeş dalların boyları toplanır; ardından gerçek sonraki harf tüketilir ve daha küçük kalan durumda devam edilir. Böylece önce 1-bazlı ağaç konumu, oradan da son aritmetik için 0-bazlı sıra değeri elde edilir.
Ters sıralama aşaması bunun tamamlayıcısıdır. Aday harfler alfabetik sırayla denenir; hedefin tamamen önünde kalan dalların boyları çıkarılır ve aranan konumu içeren ilk dala inilir.
Beş sıralama sorgusunun tamamı ve son ters sıralama çağrısı aynı önbelleklenmiş alt ağaç boylarını paylaşır. Böylece pahalı birleşimsel iş bir kez yapılır, sonra tekrar kullanılır.
\(\mathcal S\), erişilebilen kanonik durumların \((\lambda,r)\) kümesi olsun. Her durum yalnızca bir kez hesaplanır ve her hesaplama en fazla \(26\) harf yuvasını inceler. Bu yüzden dinamik programlama aşaması \(O(26|\mathcal S|)\) zaman ve \(O(|\mathcal S|)\) bellek kullanır. Sıralama işlemi en fazla \(26\) giriş üzerinde yapıldığı için yalnızca sabit çarpanı etkiler.
Uzunluğu \(m\le 15\) olan bir kelime için tek bir sıralama ya da ters sıralama işlemi, \(m\) seviyenin her birinde en fazla \(26\) aday inceler; dolayısıyla önbelleklemeden sonra maliyet \(O(26m)\)'dir. Pratikte toplam süreyi belirleyen şey, son altı sorgu değil, alt ağaç önbelleğinin doldurulmasıdır.
Partimos de la frase fuente "thereisasyetinsufficientdataforameaningfulanswer". Sus letras forman un multiconjunto, y se consideran todas las palabras distintas sobre el alfabeto de a a z cuya longitud es como mucho \(15\) y cuyas multiplicidades no superan las apariciones disponibles.
Esas palabras se ordenan lexicográficamente, con la convención habitual de diccionario: una palabra aparece antes que cualquier extensión más larga que la tenga como prefijo. El objetivo no es generar toda la lista, sino hallar primero los rangos de cinco palabras dadas, combinar esos rangos aritméticamente y luego reconstruir la palabra situada en la posición resultante.
Una enumeración directa sería demasiado grande. La idea eficaz es contar el tamaño de cada subárbol lexicográfico y reutilizar esos mismos conteos tanto para ranking como para unranking.
Sea \(s_\ell\) la multiplicidad de la letra \(\ell\) en la frase fuente y sea \(L=15\) la longitud máxima permitida. Para cualquier prefijo actual, escribimos \(\mathbf c=(c_a,\dots,c_z)\) para los conteos restantes y \(r\) para el número de posiciones todavía disponibles.
Definimos \(F(\mathbf c,r)\) como el número de sufijos válidos que todavía pueden añadirse cuando el stock restante es \(\mathbf c\) y pueden usarse a lo sumo \(r\) letras más. El sufijo vacío está permitido, así que ya aporta una posibilidad.
Por tanto,
$$F(\mathbf c,0)=1,$$
$$F(\mathbf c,r)=1+\sum_{\ell:\,c_\ell>0}F(\mathbf c-\mathbf e_\ell,r-1).$$
El \(1\) inicial significa “detenerse aquí”. Cada sumando significa “elegir primero una letra disponible y contar después todas las continuaciones bajo ese hijo”. Ese valor es exactamente el tamaño del subárbol lexicográfico del prefijo actual.
Las etiquetas concretas de las letras no importan para el tamaño del subárbol; lo que importa es solo el multiconjunto de multiplicidades restantes. Si dos estados difieren únicamente por renombrar letras, generan subárboles isomorfos y deben tener el mismo conteo.
Por eso las implementaciones sustituyen \(\mathbf c\) por un representante canónico \(\lambda(\mathbf c)\): se toman las entradas positivas, se ordenan de mayor a menor y se eliminan los ceros finales. La memoización se hace sobre el par \((\lambda(\mathbf c),r)\).
Esta compresión es crucial. Por ejemplo, \((2,1,1,0,\dots)\) y \((1,2,1,0,\dots)\) se convierten ambos en la misma clave \((2,1,1)\). Si hay partes iguales, aun así se suman por separado en la recurrencia, porque representan letras distintas con la misma disponibilidad restante.
Sea \(P_{\mathbf c,r}(w)\) la posición 1-basada de la palabra \(w\) dentro del subárbol determinado por \((\mathbf c,r)\). La palabra vacía tiene posición \(1\):
$$P_{\mathbf c,r}(\varepsilon)=1.$$
Si \(w=w_1w_2\dots w_t\) no es vacía, entonces cada primera letra válida menor que \(w_1\) aporta un subárbol completo que queda antes de \(w\). En consecuencia,
$$P_{\mathbf c,r}(w)=1+\sum_{\ell\lt w_1,\ c_\ell>0}F(\lambda(\mathbf c-\mathbf e_\ell),r-1)+P_{\mathbf c-\mathbf e_{w_1},\,r-1}(w_2\dots w_t).$$
La aritmética final de las implementaciones usa el rango 0-basado \(R(w)=P(w)-1\). Restar \(1\) elimina la palabra vacía de la raíz y hace más natural la combinación lineal posterior.
Para recuperar una palabra a partir de su rango 0-basado \(R\), primero se pasa a la posición 1-basada \(Q=R+1\). Si \(Q=1\), la continuación correcta es vacía. En caso contrario, se descarta esa opción vacía poniendo \(Q\leftarrow Q-1\).
Luego se recorren las letras en orden creciente. Para cada candidata \(\ell\) con \(c_\ell>0\), se calcula
$$T_\ell=F(\lambda(\mathbf c-\mathbf e_\ell),r-1).$$
Si \(Q>T_\ell\), todo el subárbol de \(\ell\) queda antes del objetivo, así que se actualiza \(Q\leftarrow Q-T_\ell\) y se sigue con la letra siguiente. En caso contrario, \(\ell\) es la siguiente letra de la respuesta y el mismo procedimiento continúa un nivel más abajo. Como los tamaños de subárbol son exactos, la reconstrucción es única.
Las cinco palabras dadas por el problema son legionary, calorimeters, annihilate, orchestrated y fluttering. Si sus rangos 0-basados son \(R_1,R_2,R_3,R_4,R_5\), entonces el rango objetivo es
$$T=R_1+R_2-R_3+R_4-R_5.$$
La respuesta final es la palabra obtenida al hacer unranking de \(T\) en el estado inicial completo de la frase fuente con límite de profundidad \(15\).
Tomemos un ejemplo pequeño con dos a, una b y longitud máxima \(2\). El estado canónico es \((2,1)\), y el tamaño del subárbol cumple
$$F((2,1),2)=1+F((1,1),1)+F((2),1).$$
Aquí \(F((1,1),1)=3\) porque los sufijos válidos son \(\varepsilon\), a y b, mientras que \(F((2),1)=2\) porque solo son posibles \(\varepsilon\) y a. Por lo tanto,
$$F((2,1),2)=1+3+2=6.$$
Las seis palabras en orden son
$$\varepsilon,\ a,\ aa,\ ab,\ b,\ ba.$$
Así, \(P(ab)=4\) y \(R(ab)=3\). Si aplicamos el procedimiento inverso al rango \(3\), recuperamos de nuevo ab. Este ejemplo mínimo muestra exactamente cómo encajan el conteo de subárboles, el ranking y el unranking.
Las implementaciones en C++, Python y Java comienzan contando una sola vez las letras de la frase fuente y fijando la profundidad máxima en \(15\). Después memoizan los tamaños de subárbol usando como clave las multiplicidades canónicas ordenadas junto con la profundidad restante.
Cada consulta de ranking procesa la palabra de izquierda a derecha. En cada posición suma los tamaños de todas las ramas hermanas lexicográficamente anteriores, consume la letra real siguiente y continúa con el estado restante más pequeño. Así obtiene primero una posición 1-basada en el árbol y luego el rango 0-basado usado en la combinación aritmética.
La fase de unranking realiza la operación complementaria. Prueba letras candidatas en orden alfabético, resta tamaños completos de subárbol cuando esas ramas quedan totalmente antes del objetivo y desciende a la primera rama que contiene la posición buscada.
Las cinco consultas de ranking y la llamada final de unranking comparten el mismo caché de tamaños de subárbol. De ese modo, el trabajo combinatorio costoso se hace una vez y luego se reutiliza.
Sea \(\mathcal S\) el conjunto de estados canónicos alcanzables \((\lambda,r)\). Cada estado se evalúa una sola vez, y cada evaluación inspecciona como máximo \(26\) posiciones de letra, así que la fase de programación dinámica cuesta \(O(26|\mathcal S|)\) tiempo y \(O(|\mathcal S|)\) memoria. Como la ordenación se hace sobre como mucho \(26\) entradas, solo afecta al factor constante.
Si una palabra consultada tiene longitud \(m\le 15\), entonces una operación de ranking o unranking examina a lo sumo \(26\) candidatos en cada uno de los \(m\) niveles, por lo que su coste es \(O(26m)\) una vez que la memoización está llena. En la práctica, el tiempo total está dominado por construir el caché de subárboles, no por las seis consultas finales.
题目的起点是字符串“thereisasyetinsufficientdataforameaningfulanswer”。它提供了一个字母多重集，我们要考虑所有由字母 a 到 z 构成、长度不超过 \(15\)、且每个字母使用次数不超过该多重集上限的不同单词。
这些单词按字典序排列，并采用通常的词典约定：一个单词排在任何以它为前缀的更长单词之前。题目并不是要把全部单词暴力列出来，而是先求出五个指定单词的排名，再把这些排名做加减组合，最后反过来求出该目标排名对应的单词。
直接枚举会非常庞大。真正可行的方法，是先统计每个前缀对应的字典序子树大小，然后用同一组计数同时完成“单词到排名”和“排名到单词”这两个方向的计算。
记 \(s_\ell\) 为源字符串中字母 \(\ell\) 的出现次数，记 \(L=15\) 为允许的最大长度。对任意当前前缀，设 \(\mathbf c=(c_a,\dots,c_z)\) 为剩余字母计数，\(r\) 为还可以继续使用的位置数。
定义 \(F(\mathbf c,r)\) 为：当剩余库存为 \(\mathbf c\)，并且最多还能再放 \(r\) 个字母时，可以补在当前前缀后面的合法后缀总数。空后缀是允许的，所以它本身就贡献 \(1\) 种可能。
因此有
$$F(\mathbf c,0)=1,$$
$$F(\mathbf c,r)=1+\sum_{\ell:\,c_\ell>0}F(\mathbf c-\mathbf e_\ell,r-1).$$
前面的那个 \(1\) 表示“此处停止，不再加字母”。求和中的每一项表示“先选一个当前仍可用的字母，再统计该子节点下面的全部延伸”。所以 \(F(\mathbf c,r)\) 正好就是当前前缀在字典序树中的子树大小。
对子树大小来说，字母本身的名字并不重要，真正重要的是“剩余次数的多重集”。如果两个状态只是把若干字母重新命名，那么它们生成的子树结构完全同构，因此计数也必然相同。
基于这一点，程序把 \(\mathbf c\) 替换成一个规范表示 \(\lambda(\mathbf c)\)：取出所有正数项，按不增顺序排序，并丢掉末尾的零。动态规划缓存只按 \((\lambda(\mathbf c),r)\) 这一对参数建立。
这是压缩状态数的关键一步。例如 \((2,1,1,0,\dots)\) 与 \((1,2,1,0,\dots)\) 都会被规约成同一个键 \((2,1,1)\)。需要注意的是，如果排序后出现相同的部分，它们在递推求和时仍要逐个计入，因为那代表“不同字母恰好拥有相同剩余次数”，而不是同一个选择被合并掉。
设 \(P_{\mathbf c,r}(w)\) 表示单词 \(w\) 在状态 \((\mathbf c,r)\) 所对应子树中的 1 基位置。空单词的位置定义为 \(1\)：
$$P_{\mathbf c,r}(\varepsilon)=1.$$
若 \(w=w_1w_2\dots w_t\) 非空，那么所有首字母严格小于 \(w_1\) 且当前可用的分支，都会整体排在 \(w\) 前面。因此有
$$P_{\mathbf c,r}(w)=1+\sum_{\ell\lt w_1,\ c_\ell>0}F(\lambda(\mathbf c-\mathbf e_\ell),r-1)+P_{\mathbf c-\mathbf e_{w_1},\,r-1}(w_2\dots w_t).$$
实现里真正参与最后加减运算的是 0 基排名 \(R(w)=P(w)-1\)。减去这 \(1\) 的含义，就是把根节点处那个空单词从算术表达式中去掉，使后续的加减更加自然。
如果已知一个 0 基排名 \(R\)，先把它改写成 1 基位置 \(Q=R+1\)。当 \(Q=1\) 时，说明正确的延伸就是空串。否则先把空串这个选择去掉，也就是令 \(Q\leftarrow Q-1\)。
然后按字母升序扫描所有候选字母。对于每个满足 \(c_\ell>0\) 的字母 \(\ell\)，计算
$$T_\ell=F(\lambda(\mathbf c-\mathbf e_\ell),r-1).$$
如果 \(Q>T_\ell\)，说明整个 \(\ell\) 分支都排在目标之前，于是可直接令 \(Q\leftarrow Q-T_\ell\) 并跳过整棵子树。否则，\(\ell\) 就是答案的下一个字母，再在更深一层重复同样的过程。因为每棵子树的大小都被准确计算，所以反排名得到的单词是唯一的。
题目指定的五个单词是 legionary、calorimeters、annihilate、orchestrated 和 fluttering。如果它们对应的 0 基排名分别记为 \(R_1,R_2,R_3,R_4,R_5\)，那么目标排名就是
$$T=R_1+R_2-R_3+R_4-R_5.$$
最终答案，就是在完整源状态和长度上限 \(15\) 下，对 \(T\) 执行一次反排名所得到的单词。
考虑一个玩具例子：字母库存为两个 a 和一个 b，最大长度为 \(2\)。这时规范状态是 \((2,1)\)，其子树大小满足
$$F((2,1),2)=1+F((1,1),1)+F((2),1).$$
其中 \(F((1,1),1)=3\)，因为合法后缀是 \(\varepsilon\)、a、b；而 \(F((2),1)=2\)，因为合法后缀只有 \(\varepsilon\) 和 a。所以
$$F((2,1),2)=1+3+2=6.$$
按顺序列出的六个单词是
$$\varepsilon,\ a,\ aa,\ ab,\ b,\ ba.$$
于是 \(P(ab)=4\)，对应的 0 基排名是 \(R(ab)=3\)。如果把排名 \(3\) 送入反排名过程，得到的又是 ab。这个小例子完整展示了正式解法中的三件事如何配合：先数子树，再跳过整棵分支来做排名或反排名。
C++、Python 和 Java 版本都会先统计源字符串中的字母个数，并把最大深度固定为 \(15\)。随后，它们把“规范化后的剩余重数”和“剩余深度”作为键，对所有子树大小进行记忆化缓存。
对一个给定单词求排名时，程序从左到右处理它的每个字符。在当前位置上，先把所有字典序更小的兄弟分支的子树大小累加起来，再消耗目标字符，进入更小的剩余状态继续处理。这样先得到的是树中的 1 基位置，再换算成最后算式需要的 0 基排名。
反排名阶段执行的是互补操作。程序按字母顺序尝试候选分支：如果某一整棵子树完全位于目标之前，就直接减去这棵子树的大小；一旦发现目标落在当前分支内部，就把该字母写入答案并继续向下递归。
五次排名查询和最后一次反排名，共享同一份子树计数缓存。因此最贵的组合计数工作只做一次，后续操作都只是重复利用这些结果。
记 \(\mathcal S\) 为所有可达规范状态 \((\lambda,r)\) 的集合。每个状态只会被求值一次，而每次求值至多检查 \(26\) 个字母位置，因此动态规划阶段的时间复杂度是 \(O(26|\mathcal S|)\)，空间复杂度是 \(O(|\mathcal S|)\)。规范化时的排序长度最多也是 \(26\)，所以它只影响常数因子。
如果某个查询单词长度为 \(m\le 15\)，那么一次排名或反排名在 \(m\) 层中每层至多查看 \(26\) 个候选，因此在缓存已经建立后，其代价为 \(O(26m)\)。实际运行时，主要耗时来自建立子树计数缓存，而不是最后这六次查询。
Исходной точкой служит строка "thereisasyetinsufficientdataforameaningfulanswer". Ее буквы задают мультимножество, и рассматриваются все различные слова над алфавитом от a до z, длина которых не превосходит \(15\), а число использований каждой буквы не превышает доступного запаса.
Эти слова упорядочиваются лексикографически, причем более короткое слово идет раньше любой более длинной строки, имеющей его в качестве префикса. Требуется не выписать весь список, а сначала вычислить ранги пяти заданных слов, затем сложить и вычесть эти ранги по формуле задачи и, наконец, восстановить слово по полученному рангу.
Прямой перебор слишком велик. Рабочая идея состоит в том, чтобы считать размеры всех лексикографических поддеревьев и затем использовать одни и те же значения как для ранжирования, так и для обратного восстановления слова.
Пусть \(s_\ell\) обозначает число вхождений буквы \(\ell\) в исходной строке, а \(L=15\) есть максимальная допустимая длина. Для текущего префикса обозначим через \(\mathbf c=(c_a,\dots,c_z)\) оставшиеся количества букв, а через \(r\) — сколько позиций еще можно заполнить.
Определим \(F(\mathbf c,r)\) как число допустимых суффиксов, которые еще можно приписать к текущему префиксу, если оставшийся запас равен \(\mathbf c\), а использовать можно не более \(r\) дополнительных букв. Пустой суффикс разрешен, поэтому он сразу дает одну возможность.
Следовательно,
$$F(\mathbf c,0)=1,$$
$$F(\mathbf c,r)=1+\sum_{\ell:\,c_\ell>0}F(\mathbf c-\mathbf e_\ell,r-1).$$
Начальная \(1\) означает вариант «остановиться здесь». Каждый член суммы означает «взять сначала одну доступную букву и затем посчитать все продолжения под соответствующим дочерним узлом». Тем самым \(F(\mathbf c,r)\) точно равно размеру лексикографического поддерева текущего префикса.
Для размера поддерева важны не сами названия букв, а только мультимножество оставшихся кратностей. Если два состояния отличаются лишь переименованием букв, то их поддеревья изоморфны и должны иметь одинаковое число слов.
Поэтому реализации заменяют \(\mathbf c\) каноническим представителем \(\lambda(\mathbf c)\): берутся все положительные компоненты, сортируются по невозрастанию, а нули в конце удаляются. Кэш динамического программирования индексируется парой \((\lambda(\mathbf c),r)\).
Это резко уменьшает число состояний. Например, \((2,1,1,0,\dots)\) и \((1,2,1,0,\dots)\) переходят в один и тот же ключ \((2,1,1)\). Если какие-то части равны, в рекуррентной сумме они все равно учитываются по отдельности, потому что соответствуют разным реальным буквам с одинаковым оставшимся запасом.
Пусть \(P_{\mathbf c,r}(w)\) — 1-базированная позиция слова \(w\) внутри поддерева, заданного состоянием \((\mathbf c,r)\). Пустое слово имеет позицию \(1\):
$$P_{\mathbf c,r}(\varepsilon)=1.$$
Если \(w=w_1w_2\dots w_t\) непусто, то каждая допустимая первая буква, меньшая \(w_1\), вносит целое поддерево, расположенное раньше \(w\). Поэтому
$$P_{\mathbf c,r}(w)=1+\sum_{\ell\lt w_1,\ c_\ell>0}F(\lambda(\mathbf c-\mathbf e_\ell),r-1)+P_{\mathbf c-\mathbf e_{w_1},\,r-1}(w_2\dots w_t).$$
В итоговой арифметике используется 0-базированный ранг \(R(w)=P(w)-1\). Вычитание \(1\) убирает пустое слово у корня и делает линейную комбинацию рангов более естественной.
Чтобы восстановить слово по его 0-базированному рангу \(R\), сначала переходим к 1-базированной позиции \(Q=R+1\). Если \(Q=1\), правильное продолжение пусто. Иначе убираем вариант пустого продолжения, то есть заменяем \(Q\leftarrow Q-1\).
После этого буквы перебираются в алфавитном порядке. Для каждой кандидатной буквы \(\ell\) с \(c_\ell>0\) вычисляется
$$T_\ell=F(\lambda(\mathbf c-\mathbf e_\ell),r-1).$$
Если \(Q>T_\ell\), то все поддерево \(\ell\) находится раньше цели, и можно сразу сделать \(Q\leftarrow Q-T_\ell\). Иначе именно \(\ell\) является следующей буквой ответа, и тот же процесс повторяется на следующем уровне. Поскольку размеры поддеревьев посчитаны точно, восстановление получается единственным.
Пять слов из условия — это legionary, calorimeters, annihilate, orchestrated и fluttering. Если их 0-базированные ранги равны \(R_1,R_2,R_3,R_4,R_5\), то целевой ранг задается формулой
$$T=R_1+R_2-R_3+R_4-R_5.$$
Окончательный ответ — это слово, полученное обратным ранжированием числа \(T\) в полном начальном состоянии, задаваемом исходной строкой и ограничением длины \(15\).
Рассмотрим игрушечный пример: две буквы a, одна буква b и максимальная длина \(2\). Каноническое состояние равно \((2,1)\), а размер его поддерева удовлетворяет равенству
$$F((2,1),2)=1+F((1,1),1)+F((2),1).$$
Здесь \(F((1,1),1)=3\), потому что допустимые суффиксы — это \(\varepsilon\), a и b, а \(F((2),1)=2\), потому что там возможны только \(\varepsilon\) и a. Значит,
$$F((2,1),2)=1+3+2=6.$$
Шесть слов по порядку таковы:
$$\varepsilon,\ a,\ aa,\ ab,\ b,\ ba.$$
Отсюда \(P(ab)=4\), а значит \(R(ab)=3\). Если запустить обратное ранжирование для ранга \(3\), мы снова получим ab. Этот маленький пример в точности показывает, как в полном решении сочетаются подсчет поддеревьев, ранжирование и восстановление по рангу.
Реализации на C++, Python и Java сначала один раз подсчитывают буквы исходной строки и фиксируют максимальную глубину \(15\). После этого они мемоизируют размеры поддеревьев по ключу из канонически отсортированных остаточных кратностей и оставшейся глубины.
Каждый запрос на ранжирование обрабатывает слово слева направо. На каждом шаге суммируются размеры всех лексикографически более ранних соседних ветвей, затем расходуется фактическая следующая буква, и работа продолжается в меньшем остаточном состоянии. Так получается сначала 1-базированная позиция в дереве, а затем 0-базированный ранг для итоговой арифметики.
Фаза обратного ранжирования делает противоположное. Она проверяет кандидатные буквы в алфавитном порядке, вычитает целые размеры поддеревьев, пока эти ветви целиком лежат раньше цели, и спускается в первую ветвь, содержащую нужную позицию.
Все пять запросов на ранги и финальное восстановление используют один и тот же кэш размеров поддеревьев. Поэтому дорогая комбинаторная часть вычисляется один раз, а затем многократно используется.
Пусть \(\mathcal S\) — множество достижимых канонических состояний \((\lambda,r)\). Каждое такое состояние вычисляется ровно один раз, и при каждом вычислении рассматривается не более \(26\) буквенных позиций. Следовательно, фаза динамического программирования требует \(O(26|\mathcal S|)\) времени и \(O(|\mathcal S|)\) памяти. Сортировка ведется максимум по \(26\) элементам, так что она влияет только на константу.
Если длина запрашиваемого слова равна \(m\le 15\), то одна операция ранжирования или обратного ранжирования просматривает не более \(26\) кандидатов на каждом из \(m\) уровней. После заполнения кэша это дает \(O(26m)\). На практике основное время уходит на построение кэша поддеревьев, а не на шесть заключительных запросов.
نبدأ من العبارة "thereisasyetinsufficientdataforameaningfulanswer". حروف هذه العبارة تكوّن تعددًا للحروف، وننظر إلى كل كلمة مختلفة مؤلفة من الحروف من a إلى z بطول لا يتجاوز \(15\)، على أن لا يتجاوز استعمال أي حرف عدد مرات ظهوره المتاح.
تُرتَّب هذه الكلمات ترتيبًا معجميًا، مع القاعدة المعتادة في القاموس: الكلمة الأقصر تأتي قبل أي امتداد أطول لها يشترك معها في البادئة نفسها. المطلوب ليس توليد القائمة كاملة، بل حساب رتب خمس كلمات محددة، ثم جمع هذه الرتب وطرحها وفق الصيغة المعطاة، ثم استرجاع الكلمة التي تقع عند الرتبة الناتجة.
الاستعراض المباشر لجميع الكلمات كبير جدًا. الفكرة الصحيحة هي حساب حجم كل تحت-شجرة معجمية، ثم استعمال هذه الأحجام نفسها في عمليتي الترتيب والاسترجاع العكسي.
لنرمز بـ \(s_\ell\) إلى عدد مرات ظهور الحرف \(\ell\) في العبارة الأصلية، ولتكن \(L=15\) هي القيمة العظمى للطول المسموح. وعند أي بادئة حالية، نرمز بـ \(\mathbf c=(c_a,\dots,c_z)\) إلى أعداد الحروف المتبقية، وبـ \(r\) إلى عدد المواضع التي ما زال يمكن ملؤها.
نعرّف \(F(\mathbf c,r)\) بأنه عدد اللواحق الصحيحة التي يمكن إلحاقها بالبادئة الحالية عندما يكون المخزون المتبقي هو \(\mathbf c\) ويمكن استعمال ما لا يزيد على \(r\) حروف إضافية. واللاحقة الفارغة مسموح بها، ولذلك فهي تضيف احتمالًا واحدًا من البداية.
إذن
$$F(\mathbf c,0)=1,$$
$$F(\mathbf c,r)=1+\sum_{\ell:\,c_\ell>0}F(\mathbf c-\mathbf e_\ell,r-1).$$
العدد \(1\) في البداية يعني «توقّف هنا». وكل حد في المجموع يعني «اختر أولًا حرفًا متاحًا، ثم احسب جميع الامتدادات الواقعة تحت الابن الموافق له». ولذلك فإن \(F(\mathbf c,r)\) هو بالضبط حجم التحت-شجرة المعجمية الموافقة للبادئة الحالية.
اسم الحرف نفسه لا يهم في حساب حجم التحت-شجرة؛ المهم فقط هو تعدد التكرارات المتبقية. فإذا اختلفت حالتان بمجرد إعادة تسمية الحروف، فإنهما تولدان تحت-شجرتين متماثلتين ويجب أن يكون عددهما متساويًا.
لذلك تستبدل التطبيقات المتجه \(\mathbf c\) بممثل قانوني \(\lambda(\mathbf c)\): نأخذ المدخلات الموجبة، ونرتبها ترتيبًا تنازليًا، ثم نحذف الأصفار الطرفية. ويُبنى التخزين المؤقت على الزوج \((\lambda(\mathbf c),r)\).
هذا الضغط مهم جدًا. فمثلًا الحالتان \((2,1,1,0,\dots)\) و\((1,2,1,0,\dots)\) تتحولان كلتاهما إلى المفتاح نفسه \((2,1,1)\). وإذا ظهرت أجزاء متساوية بعد الترتيب، فإنها تُحسب منفصلة داخل العلاقة العودية، لأنها تمثل حروفًا مختلفة تملك العدد المتبقي نفسه.
لتكن \(P_{\mathbf c,r}(w)\) هي الموضع ذي الأساس \(1\) للكلمة \(w\) داخل التحت-شجرة التي تحددها الحالة \((\mathbf c,r)\). الكلمة الفارغة موضعها \(1\):
$$P_{\mathbf c,r}(\varepsilon)=1.$$
إذا كانت \(w=w_1w_2\dots w_t\) غير فارغة، فإن كل حرف أول صالح أصغر من \(w_1\) يضيف تحت-شجرة كاملة تقع قبل \(w\). ومن ثم
$$P_{\mathbf c,r}(w)=1+\sum_{\ell\lt w_1,\ c_\ell>0}F(\lambda(\mathbf c-\mathbf e_\ell),r-1)+P_{\mathbf c-\mathbf e_{w_1},\,r-1}(w_2\dots w_t).$$
أما في الحساب النهائي، فتستعمل التطبيقات الرتبة ذات الأساس \(0\) والمحددة بـ \(R(w)=P(w)-1\). طرح \(1\) هنا يزيل الكلمة الفارغة عند الجذر ويجعل عمليات الجمع والطرح بين الرتب أنظف.
إذا أُعطيت رتبة ذات أساس \(0\) وقيمتها \(R\)، فنحوّلها أولًا إلى موضع ذي أساس \(1\) بكتابة \(Q=R+1\). فإذا كان \(Q=1\)، فالامتداد الصحيح هو السلسلة الفارغة. وإلا نحذف هذا الخيار الفارغ بجعل \(Q\leftarrow Q-1\).
بعد ذلك تُفحص الحروف بترتيب أبجدي تصاعدي. ولكل حرف مرشح \(\ell\) يحقق \(c_\ell>0\)، نحسب
$$T_\ell=F(\lambda(\mathbf c-\mathbf e_\ell),r-1).$$
فإن كان \(Q>T_\ell\)، فهذا يعني أن كامل تحت-شجرة \(\ell\) يقع قبل الهدف، فنستبدل \(Q\leftarrow Q-T_\ell\) ونتابع. وإلا فإن \(\ell\) هو الحرف التالي في الجواب، ونكرر الإجراء نفسه في المستوى الأعمق. وبما أن أحجام التحت-شجرات محسوبة بدقة، فإن الكلمة المسترجعة تكون وحيدة.
الكلمات الخمس المعطاة في المسألة هي legionary وcalorimeters وannihilate وorchestrated وfluttering. وإذا كانت رتبها ذات الأساس \(0\) هي \(R_1,R_2,R_3,R_4,R_5\)، فإن الرتبة المطلوبة تساوي
$$T=R_1+R_2-R_3+R_4-R_5.$$
والنتيجة النهائية هي الكلمة الناتجة من تطبيق الاسترجاع العكسي على \(T\) في الحالة الابتدائية الكاملة التي تحددها العبارة الأصلية مع حد طول يساوي \(15\).
لنأخذ مثالًا صغيرًا فيه حرفان a وحرف واحد b وطول أعظمي \(2\). الحالة القانونية هنا هي \((2,1)\)، ويحقق حجم تحت-الشجرة العلاقة
$$F((2,1),2)=1+F((1,1),1)+F((2),1).$$
لدينا \(F((1,1),1)=3\) لأن اللواحق المسموح بها هي \(\varepsilon\) وa وb، ولدينا \(F((2),1)=2\) لأن الممكن هناك هو \(\varepsilon\) وa فقط. لذلك
$$F((2,1),2)=1+3+2=6.$$
والكلمات الست بالترتيب هي
$$\varepsilon,\ a,\ aa,\ ab,\ b,\ ba.$$
إذن \(P(ab)=4\)، وبالتالي \(R(ab)=3\). وإذا شغّلنا الإجراء العكسي على الرتبة \(3\)، نحصل من جديد على ab. هذا المثال الصغير يوضح تمامًا كيف تتكامل في الحل الكامل ثلاث أفكار: عدّ التحت-شجرات، ثم تخطي الفروع الكاملة عند الترتيب أو عند الاسترجاع.
تبدأ تطبيقات C++ وPython وJava بعدّ حروف العبارة الأصلية مرة واحدة وتثبيت العمق الأقصى عند \(15\). بعد ذلك تخزّن أحجام التحت-شجرات في ذاكرة مؤقتة مفهرسة بحسب التكرارات القانونية المرتبة وبحسب العمق المتبقي.
كل استعلام لترتيب كلمة يعالج الكلمة من اليسار إلى اليمين. ففي كل موضع تُجمع أحجام الفروع الشقيقة التي تسبق حرفيًا الفرع المطلوب، ثم يُستهلك الحرف الفعلي التالي، ويستمر العمل على الحالة الأصغر الناتجة. وبهذا نحصل أولًا على موضع ذي أساس \(1\) داخل الشجرة، ثم نحوله إلى رتبة ذات أساس \(0\) لاستخدامها في الصيغة النهائية.
أما مرحلة الاسترجاع العكسي فتقوم بالعملية المتممة. فهي تجرّب الحروف المرشحة بالترتيب الأبجدي، وتطرح أحجام التحت-شجرات كاملة عندما تكون تلك الفروع كلها قبل الهدف، ثم تنزل إلى أول فرع يحتوي الموضع المطلوب.
الاستعلامات الخمسة الخاصة بالرتب والاسترجاع النهائي تشترك جميعًا في مخزن واحد لأحجام التحت-شجرات. لذلك يُنجَز العمل التوافقي المكلف مرة واحدة فقط، ثم يُعاد استعماله.
لتكن \(\mathcal S\) مجموعة الحالات القانونية القابلة للوصول من الشكل \((\lambda,r)\). كل حالة تُقيَّم مرة واحدة فقط، وكل تقييم يفحص في أقصى الأحوال \(26\) موضعًا حرفيًا، ولذلك فإن طور البرمجة الديناميكية يكلف \(O(26|\mathcal S|)\) زمنًا و\(O(|\mathcal S|)\) ذاكرة. أما خطوة الفرز فتجري على عدد لا يتجاوز \(26\) مدخلًا، ولذلك لا تؤثر إلا في الثابت المضروب.
إذا كان طول الكلمة المستعلَم عنها هو \(m\le 15\)، فإن عملية ترتيب واحدة أو استرجاع واحدة تفحص في كل مستوى من المستويات \(m\) ما لا يزيد على \(26\) مرشحًا، ومن ثم تكون كلفتها \(O(26m)\) بعد اكتمال التخزين المؤقت. عمليًا، الزمن الكلي تهيمن عليه عملية بناء مخزن أحجام التحت-شجرات، لا الاستعلامات الست الأخيرة.