Each person is infected independently with probability \(p\). A pooled blood test on any subset is negative if and only if every person in that subset is healthy. For a fixed group size \(s\), let \(T(s,p)\) be the minimum possible expected number of tests needed to determine all infection statuses.
Problem 352 asks for
$$\sum_{i=1}^{50} T\left(10000,\frac{i}{100}\right).$$
A brute-force search over all adaptive testing trees is infeasible. The repository solution succeeds because the optimal strategy can be expressed with two one-dimensional dynamic programming states whose transitions depend only on group size.
Write \(q=1-p\). Then \(q^n\) is the probability that all \(n\) people are healthy, and \(1-q^n\) is the probability that at least one person in a group of size \(n\) is infected.
Define \(A_n\) as the optimal expected number of tests for \(n\) people with no prior information, and \(B_n\) as the optimal expected number of tests for \(n\) people under the condition that at least one of them is infected.
Because the people are exchangeable, only the size \(k\) of the next tested subgroup matters. The exact identities of the chosen people do not matter.
The base values are forced:
$$A_0=B_0=0,\qquad A_1=1,\qquad B_1=0.$$
\(A_1=1\) because one unconstrained person must be tested once. \(B_1=0\) because if a single-person group is already known to contain an infected person, that person's status is already determined.
Assume \(n \ge 2\), and suppose we are in state \(B_n\): the group has size \(n\), and at least one infected person is guaranteed to exist. Testing the whole group again would be pointless, because that pooled test must be positive. So the first informative move is to test a proper subgroup of size \(k\), where \(1 \le k < n\).
Let \(E_n\) be the event that the full group of size \(n\) contains at least one infected person. Then
$$\Pr(E_n)=1-q^n.$$
If the tested subgroup of size \(k\) is negative, then all \(k\) tested people are healthy. Under the condition \(E_n\), the remaining \(n-k\) people must therefore contain at least one infected person. The corresponding conditional probability is
$$p_a=\frac{q^k(1-q^{n-k})}{1-q^n}.$$
In that branch, the problem becomes \(B_{n-k}\).
If the tested subgroup is positive, then that subgroup becomes a new conditional problem \(B_k\), while the remaining \(n-k\) people are still an unconditional problem \(A_{n-k}\). The complementary probability is
$$p_b=1-p_a=\frac{1-q^k}{1-q^n}.$$
Therefore the expected cost of choosing size \(k\) is
$$1+p_aB_{n-k}+p_b(B_k+A_{n-k}),$$
and minimizing over all legal \(k\) gives
$$\boxed{B_n=\min_{1\le k<n}\left(1+p_aB_{n-k}+p_b(B_k+A_{n-k})\right).}$$
For \(A_n\), the code compares two families of strategies.
The first option is to test the whole group immediately. That costs one test. With probability \(q^n\) the result is negative and we are done; with probability \(1-q^n\) the result is positive and we then face the conditional state \(B_n\). So this strategy costs
$$1+(1-q^n)B_n.$$
The second option is to test a proper subgroup of size \(k\) first. Regardless of the outcome, the remaining \(n-k\) people are still an unconditional subproblem, so they contribute \(A_{n-k}\). Only when the tested subgroup is positive do we also pay the extra cost \(B_k\). Thus
$$1+q^kA_{n-k}+(1-q^k)(B_k+A_{n-k})=1+A_{n-k}+(1-q^k)B_k.$$
Taking the better of the whole-pool strategy and all split-first strategies yields
$$\boxed{A_n=\min\left(1+(1-q^n)B_n,\ \min_{1\le k<n}\left(1+A_{n-k}+(1-q^k)B_k\right)\right).}$$
Both recurrences use only smaller group sizes, so the arrays can be filled in increasing order \(n=2,3,\dots,s\). The implementations also precompute
$$q^0,q^1,\dots,q^s$$
so that each transition reads the needed probabilities in constant time instead of recomputing powers repeatedly.
Once the tables are complete, the desired value for a fixed probability is simply
$$T(s,p)=A_s.$$
The Project Euler target is therefore
$$\boxed{\sum_{i=1}^{50} A_{10000}\Bigl(p=\frac{i}{100}\Bigr).}$$
The C++ source also checks two benchmark values before producing the final answer:
$$T(25,0.02)=4.155452,\qquad T(25,0.10)=12.702124.$$
The main implementation is in solutionsCpp/Euler352.cpp. It precomputes qpow[n]=q^n, fills B[n] from the conditional recurrence, then fills A[n] from the unconditional recurrence. The function T(s,p) returns A[s].
The outer solve() function evaluates \(p=0.01,0.02,\dots,0.50\) and sums the 50 independent results. In C++, those independent probability cases are distributed across pthread workers, capped at 8 threads. The Java file solutionsJava/Euler352.java is a direct port of the same DP and parallelizes with ExecutorService.
The Python file solutionsPython/Euler352.py is intentionally different: it is a small bridge that compiles the C++ solver if needed, runs the produced binary, and parses the output. So the mathematical source of truth is the C++ recurrence, with Java matching it directly and Python delegating to it.
For fixed \((s,p)\), the dynamic program loops over \(n=2,\dots,s\) and, for each \(n\), tries every \(k=1,\dots,n-1\). The total number of candidate splits is
$$\sum_{n=2}^{s}(n-1)=\frac{s(s-1)}{2}=O(s^2).$$
The arrays qpow, A, and B each have length \(s+1\), so the memory usage is \(O(s)\). The final Project Euler computation repeats this for 50 independent values of \(p\). Parallelism improves wall-clock time, but the total asymptotic work remains \(50\cdot O(s^2)\).
solutionsCpp/Euler352.cpp, solutionsJava/Euler352.java, solutionsPython/Euler352.pyJede Person ist unabhängig mit Wahrscheinlichkeit \(p\) infiziert. Ein Pooltest auf einer beliebigen Teilmenge ist genau dann negativ, wenn alle Personen in dieser Teilmenge gesund sind. Für eine feste Gruppengröße \(s\) sei \(T(s,p)\) die minimale erwartete Anzahl von Tests, die nötig ist, um den Status aller Personen zu bestimmen.
Gesucht ist
$$\sum_{i=1}^{50} T\left(10000,\frac{i}{100}\right).$$
Ein direkter Suchbaum über alle adaptiven Teststrategien wäre viel zu groß. Die Lösung im Repository reduziert das Problem deshalb auf zwei eindimensionale DP-Zustände, deren Übergänge nur von der Gruppengröße abhängen.
Setze \(q=1-p\). Dann ist \(q^n\) die Wahrscheinlichkeit, dass alle \(n\) Personen gesund sind, und \(1-q^n\) ist die Wahrscheinlichkeit, dass in einer Gruppe der Größe \(n\) mindestens eine infizierte Person vorkommt.
Definiere \(A_n\) als die optimale erwartete Testzahl für \(n\) Personen ohne Vorwissen und \(B_n\) als die optimale erwartete Testzahl für \(n\) Personen unter der Bedingung, dass mindestens eine davon infiziert ist.
Wegen der vollständigen Symmetrie der Personen ist nur die Größe \(k\) der nächsten getesteten Teilgruppe relevant. Welche konkreten Personen ausgewählt werden, spielt keine Rolle.
Die Anfangswerte sind zwingend:
$$A_0=B_0=0,\qquad A_1=1,\qquad B_1=0.$$
\(A_1=1\), weil eine einzelne unklassifizierte Person genau einen Test braucht. \(B_1=0\), weil bei einer Ein-Personen-Gruppe mit garantierter Infektion keine weitere Information mehr durch Tests gewonnen werden muss.
Sei \(n \ge 2\), und wir befinden uns im Zustand \(B_n\): In der Gruppe der Größe \(n\) gibt es sicher mindestens eine infizierte Person. Ein Test der gesamten Gruppe wäre hier nutzlos, denn er müsste positiv ausfallen. Deshalb testet man zuerst nur eine echte Teilgruppe der Größe \(k\) mit \(1 \le k < n\).
Bezeichne mit \(E_n\) das Ereignis, dass die ganze Gruppe der Größe \(n\) mindestens eine infizierte Person enthält. Dann gilt
$$\Pr(E_n)=1-q^n.$$
Ist die getestete Teilgruppe negativ, dann sind alle \(k\) getesteten Personen gesund. Unter der Bedingung \(E_n\) muss also die Restgruppe der Größe \(n-k\) mindestens eine infizierte Person enthalten. Die bedingte Wahrscheinlichkeit dafür ist
$$p_a=\frac{q^k(1-q^{n-k})}{1-q^n}.$$
In diesem Fall reduziert sich das Problem auf \(B_{n-k}\).
Ist die getestete Teilgruppe positiv, so wird sie selbst zu einem neuen konditionalen Problem \(B_k\), während die übrigen \(n-k\) Personen weiterhin ein unkonditioniertes Problem \(A_{n-k}\) bilden. Die komplementäre Wahrscheinlichkeit lautet
$$p_b=1-p_a=\frac{1-q^k}{1-q^n}.$$
Damit hat die Wahl von \(k\) die erwarteten Kosten
$$1+p_aB_{n-k}+p_b(B_k+A_{n-k}),$$
und nach Minimierung folgt
$$\boxed{B_n=\min_{1\le k<n}\left(1+p_aB_{n-k}+p_b(B_k+A_{n-k})\right).}$$
Für \(A_n\) vergleicht der Code zwei Strategiefamilien.
Erste Möglichkeit: Man testet sofort die ganze Gruppe. Das kostet einen Test. Mit Wahrscheinlichkeit \(q^n\) ist das Ergebnis negativ und man ist fertig; mit Wahrscheinlichkeit \(1-q^n\) ist es positiv und man landet im konditionalen Zustand \(B_n\). Die Kosten dieser Variante sind also
$$1+(1-q^n)B_n.$$
Zweite Möglichkeit: Man testet zuerst nur eine Teilgruppe der Größe \(k\). Unabhängig vom Ergebnis bleibt die Restgruppe der Größe \(n-k\) ein unkonditioniertes Teilproblem und trägt daher \(A_{n-k}\) bei. Nur wenn die getestete Teilgruppe positiv ist, kommt zusätzlich \(B_k\) hinzu. Also gilt
$$1+q^kA_{n-k}+(1-q^k)(B_k+A_{n-k})=1+A_{n-k}+(1-q^k)B_k.$$
Das Minimum aus Gesamtgruppentest und allen Aufspaltungen liefert
$$\boxed{A_n=\min\left(1+(1-q^n)B_n,\ \min_{1\le k<n}\left(1+A_{n-k}+(1-q^k)B_k\right)\right).}$$
Beide Rekurrenzen greifen nur auf kleinere Gruppengrößen zurück, also kann man die Felder in aufsteigender Reihenfolge \(n=2,3,\dots,s\) füllen. Außerdem berechnen die Implementierungen die Tabelle
$$q^0,q^1,\dots,q^s$$
vorab, damit in den quadratischen Schleifen keine Potenzen ständig neu berechnet werden müssen.
Nach Abschluss der Tabellen gilt für eine feste Infektionswahrscheinlichkeit
$$T(s,p)=A_s.$$
Damit wird das Euler-Ziel zu
$$\boxed{\sum_{i=1}^{50} A_{10000}\Bigl(p=\frac{i}{100}\Bigr).}$$
Die C++-Datei prüft vor der Endausgabe außerdem zwei Kontrollwerte:
$$T(25,0.02)=4.155452,\qquad T(25,0.10)=12.702124.$$
Die eigentliche Implementierung liegt in solutionsCpp/Euler352.cpp. Dort wird zuerst qpow[n]=q^n aufgebaut, anschließend werden B[n] nach der konditionalen Rekurrenz und danach A[n] nach der unkonditionalen Rekurrenz berechnet. Die Funktion T(s,p) gibt dann A[s] zurück.
Die äußere Funktion solve() berechnet die 50 Fälle \(p=0.01,0.02,\dots,0.50\) unabhängig voneinander und addiert sie. In C++ werden diese unabhängigen Wahrscheinlichkeiten mit pthread-Threads parallelisiert, höchstens mit 8 Threads. Die Java-Datei solutionsJava/Euler352.java ist eine direkte Portierung derselben DP-Idee und nutzt ExecutorService.
Die Python-Datei solutionsPython/Euler352.py implementiert die Mathematik nicht erneut. Sie kompiliert bei Bedarf den C++-Solver, führt das Binärprogramm aus und parst dessen Ausgabe. Inhaltlich ist also die C++-Rekurrenz die eigentliche Referenz, Java folgt ihr direkt, und Python delegiert an sie.
Für festes \((s,p)\) läuft die DP über \(n=2,\dots,s\) und probiert für jedes \(n\) alle \(k=1,\dots,n-1\). Die Gesamtzahl der betrachteten Aufteilungen ist
$$\sum_{n=2}^{s}(n-1)=\frac{s(s-1)}{2}=O(s^2).$$
Die Arrays qpow, A und B haben jeweils Länge \(s+1\), also beträgt der Speicherbedarf \(O(s)\). Für das Euler-Problem wird diese Arbeit für 50 voneinander unabhängige Werte von \(p\) wiederholt. Parallelisierung verkürzt die Laufzeit an der Wanduhr, ändert aber nicht die asymptotische Gesamtarbeit.
solutionsCpp/Euler352.cpp, solutionsJava/Euler352.java, solutionsPython/Euler352.pyHer kişi bağımsız olarak \(p\) olasılığıyla enfektedir. Herhangi bir alt küme üzerinde yapılan havuz testi, ancak o alt kümedeki herkes sağlıklıysa negatif çıkar. Sabit bir \(s\) grup büyüklüğü için \(T(s,p)\), tüm kişilerin durumunu belirlemek için gereken en küçük beklenen test sayısı olsun.
Problem 352 şu toplamı ister:
$$\sum_{i=1}^{50} T\left(10000,\frac{i}{100}\right).$$
Tüm uyarlanabilir test ağaçlarını doğrudan taramak pratik değildir. Depodaki çözüm bunun yerine stratejiyi, yalnızca grup büyüklüğüne bağlı iki tek boyutlu dinamik programlama durumuna indirger.
\(q=1-p\) yazalım. Böylece \(q^n\), \(n\) kişinin tamamının sağlıklı olma olasılığıdır; \(1-q^n\) ise büyüklüğü \(n\) olan bir grupta en az bir enfekte bulunma olasılığıdır.
\(A_n\), önbilgi olmadan \(n\) kişi için en iyi beklenen test sayısı; \(B_n\) ise bu \(n\) kişi arasında en az bir enfekte olduğu bilinirken en iyi beklenen test sayısı olsun.
Kişiler istatistiksel olarak simetrik olduğu için bir sonraki testte hangi kişilerin seçildiği değil, yalnızca seçilen alt grubun büyüklüğü \(k\) önemlidir.
Başlangıç değerleri zorunludur:
$$A_0=B_0=0,\qquad A_1=1,\qquad B_1=0.$$
\(A_1=1\) çünkü tek bir kişi hakkında önbilgi yoksa bir test yapmak gerekir. \(B_1=0\) çünkü tek kişilik bir grupta zaten en az bir enfekte olduğu biliniyorsa, o kişinin durumu artık nettir.
\(n \ge 2\) olsun ve \(B_n\) durumunda olalım: büyüklüğü \(n\) olan grupta en az bir enfekte olduğu kesindir. Bütün grubu yeniden test etmek bilgi kazandırmaz, çünkü sonuç zaten pozitif olmak zorundadır. Bu yüzden ilk anlamlı hamle, \(1 \le k < n\) olacak şekilde büyüklüğü \(k\) olan gerçek bir alt grubu test etmektir.
Tüm \(n\) kişilik grupta en az bir enfekte bulunması olayına \(E_n\) diyelim. O halde
$$\Pr(E_n)=1-q^n.$$
Büyüklüğü \(k\) olan test edilen alt grup negatif çıkarsa, o \(k\) kişinin tamamı sağlıklıdır. \(E_n\) koşulu altında bu, kalan \(n-k\) kişinin en az bir enfekte içermesi gerektiği anlamına gelir. Bu dalın koşullu olasılığı
$$p_a=\frac{q^k(1-q^{n-k})}{1-q^n}.$$
Bu durumda problem \(B_{n-k}\) alt problemine iner.
Test edilen alt grup pozitif çıkarsa, bu alt grup yeni bir \(B_k\) problemi haline gelir; geride kalan \(n-k\) kişi ise koşulsuz \(A_{n-k}\) problemi olarak kalır. Tamamlayıcı olasılık
$$p_b=1-p_a=\frac{1-q^k}{1-q^n}.$$
Dolayısıyla \(k\) seçiminin beklenen maliyeti
$$1+p_aB_{n-k}+p_b(B_k+A_{n-k}),$$
ve tüm uygun \(k\) değerleri arasında en iyisi
$$\boxed{B_n=\min_{1\le k<n}\left(1+p_aB_{n-k}+p_b(B_k+A_{n-k})\right).}$$
\(A_n\) için kod iki strateji ailesini karşılaştırır.
Birinci seçenek, tüm grubu hemen test etmektir. Bu bir test eder. Sonuç \(q^n\) olasılıkla negatiftir ve süreç biter; \(1-q^n\) olasılıkla pozitiftir ve bu kez koşullu durum \(B_n\) ortaya çıkar. Bu stratejinin maliyeti
$$1+(1-q^n)B_n.$$
İkinci seçenek, önce büyüklüğü \(k\) olan uygun bir alt grubu test etmektir. Sonuç ne olursa olsun geri kalan \(n-k\) kişi hâlâ koşulsuz bir alt problemdir ve \(A_{n-k}\) katkısı yapar. Yalnızca test edilen alt grup pozitif çıkarsa ek olarak \(B_k\) maliyeti gelir. Bu yüzden
$$1+q^kA_{n-k}+(1-q^k)(B_k+A_{n-k})=1+A_{n-k}+(1-q^k)B_k.$$
Tüm grup testi ile tüm bölme-stratejileri arasında minimum alınırsa
$$\boxed{A_n=\min\left(1+(1-q^n)B_n,\ \min_{1\le k<n}\left(1+A_{n-k}+(1-q^k)B_k\right)\right).}$$
Her iki bağıntı da yalnızca daha küçük grup boyutlarını kullandığı için diziler \(n=2,3,\dots,s\) artan sırasında doldurulabilir. Uygulamalar ayrıca
$$q^0,q^1,\dots,q^s$$
değerlerini önceden hesaplar; böylece karesel döngüler içinde sürekli üs alma yapılmaz.
Tablo tamamlandıktan sonra sabit bir olasılık için istenen değer
$$T(s,p)=A_s$$
olur. Böylece Euler toplamı
$$\boxed{\sum_{i=1}^{50} A_{10000}\Bigl(p=\frac{i}{100}\Bigr).}$$
C++ kaynağı ayrıca son cevaptan önce iki kontrol değerini doğrular:
$$T(25,0.02)=4.155452,\qquad T(25,0.10)=12.702124.$$
Ana uygulama solutionsCpp/Euler352.cpp içindedir. Önce qpow[n]=q^n tablosu kurulur, sonra koşullu bağıntıdan B[n], ardından koşulsuz bağıntıdan A[n] doldurulur. T(s,p) fonksiyonu da sonunda A[s] döndürür.
Dıştaki solve() fonksiyonu \(p=0.01,0.02,\dots,0.50\) için 50 bağımsız hesabı toplar. C++ sürümü bu bağımsız olasılıkları pthread iş parçacıklarına dağıtır ve iş parçacığı sayısını en fazla 8 ile sınırlar. solutionsJava/Euler352.java dosyası aynı DP'nin doğrudan Java uyarlamasıdır ve ExecutorService kullanır.
solutionsPython/Euler352.py ise matematiği yeniden yazmaz. Gerekirse C++ kaynağını derler, ortaya çıkan ikiliyi çalıştırır ve çıktıyı çözümler. Yani matematiksel asıl kaynak C++ çözümüdür; Java onu doğrudan izler, Python ise ona delegasyon yapar.
Sabit \((s,p)\) için DP, \(n=2,\dots,s\) üzerinde döner ve her \(n\) için \(k=1,\dots,n-1\) seçeneklerinin hepsini dener. Toplam aday bölme sayısı
$$\sum_{n=2}^{s}(n-1)=\frac{s(s-1)}{2}=O(s^2)$$
olur. qpow, A ve B dizilerinin her biri uzunluk olarak \(s+1\) olduğundan bellek kullanımı \(O(s)\)'dir. Nihai Euler hesabı bunu \(p\)'nin 50 bağımsız değeri için tekrarlar. Paralellik duvar saati süresini düşürür ama toplam asimptotik işi değiştirmez.
solutionsCpp/Euler352.cpp, solutionsJava/Euler352.java, solutionsPython/Euler352.pyCada persona está infectada de manera independiente con probabilidad \(p\). Un análisis agrupado sobre cualquier subconjunto da negativo si y solo si todas las personas de ese subconjunto están sanas. Para un tamaño fijo \(s\), definimos \(T(s,p)\) como el número esperado mínimo de pruebas necesario para determinar el estado de infección de todos.
El problema 352 pide calcular
$$\sum_{i=1}^{50} T\left(10000,\frac{i}{100}\right).$$
Explorar directamente todos los árboles adaptativos de decisiones es imposible. La solución del repositorio comprime la estrategia óptima en dos estados de programación dinámica de una sola dimensión, determinados únicamente por el tamaño del grupo.
Escribimos \(q=1-p\). Entonces \(q^n\) es la probabilidad de que las \(n\) personas estén sanas, y \(1-q^n\) es la probabilidad de que en un grupo de tamaño \(n\) haya al menos un infectado.
Definimos \(A_n\) como el número esperado óptimo de pruebas para \(n\) personas sin información previa, y \(B_n\) como el número esperado óptimo de pruebas para \(n\) personas sabiendo que al menos una está infectada.
Como todas las personas son intercambiables desde el punto de vista probabilístico, solo importa el tamaño \(k\) del siguiente subgrupo que se prueba. La identidad concreta de las personas elegidas no cambia el valor esperado.
Las condiciones base son
$$A_0=B_0=0,\qquad A_1=1,\qquad B_1=0.$$
\(A_1=1\) porque una persona aislada, sin condición previa, requiere exactamente una prueba. \(B_1=0\) porque si ya sabemos que en un grupo de una persona hay al menos un infectado, entonces esa persona ya queda identificada.
Supongamos \(n \ge 2\) y que estamos en el estado \(B_n\): en el grupo de tamaño \(n\) hay al menos un infectado con certeza. Probar de nuevo al grupo completo no aporta información, porque el resultado sería forzosamente positivo. Por eso la primera acción útil es probar un subgrupo propio de tamaño \(k\), con \(1 \le k < n\).
Sea \(E_n\) el evento “el grupo completo de tamaño \(n\) contiene al menos un infectado”. Entonces
$$\Pr(E_n)=1-q^n.$$
Si el subgrupo probado sale negativo, las \(k\) personas analizadas están sanas. Bajo la condición \(E_n\), eso obliga a que el resto de tamaño \(n-k\) contenga al menos un infectado. La probabilidad condicional de esa rama es
$$p_a=\frac{q^k(1-q^{n-k})}{1-q^n}.$$
En esa situación, el problema restante es exactamente \(B_{n-k}\).
Si el subgrupo probado sale positivo, ese subgrupo pasa a ser un nuevo problema condicionado \(B_k\), mientras que las \(n-k\) personas restantes siguen formando un problema no condicionado \(A_{n-k}\). La probabilidad complementaria es
$$p_b=1-p_a=\frac{1-q^k}{1-q^n}.$$
Así, el coste esperado de elegir el tamaño \(k\) es
$$1+p_aB_{n-k}+p_b(B_k+A_{n-k}),$$
y al minimizar sobre todos los \(k\) posibles obtenemos
$$\boxed{B_n=\min_{1\le k<n}\left(1+p_aB_{n-k}+p_b(B_k+A_{n-k})\right).}$$
Para \(A_n\), el código compara dos familias de estrategias.
La primera es probar inmediatamente al grupo completo. Eso cuesta una prueba. Con probabilidad \(q^n\) el resultado es negativo y terminamos; con probabilidad \(1-q^n\) el resultado es positivo y entonces entramos en el estado condicionado \(B_n\). El coste esperado de esta idea es
$$1+(1-q^n)B_n.$$
La segunda familia consiste en probar primero un subgrupo propio de tamaño \(k\). Independientemente del resultado, las \(n-k\) personas restantes siguen siendo un subproblema no condicionado, así que aportan \(A_{n-k}\). Solo si el subgrupo probado sale positivo hay que pagar además \(B_k\). Por tanto,
$$1+q^kA_{n-k}+(1-q^k)(B_k+A_{n-k})=1+A_{n-k}+(1-q^k)B_k.$$
Tomando el mínimo entre la prueba del grupo completo y todas las divisiones posibles llegamos a
$$\boxed{A_n=\min\left(1+(1-q^n)B_n,\ \min_{1\le k<n}\left(1+A_{n-k}+(1-q^k)B_k\right)\right).}$$
Ambas recurrencias dependen solo de tamaños menores, así que los arreglos pueden rellenarse en orden creciente \(n=2,3,\dots,s\). Además, las implementaciones precalculan
$$q^0,q^1,\dots,q^s$$
para no repetir exponenciaciones dentro de los bucles cuadráticos.
Una vez completas las tablas, el valor deseado para una probabilidad fija es
$$T(s,p)=A_s.$$
Por lo tanto, el objetivo de Project Euler es
$$\boxed{\sum_{i=1}^{50} A_{10000}\Bigl(p=\frac{i}{100}\Bigr).}$$
La implementación en C++ también verifica dos valores de control antes de emitir la respuesta final:
$$T(25,0.02)=4.155452,\qquad T(25,0.10)=12.702124.$$
La implementación principal está en solutionsCpp/Euler352.cpp. Primero construye qpow[n]=q^n, luego rellena B[n] con la recurrencia condicionada y después rellena A[n] con la recurrencia no condicionada. La función T(s,p) devuelve finalmente A[s].
La función externa solve() evalúa \(p=0.01,0.02,\dots,0.50\) y suma los 50 resultados independientes. En C++, esos casos independientes se reparten entre hilos pthread, con un máximo de 8. El archivo solutionsJava/Euler352.java es una traducción directa del mismo DP y usa ExecutorService para paralelizar.
El archivo solutionsPython/Euler352.py es distinto por diseño: no reimplementa la matemática. Si hace falta, compila el solucionador en C++, ejecuta el binario generado y analiza la salida. Por eso la fuente matemática principal es la versión en C++; Java la reproduce y Python delega en ella.
Para un par fijo \((s,p)\), el DP recorre \(n=2,\dots,s\) y, para cada \(n\), prueba todos los \(k=1,\dots,n-1\). El número total de divisiones candidatas es
$$\sum_{n=2}^{s}(n-1)=\frac{s(s-1)}{2}=O(s^2).$$
Los arreglos qpow, A y B tienen tamaño \(s+1\), así que la memoria es \(O(s)\). El cálculo final de Euler repite este trabajo para 50 valores independientes de \(p\). La paralelización reduce el tiempo de pared, pero no cambia el orden asintótico del trabajo total.
solutionsCpp/Euler352.cpp, solutionsJava/Euler352.java, solutionsPython/Euler352.py每个人都以独立概率 \(p\) 被感染。对任意子集做一次 pooled test 时，结果为阴性当且仅当该子集中的所有人都健康。对于固定的组大小 \(s\)，记 \(T(s,p)\) 为完全确定这 \(s\) 个人感染状态所需的最小期望检测次数。
第 352 题要求计算
$$\sum_{i=1}^{50} T\left(10000,\frac{i}{100}\right).$$
如果直接枚举所有自适应检测树，状态空间会大得无法处理。仓库中的解法之所以可行，是因为最优策略可以压缩成两个只按组大小变化的一维动态规划状态。
设 \(q=1-p\)。那么 \(q^n\) 表示 \(n\) 个人全部健康的概率，而 \(1-q^n\) 表示大小为 \(n\) 的组中至少有一名感染者的概率。
定义 \(A_n\) 为“对 \(n\) 个人没有任何先验条件时的最优期望检测次数”，定义 \(B_n\) 为“已知这 \(n\) 个人中至少有一人感染时的最优期望检测次数”。
由于每个人在概率模型下完全对称，下一次到底选哪些人进入子组并不重要，真正影响转移的只有子组大小 \(k\)。这也是代码只枚举 \(k\) 而不枚举具体成员的原因。
边界值必须满足
$$A_0=B_0=0,\qquad A_1=1,\qquad B_1=0.$$
\(A_1=1\) 的原因很直接：对一个没有任何先验信息的人，至少要做一次检测。\(B_1=0\) 也同样直接：如果单人组已经知道“至少有一人感染”，那这个人必然感染，不需要额外测试。
现在设 \(n \ge 2\)，并且我们处在状态 \(B_n\) 中，也就是已经知道这 \(n\) 个人里至少有一名感染者。此时如果再去检测整个 \(n\) 人组，这次 pooled test 一定是阳性，不会带来任何新信息。因此，第一个有意义的动作只能是先测一个真子组，其大小记为 \(k\)，其中 \(1 \le k < n\)。
记事件 \(E_n\) 为“这 \(n\) 个人里至少有一人感染”，则
$$\Pr(E_n)=1-q^n.$$
如果先测的 \(k\) 人子组结果为阴性，那么这 \(k\) 个人全部健康。在条件 \(E_n\) 下，这就强制剩余的 \(n-k\) 个人中至少有一名感染者。这个分支的条件概率为
$$p_a=\frac{q^k(1-q^{n-k})}{1-q^n}.$$
进入这个分支后，后续问题恰好变成 \(B_{n-k}\)。
如果先测的子组结果为阳性，那么被测的 \(k\) 人子组本身变成一个新的条件问题 \(B_k\)，而剩下的 \(n-k\) 人并没有获得任何额外条件，只能继续按无条件问题 \(A_{n-k}\) 处理。对应的补概率为
$$p_b=1-p_a=\frac{1-q^k}{1-q^n}.$$
因此，选择大小为 \(k\) 的第一组时，期望代价就是
$$1+p_aB_{n-k}+p_b(B_k+A_{n-k}),$$
对所有合法的 \(k\) 取最小值得到
$$\boxed{B_n=\min_{1\le k<n}\left(1+p_aB_{n-k}+p_b(B_k+A_{n-k})\right).}$$
对于 \(A_n\)，代码比较两大类策略。
第一类策略是立刻检测整个 \(n\) 人组。这样先花 1 次检测。若结果为阴性，概率为 \(q^n\)，则全部人都健康，流程结束；若结果为阳性，概率为 \(1-q^n\)，则后续正好进入条件状态 \(B_n\)。因此这种做法的期望代价为
$$1+(1-q^n)B_n.$$
第二类策略是先检测一个大小为 \(k\) 的真子组。无论这一测是阴性还是阳性，剩余的 \(n-k\) 人都仍然是一个没有附加条件的问题，所以都会贡献 \(A_{n-k}\)。只有当被测子组为阳性时，才需要额外支付 \(B_k\) 的代价。于是
$$1+q^kA_{n-k}+(1-q^k)(B_k+A_{n-k})=1+A_{n-k}+(1-q^k)B_k.$$
将“整组先测”和“分组先测”的所有可能选择一起取最小值，得到
$$\boxed{A_n=\min\left(1+(1-q^n)B_n,\ \min_{1\le k<n}\left(1+A_{n-k}+(1-q^k)B_k\right)\right).}$$
这两个递推式都只依赖更小的组大小，因此可以按 \(n=2,3,\dots,s\) 的顺序顺次填表。实现中还会预先计算
$$q^0,q^1,\dots,q^s$$
这样在二重循环内部就不需要反复做幂运算，转移只需常数时间读取概率。
表格完成后，固定某个感染概率时就有
$$T(s,p)=A_s.$$
于是 Project Euler 要求的就是
$$\boxed{\sum_{i=1}^{50} A_{10000}\Bigl(p=\frac{i}{100}\Bigr).}$$
C++ 源码在输出最终答案之前，还会验证两个检查点：
$$T(25,0.02)=4.155452,\qquad T(25,0.10)=12.702124.$$
核心实现位于 solutionsCpp/Euler352.cpp。程序先建立 qpow[n]=q^n 表，然后按上面的条件递推计算 B[n]，再按无条件递推计算 A[n]。函数 T(s,p) 最终返回 A[s]。
外层的 solve() 会分别计算 \(p=0.01,0.02,\dots,0.50\) 共 50 个彼此独立的情况，并把结果相加。C++ 版本用 pthread 工作者并行这些概率任务，线程数上限为 8。solutionsJava/Euler352.java 则是同一套 DP 的直接 Java 移植版，使用 ExecutorService 做并行。
solutionsPython/Euler352.py 的角色不同：它并没有重新实现数学过程，而是按需编译 C++ 源文件，执行生成的二进制程序，再解析输出。所以在实现层面上，真正的数学基准是 C++ 版本，Java 与之保持一致，而 Python 只是桥接器。
对固定的 \((s,p)\)，动态规划会枚举 \(n=2,\dots,s\)，并且对每个 \(n\) 尝试所有 \(k=1,\dots,n-1\)。因此候选划分的总数为
$$\sum_{n=2}^{s}(n-1)=\frac{s(s-1)}{2}=O(s^2).$$
qpow、A、B 三个数组的长度都为 \(s+1\)，所以空间复杂度是 \(O(s)\)。最终 Euler 计算需要对 50 个互相独立的 \(p\) 值重复这项工作。并行化只能降低实际运行时间，不会改变总工作量的渐近阶。
solutionsCpp/Euler352.cpp, solutionsJava/Euler352.java, solutionsPython/Euler352.pyКаждый человек заражён независимо с вероятностью \(p\). Групповой анализ для любого подмножества даёт отрицательный результат тогда и только тогда, когда все люди в этом подмножестве здоровы. Для фиксированного размера группы \(s\) обозначим через \(T(s,p)\) минимальное математическое ожидание числа тестов, достаточное для определения статуса всех людей.
В задаче 352 требуется вычислить
$$\sum_{i=1}^{50} T\left(10000,\frac{i}{100}\right).$$
Полный перебор всех адаптивных деревьев тестирования нереален. Решение в репозитории работает потому, что оптимальную стратегию можно свернуть в два одномерных состояния динамического программирования, зависящих только от размера группы.
Положим \(q=1-p\). Тогда \(q^n\) есть вероятность того, что все \(n\) человек здоровы, а \(1-q^n\) есть вероятность того, что в группе размера \(n\) есть хотя бы один заражённый.
Обозначим через \(A_n\) оптимальное ожидаемое число тестов для \(n\) человек без какой-либо предварительной информации. Обозначим через \(B_n\) оптимальное ожидаемое число тестов для \(n\) человек при условии, что среди них гарантированно есть хотя бы один заражённый.
Поскольку все люди статистически симметричны, важен только размер \(k\) следующей проверяемой подгруппы. Конкретный состав этой подгруппы на значение ожидания не влияет.
Базовые значения таковы:
$$A_0=B_0=0,\qquad A_1=1,\qquad B_1=0.$$
\(A_1=1\), потому что для одного человека без условий нужна ровно одна проверка. \(B_1=0\), потому что если в группе из одного человека уже известно наличие хотя бы одного заражённого, то статус этого человека уже установлен.
Пусть \(n \ge 2\), и мы находимся в состоянии \(B_n\): в группе из \(n\) человек точно есть хотя бы один заражённый. Проверять снова всю группу бессмысленно, потому что pooled test обязательно окажется положительным. Поэтому первый полезный ход состоит в проверке собственной подгруппы размера \(k\), где \(1 \le k < n\).
Обозначим через \(E_n\) событие “в полной группе из \(n\) человек есть хотя бы один заражённый”. Тогда
$$\Pr(E_n)=1-q^n.$$
Если проверяемая подгруппа размера \(k\) даёт отрицательный результат, то все эти \(k\) человек здоровы. При условии \(E_n\) это означает, что среди оставшихся \(n-k\) человек обязательно есть заражённый. Условная вероятность этой ветви равна
$$p_a=\frac{q^k(1-q^{n-k})}{1-q^n}.$$
После этого остаётся задача \(B_{n-k}\).
Если же первая подгруппа положительна, то сама протестированная подгруппа становится новой условной задачей \(B_k\), а оставшиеся \(n-k\) человек по-прежнему образуют безусловную задачу \(A_{n-k}\). Дополнительная вероятность равна
$$p_b=1-p_a=\frac{1-q^k}{1-q^n}.$$
Следовательно, ожидаемая стоимость выбора размера \(k\) равна
$$1+p_aB_{n-k}+p_b(B_k+A_{n-k}),$$
а после минимизации по всем допустимым \(k\) получаем
$$\boxed{B_n=\min_{1\le k<n}\left(1+p_aB_{n-k}+p_b(B_k+A_{n-k})\right).}$$
Для \(A_n\) программа сравнивает два класса стратегий.
Первый класс: сразу проверить всю группу. Это стоит один тест. С вероятностью \(q^n\) результат отрицателен, и работа заканчивается; с вероятностью \(1-q^n\) результат положителен, после чего остаётся условная задача \(B_n\). Значит, ожидаемая стоимость такого хода равна
$$1+(1-q^n)B_n.$$
Второй класс: сначала проверить собственную подгруппу размера \(k\). Независимо от результата оставшиеся \(n-k\) человек по-прежнему составляют безусловную задачу, поэтому всегда дают вклад \(A_{n-k}\). Только в случае положительного результата первой подгруппы появляется дополнительная стоимость \(B_k\). Поэтому
$$1+q^kA_{n-k}+(1-q^k)(B_k+A_{n-k})=1+A_{n-k}+(1-q^k)B_k.$$
Минимум между “тестом всей группы” и всеми вариантами “сначала подгруппа” даёт
$$\boxed{A_n=\min\left(1+(1-q^n)B_n,\ \min_{1\le k<n}\left(1+A_{n-k}+(1-q^k)B_k\right)\right).}$$
Обе рекуррентные формулы используют только меньшие размеры групп, поэтому массивы удобно заполнять в порядке \(n=2,3,\dots,s\). В реализации также заранее вычисляется таблица
$$q^0,q^1,\dots,q^s,$$
чтобы внутри квадратичных циклов не пересчитывать степени заново.
После заполнения таблиц для фиксированной вероятности имеем
$$T(s,p)=A_s.$$
Следовательно, искомая сумма Project Euler равна
$$\boxed{\sum_{i=1}^{50} A_{10000}\Bigl(p=\frac{i}{100}\Bigr).}$$
Файл на C++ дополнительно проверяет два контрольных значения:
$$T(25,0.02)=4.155452,\qquad T(25,0.10)=12.702124.$$
Основная реализация находится в solutionsCpp/Euler352.cpp. Сначала программа строит массив qpow[n]=q^n, затем по условной рекурсии вычисляет B[n], а после этого по безусловной рекурсии вычисляет A[n]. Функция T(s,p) возвращает значение A[s].
Внешняя функция solve() считает 50 независимых случаев \(p=0.01,0.02,\dots,0.50\) и суммирует их. В C++ эти независимые задачи распределяются по pthread-потокам, причём число потоков ограничивается 8. Файл solutionsJava/Euler352.java является прямым Java-переносом той же динамики и использует ExecutorService.
Файл solutionsPython/Euler352.py устроен иначе: он не повторяет математический алгоритм, а при необходимости компилирует C++-решение, запускает полученный бинарный файл и разбирает его вывод. Поэтому математическим первоисточником здесь служит именно версия на C++; Java следует ей напрямую, а Python лишь оборачивает её.
Для фиксированной пары \((s,p)\) динамика перебирает \(n=2,\dots,s\), а для каждого \(n\) рассматривает все \(k=1,\dots,n-1\). Общее число кандидатных разбиений равно
$$\sum_{n=2}^{s}(n-1)=\frac{s(s-1)}{2}=O(s^2).$$
Массивы qpow, A и B имеют длину \(s+1\), так что память равна \(O(s)\). Финальное вычисление Project Euler повторяет этот расчёт для 50 независимых значений \(p\). Параллельное выполнение уменьшает реальное время работы, но не меняет асимптотику общего объёма вычислений.
solutionsCpp/Euler352.cpp, solutionsJava/Euler352.java, solutionsPython/Euler352.pyكل شخص مصاب باحتمال مستقل مقداره \(p\). ويكون اختبار التجميع لأي مجموعة فرعية سالبًا إذا وفقط إذا كان جميع أفراد تلك المجموعة أصحاء. إذا رمزنا بـ \(T(s,p)\) إلى أقل عدد متوقع من الاختبارات اللازمة لتحديد حالة جميع الأشخاص في مجموعة حجمها \(s\)، فإن المطلوب في المسألة هو جمع هذه القيمة لعدة احتمالات مختلفة.
المسألة 352 تطلب حساب
$$\sum_{i=1}^{50} T\left(10000,\frac{i}{100}\right).$$
البحث المباشر في كل أشجار القرار التكيفية غير عملي تمامًا. ولذلك يعتمد الحل الموجود في المستودع على ضغط الاستراتيجية المثلى في حالتين فقط من البرمجة الديناميكية، وكل انتقال بينهما يعتمد على حجم المجموعة لا على هوية الأشخاص أنفسهم.
لنكتب \(q=1-p\). عندها يكون \(q^n\) هو احتمال أن يكون جميع أفراد مجموعة من \(n\) أشخاص أصحاء، ويكون \(1-q^n\) هو احتمال وجود مصاب واحد على الأقل داخل تلك المجموعة.
نعرّف \(A_n\) بأنه أقل عدد متوقع من الاختبارات لمجموعة حجمها \(n\) من دون أي معلومة مسبقة، ونعرّف \(B_n\) بأنه أقل عدد متوقع من الاختبارات لمجموعة حجمها \(n\) عندما نعلم مسبقًا أن فيها مصابًا واحدًا على الأقل.
وبسبب تماثل جميع الأشخاص إحصائيًا، فإن المهم في الخطوة التالية ليس من نختار تحديدًا، بل فقط حجم المجموعة الجزئية \(k\) التي سنختبرها أولًا.
القيم الابتدائية مفروضة مباشرة:
$$A_0=B_0=0,\qquad A_1=1,\qquad B_1=0.$$
لدينا \(A_1=1\) لأن الشخص الواحد بلا أي شرط سابق يحتاج إلى اختبار واحد. ولدينا \(B_1=0\) لأنه إذا كانت المجموعة تحوي شخصًا واحدًا فقط ونعلم أصلًا أن فيها مصابًا واحدًا على الأقل، فحالة ذلك الشخص معروفة بالفعل.
افترض أن \(n \ge 2\)، وأننا في الحالة \(B_n\)، أي إننا نعرف يقينًا أن مجموعة حجمها \(n\) تحتوي على مصاب واحد على الأقل. في هذه الحالة لا يفيد اختبار المجموعة كلها مرة أخرى، لأن نتيجة اختبار التجميع ستكون موجبة بالضرورة. لذلك تكون أول خطوة مفيدة هي اختبار مجموعة جزئية حقيقية حجمها \(k\)، حيث \(1 \le k < n\).
لنرمز بالحدث \(E_n\) إلى أن المجموعة الكاملة ذات الحجم \(n\) تحتوي على مصاب واحد على الأقل. إذن
$$\Pr(E_n)=1-q^n.$$
إذا خرجت المجموعة الجزئية المختبرة سالبة، فهذا يعني أن جميع الأشخاص \(k\) المختبرين أصحاء. وتحت الشرط \(E_n\)، يفرض ذلك أن المجموعة المتبقية ذات الحجم \(n-k\) تحتوي على مصاب واحد على الأقل. واحتمال هذا الفرع الشرطي يساوي
$$p_a=\frac{q^k(1-q^{n-k})}{1-q^n}.$$
وفي هذا الفرع تصبح المسألة المتبقية هي \(B_{n-k}\).
أما إذا خرجت المجموعة الجزئية موجبة، فإن هذه المجموعة نفسها تتحول إلى مسألة شرطية جديدة \(B_k\)، بينما تبقى المجموعة المتبقية ذات الحجم \(n-k\) مسألة غير مشروطة من النوع \(A_{n-k}\). ويكون الاحتمال المتمم
$$p_b=1-p_a=\frac{1-q^k}{1-q^n}.$$
وبالتالي فإن الكلفة المتوقعة لاختيار حجم \(k\) هي
$$1+p_aB_{n-k}+p_b(B_k+A_{n-k}),$$
وأخذ الحد الأدنى على كل القيم المسموحة لـ \(k\) يعطينا
$$\boxed{B_n=\min_{1\le k<n}\left(1+p_aB_{n-k}+p_b(B_k+A_{n-k})\right).}$$
في الحالة \(A_n\) يقارن الكود بين عائلتين من الاستراتيجيات.
الخيار الأول هو اختبار المجموعة كلها مباشرة. هذه الخطوة تكلف اختبارًا واحدًا. فإذا كانت النتيجة سالبة، واحتمال ذلك \(q^n\)، ننتهي فورًا. وإذا كانت موجبة، واحتمال ذلك \(1-q^n\)، فإننا ننتقل إلى الحالة الشرطية \(B_n\). لذلك تكون الكلفة المتوقعة لهذا الخيار
$$1+(1-q^n)B_n.$$
الخيار الثاني هو اختبار مجموعة جزئية أولًا. وبصرف النظر عن نتيجة هذا الاختبار، فإن الأشخاص المتبقين وعددهم \(n-k\) ما زالوا يشكلون مسألة غير مشروطة، ولذلك يساهمون دائمًا بالحد \(A_{n-k}\). ولا ندفع الكلفة الإضافية \(B_k\) إلا إذا كانت المجموعة المختبرة موجبة. ومن ثم
$$1+q^kA_{n-k}+(1-q^k)(B_k+A_{n-k})=1+A_{n-k}+(1-q^k)B_k.$$
وبأخذ الأصغر بين خيار اختبار المجموعة كلها وجميع خيارات التقسيم الممكنة نحصل على
$$\boxed{A_n=\min\left(1+(1-q^n)B_n,\ \min_{1\le k<n}\left(1+A_{n-k}+(1-q^k)B_k\right)\right).}$$
كلتا العلاقتين العوديتين تعتمدان فقط على أحجام أصغر، ولذلك يمكن ملء الجداول بالترتيب \(n=2,3,\dots,s\). كما أن التنفيذ يحسب مسبقًا القيم
$$q^0,q^1,\dots,q^s$$
حتى لا يعيد حساب القوى داخل الحلقات التربيعية.
بعد اكتمال الجداول، تكون القيمة المطلوبة لاحتمال ثابت هي
$$T(s,p)=A_s.$$
ومن ثم يصبح هدف Project Euler هو
$$\boxed{\sum_{i=1}^{50} A_{10000}\Bigl(p=\frac{i}{100}\Bigr).}$$
ويتحقق ملف C++ أيضًا من قيمتين مرجعيتين قبل طباعة الجواب النهائي:
$$T(25,0.02)=4.155452,\qquad T(25,0.10)=12.702124.$$
التنفيذ الرئيسي موجود في solutionsCpp/Euler352.cpp. يبني البرنامج أولًا جدول qpow[n]=q^n، ثم يملأ المصفوفة B[n] وفق العلاقة الشرطية، وبعد ذلك يملأ A[n] وفق العلاقة غير الشرطية. وفي النهاية تعيد الدالة T(s,p) القيمة A[s].
الدالة الخارجية solve() تحسب الحالات الخمسين المستقلة \(p=0.01,0.02,\dots,0.50\) ثم تجمعها. وفي نسخة C++ توزّع هذه الحالات على خيوط pthread مستقلة مع حد أعلى مقداره 8 خيوط. أما الملف solutionsJava/Euler352.java فهو نقل مباشر لنفس البرمجة الديناميكية إلى Java ويستخدم ExecutorService.
أما الملف solutionsPython/Euler352.py فلا يعيد تنفيذ المنهج الرياضي. بل يقوم عند الحاجة بترجمة حل C++ ثم تشغيل الملف التنفيذي الناتج وتحليل مخرجاته. لذلك تبقى الصياغة الرياضية الأصلية في نسخة C++، بينما تتبعها Java مباشرة، وتعمل Python كجسر تشغيل فقط.
لزوج ثابت \((s,p)\)، تدور البرمجة الديناميكية على \(n=2,\dots,s\)، ولكل \(n\) تجرّب جميع القيم \(k=1,\dots,n-1\). لذلك يكون العدد الكلي للتقسيمات المرشحة
$$\sum_{n=2}^{s}(n-1)=\frac{s(s-1)}{2}=O(s^2).$$
أما الذاكرة فهي \(O(s)\) لأن المصفوفات qpow وA وB كلها بطول \(s+1\). وفي الحساب النهائي للمسألة نكرر هذا العمل لخمسين قيمة مستقلة لـ \(p\). التنفيذ المتوازي يقلل الزمن الفعلي، لكنه لا يغيّر الرتبة التقاربية لكمية العمل الكلية.
solutionsCpp/Euler352.cpp, solutionsJava/Euler352.java, solutionsPython/Euler352.py