For each dimension \(d\) and roll cost \(c\), the problem first asks for the best expected net profit of the ordinary Ramvok game on a fixed non-empty subset \(A\subseteq\{1,\dots,d\}\). Those profits are then averaged over all subsets of the same size, and the averaged values are used in a second process whose state depends only on the current subset size. The resulting quantity is denoted \(S(d,c)\), and the final target is
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
The implementation verifies two checkpoints along the way:
$$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$$
Fix \(d\ge 4\), a cost \(c\), and a non-empty subset
$$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k.$$
The exact method implemented by the programs has three layers: optimize the ordinary game on one subset, average over all subsets with the same cardinality, then solve a one-dimensional Bellman system for the super-game.
Let \(h_t\) be the best expected gross reward when the available values are exactly the elements of \(A\) and at most \(t\) further rolls are allowed. The recurrence used by the implementation is
$$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$$
This recurrence is an optimal-stopping equation. On the first roll we see one of the \(v_i\), each with probability \(1/k\). After seeing \(v_i\), we either stop immediately and keep \(v_i\), or continue and replace it by the continuation value \(h_{t-1}\). Therefore the contribution of outcome \(v_i\) is \(\max(v_i,h_{t-1})\), and averaging over all outcomes gives the displayed formula.
If each roll costs \(c\), then using exactly \(t\) allowed rolls gives expected net profit
$$h_t-c t.$$
Hence the subset profit is
$$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr).$$
The code exploits two useful bounds. If \(c=0\), the value is simply the largest available reward, so \(R(A,0)=\max(A)\). If \(c\ge 1\) and \(A\subseteq\{1,\dots,d\}\), then \(h_t\le \max(A)\le d\), so for \(t>d\) we have
$$h_t-c t\le d-t<0.$$
Since \(t=0\) yields profit \(0\), no horizon larger than \(d\) can be optimal for the integer costs used in the main sum. That is why the exact search stops at \(t=d\).
For fixed \(d\) and \(c\), define the average subset profit at level \(k\) by
$$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d.$$
This is the key compression step. The super-game does not need the identity of the subset once we average over all \(k\)-subsets; it only needs the current size \(k\). All detailed subset structure is absorbed into the scalar quantity \(a_k(c)\).
Let \(x_k\) denote the expected total super-value when the current subset has size \(k\). The linear system in the implementations shows that the next transition depends only on whether the next uniformly chosen label is already present or absent. From a state of size \(k<d\):
$$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$$
Conditioning on that next step gives
$$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d.$$
The state \(k=0\) is an implicit zero boundary, so no separate unknown is needed there. At the top state \(k=d\), the next move must go to \(d-1\), hence
$$x_d=a_d(c)+x_{d-1}.$$
Rearranging these equations produces a tridiagonal linear system, and the desired super-value for the pair \((d,c)\) is
$$S(d,c)=x_d.$$
Once \(S(d,c)\) is known for every \(d\) and every integer cost \(0\le c\le n\), the problem asks for their double sum:
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
This is exactly the quantity accumulated by the implementations before the final rounding step.
Here \(k=4\). The recurrence gives
$$h_1=\frac{1+2+3+4}{4}=2.5,$$
$$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$$
$$h_3=\frac{3+3+3+4}{4}=3.25,$$
$$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375.$$
The corresponding profits are
$$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375.$$
So the optimum is attained at \(t=3\), proving
$$R(\{1,2,3,4\},0.2)=2.65.$$
The second checkpoint, \(S(6,1)=208.3\), verifies that the averaging stage and the tridiagonal solve are also assembled correctly.
The C++, Python, and Java implementations follow the same mathematical pipeline. For each \(d\), they enumerate every non-empty subset of \(\{1,\dots,d\}\) with a bitmask. The chosen bits already determine the subset in sorted order, so no expensive reordering is needed.
For each subset, the implementation computes the best net profit for every integer cost \(c=0,1,\dots,n\). The \(c=0\) case is handled immediately by taking the largest element of the subset. For \(c\ge 1\), the implementation advances the recurrence for \(h_t\) only up to \(t=d\), updating the best value \(h_t-c t\) for all costs in parallel.
These profits are accumulated in buckets indexed by subset size \(k\). After all subsets have been processed, each bucket sum is divided by the number of subsets of that size, producing the averages \(a_k(c)\).
Then, for each fixed cost \(c\), the implementation builds the tridiagonal system corresponding to the Bellman equations above and solves it by forward elimination followed by back substitution. The last component gives \(S(d,c)\). Finally it sums all \(S(d,c)\) over \(d=4,\dots,n\) and \(c=0,\dots,n\), and rounds the total to the nearest integer.
For a fixed \(d\), there are \(2^d-1\) non-empty subsets. Processing one subset takes \(O(d)\) time to decode its elements, \(O(dk)\) time to advance the recurrence over \(t=1,\dots,d\), and \(O(dn)\) time to update all integer costs, where \(k\le d\). Thus one subset costs \(O(d(d+n))\) in the worst case, and the dominant cost for that dimension is
$$O\bigl(2^d\,d(d+n)\bigr).$$
The tridiagonal solve contributes only \(O(nd)\) time for that same \(d\), which is much smaller than the subset enumeration. Summing over \(d=4,\dots,n\) gives an overall exponential exact algorithm, dominated by the largest dimension; for \(d\) on the order of \(n\), this is roughly \(O(2^n n^2)\). The working memory is \(O(d(n+1))\) for the level averages plus \(O(d)\) for the linear-system arrays, with additional copies only when parallel workers are used.
Für jede Dimension \(d\) und jeden Wurfpreis \(c\) wird zunächst der beste erwartete Nettogewinn des gewöhnlichen Ramvok-Spiels auf einer festen nichtleeren Teilmenge \(A\subseteq\{1,\dots,d\}\) bestimmt. Diese Werte werden anschließend über alle Teilmengen gleicher Größe gemittelt. Mit diesen Mittelwerten wird dann ein zweiter Prozess beschrieben, dessen Zustand nur noch von der aktuellen Teilmengengröße abhängt. Der gesuchte Superwert heißt \(S(d,c)\), und am Ende wird
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c)$$
berechnet. Zwei Kontrollwerte der Implementierung sind
$$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$$
Fixiere \(d\ge 4\), einen Kostenwert \(c\) und eine nichtleere Teilmenge
$$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k.$$
Die exakte Methode der Programme besteht aus drei Stufen: zuerst Optimierung auf einer festen Teilmenge, dann Mittelung nach Kardinalität, schließlich Lösung eines eindimensionalen Bellman-Systems für das Super-Spiel.
Sei \(h_t\) der beste erwartete Bruttoertrag, wenn genau die Werte aus \(A\) verfügbar sind und höchstens \(t\) weitere Würfe erlaubt sind. Die Implementierung benutzt die Rekursion
$$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$$
Das ist eine klassische Optimal-Stopping-Gleichung. Beim ersten Wurf erscheint einer der Werte \(v_i\) mit Wahrscheinlichkeit \(1/k\). Danach stoppt man sofort und nimmt \(v_i\), oder man spielt weiter und ersetzt diesen Wert durch den Fortsetzungswert \(h_{t-1}\). Für das Ergebnis \(v_i\) trägt also \(\max(v_i,h_{t-1})\) bei; das Mittel über alle Möglichkeiten liefert die Formel.
Kostet jeder Wurf \(c\), dann ist der erwartete Nettogewinn bei genau \(t\) erlaubten Würfen gleich
$$h_t-c t.$$
Damit gilt für die Teilmenge
$$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr).$$
Der Code nutzt zwei einfache Schranken. Für \(c=0\) ist der Wert sofort \(\max(A)\). Für \(c\ge 1\) und \(A\subseteq\{1,\dots,d\}\) gilt \(h_t\le \max(A)\le d\), also für \(t>d\)
$$h_t-c t\le d-t<0.$$
Da \(t=0\) stets Gewinn \(0\) liefert, kann für die ganzzahligen Kosten der Hauptrechnung kein Horizont größer als \(d\) optimal sein.
Für festes \(d\) und \(c\) definieren wir
$$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d.$$
Das ist der entscheidende Kompressionsschritt. Nach der Mittelung über alle \(k\)-Teilmengen spielt ihre konkrete Identität keine Rolle mehr; übrig bleibt nur noch die Größe \(k\). Alle feineren Details der Teilmengen gehen in den skalaren Wert \(a_k(c)\) ein.
Sei \(x_k\) der erwartete gesamte Superwert, wenn die aktuelle Teilmenge Größe \(k\) hat. Aus dem linearen System der Implementierungen liest man ab, dass der nächste Übergang nur davon abhängt, ob das gleichmäßig gewählte Label schon enthalten ist oder nicht. Für einen Zustand der Größe \(k<d\) gilt:
$$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$$
Durch Bedingung auf diesen nächsten Schritt erhält man
$$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d.$$
Der Zustand \(k=0\) ist implizit der Nullrand. Für \(k=d\) muss der nächste Schritt nach \(d-1\) gehen, also
$$x_d=a_d(c)+x_{d-1}.$$
Nach Umstellen entsteht ein tridiagonales lineares Gleichungssystem, und der gesuchte Wert für das Paar \((d,c)\) ist
$$S(d,c)=x_d.$$
Sobald \(S(d,c)\) für alle \(d\) und alle ganzzahligen Kosten \(0\le c\le n\) vorliegt, wird genau die Doppelsumme
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c)$$
gebildet. Genau diese Größe addieren die Programme auf und runden sie am Schluss.
Hier ist \(k=4\). Aus der Rekursion folgt
$$h_1=\frac{1+2+3+4}{4}=2.5,$$
$$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$$
$$h_3=\frac{3+3+3+4}{4}=3.25,$$
$$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375.$$
Die Nettogewinne sind damit
$$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375.$$
Das Maximum liegt also bei \(t=3\), somit
$$R(\{1,2,3,4\},0.2)=2.65.$$
Der zweite Kontrollwert \(S(6,1)=208.3\) bestätigt zusätzlich, dass Mittelung und tridiagonale Lösung korrekt zusammengesetzt sind.
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Zerlegung. Für jedes \(d\) werden alle nichtleeren Teilmengen von \(\{1,\dots,d\}\) per Bitmaske enumeriert. Die gesetzten Bits bestimmen die Teilmenge bereits in sortierter Reihenfolge, daher ist keine teure Nachsortierung notwendig.
Für jede Teilmenge berechnet die Implementierung den besten Nettogewinn für alle ganzzahligen Kosten \(c=0,1,\dots,n\). Der Fall \(c=0\) wird sofort durch das Maximum der Teilmenge erledigt. Für \(c\ge 1\) wird die Rekursion für \(h_t\) nur bis \(t=d\) fortgeführt, und die Werte \(h_t-c t\) werden für alle Kosten parallel aktualisiert.
Danach werden die Gewinne in Behältern nach Teilmengengröße \(k\) aufsummiert. Durch Division mit der Anzahl der \(k\)-Teilmengen erhält man die Mittelwerte \(a_k(c)\).
Für jeden festen Kostenwert \(c\) baut die Implementierung anschließend das tridiagonale Gleichungssystem der obigen Bellman-Gleichungen auf und löst es mit Vorwärtselfimination und Rückwärtseinsetzen. Die letzte Komponente ist \(S(d,c)\). Abschließend werden alle \(S(d,c)\) für \(d=4,\dots,n\) und \(c=0,\dots,n\) aufsummiert und auf die nächste ganze Zahl gerundet.
Für festes \(d\) gibt es \(2^d-1\) nichtleere Teilmengen. Eine Teilmenge kostet \(O(d)\) zum Dekodieren ihrer Elemente, \(O(dk)\) für die Rekursion über \(t=1,\dots,d\) und \(O(dn)\) für die Aktualisierung aller ganzzahligen Kosten, wobei \(k\le d\). Somit liegt der Aufwand pro Teilmenge im Worst Case bei \(O(d(d+n))\), und die dominierende Arbeit für diese Dimension ist
$$O\bigl(2^d\,d(d+n)\bigr).$$
Die tridiagonalen Gleichungssysteme benötigen dagegen nur \(O(nd)\) Zeit für dasselbe \(d\) und fallen gegenüber der Teilmengen-Enumeration kaum ins Gewicht. Über \(d=4,\dots,n\) summiert bleibt der exakte Algorithmus exponentiell und wird von der größten Dimension dominiert; für \(d\) von der Größenordnung \(n\) ist das grob \(O(2^n n^2)\). Der Arbeitsspeicher beträgt \(O(d(n+1))\) für die Ebenenmittelwerte plus \(O(d)\) für die Arrays des linearen Systems; bei paralleler Verarbeitung kommen nur zusätzliche Kopien derselben Tabellen hinzu.
Her \(d\) boyutu ve her \(c\) atış maliyeti için önce sıradan Ramvok oyununun sabit bir boş olmayan \(A\subseteq\{1,\dots,d\}\) alt kümesi üzerindeki en iyi beklenen net kazancı hesaplanır. Sonra bu kazançlar aynı büyüklükteki tüm alt kümeler üzerinde ortalanır. Elde edilen ortalamalar, durumu yalnızca mevcut alt küme büyüklüğüne bağlı olan ikinci bir süreci tanımlar. Bu sürecin değeri \(S(d,c)\) ile gösterilir ve en son
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c)$$
hesaplanır. Uygulamanın kullandığı iki kontrol noktası şunlardır:
$$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$$
\(d\ge 4\), bir maliyet \(c\) ve boş olmayan bir
$$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k$$
alt kümesi sabit olsun. Programların uyguladığı kesin yöntem üç katmandan oluşur: önce tek bir alt kümede optimizasyon, sonra alt küme boyutuna göre ortalama, en sonunda da süper oyun için tek boyutlu bir Bellman sistemi.
\(h_t\), tam olarak \(A\) içindeki değerler kullanılabilirken ve en fazla \(t\) ek atış hakkı varken elde edilebilecek en iyi beklenen brüt getiri olsun. Uygulamadaki özyineleme şöyledir:
$$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$$
Bu bir optimal durma denklemidir. İlk atışta \(v_i\) değerlerinden biri \(1/k\) olasılıkla görülür. O anda ya hemen durup \(v_i\) alınır ya da devam edilip bu değer, devam değerini temsil eden \(h_{t-1}\) ile karşılaştırılır. Bu yüzden her sonuç \(\max(v_i,h_{t-1})\) katkısı yapar; tüm sonuçların ortalaması da formülü verir.
Her atışın maliyeti \(c\) ise, tam olarak \(t\) atış hakkı kullanmanın beklenen net kazancı
$$h_t-c t$$
olur. Dolayısıyla alt küme için kâr
$$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr)$$
şeklindedir. Kod iki basit sınırdan yararlanır. \(c=0\) ise değer doğrudan en büyük elemandır; yani \(R(A,0)=\max(A)\). Eğer \(c\ge 1\) ve \(A\subseteq\{1,\dots,d\}\) ise \(h_t\le \max(A)\le d\) olduğundan \(t>d\) için
$$h_t-c t\le d-t<0$$
elde edilir. \(t=0\) zaten \(0\) kazanç verdiği için, ana toplamda kullanılan tamsayı maliyetlerde en iyi ufuk hiçbir zaman \(d\)'yi aşmaz.
Sabit \(d\) ve \(c\) için
$$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d$$
tanımını yapalım. Burası temel sıkıştırma adımıdır. Süper oyunda, tüm \(k\)-elemanlı alt kümeler üzerinde ortalama alındıktan sonra alt kümenin hangi elemanlardan oluştuğu değil, yalnızca büyüklüğü \(k\) önemlidir. Ayrıntılı yapı tek bir skaler olan \(a_k(c)\) içinde toplanır.
\(x_k\), mevcut alt kümenin büyüklüğü \(k\) iken toplam beklenen süper değer olsun. Uygulamadaki doğrusal sistem, bir sonraki geçişin yalnızca eşit olasılıkla seçilen etiketin alt kümede bulunup bulunmamasına bağlı olduğunu gösterir. \(k<d\) büyüklüğündeki bir durumdan
$$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$$
Bir sonraki adıma göre koşullandırınca
$$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d$$
elde edilir. \(k=0\) durumu örtük bir sıfır sınırıdır. En üst durum olan \(k=d\) için bir sonraki adım zorunlu olarak \(d-1\)'e gider; dolayısıyla
$$x_d=a_d(c)+x_{d-1}.$$
Bu denklemler düzenlenince üç köşegenli bir doğrusal sistem oluşur ve \((d,c)\) çifti için aranan değer
$$S(d,c)=x_d$$
olur.
\(S(d,c)\) tüm \(d\) değerleri ve tüm \(0\le c\le n\) tamsayı maliyetleri için hesaplandıktan sonra, problem tam olarak şu çift toplamı ister:
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
Uygulamalar da son yuvarlamadan önce tam olarak bu miktarı biriktirir.
Burada \(k=4\). Özyineleme
$$h_1=\frac{1+2+3+4}{4}=2.5,$$
$$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$$
$$h_3=\frac{3+3+3+4}{4}=3.25,$$
$$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375$$
değerlerini verir. Buna karşılık net kârlar
$$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375$$
olur. En iyi değer \(t=3\) noktasında elde edilir; yani
$$R(\{1,2,3,4\},0.2)=2.65.$$
İkinci kontrol noktası olan \(S(6,1)=208.3\), ortalama alma ve üç köşegenli sistem çözümünün de doğru kurulduğunu teyit eder.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Her \(d\) için \(\{1,\dots,d\}\) kümesinin tüm boş olmayan alt kümeleri bit maskeleriyle dolaşılır. Açık olan bitler alt kümeyi zaten sıralı biçimde belirlediği için ayrıca sıralama yapılmaz.
Her alt küme için uygulama, tüm tamsayı maliyetler \(c=0,1,\dots,n\) adına en iyi net kazancı hesaplar. \(c=0\) durumu doğrudan alt kümenin en büyük elemanıdır. \(c\ge 1\) olduğunda \(h_t\) özyinelemesi yalnızca \(t=d\)'ye kadar ilerletilir ve \(h_t-c t\) değerleri bütün maliyetler için aynı anda güncellenir.
Daha sonra bu kârlar alt küme büyüklüğü \(k\)'ya göre kovalanıp toplanır. Her kovadaki toplam, o büyüklükteki alt küme sayısına bölünerek \(a_k(c)\) ortalamaları elde edilir.
Ardından her sabit maliyet \(c\) için, yukarıdaki Bellman denklemlerine karşılık gelen üç köşegenli doğrusal sistem kurulur ve ileri eliminasyon ile geri yerine koyma kullanılarak çözülür. Son bileşen \(S(d,c)\)'dir. En sonunda tüm \(d=4,\dots,n\) ve \(c=0,\dots,n\) için bulunan \(S(d,c)\) değerleri toplanır ve en yakın tam sayıya yuvarlanır.
Sabit bir \(d\) için \(2^d-1\) tane boş olmayan alt küme vardır. Bir alt kümeyi işlemek, elemanlarını çıkarmak için \(O(d)\), \(t=1,\dots,d\) boyunca özyinelemeyi ilerletmek için \(O(dk)\) ve tüm tamsayı maliyetleri güncellemek için \(O(dn)\) zaman alır; burada \(k\le d\). Dolayısıyla tek alt küme için en kötü durum maliyeti \(O(d(d+n))\) olur ve bu boyuttaki baskın iş yükü
$$O\bigl(2^d\,d(d+n)\bigr)$$
şeklindedir. Üç köşegenli doğrusal sistem çözümü aynı \(d\) için yalnızca \(O(nd)\) zaman gerektirir ve alt küme sayımının yanında küçük kalır. \(d=4,\dots,n\) üzerinde toplandığında yöntem tam olarak üstel bir algoritmadır ve en büyük boyut tarafından domine edilir; \(d\) ile \(n\) aynı mertebedeyken toplam maliyet kabaca \(O(2^n n^2)\) olur. Çalışma belleği, seviye ortalamaları için \(O(d(n+1))\) ve doğrusal sistem dizileri için \(O(d)\) kadardır; paralel işçiler kullanıldığında yalnızca bu tabloların ek kopyaları oluşur.
Para cada dimensión \(d\) y cada coste de tirada \(c\), primero se calcula el mejor beneficio neto esperado del juego Ramvok ordinario sobre un subconjunto no vacío fijo \(A\subseteq\{1,\dots,d\}\). Después esos beneficios se promedian sobre todos los subconjuntos del mismo tamaño. Con esos promedios se define un segundo proceso cuyo estado depende solo del tamaño actual del subconjunto. El valor correspondiente se denota por \(S(d,c)\), y el objetivo final es
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
La implementación comprueba además dos valores de control:
$$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$$
Fijemos \(d\ge 4\), un coste \(c\) y un subconjunto no vacío
$$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k.$$
El método exacto implementado por los programas tiene tres capas: optimizar el juego ordinario en un subconjunto, promediar por cardinalidad y resolver después un sistema de Bellman unidimensional para el superjuego.
Sea \(h_t\) la mejor recompensa bruta esperada cuando los valores disponibles son exactamente los de \(A\) y se permiten como máximo \(t\) tiradas adicionales. La recurrencia usada por la implementación es
$$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$$
Esta recurrencia es una ecuación de parada óptima. En la primera tirada aparece uno de los valores \(v_i\), cada uno con probabilidad \(1/k\). Tras observar \(v_i\), se puede parar y quedarse con \(v_i\), o continuar y sustituirlo por el valor de continuación \(h_{t-1}\). Por eso la contribución del resultado \(v_i\) es \(\max(v_i,h_{t-1})\), y al promediar sobre todos los resultados se obtiene la fórmula.
Si cada tirada cuesta \(c\), entonces permitir exactamente \(t\) tiradas produce el beneficio neto esperado
$$h_t-c t.$$
Por tanto, el beneficio del subconjunto es
$$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr).$$
El código aprovecha dos cotas sencillas. Si \(c=0\), el valor es simplemente el mayor elemento disponible, así que \(R(A,0)=\max(A)\). Si \(c\ge 1\) y \(A\subseteq\{1,\dots,d\}\), entonces \(h_t\le \max(A)\le d\), de modo que para \(t>d\)
$$h_t-c t\le d-t<0.$$
Como \(t=0\) ya da beneficio \(0\), ningún horizonte mayor que \(d\) puede ser óptimo para los costes enteros usados en la suma principal.
Para \(d\) y \(c\) fijos definimos
$$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d.$$
Este es el paso clave de compresión. Una vez que se promedia sobre todos los subconjuntos de tamaño \(k\), la identidad concreta del subconjunto deja de importar; solo importa su tamaño \(k\). Toda la estructura fina queda resumida en el escalar \(a_k(c)\).
Sea \(x_k\) el valor total esperado del superjuego cuando el subconjunto actual tiene tamaño \(k\). El sistema lineal de las implementaciones muestra que la siguiente transición solo depende de si la etiqueta elegida uniformemente ya está presente o no. Desde un estado de tamaño \(k<d\):
$$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$$
Condicionando por ese siguiente paso se obtiene
$$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d.$$
El estado \(k=0\) actúa como frontera nula implícita. En el extremo \(k=d\), el siguiente paso debe ir necesariamente a \(d-1\), así que
$$x_d=a_d(c)+x_{d-1}.$$
Al reorganizar estas ecuaciones aparece un sistema lineal tridiagonal, y el valor buscado para el par \((d,c)\) es
$$S(d,c)=x_d.$$
Una vez conocidos \(S(d,c)\) para todos los \(d\) y todos los costes enteros \(0\le c\le n\), el problema pide la suma doble
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
Eso es exactamente lo que acumulan las implementaciones antes del redondeo final.
Aquí \(k=4\). La recurrencia produce
$$h_1=\frac{1+2+3+4}{4}=2.5,$$
$$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$$
$$h_3=\frac{3+3+3+4}{4}=3.25,$$
$$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375.$$
Los beneficios correspondientes son
$$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375.$$
Por tanto, el óptimo se alcanza en \(t=3\), lo que demuestra que
$$R(\{1,2,3,4\},0.2)=2.65.$$
El segundo punto de control, \(S(6,1)=208.3\), confirma que la etapa de promedios y la resolución tridiagonal también están bien montadas.
Las implementaciones en C++, Python y Java siguen la misma descomposición matemática. Para cada \(d\), enumeran todos los subconjuntos no vacíos de \(\{1,\dots,d\}\) mediante máscaras de bits. Los bits activos ya determinan el subconjunto en orden creciente, así que no hace falta una ordenación costosa.
Para cada subconjunto, la implementación calcula el mejor beneficio neto para todos los costes enteros \(c=0,1,\dots,n\). El caso \(c=0\) se resuelve inmediatamente tomando el mayor elemento del subconjunto. Para \(c\ge 1\), la recurrencia de \(h_t\) solo se avanza hasta \(t=d\), y los valores \(h_t-c t\) se actualizan para todos los costes a la vez.
Esos beneficios se acumulan en cubos indexados por el tamaño del subconjunto \(k\). Después, cada suma se divide por el número de subconjuntos de ese tamaño y así se obtienen los promedios \(a_k(c)\).
Luego, para cada coste fijo \(c\), la implementación construye el sistema tridiagonal asociado a las ecuaciones de Bellman anteriores y lo resuelve mediante eliminación hacia delante y sustitución hacia atrás. La última componente da \(S(d,c)\). Finalmente se suman todos los \(S(d,c)\) para \(d=4,\dots,n\) y \(c=0,\dots,n\), y el total se redondea al entero más cercano.
Para un \(d\) fijo hay \(2^d-1\) subconjuntos no vacíos. Procesar un subconjunto cuesta \(O(d)\) para decodificar sus elementos, \(O(dk)\) para avanzar la recurrencia sobre \(t=1,\dots,d\) y \(O(dn)\) para actualizar todos los costes enteros, con \(k\le d\). Por ello, el coste por subconjunto es \(O(d(d+n))\) en el peor caso, y el trabajo dominante para esa dimensión es
$$O\bigl(2^d\,d(d+n)\bigr).$$
La resolución tridiagonal añade solo \(O(nd)\) tiempo para ese mismo \(d\), mucho menor que la enumeración de subconjuntos. Sumando sobre \(d=4,\dots,n\), el algoritmo exacto sigue siendo exponencial y queda dominado por la dimensión mayor; cuando \(d\) es del orden de \(n\), esto es aproximadamente \(O(2^n n^2)\). La memoria de trabajo es \(O(d(n+1))\) para los promedios por nivel y \(O(d)\) para los vectores del sistema lineal, con copias adicionales solo si se usan trabajadores en paralelo.
对每个维度 \(d\) 和每个掷骰成本 \(c\)，题目先要求出普通 Ramvok 游戏在一个固定非空子集 \(A\subseteq\{1,\dots,d\}\) 上的最优期望净收益。然后把这些收益按照子集大小分组取平均。接着，利用这些按大小得到的平均值，再去分析一个“超级”过程；在这个过程中，状态只取决于当前子集的大小，而不再取决于子集的具体元素。这个超级过程的值记为 \(S(d,c)\)，最终目标是
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
实现中还使用了两个校验点来确保推导和程序一致：
$$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$$
固定 \(d\ge 4\)、成本 \(c\)，以及一个非空子集
$$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k.$$
程序采用的精确方法可以分成三个层次：先求固定子集上的最优停止值，再按子集大小做平均，最后对超级过程求解一维 Bellman 方程组。
记 \(h_t\) 为这样一个量：当可选数值恰好是子集 \(A\) 中的元素，并且最多还允许 \(t\) 次额外掷骰时，能够获得的最优期望毛收益。实现里使用的递推关系是
$$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$$
这实际上就是一个最优停止递推。第一次掷骰会以相同概率 \(1/k\) 落到某个 \(v_i\)。看到 \(v_i\) 之后，你有两个选择：立刻停止并拿走 \(v_i\)，或者继续玩，把这一步的价值视为后续还能玩的期望值 \(h_{t-1}\)。因此，结果 \(v_i\) 对应的最优贡献就是 \(\max(v_i,h_{t-1})\)。对所有可能结果求平均，就得到上面的公式。
如果每次掷骰都要支付成本 \(c\)，那么允许恰好使用 \(t\) 次机会时，对应的期望净收益就是
$$h_t-c t.$$
于是固定子集 \(A\) 的最优净收益定义为
$$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr).$$
程序在这里利用了两个非常重要的界。第一，如果 \(c=0\)，那么没有继续等待的成本，最终最优值就是子集中的最大元素，所以 \(R(A,0)=\max(A)\)。第二，如果 \(c\ge 1\) 且 \(A\subseteq\{1,\dots,d\}\)，那么不管递推进行了多少轮，总有 \(h_t\le \max(A)\le d\)。因此当 \(t>d\) 时，
$$h_t-c t\le d-t<0.$$
而 \(t=0\) 至少还能给出利润 \(0\)。所以对于主计算里出现的整数成本，最优步数根本不可能超过 \(d\)。这解释了为什么实现只需要把递推推进到 \(t=d\) 为止。
对固定的 \(d\) 和 \(c\)，定义
$$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d.$$
这一步是整个方法的核心压缩。超级过程并不需要记住“具体是哪一个 \(k\) 元子集”，只需要知道当前子集的大小是 \(k\)。所有关于具体元素组成的复杂信息，都已经被折叠进了平均值 \(a_k(c)\) 里。换句话说，普通 Ramvok 的组合复杂度先在这一层被完全消化掉，后面的方程只需要处理一维状态 \(k\)。
设 \(x_k\) 表示当前子集大小为 \(k\) 时，超级过程的期望总价值。实现中的线性系统说明：下一步如何变化，只取决于“均匀随机选中的标签”当前是否已经在子集中。若当前大小 \(k<d\)，那么
$$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$$
因此，对下一步分类讨论后可得
$$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d.$$
这里的 \(a_k(c)\) 是当前层立即获得的平均收益，而后两项对应转移后的继续价值。状态 \(k=0\) 在程序中作为隐含的零边界出现，因此不需要单独列入未知量。当 \(k=d\) 时，所有标签都已经出现，下一步不可能再升到 \(d+1\)，只能退回 \(d-1\)，所以边界条件变成
$$x_d=a_d(c)+x_{d-1}.$$
把这些方程整理到同一边，就得到一个三对角线性系统。解出该系统后，最右端分量就是所需的超级值：
$$S(d,c)=x_d.$$
当所有 \(d\) 和所有整数成本 \(0\le c\le n\) 的 \(S(d,c)\) 都算出来之后，题目要求的正是
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
程序会按照这个定义逐项累加，然后把总和四舍五入到最近的整数。
这个例子正好对应实现中的第一个校验点。此时 \(k=4\)，递推为
$$h_1=\frac{1+2+3+4}{4}=2.5,$$
$$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$$
$$h_3=\frac{3+3+3+4}{4}=3.25,$$
$$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375.$$
对应的净收益分别是
$$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375.$$
最优值出现在 \(t=3\)，因此
$$R(\{1,2,3,4\},0.2)=2.65.$$
第二个校验点 \(S(6,1)=208.3\) 则说明“按大小取平均”以及“三对角系统求解”这两部分也与数学模型完全一致。
C++、Python 和 Java 实现遵循同一条数学流水线。对每个 \(d\)，程序先用位掩码枚举 \(\{1,\dots,d\}\) 的所有非空子集。由于被置位的位置天然对应递增的元素编号，所以子集本身已经按顺序给出，不需要再额外排序。
对于每个子集，实现会同时计算所有整数成本 \(c=0,1,\dots,n\) 下的最优净收益。\(c=0\) 的情况可以直接取子集最大值。对于 \(c\ge 1\)，程序把 \(h_t\) 的递推推进到 \(t=d\)，并在每一步同时更新全部成本对应的最佳值 \(h_t-c t\)。
这些结果会按照子集大小 \(k\) 累加到不同的桶中。全部子集处理完以后，再除以该大小子集的个数，就得到平均值 \(a_k(c)\)。
然后，对每个固定成本 \(c\)，程序构造上面 Bellman 方程对应的三对角系统，并用前向消元加回代的方式求解。最后一个分量就是 \(S(d,c)\)。最终再把所有 \(d=4,\dots,n\) 和 \(c=0,\dots,n\) 的 \(S(d,c)\) 相加，并输出四舍五入后的结果。
对固定的 \(d\)，一共有 \(2^d-1\) 个非空子集。处理一个子集需要 \(O(d)\) 时间提取元素，\(O(dk)\) 时间推进 \(t=1,\dots,d\) 的递推，以及 \(O(dn)\) 时间更新所有整数成本，其中 \(k\le d\)。因此单个子集的最坏代价是 \(O(d(d+n))\)，该维度上的主导时间复杂度为
$$O\bigl(2^d\,d(d+n)\bigr).$$
相比之下，同一个 \(d\) 上的三对角系统求解总共只需要 \(O(nd)\) 时间，远小于子集枚举的代价。把 \(d=4,\dots,n\) 全部加起来后，算法仍然是一个精确的指数级方法，并且主要由最大的维度主导；当 \(d\) 与 \(n\) 同阶时，总体规模大致可写成 \(O(2^n n^2)\)。工作内存方面，按层平均值表需要 \(O(d(n+1))\)，线性系统向量需要 \(O(d)\)；若使用并行工作线程，则只是在此基础上复制若干份相同结构的临时表。
Для каждого размера \(d\) и каждой стоимости броска \(c\) сначала вычисляется наилучшая ожидаемая чистая прибыль обычной игры Ramvok на фиксированном непустом подмножестве \(A\subseteq\{1,\dots,d\}\). Затем эти прибыли усредняются по всем подмножествам одинаковой мощности. Полученные средние значения используются во втором процессе, где состояние определяется только текущей мощностью подмножества. Этот супер-значение обозначается через \(S(d,c)\), а конечная цель имеет вид
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
В реализации дополнительно проверяются две контрольные точки:
$$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$$
Зафиксируем \(d\ge 4\), стоимость \(c\) и непустое подмножество
$$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k.$$
Точный метод, реализованный в программах, состоит из трёх слоёв: оптимизация на одном подмножестве, усреднение по мощности и затем решение одномерной системы Беллмана для супер-игры.
Пусть \(h_t\) обозначает наилучшее ожидаемое валовое вознаграждение, если доступны ровно значения из \(A\) и разрешено не более \(t\) дополнительных бросков. В реализации используется рекуррентная формула
$$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$$
Это уравнение оптимальной остановки. На первом броске появляется одно из \(v_i\) с вероятностью \(1/k\). После появления значения \(v_i\) можно либо остановиться и взять \(v_i\), либо продолжить и заменить его значением продолжения \(h_{t-1}\). Поэтому вклад исхода \(v_i\) равен \(\max(v_i,h_{t-1})\), а усреднение по всем исходам даёт указанную формулу.
Если каждый бросок стоит \(c\), то при использовании ровно \(t\) попыток ожидаемая чистая прибыль равна
$$h_t-c t.$$
Следовательно, прибыль на подмножестве равна
$$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr).$$
Код использует две простые оценки. При \(c=0\) ответ сразу равен максимальному доступному значению, то есть \(R(A,0)=\max(A)\). Если \(c\ge 1\) и \(A\subseteq\{1,\dots,d\}\), то \(h_t\le \max(A)\le d\), поэтому при \(t>d\)
$$h_t-c t\le d-t<0.$$
Так как при \(t=0\) прибыль уже равна \(0\), ни один горизонт больше \(d\) не может быть оптимальным для целочисленных стоимостей из основной суммы.
Для фиксированных \(d\) и \(c\) определим
$$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d.$$
Это главный шаг сжатия. После усреднения по всем \(k\)-элементным подмножествам конкретный состав подмножества уже не важен; остаётся только его размер \(k\). Вся подробная комбинаторная структура упаковывается в одно число \(a_k(c)\).
Пусть \(x_k\) обозначает ожидаемое полное супер-значение, когда текущее подмножество имеет мощность \(k\). Линейная система в реализациях показывает, что следующий переход зависит только от того, принадлежит ли равновероятно выбранная метка текущему подмножеству. Из состояния размера \(k<d\) имеем
$$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$$
Условившись по следующему шагу, получаем
$$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d.$$
Состояние \(k=0\) выступает как неявная нулевая граница. В верхнем состоянии \(k=d\) следующий шаг обязан перейти в \(d-1\), поэтому
$$x_d=a_d(c)+x_{d-1}.$$
После переноса слагаемых получаем трёхдиагональную систему линейных уравнений, и искомое значение для пары \((d,c)\) равно
$$S(d,c)=x_d.$$
Когда значения \(S(d,c)\) найдены для всех \(d\) и всех целых стоимостей \(0\le c\le n\), задача требует вычислить двойную сумму
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
Именно эту величину реализации накапливают перед окончательным округлением.
Здесь \(k=4\). Рекурсия даёт
$$h_1=\frac{1+2+3+4}{4}=2.5,$$
$$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$$
$$h_3=\frac{3+3+3+4}{4}=3.25,$$
$$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375.$$
Соответствующие прибыли равны
$$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375.$$
Максимум достигается при \(t=3\), откуда
$$R(\{1,2,3,4\},0.2)=2.65.$$
Вторая контрольная точка, \(S(6,1)=208.3\), проверяет уже стадию усреднения и решение трёхдиагональной системы.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Для каждого \(d\) они перебирают все непустые подмножества множества \(\{1,\dots,d\}\) с помощью битовых масок. Установленные биты уже задают подмножество в возрастающем порядке, поэтому дополнительная сортировка не требуется.
Для каждого подмножества реализация вычисляет наилучшую чистую прибыль сразу для всех целочисленных стоимостей \(c=0,1,\dots,n\). Случай \(c=0\) обрабатывается напрямую как максимум элементов подмножества. Для \(c\ge 1\) рекурсия для \(h_t\) продвигается только до \(t=d\), а значения \(h_t-c t\) одновременно обновляются для всех стоимостей.
Далее эти прибыли суммируются по корзинам, индексированным размером подмножества \(k\). После обработки всех подмножеств каждая сумма делится на число подмножеств соответствующего размера, и так получаются средние \(a_k(c)\).
Затем для каждого фиксированного \(c\) реализация строит трёхдиагональную систему, соответствующую уравнениям Беллмана выше, и решает её методом прямого исключения с обратной подстановкой. Последняя компонента и есть \(S(d,c)\). В конце все значения \(S(d,c)\) для \(d=4,\dots,n\) и \(c=0,\dots,n\) суммируются, после чего итог округляется до ближайшего целого.
Для фиксированного \(d\) существует \(2^d-1\) непустых подмножеств. Обработка одного подмножества требует \(O(d)\) времени на извлечение элементов, \(O(dk)\) времени на продвижение рекурсии по \(t=1,\dots,d\) и \(O(dn)\) времени на обновление всех целочисленных стоимостей, где \(k\le d\). Поэтому стоимость одного подмножества в худшем случае равна \(O(d(d+n))\), а доминирующая трудоёмкость для данного \(d\) имеет вид
$$O\bigl(2^d\,d(d+n)\bigr).$$
Решение трёхдиагональной системы добавляет только \(O(nd)\) времени для того же \(d\), что значительно меньше перебора подмножеств. После суммирования по \(d=4,\dots,n\) алгоритм остаётся точным, но экспоненциальным и определяется наибольшей размерностью; когда \(d\) имеет порядок \(n\), общая оценка составляет примерно \(O(2^n n^2)\). Рабочая память равна \(O(d(n+1))\) для таблицы средних по уровням и \(O(d)\) для векторов линейной системы; дополнительные копии возникают только при использовании параллельных рабочих потоков.
لكل بُعد \(d\) ولكل كلفة رمية \(c\)، نحسب أولاً أفضل ربح صافٍ متوقَّع للعبة Ramvok العادية على مجموعة جزئية غير فارغة ثابتة \(A\subseteq\{1,\dots,d\}\). بعد ذلك نأخذ متوسط هذه الأرباح على جميع المجموعات الجزئية ذات الحجم نفسه. ثم تُستعمل هذه المتوسطات في عملية ثانية لا تعتمد حالتها إلا على حجم المجموعة الجزئية الحالي. قيمة هذه العملية تُكتب \(S(d,c)\)، والكمية المطلوبة في النهاية هي
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
كما تتحقق البرامج من نقطتي اختبار مهمتين:
$$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$$
ثبّت \(d\ge 4\)، وكلفة \(c\)، ومجموعة جزئية غير فارغة
$$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k.$$
الطريقة الدقيقة المستعملة في التنفيذ تمر بثلاث طبقات: تحسين اللعبة العادية على مجموعة جزئية واحدة، ثم أخذ المتوسط بحسب الحجم، ثم حل نظام Bellman أحادي البعد للعبة الفائقة.
لتكن \(h_t\) أفضل مكافأة إجمالية متوقعة عندما تكون القيم المتاحة هي عناصر \(A\) فقط، ويُسمح بما لا يزيد على \(t\) رميات إضافية. العلاقة التراجعية المستعملة هي
$$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$$
هذه علاقة توقف أمثل. في الرمية الأولى تظهر إحدى القيم \(v_i\) باحتمال \(1/k\). بعد رؤية \(v_i\)، يمكن التوقف فوراً وأخذ \(v_i\)، أو المتابعة واستبدالها بقيمة المتابعة \(h_{t-1}\). لذلك تكون مساهمة النتيجة \(v_i\) هي \(\max(v_i,h_{t-1})\)، وأخذ المتوسط على جميع النتائج يعطينا الصيغة السابقة.
إذا كانت كل رمية تكلف \(c\)، فإن السماح بعددٍ مقداره \(t\) من الرميات يعطي ربحاً صافياً متوقعاً يساوي
$$h_t-c t.$$
ومن ثم يكون ربح المجموعة الجزئية
$$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr).$$
يستفيد التنفيذ من حدين بسيطين. إذا كان \(c=0\)، فالقيمة تساوي أكبر عنصر متاح مباشرة، أي \(R(A,0)=\max(A)\). وإذا كان \(c\ge 1\) وكانت \(A\subseteq\{1,\dots,d\}\)، فلدينا دائماً \(h_t\le \max(A)\le d\)، ولذلك عندما \(t>d\) نحصل على
$$h_t-c t\le d-t<0.$$
وبما أن \(t=0\) يعطي ربحاً مقداره \(0\)، فلا يمكن أن يكون أي أفق أكبر من \(d\) هو الأمثل في حالة التكاليف الصحيحة المستعملة في المجموع الرئيسي.
لـ \(d\) و\(c\) ثابتين نعرّف
$$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d.$$
هذه هي خطوة الضغط الأساسية. بعد أخذ المتوسط على جميع المجموعات الجزئية ذات الحجم \(k\)، لا تعود هوية المجموعة نفسها مهمة، بل يصبح المهم فقط هو حجمها \(k\). كل التفاصيل التركيبية الدقيقة تُضغط داخل العدد الواحد \(a_k(c)\).
لتكن \(x_k\) القيمة الكلية المتوقعة للعبة الفائقة عندما يكون حجم المجموعة الجزئية الحالية هو \(k\). يوضح النظام الخطي في التنفيذ أن الانتقال التالي يعتمد فقط على ما إذا كانت العلامة المختارة بانتظام موجودة بالفعل أم غير موجودة. من حالة حجمها \(k<d\) نحصل على
$$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$$
وبالتالي، بعد التكييف على الخطوة التالية، نجد
$$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d.$$
الحالة \(k=0\) تمثل حداً صفرياً ضمنياً. أما عند \(k=d\)، فلا يمكن إلا الانتقال إلى \(d-1\)، ولذلك يكون الشرط الحدي
$$x_d=a_d(c)+x_{d-1}.$$
بإعادة ترتيب هذه المعادلات نحصل على نظام خطي ثلاثي القطر، وتكون القيمة المطلوبة للزوج \((d,c)\) هي
$$S(d,c)=x_d.$$
بعد حساب \(S(d,c)\) لكل \(d\) ولكل كلفة صحيحة \(0\le c\le n\)، تطلب المسألة المجموع المزدوج
$$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$$
وهذه هي الكمية نفسها التي تجمعها البرامج قبل التقريب النهائي.
هنا \(k=4\). تعطي العلاقة التراجعية
$$h_1=\frac{1+2+3+4}{4}=2.5,$$
$$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$$
$$h_3=\frac{3+3+3+4}{4}=3.25,$$
$$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375.$$
ومن ثم تكون الأرباح الصافية
$$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375.$$
إذن القيمة المثلى تتحقق عند \(t=3\)، أي
$$R(\{1,2,3,4\},0.2)=2.65.$$
أما نقطة الاختبار الثانية \(S(6,1)=208.3\) فتؤكد أن مرحلة المتوسطات وحل النظام ثلاثي القطر قد بُنِيا بطريقة صحيحة أيضاً.
تتبع تطبيقات C++ وPython وJava السلسلة الرياضية نفسها. لكل \(d\)، تُعَدِّد جميع المجموعات الجزئية غير الفارغة من \(\{1,\dots,d\}\) باستعمال أقنعة البتات. والبتات المفعّلة تحدد العناصر بترتيب تصاعدي من الأصل، لذلك لا حاجة إلى فرز إضافي.
لكل مجموعة جزئية، يحسب التنفيذ أفضل ربح صافٍ لجميع القيم الصحيحة للكلفة \(c=0,1,\dots,n\). حالة \(c=0\) تُعالج فوراً بأخذ أكبر عنصر في المجموعة. أما عندما \(c\ge 1\)، فتُدفَع علاقة \(h_t\) حتى \(t=d\) فقط، ويجري تحديث أفضل القيم \(h_t-c t\) لجميع الكلف في آن واحد.
بعد ذلك تُجمع هذه الأرباح في حاويات مفهرسة بحجم المجموعة الجزئية \(k\). وعند انتهاء التعداد، يُقسَم مجموع كل حاوية على عدد المجموعات من ذلك الحجم للحصول على المتوسطات \(a_k(c)\).
ثم، لكل كلفة ثابتة \(c\)، يبني التنفيذ النظام ثلاثي القطر الموافق لمعادلات Bellman السابقة ويحلّه بالحذف الأمامي ثم التعويض الخلفي. المركبة الأخيرة هي \(S(d,c)\). وفي النهاية تُجمع كل القيم \(S(d,c)\) على \(d=4,\dots,n\) و\(c=0,\dots,n\)، ثم يُقرَّب المجموع إلى أقرب عدد صحيح.
لـ \(d\) ثابت يوجد \(2^d-1\) مجموعة جزئية غير فارغة. معالجة مجموعة واحدة تتطلب زمناً مقداره \(O(d)\) لاستخراج عناصرها، و\(O(dk)\) لدفع العلاقة التراجعية عبر \(t=1,\dots,d\)، و\(O(dn)\) لتحديث جميع الكلف الصحيحة، حيث \(k\le d\). لذلك تكون كلفة المجموعة الواحدة في أسوأ حالة هي \(O(d(d+n))\)، ويصبح العبء الزمني المسيطر في ذلك البعد
$$O\bigl(2^d\,d(d+n)\bigr).$$
أما حل النظام ثلاثي القطر فلا يضيف إلا \(O(nd)\) زمناً لذلك \(d\)، وهو أصغر بكثير من كلفة تعداد المجموعات. وبعد الجمع على \(d=4,\dots,n\)، تبقى الخوارزمية الدقيقة أسية ويهيمن عليها أكبر بعد؛ وعندما يكون \(d\) من رتبة \(n\)، يمكن تلخيص الكلفة الكلية تقريباً بـ \(O(2^n n^2)\). من ناحية الذاكرة، نحتاج إلى \(O(d(n+1))\) لجدول المتوسطات حسب المستوى و\(O(d)\) لمتجهات النظام الخطي، مع نسخ إضافية فقط عند تشغيل عمّال متوازيين.