We must compute the success probability of the optimal decision rule for 25 independent probability pairs. For each \(k=25,26,\dots,49\), the parameter is \(q_k=k/100\), so each component compares \(q_k\) against its complement \(1-q_k\). After compressing one component into its net evidence, every component has three possible effects on the global decision, so a naive enumeration would still require \(3^{25}\) combined outcomes.
The quantity we want is not only \(\Pr(S>0)\). If the total evidence is exactly balanced, the two global interpretations are equally likely, so a tie contributes half credit. The target value is therefore
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
The implementations turn the original probabilistic comparison into a sum of independent log-likelihood contributions and then evaluate the exact tie rule without enumerating all \(3^{25}\) states at once.
For each \(k\in\{25,\dots,49\}\), define
$$q_k=\frac{k}{100},\qquad w_k=2\log\frac{1-q_k}{q_k}=2\log\frac{100-k}{k}.$$
One component contributes a signed amount \(X_k\) to the total log-likelihood ratio. The three possible values are
$$X_k\in\{+w_k,\,0,\,-w_k\},$$
with probabilities
$$\Pr(X_k=+w_k)=(1-q_k)^2,\qquad \Pr(X_k=0)=2q_k(1-q_k),\qquad \Pr(X_k=-w_k)=q_k^2.$$
This already explains why every component is ternary after aggregation: it can favor the correct global interpretation, remain neutral, or favor the opposite interpretation.
The 25 components are independent, so the total evidence is
$$S=\sum_{k=25}^{49} X_k.$$
The optimal decision is to choose the correct global interpretation when \(S>0\), to choose the wrong one when \(S<0\), and to split the mass evenly when \(S=0\). Hence
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
The direct state space has size \(3^{25}\), so the main task is to evaluate this probability exactly enough without brute force over all global combinations at once.
For one concrete global state, let \(\sigma_k\in\{-1,0,1\}\) indicate whether the \(k\)-th component contributes \(-w_k\), \(0\), or \(+w_k\). Then
$$S=\sum_{k=25}^{49} \sigma_k\,2\log\frac{100-k}{k}=\log\left(\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\right).$$
Therefore the sign of \(S\) is exactly the same as the comparison
$$\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\mathop{\gtrless}_{=}\,1.$$
This reformulation is crucial. Floating-point logarithms are convenient for sorting and thresholding, but ties and near-ties must be decided by exact rational arithmetic, not by rounded decimal values.
All numbers involved come from the fixed set \(k\) and \(100-k\) for \(25\le k\le 49\), so only a fixed finite set of primes can appear. For each \(k\), write
$$\left(\frac{100-k}{k}\right)^2=\prod_{p} p^{e_{k,p}}.$$
If a global state uses the signs \(\sigma_k\), then the total exponent of a prime \(p\) becomes
$$E_p=\sum_{k=25}^{49}\sigma_k e_{k,p}.$$
The exact product is then
$$\prod_{p} p^{E_p}=\frac{\prod_{E_p>0} p^{E_p}}{\prod_{E_p<0} p^{-E_p}}.$$
So checking whether \(S\) is positive, zero, or negative reduces to an exact integer comparison between one numerator and one denominator built from these exponents.
Split the 25 components into two groups of sizes \(12\) and \(13\). For each half, enumerate all ternary states. A half-state stores three pieces of information:
$$\text{approximate score},\qquad \text{probability mass},\qquad \text{exact prime-exponent vector}.$$
After sorting the right-half states by approximate score, a left-half state with score \(s_L\) only needs right-half states with score near \(-s_L\) for possible ties. All right states with clearly larger score make the total positive automatically and can be summed at once by prefix sums.
This is why the method is fast: exact arithmetic is used only in a very narrow band around the decision boundary, not for every pair of states.
Take \(k=25\). Then \(q=\frac{1}{4}\) and
$$w=2\log\frac{3}{1}=2\log 3.$$
The three local outcomes are
$$+w\text{ with probability }\left(\frac{3}{4}\right)^2=\frac{9}{16},\qquad 0\text{ with probability }2\cdot\frac{1}{4}\cdot\frac{3}{4}=\frac{6}{16},\qquad -w\text{ with probability }\left(\frac{1}{4}\right)^2=\frac{1}{16}.$$
For this one-pair toy case, the optimal accuracy is
$$\frac{9}{16}+\frac{1}{2}\cdot\frac{6}{16}=\frac{12}{16}=\frac{3}{4}.$$
The full problem uses the same rule, but now all 25 ternary contributions are combined.
The C++, Python, and Java implementations use the same pipeline. They first build the fixed prime basis coming from the integers \(k\) and \(100-k\) for \(25\le k\le 49\). For each of the 25 components they then precompute the floating-point weight \(w_k\), the three local probabilities \((1-q_k)^2\), \(2q_k(1-q_k)\), and \(q_k^2\), and the exact prime-exponent representation of \(\left(\frac{100-k}{k}\right)^2\).
Next, the implementation enumerates all ternary states in a left half and a right half. Every stored state contains an approximate score, its probability mass, and its exact exponent vector. The right-half states are sorted by approximate score, and a prefix-sum array lets the program add the probability of all definitely winning combinations immediately after a binary search.
Only combinations whose approximate score falls inside a tiny neighborhood of zero need extra care. For that narrow band, the implementation combines the two exponent vectors, reconstructs an exact rational comparison with arbitrary-precision integers, and decides whether the product is greater than \(1\), equal to \(1\), or less than \(1\). That exact sign determines whether the combination contributes full probability, half probability, or nothing.
Let \(L=3^{12}\) and \(R=3^{13}\). Enumerating the two halves costs \(O(L+R)\). Sorting the right-half states costs \(O(R\log R)\). For each left-half state, the merge phase performs two binary searches, so the main combination work is \(O(L\log R)\), plus a smaller extra term for the exact checks inside the near-tie window. Memory usage is \(O(L+R)\) states, with only a fixed small prime-exponent vector attached to each state.
Gesucht ist die Erfolgswahrscheinlichkeit der optimalen Entscheidungsregel für 25 unabhängige Wahrscheinlichkeits-Paare. Für jedes \(k=25,26,\dots,49\) gilt \(q_k=k/100\), also vergleicht jede Komponente \(q_k\) mit dem Komplement \(1-q_k\). Verdichtet man eine Komponente auf ihren Netto-Beitrag zur Evidenz, bleiben pro Komponente genau drei Möglichkeiten, sodass eine naive Gesamtauswertung immer noch \(3^{25}\) Zustände hätte.
Die Zielgröße ist nicht nur \(\Pr(S>0)\). Wenn die gesamte Evidenz exakt ausgeglichen ist, sind beide globalen Interpretationen gleich wahrscheinlich; ein Gleichstand zählt daher mit dem Faktor \(\frac{1}{2}\). Gesucht ist also
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
Die Implementierungen übersetzen den probabilistischen Vergleich in eine Summe unabhängiger Log-Likelihood-Beiträge und behandeln Gleichstände exakt, ohne alle \(3^{25}\) Zustände gleichzeitig auszuwerten.
Für jedes \(k\in\{25,\dots,49\}\) definieren wir
$$q_k=\frac{k}{100},\qquad w_k=2\log\frac{1-q_k}{q_k}=2\log\frac{100-k}{k}.$$
Der Beitrag der \(k\)-ten Komponente zur gesamten Log-Likelihood sei \(X_k\). Es gibt genau drei mögliche Werte:
$$X_k\in\{+w_k,\,0,\,-w_k\},$$
mit Wahrscheinlichkeiten
$$\Pr(X_k=+w_k)=(1-q_k)^2,\qquad \Pr(X_k=0)=2q_k(1-q_k),\qquad \Pr(X_k=-w_k)=q_k^2.$$
Damit ist jede Komponente nach der Verdichtung ternär: Sie spricht entweder für die richtige globale Interpretation, ist neutral oder spricht für die falsche.
Wegen der Unabhängigkeit der 25 Komponenten ist die gesamte Evidenz
$$S=\sum_{k=25}^{49} X_k.$$
Die optimale Regel wählt die richtige globale Interpretation für \(S>0\), die falsche für \(S<0\) und teilt die Masse bei \(S=0\) gleich auf. Also gilt
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
Die direkte Zustandszahl ist \(3^{25}\). Das eigentliche Problem besteht daher darin, diese Wahrscheinlichkeit exakt genug zu berechnen, ohne brutale Gesamtenumeration.
Für einen konkreten Gesamtzustand bezeichne \(\sigma_k\in\{-1,0,1\}\), ob die \(k\)-te Komponente \(-w_k\), \(0\) oder \(+w_k\) beiträgt. Dann ist
$$S=\sum_{k=25}^{49} \sigma_k\,2\log\frac{100-k}{k}=\log\left(\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\right).$$
Das Vorzeichen von \(S\) ist also exakt äquivalent zum Vergleich
$$\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\mathop{\gtrless}_{=}\,1.$$
Diese Umformung ist entscheidend: Gleitkomma-Logarithmen sind praktisch zum Sortieren, aber Gleichstände und Fast-Gleichstände müssen mit exakter rationaler Arithmetik entschieden werden.
Alle Zahlen stammen aus der festen Menge \(k\) und \(100-k\) mit \(25\le k\le 49\), also kann nur eine feste endliche Primmenge auftreten. Für jedes \(k\) schreiben wir
$$\left(\frac{100-k}{k}\right)^2=\prod_{p} p^{e_{k,p}}.$$
Verwendet ein Gesamtzustand die Vorzeichen \(\sigma_k\), so ist der Gesamtexponent einer Primzahl \(p\)
$$E_p=\sum_{k=25}^{49}\sigma_k e_{k,p}.$$
Das exakte Produkt ist dann
$$\prod_{p} p^{E_p}=\frac{\prod_{E_p>0} p^{E_p}}{\prod_{E_p<0} p^{-E_p}}.$$
Die Frage, ob \(S\) positiv, null oder negativ ist, wird damit zu einem exakten Integer-Vergleich zwischen einem Zähler und einem Nenner, die aus diesen Exponenten aufgebaut werden.
Die 25 Komponenten werden in Gruppen der Größen \(12\) und \(13\) geteilt. Für jede Hälfte werden alle ternären Zustände enumeriert. Ein Halbstaat speichert drei Informationen:
$$\text{approximativer Score},\qquad \text{Wahrscheinlichkeitsmasse},\qquad \text{exakter Primexponentenvektor}.$$
Nach dem Sortieren der rechten Hälfte nach approximativem Score braucht ein linker Zustand mit Score \(s_L\) nur noch rechte Zustände nahe \(-s_L\) für mögliche Gleichstände. Alle rechten Zustände mit klar größerem Score machen die Gesamtsumme automatisch positiv und können per Präfixsummen auf einmal addiert werden.
Genau deshalb ist die Methode schnell: Exakte Arithmetik wird nur in einem sehr schmalen Band um die Entscheidungsgrenze benötigt, nicht für jedes Zustandspaar.
Setze \(k=25\). Dann ist \(q=\frac{1}{4}\) und
$$w=2\log\frac{3}{1}=2\log 3.$$
Die drei lokalen Möglichkeiten sind
$$+w\text{ mit Wahrscheinlichkeit }\left(\frac{3}{4}\right)^2=\frac{9}{16},\qquad 0\text{ mit Wahrscheinlichkeit }2\cdot\frac{1}{4}\cdot\frac{3}{4}=\frac{6}{16},\qquad -w\text{ mit Wahrscheinlichkeit }\left(\frac{1}{4}\right)^2=\frac{1}{16}.$$
Für dieses Ein-Komponenten-Beispiel ist die optimale Genauigkeit
$$\frac{9}{16}+\frac{1}{2}\cdot\frac{6}{16}=\frac{12}{16}=\frac{3}{4}.$$
Im vollständigen Problem wird dieselbe Regel auf die Summe aller 25 ternären Beiträge angewendet.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst wird die feste Primzahlbasis aus den Zahlen \(k\) und \(100-k\) für \(25\le k\le 49\) aufgebaut. Für jede der 25 Komponenten werden dann das Gleitkomma-Gewicht \(w_k\), die drei lokalen Wahrscheinlichkeiten \((1-q_k)^2\), \(2q_k(1-q_k)\) und \(q_k^2\) sowie die exakte Primexponenten-Darstellung von \(\left(\frac{100-k}{k}\right)^2\) vorbereitet.
Anschließend enumeriert die Implementierung alle ternären Zustände in einer linken und einer rechten Hälfte. Jeder gespeicherte Zustand enthält einen approximativen Score, seine Wahrscheinlichkeitsmasse und den exakten Exponentenvektor. Die Zustände der rechten Hälfte werden nach dem approximativen Score sortiert, und ein Präfixsummen-Array erlaubt es, die Wahrscheinlichkeit aller sicher gewinnenden Kombinationen direkt nach einer Binärsuche zu addieren.
Nur Kombinationen, deren approximativer Score in einer winzigen Umgebung von null liegt, benötigen Sonderbehandlung. In diesem schmalen Band werden die beiden Exponentenvektoren kombiniert, zu einem exakten rationalen Vergleich mit Ganzzahlen beliebiger Länge rekonstruiert und dann als größer als \(1\), gleich \(1\) oder kleiner als \(1\) klassifiziert. Dieses exakte Vorzeichen entscheidet über volle, halbe oder keine Wahrscheinlichkeitsgutschrift.
Seien \(L=3^{12}\) und \(R=3^{13}\). Das Enumerieren der beiden Hälften kostet \(O(L+R)\). Das Sortieren der rechten Hälfte kostet \(O(R\log R)\). Für jeden linken Zustand werden in der Zusammenführung zwei Binärsuchen ausgeführt, also kostet die Hauptphase \(O(L\log R)\), zuzüglich eines kleineren Zusatzterms für die exakten Prüfungen innerhalb des Fast-Gleichstandsfensters. Der Speicherbedarf beträgt \(O(L+R)\) Zustände; an jedem Zustand hängt nur ein fester kleiner Primexponentenvektor.
Burada amaç, 25 bağımsız olasılık çifti için en iyi karar kuralının başarı olasılığını hesaplamaktır. Her \(k=25,26,\dots,49\) için \(q_k=k/100\) alınır ve her bileşen \(q_k\) ile tamamlayıcısı \(1-q_k\) arasında bir karşılaştırma üretir. Tek bir bileşeni net kanıt katkısına indirgediğimizde her bileşenin yalnızca üç olası etkisi kaldığı için doğrudan tarama yine de \(3^{25}\) durum gerektirir.
Aranan büyüklük yalnızca \(\Pr(S>0)\) değildir. Toplam kanıt tam olarak dengelenirse iki genel yorum eşit olasılıklıdır; bu nedenle beraberlikler yarım puan değerindedir. Hesaplanması gereken ifade
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0)$$
olur.
Uygulamalar, asıl olasılık problemini bağımsız log-olasılık oranı katkılarının toplamına dönüştürür ve beraberlikleri bütün \(3^{25}\) durumu aynı anda saymadan tam olarak işler.
Her \(k\in\{25,\dots,49\}\) için
$$q_k=\frac{k}{100},\qquad w_k=2\log\frac{1-q_k}{q_k}=2\log\frac{100-k}{k}$$
tanımlarını yapalım. \(k\)-inci bileşenin toplam log-olasılık oranına katkısı \(X_k\) olsun. Bu katkı yalnızca şu üç değerden birini alır:
$$X_k\in\{+w_k,\,0,\,-w_k\}.$$
Olasılıklar ise
$$\Pr(X_k=+w_k)=(1-q_k)^2,\qquad \Pr(X_k=0)=2q_k(1-q_k),\qquad \Pr(X_k=-w_k)=q_k^2$$
şeklindedir. Böylece her bileşen ya doğru genel yorumu destekler, ya nötr kalır ya da ters yönde kanıt üretir.
25 bileşen bağımsız olduğundan toplam kanıt
$$S=\sum_{k=25}^{49} X_k$$
olur. En iyi karar kuralı \(S>0\) ise doğru genel yorumu seçer, \(S<0\) ise yanlışı seçer ve \(S=0\) ise olasılığı ikiye böler. Dolayısıyla
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0)$$
elde edilir. Doğrudan durum uzayı \(3^{25}\) olduğu için hedef, bu değeri tamlıktan ödün vermeden daha akıllı bir şekilde hesaplamaktır.
Belirli bir genel durumda \(\sigma_k\in\{-1,0,1\}\), \(k\)-inci bileşenin sırasıyla \(-w_k\), \(0\) veya \(+w_k\) katkı verdiğini göstersin. O zaman
$$S=\sum_{k=25}^{49} \sigma_k\,2\log\frac{100-k}{k}=\log\left(\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\right).$$
Demek ki \(S\)'nin işareti tam olarak şu karşılaştırmaya eşdeğerdir:
$$\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\mathop{\gtrless}_{=}\,1.$$
Bu dönüşüm çok önemlidir. Kayan noktalı logaritmalar sıralama ve eşik bulma için uygundur; ancak beraberlikler ve neredeyse beraberlikler yuvarlamayla değil, tam rasyonel karşılaştırmayla çözülmelidir.
Kullanılan tüm sayılar \(25\le k\le 49\) aralığındaki \(k\) ve \(100-k\) değerlerinden geldiği için ortaya çıkabilecek asal çarpanlar sabit bir kümedir. Her \(k\) için
$$\left(\frac{100-k}{k}\right)^2=\prod_{p} p^{e_{k,p}}$$
yazalım. Bir genel durumun seçtiği işaretler \(\sigma_k\) ise, asal \(p\)'nin toplam üssü
$$E_p=\sum_{k=25}^{49}\sigma_k e_{k,p}$$
olur. Böylece tam çarpım
$$\prod_{p} p^{E_p}=\frac{\prod_{E_p>0} p^{E_p}}{\prod_{E_p<0} p^{-E_p}}$$
şeklinde yazılır. Sonuç olarak \(S\)'nin pozitif, sıfır ya da negatif olup olmadığı; bu üslerden kurulan pay ve paydanın tam sayı karşılaştırmasına indirgenir.
25 bileşen \(12\) ve \(13\) elemanlı iki gruba ayrılır. Her yarı için tüm üç değerli durumlar üretilir. Bir yarı-durum üç bilgi taşır:
$$\text{yaklaşık skor},\qquad \text{olasılık kütlesi},\qquad \text{tam asal-üs vektörü}.$$
Sağ yarının durumları yaklaşık skora göre sıralandıktan sonra, skoru \(s_L\) olan bir sol durum için yalnızca \(-s_L\) civarındaki sağ durumlar beraberlik adayı olabilir. Skoru açık biçimde daha büyük olan tüm sağ durumlar toplam skoru otomatik olarak pozitif yapar ve prefix toplamlarla tek seferde eklenebilir.
Yöntemin verimli olmasının nedeni budur: tam aritmetik yalnızca karar sınırının çevresindeki çok dar bir bantta kullanılır.
\(k=25\) alalım. O zaman \(q=\frac{1}{4}\) ve
$$w=2\log\frac{3}{1}=2\log 3$$
olur. Üç yerel sonuç şunlardır:
$$+w\text{ olasılık }\left(\frac{3}{4}\right)^2=\frac{9}{16},\qquad 0\text{ olasılık }2\cdot\frac{1}{4}\cdot\frac{3}{4}=\frac{6}{16},\qquad -w\text{ olasılık }\left(\frac{1}{4}\right)^2=\frac{1}{16}.$$
Bu tek bileşenli oyuncak örnekte en iyi doğruluk
$$\frac{9}{16}+\frac{1}{2}\cdot\frac{6}{16}=\frac{12}{16}=\frac{3}{4}$$
çıkar. Tam problemde de aynı kural uygulanır; fark yalnızca 25 üç değerli katkının birlikte toplanmasıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(25\le k\le 49\) aralığındaki \(k\) ve \(100-k\) değerlerinden gelen sabit asal tabanı kurulur. Daha sonra 25 bileşenin her biri için kayan noktalı ağırlık \(w_k\), üç yerel olasılık \((1-q_k)^2\), \(2q_k(1-q_k)\), \(q_k^2\) ve \(\left(\frac{100-k}{k}\right)^2\) oranının tam asal-üs gösterimi önceden hazırlanır.
Sonraki adımda sol ve sağ yarılar için bütün üç değerli durumlar üretilir. Her kayıt, yaklaşık bir skor, o durumun olasılık kütlesi ve tam üs vektörü taşır. Sağ yarı skorlarına göre sıralanır; ardından prefix toplamlar sayesinde, ikili arama sonrasında kesin olarak kazandıran tüm sağ durumların olasılığı doğrudan eklenebilir.
Yaklaşık toplam skoru sıfıra çok yakın olan kombinasyonlar ayrıca incelenir. Bu dar bantta uygulama iki üs vektörünü birleştirir, tam rasyonel karşılaştırmayı büyük tamsayı aritmetiğiyle yapar ve sonucun \(1\)'den büyük, eşit ya da küçük olduğunu belirler. Bu işaret bilgisi, ilgili kombinasyonun tam puan, yarım puan veya sıfır katkı yapıp yapmadığını söyler.
\(L=3^{12}\) ve \(R=3^{13}\) olsun. İki yarının üretilmesi \(O(L+R)\) zaman alır. Sağ yarının sıralanması \(O(R\log R)\) zaman ister. Her sol durum için iki ikili arama yapıldığından birleştirme aşamasının ana maliyeti \(O(L\log R)\)'dir; buna, neredeyse beraberlik penceresindeki tam karşılaştırmalar için daha küçük bir ek terim eklenir. Bellek kullanımı \(O(L+R)\) durumdur ve her durumda yalnızca sabit küçük boyutlu bir asal-üs vektörü saklanır.
Hay que calcular la probabilidad de acierto de la regla de decisión óptima para 25 pares de probabilidades independientes. Para cada \(k=25,26,\dots,49\), se toma \(q_k=k/100\), así que cada componente contrapone \(q_k\) con su complemento \(1-q_k\). Cuando una componente se reduce a su evidencia neta, sólo quedan tres efectos posibles sobre la decisión global, de modo que una enumeración directa todavía tendría \(3^{25}\) casos.
La cantidad buscada no es solamente \(\Pr(S>0)\). Si la evidencia total queda exactamente empatada, las dos interpretaciones globales son igual de plausibles y el empate vale medio punto. Por tanto, la magnitud objetivo es
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
Las implementaciones convierten el problema probabilístico original en una suma de contribuciones independientes de log-verosimilitud y resuelven los empates de forma exacta sin recorrer a la vez los \(3^{25}\) estados.
Para cada \(k\in\{25,\dots,49\}\), definimos
$$q_k=\frac{k}{100},\qquad w_k=2\log\frac{1-q_k}{q_k}=2\log\frac{100-k}{k}.$$
La contribución de la componente \(k\) a la log-verosimilitud total será \(X_k\). Sólo puede tomar tres valores:
$$X_k\in\{+w_k,\,0,\,-w_k\},$$
con probabilidades
$$\Pr(X_k=+w_k)=(1-q_k)^2,\qquad \Pr(X_k=0)=2q_k(1-q_k),\qquad \Pr(X_k=-w_k)=q_k^2.$$
Así, cada componente ya queda resumida como evidencia a favor, evidencia neutra o evidencia en contra de la interpretación correcta.
Como las 25 componentes son independientes, la evidencia total es
$$S=\sum_{k=25}^{49} X_k.$$
La regla óptima escoge la interpretación correcta si \(S>0\), la incorrecta si \(S<0\), y reparte el peso por igual si \(S=0\). Por ello
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
El espacio directo tiene tamaño \(3^{25}\), así que el verdadero reto es evaluar esta probabilidad con exactitud suficiente sin hacer fuerza bruta completa.
Para un estado global concreto, sea \(\sigma_k\in\{-1,0,1\}\) el indicador de que la componente \(k\) aporta \(-w_k\), \(0\) o \(+w_k\). Entonces
$$S=\sum_{k=25}^{49} \sigma_k\,2\log\frac{100-k}{k}=\log\left(\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\right).$$
Por lo tanto, el signo de \(S\) equivale exactamente a decidir si
$$\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\mathop{\gtrless}_{=}\,1.$$
Esta reformulación es esencial. Los logaritmos en coma flotante sirven para ordenar y localizar umbrales, pero los empates y casi empates deben resolverse con aritmética racional exacta.
Todos los números provienen del conjunto fijo de valores \(k\) y \(100-k\) con \(25\le k\le 49\), así que sólo aparece un conjunto finito de primos. Para cada \(k\), escribimos
$$\left(\frac{100-k}{k}\right)^2=\prod_{p} p^{e_{k,p}}.$$
Si un estado global usa los signos \(\sigma_k\), entonces el exponente total del primo \(p\) es
$$E_p=\sum_{k=25}^{49}\sigma_k e_{k,p}.$$
El producto exacto toma la forma
$$\prod_{p} p^{E_p}=\frac{\prod_{E_p>0} p^{E_p}}{\prod_{E_p<0} p^{-E_p}}.$$
Así, decidir si \(S\) es positivo, nulo o negativo se reduce a una comparación exacta entre un numerador y un denominador enteros construidos a partir de esos exponentes.
Se dividen las 25 componentes en dos grupos de tamaños \(12\) y \(13\). En cada mitad se enumeran todos los estados ternarios. Un estado de media lista almacena tres datos:
$$\text{puntuación aproximada},\qquad \text{masa de probabilidad},\qquad \text{vector exacto de exponentes primos}.$$
Después de ordenar la mitad derecha por puntuación aproximada, un estado izquierdo con puntuación \(s_L\) sólo necesita examinar estados derechos cercanos a \(-s_L\) para detectar posibles empates. Todos los estados derechos con puntuación claramente mayor hacen que la suma total sea positiva automáticamente y pueden sumarse de una vez mediante prefijos.
Ahí está la ventaja del método: la aritmética exacta sólo se usa en una franja muy estrecha alrededor de la frontera de decisión.
Tomemos \(k=25\). Entonces \(q=\frac{1}{4}\) y
$$w=2\log\frac{3}{1}=2\log 3.$$
Los tres resultados locales son
$$+w\text{ con probabilidad }\left(\frac{3}{4}\right)^2=\frac{9}{16},\qquad 0\text{ con probabilidad }2\cdot\frac{1}{4}\cdot\frac{3}{4}=\frac{6}{16},\qquad -w\text{ con probabilidad }\left(\frac{1}{4}\right)^2=\frac{1}{16}.$$
En este caso de juguete con un solo par, la exactitud óptima vale
$$\frac{9}{16}+\frac{1}{2}\cdot\frac{6}{16}=\frac{12}{16}=\frac{3}{4}.$$
El problema completo usa exactamente la misma regla, pero sumando las 25 contribuciones ternarias.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen la base fija de primos que aparece en los enteros \(k\) y \(100-k\) para \(25\le k\le 49\). Después, para cada una de las 25 componentes, precalculan el peso en coma flotante \(w_k\), las tres probabilidades locales \((1-q_k)^2\), \(2q_k(1-q_k)\) y \(q_k^2\), y la representación exacta por exponentes primos de \(\left(\frac{100-k}{k}\right)^2\).
A continuación, la implementación enumera todos los estados ternarios de una mitad izquierda y una mitad derecha. Cada estado guardado contiene una puntuación aproximada, su masa de probabilidad y su vector exacto de exponentes. Los estados de la mitad derecha se ordenan por puntuación aproximada, y un arreglo de sumas prefijo permite añadir inmediatamente la probabilidad de todas las combinaciones claramente ganadoras tras una búsqueda binaria.
Sólo requieren tratamiento adicional las combinaciones cuyo valor aproximado cae en una vecindad minúscula de cero. En esa banda estrecha, la implementación combina los dos vectores de exponentes, reconstruye una comparación racional exacta con enteros de precisión arbitraria y decide si el producto es mayor que \(1\), igual a \(1\) o menor que \(1\). Ese signo exacto determina si la combinación aporta probabilidad completa, media probabilidad o nada.
Sea \(L=3^{12}\) y \(R=3^{13}\). Enumerar las dos mitades cuesta \(O(L+R)\). Ordenar los estados de la mitad derecha cuesta \(O(R\log R)\). Para cada estado izquierdo, la fase de combinación realiza dos búsquedas binarias, así que el trabajo principal es \(O(L\log R)\), más un término adicional menor debido a las comprobaciones exactas dentro de la ventana de casi empate. La memoria es \(O(L+R)\) estados, y cada estado sólo lleva asociado un vector pequeño y fijo de exponentes primos.
本题要求计算 25 个独立概率对所对应的最优判别规则的成功概率。对每个 \(k=25,26,\dots,49\)，参数取为 \(q_k=k/100\)，因此每一项都在 \(q_k\) 与其补概率 \(1-q_k\) 之间形成一份局部证据。把单项压缩成净证据之后，每项只剩下三种可能影响，所以如果直接枚举整体情况，仍然需要处理 \(3^{25}\) 个组合状态。
目标量并不只是 \(\Pr(S>0)\)。如果总证据恰好打平，那么两种整体解释同样可能，平局只能记半分。因此真正要求的是
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
这些实现先把原问题改写成若干独立对数似然贡献的求和，再用折半搜索和精确有理数比较来处理边界情况，从而避免一次性枚举全部 \(3^{25}\) 个状态。
对每个 \(k\in\{25,\dots,49\}\)，定义
$$q_k=\frac{k}{100},\qquad w_k=2\log\frac{1-q_k}{q_k}=2\log\frac{100-k}{k}.$$
记第 \(k\) 项对总对数似然比的贡献为 \(X_k\)。它只可能取三种值：
$$X_k\in\{+w_k,\,0,\,-w_k\}.$$
对应概率分别是
$$\Pr(X_k=+w_k)=(1-q_k)^2,\qquad \Pr(X_k=0)=2q_k(1-q_k),\qquad \Pr(X_k=-w_k)=q_k^2.$$
这一步解释了为什么原始局部结构可以压缩成三叉分支：它要么支持正确的整体解释，要么不提供净证据，要么支持相反的整体解释。
由于 25 项彼此独立，总证据就是
$$S=\sum_{k=25}^{49} X_k.$$
最优规则在 \(S>0\) 时选择正确的整体解释，在 \(S<0\) 时选择错误解释，而在 \(S=0\) 时把概率质量平均分给两边。因此
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
如果直接对全部情况做朴素枚举，状态数就是 \(3^{25}\)。因此真正的难点在于：既要保持边界判断的精确性，又要避免完整暴力搜索。
对某个具体整体状态，用 \(\sigma_k\in\{-1,0,1\}\) 表示第 \(k\) 项分别贡献 \(-w_k\)、\(0\)、或 \(+w_k\)。于是
$$S=\sum_{k=25}^{49} \sigma_k\,2\log\frac{100-k}{k}=\log\left(\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\right).$$
因此，\(S\) 的符号与下面这个乘积和 \(1\) 的大小关系完全等价：
$$\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\mathop{\gtrless}_{=}\,1.$$
这一步非常关键。浮点对数很适合做排序和阈值定位，但在 \(S\) 非常接近 \(0\) 时，任何舍入误差都可能把平局误判成正或负。改写成精确有理数比较以后，临界情况就能被严格处理。
所有用到的数都来自固定集合 \(k\) 和 \(100-k\)（其中 \(25\le k\le 49\)），所以可能出现的质数集合也是固定且有限的。对每个 \(k\)，写成
$$\left(\frac{100-k}{k}\right)^2=\prod_{p} p^{e_{k,p}}.$$
如果整体状态选择了符号 \(\sigma_k\)，那么质数 \(p\) 的总指数就是
$$E_p=\sum_{k=25}^{49}\sigma_k e_{k,p}.$$
于是精确乘积可以写成
$$\prod_{p} p^{E_p}=\frac{\prod_{E_p>0} p^{E_p}}{\prod_{E_p<0} p^{-E_p}}.$$
也就是说，只要把所有正指数放到分子、负指数放到分母，就能通过整数比较精确判断整体乘积是大于 \(1\)、等于 \(1\) 还是小于 \(1\)。这正是平局判定所需要的信息。
把 25 项拆成大小分别为 \(12\) 和 \(13\) 的两半。对每一半枚举所有三值状态，并为每个半状态保存三类信息：
$$\text{近似得分},\qquad \text{概率质量},\qquad \text{精确的质数指数向量}.$$
随后按近似得分对右半部分排序。对于左半部分中一个得分为 \(s_L\) 的状态，只有右半部分中接近 \(-s_L\) 的状态才可能造成总和接近 \(0\) 的平局。那些得分明显更大的右侧状态会自动使总和为正，因此可以用前缀和一次性累加，无须逐个做精确判断。
这就是算法高效的原因：真正昂贵的精确大整数比较只发生在零附近的极窄窗口中，而不是发生在左右两半所有状态对之间。
取 \(k=25\)。此时 \(q=\frac{1}{4}\)，并且
$$w=2\log\frac{3}{1}=2\log 3.$$
三种局部结果分别为
$$+w\text{ 的概率是 }\left(\frac{3}{4}\right)^2=\frac{9}{16},\qquad 0\text{ 的概率是 }2\cdot\frac{1}{4}\cdot\frac{3}{4}=\frac{6}{16},\qquad -w\text{ 的概率是 }\left(\frac{1}{4}\right)^2=\frac{1}{16}.$$
如果只考虑这一项，那么最优判别成功率就是
$$\frac{9}{16}+\frac{1}{2}\cdot\frac{6}{16}=\frac{12}{16}=\frac{3}{4}.$$
完整题目只是把同样的规则扩展到 25 个独立的三值贡献之和。
C++、Python 和 Java 实现采用同一条主线。首先，它们从所有 \(25\le k\le 49\) 的 \(k\) 与 \(100-k\) 中提取会出现的质数，建立固定的质数基。然后，对 25 个局部组件中的每一个，预先计算浮点形式的权重 \(w_k\)、三种局部概率 \((1-q_k)^2\)、\(2q_k(1-q_k)\)、\(q_k^2\)，以及比值 \(\left(\frac{100-k}{k}\right)^2\) 的精确质因数指数表示。
接下来，程序分别枚举左半与右半的全部三值状态。每个记录同时携带近似得分、该状态的概率质量和精确指数向量。右半状态按近似得分排序，并建立前缀概率和；这样一来，对任意左侧状态，只要通过二分找到阈值位置，就能立刻累加所有“必然胜出”的右侧质量。
只有那些近似总得分落在零附近极小区间内的组合，才需要额外处理。对这部分组合，程序把左右两边的指数向量相加，用任意精度整数重建出精确的分子与分母，并比较乘积相对于 \(1\) 的大小。这个精确符号直接决定该组合应计入全部概率、半个概率，还是完全不计入。
记 \(L=3^{12}\)，\(R=3^{13}\)。两半状态的枚举代价是 \(O(L+R)\)。右半部分排序需要 \(O(R\log R)\)。对每个左半状态，在合并阶段只需要做两次二分搜索，因此主合并代价为 \(O(L\log R)\)，外加一个更小的附加项，用来处理接近平局窗口中的精确比较。空间复杂度为 \(O(L+R)\) 个状态，而每个状态额外携带的质数指数向量大小是固定且很小的。
Нужно вычислить вероятность успеха оптимального правила классификации для 25 независимых пар вероятностей. Для каждого \(k=25,26,\dots,49\) берётся параметр \(q_k=k/100\), то есть каждая компонента сравнивает \(q_k\) с дополнением \(1-q_k\). После сжатия одной компоненты до её чистого вклада в итоговую доказательность у каждой компоненты остаётся только три возможных эффекта, так что прямой перебор всё равно имел бы размер \(3^{25}\).
Искомая величина не сводится к \(\Pr(S>0)\). Если суммарная доказательность точно равна нулю, обе глобальные интерпретации одинаково правдоподобны, поэтому ничья даёт половинный вклад. Следовательно, требуется вычислить
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
Реализации переводят исходную вероятностную задачу в сумму независимых вкладов логарифма отношения правдоподобий, а затем обрабатывают ничьи точно, не перебирая все \(3^{25}\) состояний сразу.
Для каждого \(k\in\{25,\dots,49\}\) введём
$$q_k=\frac{k}{100},\qquad w_k=2\log\frac{1-q_k}{q_k}=2\log\frac{100-k}{k}.$$
Пусть вклад \(k\)-й компоненты в общий логарифм отношения правдоподобий равен \(X_k\). Тогда возможны только три значения:
$$X_k\in\{+w_k,\,0,\,-w_k\}.$$
Соответствующие вероятности таковы:
$$\Pr(X_k=+w_k)=(1-q_k)^2,\qquad \Pr(X_k=0)=2q_k(1-q_k),\qquad \Pr(X_k=-w_k)=q_k^2.$$
Тем самым каждая компонента после сжатия либо поддерживает правильную глобальную интерпретацию, либо ничего не меняет, либо поддерживает противоположную интерпретацию.
Так как все 25 компонент независимы, суммарная доказательность равна
$$S=\sum_{k=25}^{49} X_k.$$
Оптимальное правило выбирает правильную интерпретацию при \(S>0\), неправильную при \(S<0\), а при \(S=0\) делит массу пополам. Поэтому
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
Прямое пространство состояний имеет размер \(3^{25}\), поэтому основная задача состоит в том, чтобы вычислить эту вероятность точно, но без полного грубого перебора.
Для конкретного глобального состояния обозначим через \(\sigma_k\in\{-1,0,1\}\), даёт ли \(k\)-я компонента вклад \(-w_k\), \(0\) или \(+w_k\). Тогда
$$S=\sum_{k=25}^{49} \sigma_k\,2\log\frac{100-k}{k}=\log\left(\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\right).$$
Следовательно, знак \(S\) в точности определяется сравнением
$$\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\mathop{\gtrless}_{=}\,1.$$
Это ключевой шаг. Плавающая точка удобна для сортировки и оценки порога, но ничьи и почти ничьи нужно решать на уровне точной рациональной арифметики, а не по округлённым логарифмам.
Все числа возникают из фиксированного набора \(k\) и \(100-k\) при \(25\le k\le 49\), поэтому множество возможных простых чисел конечно и заранее фиксировано. Для каждого \(k\) можно записать
$$\left(\frac{100-k}{k}\right)^2=\prod_{p} p^{e_{k,p}}.$$
Если глобальное состояние использует знаки \(\sigma_k\), то суммарный показатель простого \(p\) равен
$$E_p=\sum_{k=25}^{49}\sigma_k e_{k,p}.$$
Тогда точное произведение принимает вид
$$\prod_{p} p^{E_p}=\frac{\prod_{E_p>0} p^{E_p}}{\prod_{E_p<0} p^{-E_p}}.$$
Значит, вопрос о том, положителен ли \(S\), равен ли нулю или отрицателен, сводится к точному сравнению целого числителя и целого знаменателя, построенных из этих показателей.
25 компонент разбиваются на две группы размеров \(12\) и \(13\). Для каждой половины перечисляются все тернарные состояния. Полусостояние хранит три величины:
$$\text{приближённый score},\qquad \text{масса вероятности},\qquad \text{точный вектор простых показателей}.$$
После сортировки состояний правой половины по приближённому score для левого состояния со score \(s_L\) потенциально опасны только те правые состояния, которые лежат рядом с \(-s_L\). Все правые состояния с заметно большим score автоматически дают положительную суммарную величину и могут быть добавлены сразу с помощью префиксных сумм.
Именно поэтому метод работает быстро: точная арифметика используется только в очень узкой полосе около границы решения, а не для каждой пары состояний.
Возьмём \(k=25\). Тогда \(q=\frac{1}{4}\) и
$$w=2\log\frac{3}{1}=2\log 3.$$
Три локальных исхода имеют вид
$$+w\text{ с вероятностью }\left(\frac{3}{4}\right)^2=\frac{9}{16},\qquad 0\text{ с вероятностью }2\cdot\frac{1}{4}\cdot\frac{3}{4}=\frac{6}{16},\qquad -w\text{ с вероятностью }\left(\frac{1}{4}\right)^2=\frac{1}{16}.$$
Для этой игрушечной задачи из одной компоненты оптимальная точность равна
$$\frac{9}{16}+\frac{1}{2}\cdot\frac{6}{16}=\frac{12}{16}=\frac{3}{4}.$$
Полная задача использует ту же формулу, только для суммы всех 25 тернарных вкладов.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала строится фиксированный базис простых чисел, возникающих в числах \(k\) и \(100-k\) для \(25\le k\le 49\). Затем для каждой из 25 компонент заранее вычисляются вещественный вес \(w_k\), три локальные вероятности \((1-q_k)^2\), \(2q_k(1-q_k)\), \(q_k^2\), а также точное представление отношения \(\left(\frac{100-k}{k}\right)^2\) через показатели простых чисел.
После этого программа перечисляет все тернарные состояния левой и правой половин. Каждое сохранённое состояние содержит приближённый score, свою массу вероятности и точный вектор показателей. Правая половина сортируется по приближённому score, а массив префиксных сумм позволяет сразу добавить вероятность всех заведомо выигрышных комбинаций после бинарного поиска.
Только комбинации, чья приближённая суммарная величина попадает в крошечную окрестность нуля, требуют дополнительной обработки. Для них реализация складывает два вектора показателей, восстанавливает точное рациональное сравнение с помощью целых чисел произвольной длины и определяет, больше ли произведение \(1\), равно ли \(1\) или меньше \(1\). Этот точный знак и говорит, нужно ли добавлять полную вероятность, половину вероятности или ничего.
Пусть \(L=3^{12}\), \(R=3^{13}\). Перечисление двух половин стоит \(O(L+R)\). Сортировка состояний правой половины требует \(O(R\log R)\). Для каждого левого состояния на этапе объединения выполняются две бинарные поисковые операции, так что основная стоимость равна \(O(L\log R)\), плюс меньший дополнительный член на точные проверки в окне почти-ничьих. Память составляет \(O(L+R)\) состояний, и к каждому состоянию прикреплён только небольшой фиксированный вектор простых показателей.
المطلوب هو حساب احتمال نجاح قاعدة القرار المثلى لخمسة وعشرين زوجًا مستقلًا من الاحتمالات. لكل \(k=25,26,\dots,49\) نأخذ \(q_k=k/100\)، وبالتالي فإن كل مكوّن يقارن بين \(q_k\) ومتممه \(1-q_k\). وعندما نختزل المكوّن الواحد إلى صافي الأثر الذي يضيفه إلى القرار الكلي، لا يبقى أمامنا إلا ثلاث حالات ممكنة لكل مكوّن، ولذلك فإن العد المباشر ما زال يتطلب \(3^{25}\) حالة مشتركة.
الكمية المطلوبة ليست مجرد \(\Pr(S>0)\). فإذا كان مجموع الدليل مساويًا للصفر تمامًا، تصبح القراءتان الكليتان متكافئتين في الاحتمال، ولذلك يمنح التعادل نصف نقطة فقط. إذن الكمية المستهدفة هي
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
تحوّل الحلول البرمجية المسألة الأصلية إلى مجموع من مساهمات مستقلة في لوغاريتم نسبة الإمكان، ثم تعالج حالات التعادل بدقة كاملة من غير تعداد جميع حالات \(3^{25}\) دفعة واحدة.
لكل \(k\in\{25,\dots,49\}\) نعرّف
$$q_k=\frac{k}{100},\qquad w_k=2\log\frac{1-q_k}{q_k}=2\log\frac{100-k}{k}.$$
ولنسمِّ مساهمة المكوّن رقم \(k\) في مجموع لوغاريتم نسبة الإمكان \(X_k\). عندئذ لا توجد إلا ثلاث قيم ممكنة:
$$X_k\in\{+w_k,\,0,\,-w_k\}.$$
واحتمالات هذه القيم هي
$$\Pr(X_k=+w_k)=(1-q_k)^2,\qquad \Pr(X_k=0)=2q_k(1-q_k),\qquad \Pr(X_k=-w_k)=q_k^2.$$
وهكذا يصبح كل مكوّن بعد هذا الاختزال إمّا دليلًا لصالح التفسير الصحيح، أو مساهمة محايدة، أو دليلًا في الاتجاه المعاكس.
بما أن المكوّنات الخمسة والعشرين مستقلة، فإن مجموع الدليل يساوي
$$S=\sum_{k=25}^{49} X_k.$$
وتختار القاعدة المثلى التفسير الصحيح عندما يكون \(S>0\)، وتختار الخاطئ عندما يكون \(S<0\)، وتقسم الكتلة الاحتمالية بالتساوي عندما يكون \(S=0\). لذلك نحصل على
$$A=\Pr(S>0)+\frac{1}{2}\Pr(S=0).$$
وبما أن فضاء الحالات المباشر حجمه \(3^{25}\)، فالتحدي الحقيقي هو حساب هذه الكمية بدقة من غير اللجوء إلى الفحص الكامل لكل التوافيق.
في حالة كلية محددة، ليمثل \(\sigma_k\in\{-1,0,1\}\) ما إذا كان المكوّن \(k\) يضيف \(-w_k\) أو \(0\) أو \(+w_k\). عندئذ
$$S=\sum_{k=25}^{49} \sigma_k\,2\log\frac{100-k}{k}=\log\left(\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\right).$$
ومن ثم فإن إشارة \(S\) تكافئ تمامًا مقارنة
$$\prod_{k=25}^{49}\left(\frac{100-k}{k}\right)^{2\sigma_k}\mathop{\gtrless}_{=}\,1.$$
وهذه الصياغة أساسية. فالأعداد العشرية مناسبة للترتيب وتحديد العتبات التقريبية، لكن التعادل والحالات القريبة منه يجب أن تُحسم بحساب نسبي دقيق لا يتأثر بأخطاء التقريب.
كل الأعداد المستخدمة تأتي من المجموعة الثابتة \(k\) و\(100-k\) عندما \(25\le k\le 49\)، ولذلك فإن مجموعة الأعداد الأولية الممكنة ثابتة ومحدودة. ولكل \(k\) نكتب
$$\left(\frac{100-k}{k}\right)^2=\prod_{p} p^{e_{k,p}}.$$
إذا اختارت الحالة الكلية الإشارات \(\sigma_k\)، فإن الأس الكلي للعدد الأولي \(p\) يصبح
$$E_p=\sum_{k=25}^{49}\sigma_k e_{k,p}.$$
وعندئذ يمكن كتابة الناتج الدقيق على صورة
$$\prod_{p} p^{E_p}=\frac{\prod_{E_p>0} p^{E_p}}{\prod_{E_p<0} p^{-E_p}}.$$
وبذلك تتحول مسألة تحديد ما إذا كان \(S\) موجبًا أو صفريًا أو سالبًا إلى مقارنة صحيحة بين بسط ومقام صحيحين مبنيين من هذه الأسس.
تُقسَّم المكوّنات الخمسة والعشرون إلى مجموعتين بحجم \(12\) و\(13\). ثم تُعدَّد جميع الحالات الثلاثية في كل نصف. وكل نصف-حالة تخزن درجة تقريبية، وكتلة احتمالية، ومتجهًا دقيقًا لأسس العوامل الأولية.
بعد ترتيب حالات النصف الأيمن حسب الدرجة التقريبية، فإن الحالة اليسرى ذات الدرجة \(s_L\) لا تحتاج إلى فحص دقيق إلا مع الحالات اليمنى القريبة من \(-s_L\)، لأن هذه فقط قد تؤدي إلى تعادل أو شبه تعادل. أما الحالات اليمنى ذات الدرجة الأكبر بوضوح، فإنها تجعل المجموع موجبًا تلقائيًا ويمكن جمع كتلتها بسرعة باستخدام المجاميع السابقة.
وهنا تكمن الفكرة الأساسية في الكفاءة: الحساب الدقيق بالأعداد الكبيرة لا يُستخدم إلا داخل نافذة ضيقة جدًا حول حد القرار، وليس لكل زوج ممكن من الحالات.
خذ \(k=25\). عندئذ \(q=\frac{1}{4}\)، وبالتالي
$$w=2\log\frac{3}{1}=2\log 3.$$
والنتيجة \(+w\) تحدث بالاحتمال
$$\left(\frac{3}{4}\right)^2=\frac{9}{16}.$$
والنتيجة \(0\) تحدث بالاحتمال
$$2\cdot\frac{1}{4}\cdot\frac{3}{4}=\frac{6}{16}.$$
والنتيجة \(-w\) تحدث بالاحتمال
$$\left(\frac{1}{4}\right)^2=\frac{1}{16}.$$
في هذا المثال المصغر ذي المكوّن الواحد، تكون الدقة المثلى مساوية لـ
$$\frac{9}{16}+\frac{1}{2}\cdot\frac{6}{16}=\frac{12}{16}=\frac{3}{4}.$$
أما المسألة الكاملة فتطبق القاعدة نفسها بعد جمع جميع المساهمات الثلاثية الخمس والعشرين.
تتبع تطبيقات C++ وPython وJava المسار نفسه. تبدأ أولًا ببناء الأساس الثابت من الأعداد الأولية التي تظهر داخل الأعداد \(k\) و\(100-k\) عندما \(25\le k\le 49\). ثم تُحضِّر لكل واحد من المكوّنات الخمسة والعشرين الوزن التقريبي \(w_k\)، والاحتمالات المحلية الثلاثة \((1-q_k)^2\) و\(2q_k(1-q_k)\) و\(q_k^2\)، بالإضافة إلى التمثيل الدقيق بأسس العوامل الأولية للنسبة \(\left(\frac{100-k}{k}\right)^2\).
بعد ذلك تُعدَّد جميع الحالات الثلاثية في النصف الأيسر وفي النصف الأيمن. كل حالة مخزنة تتضمن درجة تقريبية وكتلتها الاحتمالية ومتجه الأسس الدقيق. ثم تُرتَّب حالات النصف الأيمن حسب الدرجة، وتُبنى مجاميع سابقة تسمح بإضافة احتمال جميع التركيبات الرابحة بوضوح مباشرة بعد بحث ثنائي واحد.
ولا تحتاج إلى المعالجة الإضافية إلا التركيبات التي تقع درجتها التقريبية داخل جوار صغير جدًا من الصفر. في هذه المنطقة الضيقة تجمع الشيفرة متجهي الأسس، ثم تعيد بناء مقارنة نسبية دقيقة باستخدام أعداد صحيحة ذات دقة غير محدودة، وتحدد هل الناتج أكبر من \(1\) أم يساويه أم أصغر منه. وهذه الإشارة الدقيقة هي التي تحدد ما إذا كانت تلك التركيبة تضيف الاحتمال كاملًا أو نصفه أو لا تضيف شيئًا.
لنكتب \(L=3^{12}\) و\(R=3^{13}\). تعداد حالتي النصفين يكلف \(O(L+R)\). وفرز حالات النصف الأيمن يكلف \(O(R\log R)\). ولكل حالة في النصف الأيسر تُجرى عمليتا بحث ثنائي في مرحلة الدمج، لذا فإن الكلفة الأساسية للدمج هي \(O(L\log R)\)، مع حد إضافي أصغر ناتج عن المقارنات الدقيقة داخل نافذة شبه التعادل. أما الذاكرة فهي \(O(L+R)\) حالة، وكل حالة تحمل فقط متجهًا صغيرًا وثابت الحجم من أسس العوامل الأولية.