We start with 40 occupied cells in a row. At each step, one occupied cell is chosen uniformly at random and removed. The occupied cells always form a disjoint union of contiguous segments. If \(C_t\) denotes the number of occupied segments after the \(t\)-th removal, the goal is to compute
$$\mathbb{E}\!\left[\max_t C_t\right].$$
The key difficulty is that the process has \(40!\) possible removal orders, so a direct permutation average is infeasible. The code solves the problem exactly by compressing configurations to segment lengths and then applying a memoized expectation recursion.
Every deletion history is just a permutation of the 40 positions. If we reverse that permutation and insert cells instead of deleting them, we obtain the same sequence of occupied sets in reverse order. Therefore the maximum number of segments is identical in the forward deletion process and in the reverse insertion process.
This observation is not needed for the main DP, but it explains why the brute-force validator in the C++ file can enumerate insertion permutations for small \(n\).
A configuration does not need absolute coordinates. Only the lengths of the current occupied segments matter. So the state is stored as a sorted vector
$$S=(\ell_1,\ell_2,\dots,\ell_m),\qquad 1\le \ell_1\le \ell_2\le \cdots \le \ell_m,$$
where \(m=|S|\) is the current number of segments and
$$R(S)=\ell_1+\ell_2+\cdots+\ell_m$$
is the number of occupied cells still remaining.
The order of segments is irrelevant: states such as \((1,3)\) and \((3,1)\) have the same future law because each segment evolves independently except for its length, and deletions never reconnect separated segments. In other words, a state is just an integer partition of the remaining occupied cells.
Consider one segment of length \(L\).
If \(L=1\), deleting its only cell removes that segment completely.
If \(L\ge 2\), there are two qualitatively different removals:
1. Deleting an endpoint leaves one segment of length \(L-1\). There are exactly 2 such cells.
2. Deleting an interior cell splits the segment into two smaller segments. If the removed cell leaves \(a\) cells on the left and \(b\) cells on the right, then
$$a+b=L-1,\qquad a\ge 1,\quad b\ge 1.$$
Equivalently, for each
$$a=1,2,\dots,L-2,$$
we obtain the split
$$\bigl(a,\;L-1-a\bigr).$$
The implementation removes one copy of \(L\) from the sorted state vector and inserts the new lengths back in sorted order.
If the same segment length appears several times, the corresponding transitions are multiplied by that multiplicity. Suppose length \(L\) occurs \(c_L\) times in the state. Then every transition caused by deleting a cell from a segment of length \(L\) receives an extra factor \(c_L\).
The code aggregates all identical next states into an integer weight
$$w(S\to S').$$
Because each occupied cell is equally likely to be removed, the transition probability is simply
$$\Pr(S\to S')=\frac{w(S\to S')}{R(S)}.$$
The total outgoing weight is always
$$\sum_{S'} w(S\to S')=R(S),$$
because each of the \(R(S)\) occupied cells contributes exactly one deletion outcome.
Let
$$E(S,M)$$
denote the expected final value of the maximum segment count, assuming the current compressed state is \(S\) and the largest segment count seen so far is \(M\).
The base case is immediate:
$$E(\varnothing,M)=M.$$
If \(S\neq\varnothing\), condition on the next deletion. Then
$$E(S,M)=\sum_{S'} \Pr(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
Using the aggregated weights, this becomes
$$E(S,M)=\frac{1}{R(S)}\sum_{S'} w(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
This is the exact recurrence implemented in all three languages.
For the initial state \(S=(3)\), there are three equally likely deletions. Removing either endpoint gives the state \((2)\), while removing the middle cell gives \((1,1)\). Hence
$$E((3),1)=\frac{2}{3}E((2),1)+\frac{1}{3}E((1,1),2).$$
Now \((2)\) can only go to \((1)\), so
$$E((2),1)=1.$$
And from \((1,1)\), deleting one singleton leaves \((1)\) while the maximum segment count has already reached 2, so
$$E((1,1),2)=2.$$
Therefore
$$E((3),1)=\frac{2}{3}\cdot 1+\frac{1}{3}\cdot 2=\frac{4}{3}.$$
This matches the brute-force average over the \(3!=6\) possible deletion orders.
The process is Markovian after compression: once we know the multiset of current segment lengths and the best segment count seen so far, the future no longer depends on the detailed history. Thus the pair \((S,M)\) is a sufficient state description.
The recursion is exact because it is just the law of total expectation applied to the first random deletion. Memoization merely avoids recomputing the same subproblem; it does not introduce approximation.
The C++ code explicitly validates the recurrence against brute force for small sizes:
$$E((6),1)=2.255555555556,$$
$$E((7),1)=2.544444444444.$$
Both values agree with exhaustive enumeration of all \(6!\) and \(7!\) insertion permutations, which is a strong sanity check before solving the full \(40\)-cell problem.
The helper make_next constructs a new sorted state after removing one segment length and inserting the child lengths. The function get_transitions scans equal segment lengths together, aggregates identical next states in a hash map, and stores the resulting list of (nextState, weight) pairs. The function expected_max memoizes the recurrence above; in C++ each compressed state owns a vector of length 41, because the running maximum can only be between 0 and 40. Finally, the program starts from the one-segment state
$$S_0=(40)$$
with initial maximum \(M=1\), after first checking the DP against brute force for \(n=6\) and \(n=7\).
A pure shape state with \(r\) remaining cells is an integer partition of \(r\). Therefore the number of possible compressed shape states is at most
$$\sum_{r=0}^{40} p(r)=215308,$$
where \(p(r)\) is the partition function and \(p(40)=37338\). This is dramatically smaller than \(40!\) deletion orders.
For one fixed state \(S\), the number of raw deletion outcomes is exactly \(R(S)\), and after aggregation the number of distinct next states is still \(O(R(S))\). Memoization ensures that each pair \((S,M)\) is solved only once, so the actual runtime is governed by the number of reachable compressed states and their aggregated transitions rather than by permutations.
Memory usage is proportional to the cached transition table plus the memo table for \((S,M)\).
Wir starten mit 40 besetzten Zellen in einer Reihe. In jedem Schritt wird eine besetzte Zelle gleichwahrscheinlich entfernt. Die verbleibenden besetzten Zellen bilden stets eine disjunkte Vereinigung zusammenhängender Segmente. Bezeichnet \(C_t\) die Anzahl dieser Segmente nach dem \(t\)-ten Entfernen, so ist gesucht:
$$\mathbb{E}\!\left[\max_t C_t\right].$$
Die Schwierigkeit besteht darin, dass es \(40!\) mögliche Entfernungsreihenfolgen gibt. Der Code vermeidet diese Explosion durch Zustandskompression auf Segmentlängen und eine memoisierten Erwartungswert-Rekursion.
Jede Löschhistorie ist eine Permutation der 40 Positionen. Liest man diese Permutation rückwärts und fügt Zellen ein statt sie zu löschen, erhält man dieselben besetzten Mengen in umgekehrter Reihenfolge. Daher ist die maximale Segmentanzahl im Vorwärtsprozess exakt dieselbe wie im rückwärts gelesenen Einfügeprozess.
Für die eigentliche DP ist das nicht notwendig, aber genau deshalb kann der brute-force-Test im C++-Code kleine Fälle über Einfügepermutationen prüfen.
Absolute Positionen spielen keine Rolle. Relevant sind nur die Längen der aktuell vorhandenen Segmente. Der Zustand wird daher als sortierter Vektor gespeichert:
$$S=(\ell_1,\ell_2,\dots,\ell_m),\qquad 1\le \ell_1\le \ell_2\le \cdots \le \ell_m,$$
wobei \(m=|S|\) die aktuelle Segmentanzahl und
$$R(S)=\ell_1+\ell_2+\cdots+\ell_m$$
die Zahl der noch besetzten Zellen ist.
Die Reihenfolge der Segmente ist unerheblich: \((1,3)\) und \((3,1)\) besitzen dieselbe Zukunftsverteilung. Segmente interagieren nur über ihre Länge, und gelöschte Lücken verbinden sich nie wieder. Ein Zustand ist also nichts anderes als eine ganzzahlige Partition der noch verbleibenden Zellen.
Betrachte ein Segment der Länge \(L\).
Für \(L=1\) verschwindet das Segment vollständig.
Für \(L\ge 2\) gibt es zwei Typen von Löschungen:
1. Entfernt man einen Endpunkt, bleibt genau ein Segment der Länge \(L-1\). Das kann auf 2 Arten passieren.
2. Entfernt man eine innere Zelle, zerfällt das Segment in zwei Teilsegmente. Bleiben links \(a\) und rechts \(b\) Zellen, dann gilt
$$a+b=L-1,\qquad a\ge 1,\quad b\ge 1.$$
Äquivalent kann man für
$$a=1,2,\dots,L-2$$
den Split
$$\bigl(a,\;L-1-a\bigr)$$
erzeugen. Die Implementierung entfernt dazu ein Exemplar von \(L\) aus dem sortierten Zustandsvektor und fügt die neuen Längen wieder sortiert ein.
Kommt dieselbe Segmentlänge mehrfach vor, werden die entsprechenden Übergänge mit ihrer Multiplizität gewichtet. Tritt Länge \(L\) genau \(c_L\)-mal auf, erhält jeder von einem solchen Segment erzeugte Übergang den Zusatzfaktor \(c_L\).
Der Code fasst alle identischen Folgezustände in einem ganzzahligen Gewicht
$$w(S\to S')$$
zusammen. Da jede der \(R(S)\) besetzten Zellen gleichwahrscheinlich gelöscht wird, ist
$$\Pr(S\to S')=\frac{w(S\to S')}{R(S)}.$$
Die Summe aller ausgehenden Gewichte ist stets
$$\sum_{S'} w(S\to S')=R(S),$$
denn jede besetzte Zelle liefert genau einen Löschfall.
Sei
$$E(S,M)$$
der erwartete Endwert der maximal jemals gesehenen Segmentanzahl, wenn der aktuelle komprimierte Zustand \(S\) ist und bisher das Maximum \(M\) erreicht wurde.
Der Basisfall lautet:
$$E(\varnothing,M)=M.$$
Für \(S\neq\varnothing\) bedingt man auf den nächsten Schritt und erhält
$$E(S,M)=\sum_{S'} \Pr(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
Mit den aggregierten Gewichten also
$$E(S,M)=\frac{1}{R(S)}\sum_{S'} w(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
Genau diese Gleichung implementieren C++, Java und Python.
Für den Anfangszustand \(S=(3)\) gibt es drei gleichwahrscheinliche Löschungen. Zwei Endpunkte führen zu \((2)\), die mittlere Zelle führt zu \((1,1)\). Also:
$$E((3),1)=\frac{2}{3}E((2),1)+\frac{1}{3}E((1,1),2).$$
Aus \((2)\) wird zwingend \((1)\), also
$$E((2),1)=1.$$
Aus \((1,1)\) bleibt nach einem Schritt \((1)\), das bisherige Maximum ist aber bereits 2, also
$$E((1,1),2)=2.$$
Damit folgt
$$E((3),1)=\frac{2}{3}\cdot 1+\frac{1}{3}\cdot 2=\frac{4}{3}.$$
Das stimmt exakt mit dem brute-force-Mittel über alle \(3!=6\) Reihenfolgen überein.
Nach der Kompression ist der Prozess Markowsch: Kennt man das Multiset der aktuellen Segmentlängen und das bisherige Maximum, hängt die Zukunft nicht mehr von der vollständigen Historie ab. Das Paar \((S,M)\) ist also ein vollständiger Zustand.
Die Rekursion ist nichts anderes als das Gesetz der totalen Erwartung über den ersten Zufallsschritt. Memoisierung spart nur Wiederholungen; sie approximiert nichts.
Der C++-Code prüft die DP explizit gegen brute force für kleine \(n\):
$$E((6),1)=2.255555555556,$$
$$E((7),1)=2.544444444444.$$
Beide Werte stimmen mit der vollständigen Enumeration aller \(6!\)- bzw. \(7!\)-Einfügepermutationen überein.
make_next baut aus einem Zustand den nächsten sortierten Zustand auf, indem eine Segmentlänge entfernt und die Kindlängen eingefügt werden. get_transitions gruppiert gleiche Segmentlängen, akkumuliert identische Folgezustände in einer Hash-Map und speichert Paare der Form (nextState, weight). expected_max memoisiert dann die obige Erwartungswertgleichung; im C++-Code besitzt jeder Zustand einen Vektor der Länge 41, weil das laufende Maximum nur zwischen 0 und 40 liegen kann. Gestartet wird bei
$$S_0=(40)$$
mit Anfangsmaximum \(M=1\), nach den Validierungen für \(n=6\) und \(n=7\).
Ein Formzustand mit \(r\) verbleibenden Zellen ist eine ganzzahlige Partition von \(r\). Daher ist die Anzahl möglicher komprimierter Formzustände höchstens
$$\sum_{r=0}^{40} p(r)=215308,$$
wobei \(p(r)\) die Partitionsfunktion ist und \(p(40)=37338\) gilt. Das ist verschwindend klein gegenüber \(40!\).
Für einen festen Zustand \(S\) gibt es genau \(R(S)\) rohe Löschmöglichkeiten; auch nach der Aggregation bleibt die Zahl verschiedener Folgezustände \(O(R(S))\). Da jedes Paar \((S,M)\) höchstens einmal berechnet wird, bestimmt die Anzahl erreichbarer komprimierter Zustände plus ihrer aggregierten Übergänge die Laufzeit, nicht die Anzahl der Permutationen.
Der Speicherbedarf ist proportional zur Übergangstabelle und zur Memo-Tabelle für \((S,M)\).
Başlangıçta bir satır üzerinde 40 dolu hücre vardır. Her adımda dolu hücrelerden biri eşit olasılıkla seçilip silinir. Geriye kalan dolu hücreler her zaman ayrık ardışık segmentler oluşturur. \(t\). silmeden sonra segment sayısı \(C_t\) ise aranan değer
$$\mathbb{E}\!\left[\max_t C_t\right]$$
olur. Zorluk, 40 hücrenin silinme sırasının \(40!\) farklı olasılık üretmesidir. Kod bunu doğrudan ortalamalamak yerine, durumu segment uzunluklarına sıkıştırıp memoization içeren kesin bir beklenti rekürsiyonu çözer.
Her silme geçmişi, 40 pozisyonun bir permütasyonudur. Bu permütasyonu ters çevirip silme yerine hücre ekleme işlemi düşünülürse, dolu hücre kümeleri aynı sıranın tersten okunmuş hali olarak elde edilir. Bu yüzden görülen en büyük segment sayısı, ileri yöndeki silme süreciyle ters yöndeki ekleme sürecinde aynıdır.
Asıl DP için bu bakış zorunlu değildir; fakat C++ dosyasındaki brute-force doğrulamanın neden küçük \(n\) için ekleme permütasyonlarını gezdiğini açıklar.
Mutlak koordinatlara ihtiyaç yoktur. Geleceği belirleyen tek bilgi, mevcut segmentlerin uzunluklarıdır. Bu nedenle durum şu sıralı vektörle temsil edilir:
$$S=(\ell_1,\ell_2,\dots,\ell_m),\qquad 1\le \ell_1\le \ell_2\le \cdots \le \ell_m,$$
burada \(m=|S|\) anlık segment sayısı ve
$$R(S)=\ell_1+\ell_2+\cdots+\ell_m$$
kalan dolu hücre sayısıdır.
Segmentlerin soldan sağa sırası önemli değildir: \((1,3)\) ile \((3,1)\) aynı olasılık yasasına sahiptir. Çünkü segmentler sadece uzunlukları üzerinden evrilir ve silinmiş boşluklar bir daha segmentleri birleştirmez. Başka bir deyişle, sıkıştırılmış durum aslında kalan hücre sayısının bir tamsayı partition'ıdır.
Uzunluğu \(L\) olan tek bir segmenti ele alalım.
Eğer \(L=1\) ise tek hücre silinince segment tamamen yok olur.
Eğer \(L\ge 2\) ise iki temel durum vardır:
1. Uçtan silme, uzunluğu \(L-1\) olan tek bir segment bırakır. Böyle 2 hücre vardır.
2. İçten silme, segmenti iki parçaya böler. Solda \(a\), sağda \(b\) hücre kalıyorsa
$$a+b=L-1,\qquad a\ge 1,\quad b\ge 1$$
olmalıdır. Eşdeğer olarak
$$a=1,2,\dots,L-2$$
için şu ayrılmalar elde edilir:
$$\bigl(a,\;L-1-a\bigr).$$
Uygulamada kod, durum vektöründen bir adet \(L\) çıkarır ve oluşan yeni uzunlukları tekrar sıralı biçimde geri ekler.
Aynı uzunlukta birden fazla segment varsa, bu segmentlerden gelen geçişler çokluk kadar ağırlık kazanır. Uzunluk \(L\) durum içinde \(c_L\) kez geçiyorsa, o uzunluktan kaynaklanan her geçişin ağırlığı \(c_L\) ile çarpılır.
Kod, aynı yeni duruma giden tüm yolları tek bir tamsayı ağırlıkta toplar:
$$w(S\to S').$$
Her dolu hücre eşit olasılıkla seçildiği için geçiş olasılığı
$$\Pr(S\to S')=\frac{w(S\to S')}{R(S)}$$
olur. Ayrıca tüm çıkış ağırlıklarının toplamı her zaman
$$\sum_{S'} w(S\to S')=R(S)$$
eşitliğini sağlar; çünkü kalan her dolu hücre tam olarak bir silme sonucuna karşılık gelir.
\(E(S,M)\), mevcut sıkıştırılmış durum \(S\) iken ve şimdiye kadar görülen en büyük segment sayısı \(M\) iken sürecin sonunda elde edilecek maksimum segment sayısının beklenen değeri olsun.
Temel durum açıktır:
$$E(\varnothing,M)=M.$$
\(S\neq\varnothing\) ise bir sonraki silme üzerine koşullayarak
$$E(S,M)=\sum_{S'} \Pr(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr)$$
elde edilir. Ağırlıklı biçimde aynı denklem
$$E(S,M)=\frac{1}{R(S)}\sum_{S'} w(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr)$$
şeklindedir. C++, Java ve Python çözümleri tam olarak bu rekürsiyonu uygular.
Başlangıç durumu \(S=(3)\) olsun. Üç eşit olasılıklı silme vardır. İki uçtan biri silinirse \((2)\) durumuna, orta hücre silinirse \((1,1)\) durumuna gidilir. Bu nedenle
$$E((3),1)=\frac{2}{3}E((2),1)+\frac{1}{3}E((1,1),2).$$
\((2)\) yalnızca \((1)\)'e gidebildiği için
$$E((2),1)=1.$$
\((1,1)\) durumunda bir tekli segment silinince \((1)\) kalır; fakat maksimum zaten 2'ye ulaşmıştır. Dolayısıyla
$$E((1,1),2)=2.$$
Sonuç olarak
$$E((3),1)=\frac{2}{3}\cdot 1+\frac{1}{3}\cdot 2=\frac{4}{3}$$
bulunur. Bu değer, \(3!=6\) olası sıranın brute-force ortalamasıyla aynıdır.
Süreç, sıkıştırılmış durumda Markov özelliğine sahiptir: mevcut segment uzunlukları çoklu kümesi ve şimdiye kadarki maksimum biliniyorsa, geleceğin dağılımı geçmişin ayrıntılarına artık bağlı değildir. Yani \((S,M)\) çifti yeterli durum tanımıdır.
Rekürsiyon sadece toplam beklenti yasasının ilk rastgele adıma uygulanmış halidir. Memoization herhangi bir yaklaşım kullanmaz; yalnızca aynı alt problemi tekrar çözmeyi önler.
C++ kodu, rekürsiyonu küçük boyutlarda brute-force ile açıkça doğrular:
$$E((6),1)=2.255555555556,$$
$$E((7),1)=2.544444444444.$$
Bu iki sonuç, sırasıyla tüm \(6!\) ve \(7!\) ekleme permütasyonlarının tam taramasıyla birebir uyuşur. Bu da 40 hücrelik asıl hesap öncesinde güçlü bir doğruluk testi sağlar.
make_next, bir segment uzunluğunu kaldırıp çocuk uzunlukları sıralı biçimde ekleyerek yeni durumu üretir. get_transitions, eşit uzunlukları gruplayarak aynı hedef duruma giden yolları hash map içinde toplar ve (nextState, weight) çiftleri üretir. expected_max ise yukarıdaki beklenti denklemini memoization ile çözer; C++ sürümünde her durum için uzunluğu 41 olan bir dizi tutulur, çünkü çalışan maksimum yalnızca 0 ile 40 arasında olabilir. Program sonunda başlangıç durumu
$$S_0=(40)$$
ve başlangıç maksimumu \(M=1\) ile çözüm hesaplanır; bundan önce \(n=6\) ve \(n=7\) doğrulamaları yapılır.
Kalan hücre sayısı \(r\) olan bir şekil durumu, \(r\)'nin bir tamsayı partition'ıdır. Bu yüzden olası sıkıştırılmış şekil durumlarının sayısı en fazla
$$\sum_{r=0}^{40} p(r)=215308$$
kadardır; burada \(p(r)\) partition fonksiyonudur ve \(p(40)=37338\)'dir. Bu, \(40!\) silme sırasına kıyasla son derece küçüktür.
Sabit bir \(S\) durumu için ham silme sonucu sayısı tam olarak \(R(S)\)'dir; gruplanmış farklı hedef durum sayısı da yine \(O(R(S))\) mertebesindedir. Memoization sayesinde her \((S,M)\) çifti en fazla bir kez çözülür. Bu nedenle gerçek maliyeti belirleyen şey permütasyon sayısı değil, ulaşılabilir sıkıştırılmış durumlar ve onların geçişleridir.
Bellek kullanımı, önbelleğe alınan geçiş tablosu ile \((S,M)\) memo tablosuna orantılıdır.
Comenzamos con 40 celdas ocupadas en una fila. En cada paso se elimina, con probabilidad uniforme, una de las celdas aún ocupadas. Las celdas ocupadas restantes forman siempre una unión disjunta de segmentos contiguos. Si \(C_t\) es el número de segmentos tras la eliminación \(t\), debemos calcular
$$\mathbb{E}\!\left[\max_t C_t\right].$$
Un promedio directo sobre todas las historias de borrado sería inviable, porque hay \(40!\) órdenes posibles. La solución usa compresión de estado por longitudes de segmentos y una recurrencia exacta con memoización.
Cada historia de borrado es una permutación de las 40 posiciones. Si invertimos esa permutación e interpretamos el proceso como inserciones, obtenemos la misma sucesión de conjuntos ocupados leída al revés. Por tanto, el máximo número de segmentos es el mismo en el proceso de borrado y en el proceso inverso de inserción.
Esta observación no es necesaria para la DP principal, pero explica por qué la validación por fuerza bruta del archivo C++ enumera permutaciones de inserción para tamaños pequeños.
Las coordenadas absolutas no importan. El futuro del proceso depende solo de las longitudes de los segmentos actuales. Por eso el estado se guarda como un vector ordenado
$$S=(\ell_1,\ell_2,\dots,\ell_m),\qquad 1\le \ell_1\le \ell_2\le \cdots \le \ell_m,$$
donde \(m=|S|\) es el número actual de segmentos y
$$R(S)=\ell_1+\ell_2+\cdots+\ell_m$$
es el número de celdas ocupadas restantes.
El orden izquierda-derecha de los bloques no afecta la evolución: \((1,3)\) y \((3,1)\) tienen la misma ley futura. En esencia, el estado comprimido es una partición entera del número de celdas restantes.
Tomemos un segmento de longitud \(L\).
Si \(L=1\), al borrar su única celda el segmento desaparece.
Si \(L\ge 2\), hay dos tipos de borrado:
1. Borrar un extremo deja un único segmento de longitud \(L-1\). Hay exactamente 2 extremos.
2. Borrar una celda interior parte el segmento en dos. Si quedan \(a\) celdas a la izquierda y \(b\) a la derecha, entonces
$$a+b=L-1,\qquad a\ge 1,\quad b\ge 1.$$
Equivalentemente, para
$$a=1,2,\dots,L-2$$
aparece la partición
$$\bigl(a,\;L-1-a\bigr).$$
Si una longitud \(L\) aparece varias veces, sus transiciones se multiplican por esa multiplicidad. Si \(L\) aparece \(c_L\) veces, cada transición generada por un bloque de longitud \(L\) recibe un factor adicional \(c_L\).
El código agrega todos los caminos que llevan al mismo estado siguiente en un peso entero
$$w(S\to S').$$
Como cada una de las \(R(S)\) celdas ocupadas es equiprobable,
$$\Pr(S\to S')=\frac{w(S\to S')}{R(S)}.$$
Además, siempre se cumple
$$\sum_{S'} w(S\to S')=R(S),$$
porque cada celda ocupada produce exactamente un resultado elemental.
Sea \(E(S,M)\) el valor esperado del máximo final de segmentos, suponiendo que el estado comprimido actual es \(S\) y que el mayor número de segmentos visto hasta ahora es \(M\).
El caso base es
$$E(\varnothing,M)=M.$$
Condicionando sobre el siguiente borrado, obtenemos
$$E(S,M)=\sum_{S'} \Pr(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
O, con pesos agregados,
$$E(S,M)=\frac{1}{R(S)}\sum_{S'} w(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
Para \(S=(3)\), borrar un extremo lleva a \((2)\) y borrar la celda central lleva a \((1,1)\). Por tanto,
$$E((3),1)=\frac{2}{3}E((2),1)+\frac{1}{3}E((1,1),2).$$
Como \((2)\) solo puede ir a \((1)\), tenemos
$$E((2),1)=1.$$
Y desde \((1,1)\), al borrar uno de los dos bloques unitarios queda \((1)\), pero el máximo ya ha alcanzado 2, así que
$$E((1,1),2)=2.$$
Entonces
$$E((3),1)=\frac{2}{3}\cdot 1+\frac{1}{3}\cdot 2=\frac{4}{3}.$$
Tras la compresión, el proceso tiene propiedad de Markov: conocido el multiconjunto de longitudes actuales y el máximo ya observado, el futuro no depende del detalle de la historia. El par \((S,M)\) es por tanto un estado suficiente.
La recurrencia no es una aproximación; es simplemente la ley de la esperanza total aplicada al siguiente paso aleatorio. La memoización solo evita recalcular subproblemas repetidos.
El código C++ compara explícitamente la DP con fuerza bruta para tamaños pequeños:
$$E((6),1)=2.255555555556,$$
$$E((7),1)=2.544444444444.$$
Ambos valores coinciden exactamente con la enumeración completa de las \(6!\) y \(7!\) permutaciones.
make_next construye el siguiente estado ordenado quitando una longitud y añadiendo las nuevas sublongitudes. get_transitions agrupa longitudes iguales, acumula estados siguientes idénticos en un mapa hash y guarda pares (nextState, weight). expected_max memoriza la recurrencia anterior; en C++ cada estado dispone de un vector de longitud 41 porque el máximo acumulado solo puede estar entre 0 y 40. El cálculo final comienza en
$$S_0=(40)$$
con máximo inicial \(M=1\).
Un estado de forma con \(r\) celdas restantes es una partición entera de \(r\). Por ello, el número de estados comprimidos posibles está acotado por
$$\sum_{r=0}^{40} p(r)=215308,$$
donde \(p(r)\) es la función de partición y \(p(40)=37338\). Esto es muchísimo menor que \(40!\).
Para un estado fijo \(S\), el número de resultados elementales de borrado es exactamente \(R(S)\), y tras agruparlos el número de estados siguientes distintos sigue siendo \(O(R(S))\). Gracias a la memoización, cada par \((S,M)\) se resuelve solo una vez.
初始时一行中有 40 个已占据的格子。每一步都从当前已占据的格子里等概率删除一个。剩余的已占据格子始终构成若干互不相交的连续段。若 \(C_t\) 表示第 \(t\) 次删除后的连续段数量，则目标是计算
$$\mathbb{E}\!\left[\max_t C_t\right].$$
直接对所有删除顺序求平均是不现实的，因为一共有 \(40!\) 种顺序。代码的做法是把状态压缩为“各段长度的有序多重集”，然后对期望值建立精确递推并做记忆化。
任意一次删除历史，本质上都是 40 个位置的一个排列。如果把这个排列反过来读，并把“删除”改成“插入”，那么得到的占据集合序列恰好是原过程的逆序。因此，整个过程中出现过的最大段数，在正向删除过程与逆向插入过程里是相同的。
主算法本身不依赖这个观点，但它解释了为什么 C++ 里的暴力校验可以对小规模 \(n\) 枚举插入排列。
未来演化只依赖当前各连续段的长度，而不依赖它们的绝对坐标。所以状态记为排好序的向量
$$S=(\ell_1,\ell_2,\dots,\ell_m),\qquad 1\le \ell_1\le \ell_2\le \cdots \le \ell_m,$$
其中 \(m=|S|\) 是当前段数，而
$$R(S)=\ell_1+\ell_2+\cdots+\ell_m$$
是当前仍然占据的格子数。
段的左右顺序并不重要；例如 \((1,3)\) 与 \((3,1)\) 的未来分布完全相同。因为各段只通过自身长度演化，而且删除产生的空隙不会再把两段重新连起来。换句话说，压缩状态就是“剩余格子数的一个整数分拆”。
考虑一个长度为 \(L\) 的连续段。
若 \(L=1\)，删除唯一的格子后该段直接消失。
若 \(L\ge 2\)，有两类删除方式：
1. 删除端点，结果留下一个长度为 \(L-1\) 的段，一共有 2 个端点。
2. 删除内部格子，原段裂成两个子段。若左边留下 \(a\) 个格子、右边留下 \(b\) 个格子，则
$$a+b=L-1,\qquad a\ge 1,\quad b\ge 1.$$
等价地，对
$$a=1,2,\dots,L-2$$
可得到拆分
$$\bigl(a,\;L-1-a\bigr).$$
如果某个长度 \(L\) 在当前状态中出现了多次，那么由这些相同长度段产生的转移需要乘以出现次数。设长度 \(L\) 的出现次数为 \(c_L\)，则该长度对应的每个转移都带有额外因子 \(c_L\)。
代码把所有通往同一个下一状态的路径合并成一个整数权重
$$w(S\to S').$$
由于每个已占据格子被选中的概率都是 \(1/R(S)\)，因此
$$\Pr(S\to S')=\frac{w(S\to S')}{R(S)}.$$
并且总有
$$\sum_{S'} w(S\to S')=R(S),$$
因为每一个已占据格子都对应一个且仅一个基本删除结果。
定义 \(E(S,M)\) 为：当前压缩状态为 \(S\)，且迄今为止出现过的最大段数为 \(M\) 时，最终最大段数的期望。
边界条件是
$$E(\varnothing,M)=M.$$
对下一次删除做条件化，有
$$E(S,M)=\sum_{S'} \Pr(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
写成权重形式即
$$E(S,M)=\frac{1}{R(S)}\sum_{S'} w(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
当 \(S=(3)\) 时，删除两个端点都会到 \((2)\)，删除中间格子会到 \((1,1)\)。因此
$$E((3),1)=\frac{2}{3}E((2),1)+\frac{1}{3}E((1,1),2).$$
而 \((2)\) 只能转到 \((1)\)，所以
$$E((2),1)=1.$$
从 \((1,1)\) 删除任意一个单点段后都变成 \((1)\)，但最大段数已经达到 2，因此
$$E((1,1),2)=2.$$
于是
$$E((3),1)=\frac{2}{3}\cdot 1+\frac{1}{3}\cdot 2=\frac{4}{3}.$$
压缩之后，这个过程满足 Markov 性质：只要知道当前段长多重集和历史最大段数，未来分布就不再依赖更早的细节。因此 \((S,M)\) 是充分状态。
递推式本身只是对下一次随机删除应用全期望公式，并不是近似。记忆化只是在避免重复求解相同子问题。
C++ 代码对小规模情形做了显式校验：
$$E((6),1)=2.255555555556,$$
$$E((7),1)=2.544444444444.$$
这两个结果与对所有 \(6!\) 和 \(7!\) 种排列的暴力枚举完全一致。
make_next 负责删除一个段长并把生成出的子段长度重新按序插回。get_transitions 把相同长度的段分组，并用哈希表累加相同下一状态的权重，最终得到 (nextState, weight) 列表。expected_max 对上面的期望递推做记忆化；在 C++ 版本中，每个压缩状态对应一个长度为 41 的数组，因为运行中的最大段数只可能在 0 到 40 之间。最终从
$$S_0=(40)$$
和初始最大值 \(M=1\) 开始求解。
若还剩 \(r\) 个格子，则一个“形状状态”就是 \(r\) 的一个整数分拆。因此压缩状态总数至多为
$$\sum_{r=0}^{40} p(r)=215308,$$
其中 \(p(r)\) 是分拆函数，且 \(p(40)=37338\)。这比 \(40!\) 小得多。
对固定状态 \(S\)，原始删除结果的个数恰好是 \(R(S)\)，聚合之后不同下一状态的数量仍为 \(O(R(S))\)。由于每个 \((S,M)\) 只会被求解一次，实际复杂度由可达压缩状态数和它们的转移数决定，而不是由排列总数决定。
Изначально имеется 40 занятых клеток в одной линии. На каждом шаге одна из занятых клеток выбирается равновероятно и удаляется. Оставшиеся занятые клетки всегда образуют несколько непересекающихся непрерывных отрезков. Если \(C_t\) обозначает число таких отрезков после \(t\)-го удаления, требуется вычислить
$$\mathbb{E}\!\left[\max_t C_t\right].$$
Прямое усреднение по всем историям удаления невозможно, потому что существует \(40!\) порядков. Поэтому решение сжимает конфигурацию до длин отрезков и строит точную рекурсию для математического ожидания с мемоизацией.
Любая история удаления есть просто перестановка 40 позиций. Если прочитать эту перестановку в обратном порядке и вместо удаления выполнять добавление клеток, мы получим ту же последовательность занятых множеств, только в обратную сторону. Следовательно, максимальное число сегментов одинаково в прямом процессе удаления и в обратном процессе вставки.
Для основной DP это не требуется, но именно поэтому brute-force-проверка в C++ перечисляет перестановки вставки для малых \(n\).
Абсолютные координаты не нужны. Важно только, какие длины имеют текущие непрерывные отрезки. Поэтому состояние хранится как отсортированный вектор
$$S=(\ell_1,\ell_2,\dots,\ell_m),\qquad 1\le \ell_1\le \ell_2\le \cdots \le \ell_m,$$
где \(m=|S|\) есть текущее число сегментов, а
$$R(S)=\ell_1+\ell_2+\cdots+\ell_m$$
есть число ещё занятых клеток.
Порядок сегментов слева направо не влияет на будущее: состояния \((1,3)\) и \((3,1)\) имеют одинаковый закон эволюции. По сути, такое состояние является просто целочисленным разбиением числа оставшихся клеток.
Рассмотрим сегмент длины \(L\).
Если \(L=1\), удаление единственной клетки уничтожает сегмент.
Если \(L\ge 2\), возможны два типа удаления:
1. Удаление крайней клетки оставляет один сегмент длины \(L-1\). Таких вариантов ровно 2.
2. Удаление внутренней клетки разбивает сегмент на два. Если слева остаётся \(a\) клеток, а справа \(b\), то
$$a+b=L-1,\qquad a\ge 1,\quad b\ge 1.$$
То есть для
$$a=1,2,\dots,L-2$$
получается разбиение
$$\bigl(a,\;L-1-a\bigr).$$
Если одна и та же длина встречается несколько раз, соответствующие переходы умножаются на кратность. Если длина \(L\) встречается \(c_L\) раз, каждый переход, порождённый сегментом длины \(L\), получает дополнительный множитель \(c_L\).
Все одинаковые следующие состояния код агрегирует в целочисленный вес
$$w(S\to S').$$
Так как каждая из \(R(S)\) занятых клеток выбирается с вероятностью \(1/R(S)\), то
$$\Pr(S\to S')=\frac{w(S\to S')}{R(S)}.$$
При этом всегда
$$\sum_{S'} w(S\to S')=R(S),$$
потому что каждая занятая клетка даёт ровно один элементарный исход удаления.
Обозначим через \(E(S,M)\) математическое ожидание окончательного максимума числа сегментов, если текущим сжатым состоянием является \(S\), а максимум, наблюдавшийся до сих пор, равен \(M\).
Базовый случай:
$$E(\varnothing,M)=M.$$
Если \(S\neq\varnothing\), то по формуле полной вероятности и полной ожидания
$$E(S,M)=\sum_{S'} \Pr(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
В терминах весов это же записывается как
$$E(S,M)=\frac{1}{R(S)}\sum_{S'} w(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
Для состояния \(S=(3)\) удаление края переводит в \((2)\), а удаление середины переводит в \((1,1)\). Значит,
$$E((3),1)=\frac{2}{3}E((2),1)+\frac{1}{3}E((1,1),2).$$
Поскольку \((2)\) может перейти только в \((1)\), имеем
$$E((2),1)=1.$$
А из \((1,1)\) после одного удаления остаётся \((1)\), но максимум уже достиг 2, поэтому
$$E((1,1),2)=2.$$
Следовательно,
$$E((3),1)=\frac{2}{3}\cdot 1+\frac{1}{3}\cdot 2=\frac{4}{3}.$$
После сжатия процесс становится марковским: если известны текущее мультимножество длин сегментов и уже достигнутый максимум, будущее не зависит от подробной истории. Пара \((S,M)\) является достаточным состоянием.
Сама рекурсия точна, потому что это всего лишь закон полного математического ожидания по первому случайному шагу. Мемоизация лишь убирает повторные вычисления.
C++-код явно сверяет DP с brute force для малых размеров:
$$E((6),1)=2.255555555556,$$
$$E((7),1)=2.544444444444.$$
Эти значения в точности совпадают с полным перебором всех \(6!\) и \(7!\) перестановок.
make_next строит следующее отсортированное состояние: удаляет одну длину сегмента и вставляет новые длины потомков. get_transitions группирует одинаковые длины, накапливает одинаковые следующие состояния в хеш-таблице и возвращает список пар (nextState, weight). Функция expected_max мемоизирует приведённую выше рекурсию; в C++ на каждое сжатое состояние отводится вектор длины 41, потому что текущий максимум может лежать только между 0 и 40. Основной расчёт стартует из
$$S_0=(40)$$
при начальном максимуме \(M=1\).
Форма состояния с \(r\) оставшимися клетками есть целочисленное разбиение числа \(r\). Поэтому количество возможных сжатых форм не превосходит
$$\sum_{r=0}^{40} p(r)=215308,$$
где \(p(r)\) — функция разбиений, причём \(p(40)=37338\). Это несравнимо меньше, чем \(40!\).
Для фиксированного состояния \(S\) число элементарных исходов удаления равно ровно \(R(S)\), а после агрегации число различных следующих состояний остаётся порядка \(O(R(S))\). Благодаря мемоизации каждая пара \((S,M)\) вычисляется не более одного раза.
نبدأ بصف من 40 خانة ممتلئة. في كل خطوة نختار خانة ممتلئة عشوائيًا باحتمال متساوٍ ثم نحذفها. الخانات الممتلئة الباقية تكوّن دائمًا اتحادًا من مقاطع متصلة منفصلة. إذا رمزنا بعدد المقاطع بعد الحذف رقم \(t\) بالرمز \(C_t\)، فالمطلوب هو حساب
$$\mathbb{E}\!\left[\max_t C_t\right].$$
المشكلة لا يمكن حلها بتعداد جميع ترتيبات الحذف مباشرة، لأن عددها \(40!\). لذلك يضغط الكود الحالة إلى أطوال المقاطع فقط، ثم يحسب التوقع بدقة عبر علاقة عودية مع memoization.
كل تاريخ حذف هو مجرد ترتيب permuation للمواقع الأربعين. إذا قلبنا هذا الترتيب وفسرنا العملية على أنها إضافة خلايا بدل حذفها، نحصل على نفس مجموعات الخلايا الممتلئة ولكن بترتيب زمني معكوس. لذلك فإن أكبر عدد من المقاطع يظهر أثناء الحذف يساوي تمامًا أكبر عدد من المقاطع في عملية الإضافة المعكوسة.
هذا المنظور ليس ضروريًا للـ DP نفسها، لكنه يفسر لماذا يقوم جزء التحقق brute-force في ملف C++ بتعداد ترتيبات الإضافة للحالات الصغيرة.
الإحداثيات المطلقة لا تهم. ما يحدد المستقبل هو أطوال المقاطع الحالية فقط. لذلك تمثل الحالة بالمتجه المرتب
$$S=(\ell_1,\ell_2,\dots,\ell_m),\qquad 1\le \ell_1\le \ell_2\le \cdots \le \ell_m,$$
حيث \(m=|S|\) هو عدد المقاطع الحالي، و
$$R(S)=\ell_1+\ell_2+\cdots+\ell_m$$
هو عدد الخلايا الممتلئة المتبقية.
ترتيب المقاطع على الخط لا يؤثر في التوزيع المستقبلي؛ فالحالتان \((1,3)\) و\((3,1)\) متكافئتان تمامًا. عمليًا، الحالة المضغوطة ليست إلا partition صحيحًا لعدد الخلايا المتبقية.
خذ مقطعًا طوله \(L\).
إذا كان \(L=1\)، فإن حذف خليته الوحيدة يزيل المقطع كله.
أما إذا كان \(L\ge 2\)، فهناك حالتان أساسيتان:
1. حذف طرف من المقطع يترك مقطعًا واحدًا بطول \(L-1\)، وهناك حالتان من هذا النوع.
2. حذف خلية داخلية يشطر المقطع إلى مقطعين. إذا بقي \(a\) خلية يسارًا و\(b\) خلية يمينًا، فلابد أن
$$a+b=L-1,\qquad a\ge 1,\quad b\ge 1.$$
وبصورة مكافئة، لكل
$$a=1,2,\dots,L-2$$
نحصل على الانقسام
$$\bigl(a,\;L-1-a\bigr).$$
إذا ظهر الطول نفسه أكثر من مرة داخل الحالة، فإن الانتقالات الناتجة عنه تُضرب في عدد مرات ظهوره. فإذا كان الطول \(L\) موجودًا \(c_L\) مرات، فإن كل انتقال ناتج من مقطع بهذا الطول يحصل على عامل إضافي \(c_L\).
يجمع الكود كل المسارات التي تصل إلى الحالة التالية نفسها داخل وزن صحيح واحد
$$w(S\to S').$$
وبما أن كل خلية ممتلئة تُختار باحتمال \(1/R(S)\)، فإن
$$\Pr(S\to S')=\frac{w(S\to S')}{R(S)}.$$
كما أن مجموع الأوزان الخارجة يساوي دائمًا
$$\sum_{S'} w(S\to S')=R(S),$$
لأن كل خلية ممتلئة تمثل نتيجة حذف أولية واحدة بالضبط.
لنعرّف \(E(S,M)\) بأنه القيمة المتوقعة لأكبر عدد مقاطع سيظهر في النهاية، إذا كانت الحالة المضغوطة الحالية هي \(S\) وكان أكبر عدد مقاطع شوهد حتى الآن هو \(M\).
الحالة الأساسية هي
$$E(\varnothing,M)=M.$$
وعند تكييف التوقع على خطوة الحذف التالية نحصل على
$$E(S,M)=\sum_{S'} \Pr(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
وبصيغة الأوزان المجمعة تصبح
$$E(S,M)=\frac{1}{R(S)}\sum_{S'} w(S\to S')\;E\bigl(S',\max(M,|S'|)\bigr).$$
عندما تكون الحالة \(S=(3)\)، فإن حذف أحد الطرفين ينقلنا إلى \((2)\)، بينما حذف الخلية الوسطى ينقلنا إلى \((1,1)\). إذن
$$E((3),1)=\frac{2}{3}E((2),1)+\frac{1}{3}E((1,1),2).$$
وبما أن \((2)\) لا يمكن أن تذهب إلا إلى \((1)\)، فلدينا
$$E((2),1)=1.$$
أما من \((1,1)\)، فعند حذف أحد المقطعين الأحاديين تبقى \((1)\)، لكن القيمة العظمى وصلت أصلًا إلى 2، ولذلك
$$E((1,1),2)=2.$$
ومن ثم
$$E((3),1)=\frac{2}{3}\cdot 1+\frac{1}{3}\cdot 2=\frac{4}{3}.$$
بعد ضغط الحالة يصبح المسار ذا خاصية Markov: إذا عرفنا أطوال المقاطع الحالية وأكبر عدد مقاطع شوهد حتى الآن، فإن المستقبل لا يعتمد على التفاصيل الأقدم. لذلك فالزوج \((S,M)\) يكفي كوصف كامل للحالة.
العلاقة العودية ليست تقريبًا عدديًا، بل هي تطبيق مباشر لقانون التوقع الكلي على الخطوة العشوائية التالية. ودور memoization يقتصر على منع إعادة حل نفس المسألة الفرعية مرات متعددة.
يفحص كود C++ صحة العلاقة العودية بمقارنتها مع brute force في الأحجام الصغيرة:
$$E((6),1)=2.255555555556,$$
$$E((7),1)=2.544444444444.$$
وهاتان القيمتان تتطابقان تمامًا مع التعداد الكامل لكل \(6!\) و\(7!\) من الترتيبات.
الدالة make_next تبني الحالة التالية بعد إزالة طول مقطع واحد وإدراج الأطوال الجديدة بترتيب مرتب. والدالة get_transitions تجمع الأطوال المتساوية، وتراكم الحالات التالية المتماثلة داخل hash map، ثم تعيد أزواجًا من الشكل (nextState, weight). أما expected_max فتطبق العلاقة العودية السابقة مع memoization؛ وفي نسخة C++ يمتلك كل state متجهًا بطول 41 لأن القيمة العظمى الجارية لا يمكن أن تتجاوز 40. يبدأ الحل من
$$S_0=(40)$$
مع قيمة ابتدائية \(M=1\).
أي حالة شكلية مع \(r\) خلية متبقية تمثل partition صحيحًا للعدد \(r\). ولذلك فإن عدد الحالات المضغوطة الممكنة لا يزيد على
$$\sum_{r=0}^{40} p(r)=215308,$$
حيث \(p(r)\) هي دالة partitions و\(p(40)=37338\). وهذا أصغر بكثير من \(40!\).
بالنسبة إلى حالة ثابتة \(S\)، فإن عدد نتائج الحذف الأولية يساوي بالضبط \(R(S)\)، وحتى بعد التجميع يبقى عدد الحالات التالية المختلفة من رتبة \(O(R(S))\). وبفضل memoization لا يُحل كل زوج \((S,M)\) إلا مرة واحدة.