There are \(n\) rounds, and the hidden absolute ranks \(1,2,\dots,n\) appear in uniformly random order, where rank \(1\) is best. At round \(t\), you do not know the absolute rank of the current item; you only know its relative rank among the first \(t\) items seen so far. After seeing that relative rank, you must choose between stopping immediately and accepting the current item, or continuing to the next round. If you reach the final round, you must accept the last remaining item.
The goal is to minimize the expected absolute rank of the accepted item. Let \(F(n)\) denote that minimum expected value. A brute-force search over all decision trees is hopeless, so the solution uses backward dynamic programming and the fact that the stopping value depends only on the observed relative rank.
Let \(V_t\) be the minimum expected final absolute rank when round \(t\) is about to begin, before the relative rank of the current item has been revealed. The desired answer is \(F(n)=V_1\).
At the last round there is no decision left: the current item must be accepted. Because every absolute rank from \(1\) to \(n\) is equally likely to be the final unseen item, the expected rank at round \(n\) is simply the average of all ranks:
$$V_n=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.$$
This gives the base case for the backward recurrence. Every earlier round will compare the value of stopping now against the value \(V_{t+1}\) of postponing the decision.
Suppose that at round \(t\) the observed item is the \(r\)-th best among the first \(t\) items, with \(1\le r\le t\). We need the expected absolute rank of that item among all \(n\) items.
If the \(t\) revealed absolute ranks are written in increasing order as
$$1\le a_1<a_2<\cdots<a_t\le n,$$
then the observed item has absolute rank \(a_r\). Now adjoin the endpoints \(a_0=0\) and \(a_{t+1}=n+1\). The \(t+1\) gaps
$$a_1-a_0,\ a_2-a_1,\ \dots,\ a_{t+1}-a_t$$
are exchangeable and their sum is \(n+1\). Therefore each gap has expected size
$$\frac{n+1}{t+1}.$$
Adding the first \(r\) expected gaps gives
$$\mathbb{E}[a_r]=\frac{r(n+1)}{t+1}.$$
So if we stop after seeing relative rank \(r\) at round \(t\), the expected final absolute rank is
$$S_t(r)=\frac{n+1}{t+1}\,r.$$
It is convenient to write
$$s_t=\frac{n+1}{t+1},\qquad S_t(r)=s_t r.$$
At round \(t\), once the relative rank \(r\) is known, there are only two possible costs: stopping costs \(s_t r\), while continuing costs \(V_{t+1}\).
Stopping is optimal exactly when
$$s_t r\le V_{t+1}.$$
Because \(s_t r\) increases linearly with \(r\), the set of ranks for which we stop is an initial segment \(r=1,2,\dots,k_t\). Hence the policy at every round is characterized by a single threshold
$$k_t=\left\lfloor\frac{V_{t+1}}{s_t}\right\rfloor,$$
with the obvious clipping
$$0\le k_t\le t.$$
If \(k_t=0\), we always continue. If \(k_t=t\), we always stop. Otherwise we stop precisely when the observed relative rank is at most \(k_t\).
For a random permutation, the relative rank of the current item among the first \(t\) items is uniformly distributed on \(\{1,2,\dots,t\}\). Therefore each \(r\) occurs with probability \(1/t\).
Using the threshold rule, the Bellman update is
$$V_t=\frac{1}{t}\left(\sum_{r=1}^{k_t} s_t r+\sum_{r=k_t+1}^{t} V_{t+1}\right).$$
The second sum is simply \((t-k_t)V_{t+1}\), and the first uses the triangular-number identity
$$\sum_{r=1}^{k_t} r=\frac{k_t(k_t+1)}{2}.$$
Thus
$$V_t=\frac{1}{t}\left(s_t\frac{k_t(k_t+1)}{2}+(t-k_t)V_{t+1}\right).$$
This recurrence matches the program line for line.
Starting from \(V_n=(n+1)/2\), we compute
$$V_{n-1},\ V_{n-2},\ \dots,\ V_1$$
one round at a time. Each update needs only the value from the next round, so the entire dynamic program can be run with constant memory. No large table is required even when \(n=10^6\).
The implementations also protect the floor operation from roundoff drift by adding a tiny positive tolerance before taking \(\lfloor\cdot\rfloor\), then clamping the threshold into the valid interval \([0,t]\).
The checkpoint \(F(4)=15/8\) can be reproduced directly from the recurrence.
At the last round,
$$V_4=\frac{5}{2}.$$
For \(t=3\), we have \(s_3=5/4\), so
$$k_3=\left\lfloor\frac{V_4}{s_3}\right\rfloor=\left\lfloor\frac{5/2}{5/4}\right\rfloor=\lfloor 2\rfloor=2.$$
Therefore
$$V_3=\frac{1}{3}\left(\frac{5}{4}(1+2)+1\cdot\frac{5}{2}\right)=\frac{25}{12}.$$
For \(t=2\), we have \(s_2=5/3\), hence
$$k_2=\left\lfloor\frac{V_3}{s_2}\right\rfloor=\left\lfloor\frac{25/12}{5/3}\right\rfloor=\left\lfloor\frac{5}{4}\right\rfloor=1,$$
and so
$$V_2=\frac{1}{2}\left(\frac{5}{3}\cdot 1+1\cdot\frac{25}{12}\right)=\frac{15}{8}.$$
For \(t=1\), we get \(s_1=5/2\) and
$$k_1=\left\lfloor\frac{15/8}{5/2}\right\rfloor=\left\lfloor\frac{3}{4}\right\rfloor=0.$$
So the first round is never accepted immediately, and
$$V_1=V_2=\frac{15}{8}.$$
Hence
$$F(4)=\frac{15}{8},$$
which agrees with the checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same compact loop. They begin with the forced-final-round value \((n+1)/2\), interpreted as the value for the next round. Then, for each \(t\) from \(n-1\) down to \(1\), they compute the slope \(s_t=(n+1)/(t+1)\), divide the next-round value by that slope to obtain the stopping threshold, round it down with a small tolerance, and clamp it to the interval \([0,t]\).
After that, the implementation evaluates the stopping contribution with the closed form \(1+2+\cdots+k_t=k_t(k_t+1)/2\), adds the continuation contribution \((t-k_t)V_{t+1}\), divides by \(t\), and overwrites the stored value with the newly computed \(V_t\). The loop therefore stores only one floating-point state instead of an array of all \(V_t\) values. One of the implementations also checks the small cases \(n=3\), \(n=4\), and \(n=10\) before printing the answer for \(n=1{,}000{,}000\).
Each round performs only a constant number of arithmetic operations, and the triangular sum is replaced by a closed formula. Therefore the running time is
$$O(n),$$
and the memory usage is
$$O(1).$$
For the target input, the computation is simply a single backward pass from \(t=n-1\) down to \(t=1\).
Es gibt \(n\) Runden, und die verborgenen absoluten Ränge \(1,2,\dots,n\) erscheinen in zufälliger Reihenfolge, wobei Rang \(1\) der beste ist. In Runde \(t\) kennt man den absoluten Rang des aktuellen Objekts nicht, sondern nur seinen relativen Rang unter den ersten \(t\) bisher gesehenen Objekten. Nach dieser Beobachtung muss man entscheiden, ob man sofort stoppt und das aktuelle Objekt akzeptiert, oder ob man weitermacht. In der letzten Runde muss das verbleibende Objekt genommen werden.
Gesucht ist die Strategie mit minimalem Erwartungswert des absoluten Rangs des gewählten Objekts. Bezeichne diesen Minimalwert mit \(F(n)\). Eine direkte Analyse aller Entscheidungsbäume ist unpraktisch; stattdessen nutzt die Lösung rückwärts gerichtete dynamische Programmierung und die lineare Form des Stoppwerts.
Sei \(V_t\) der minimale erwartete endgültige absolute Rang, wenn Runde \(t\) gerade beginnt und der relative Rang des aktuellen Objekts noch nicht bekannt ist. Gesucht ist also \(F(n)=V_1\).
In der letzten Runde gibt es keine Wahl mehr: Das aktuelle Objekt muss akzeptiert werden. Jeder absolute Rang von \(1\) bis \(n\) ist dort gleich wahrscheinlich, also ist der Erwartungswert einfach der Mittelwert aller Ränge:
$$V_n=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.$$
Das ist der Startpunkt der Rückwärtsrekursion. In jeder früheren Runde vergleicht man den Wert des sofortigen Stoppens mit dem Wert \(V_{t+1}\) des Weitergehens.
Angenommen, in Runde \(t\) ist das beobachtete Objekt das \(r\)-tbeste unter den ersten \(t\) gesehenen Objekten, wobei \(1\le r\le t\). Dann benötigen wir den erwarteten absoluten Rang dieses Objekts unter allen \(n\) Objekten.
Ordnen wir die \(t\) bereits erschienenen absoluten Ränge aufsteigend als
$$1\le a_1<a_2<\cdots<a_t\le n,$$
so hat das aktuelle Objekt den absoluten Rang \(a_r\). Ergänzt man \(a_0=0\) und \(a_{t+1}=n+1\), dann sind die \(t+1\) Lücken
$$a_1-a_0,\ a_2-a_1,\ \dots,\ a_{t+1}-a_t$$
austauschbar und ihre Summe ist \(n+1\). Daher hat jede Lücke den Erwartungswert
$$\frac{n+1}{t+1}.$$
Durch Summation der ersten \(r\) erwarteten Lücken erhält man
$$\mathbb{E}[a_r]=\frac{r(n+1)}{t+1}.$$
Wenn man also in Runde \(t\) bei relativem Rang \(r\) stoppt, ist der erwartete endgültige absolute Rang
$$S_t(r)=\frac{n+1}{t+1}\,r.$$
Praktisch ist die Schreibweise
$$s_t=\frac{n+1}{t+1},\qquad S_t(r)=s_t r.$$
In Runde \(t\) gibt es nach Beobachtung von \(r\) genau zwei relevante Kosten: Stoppen kostet \(s_t r\), Weitergehen kostet \(V_{t+1}\).
Stoppen ist genau dann optimal, wenn
$$s_t r\le V_{t+1}.$$
Da \(s_t r\) linear mit \(r\) wächst, bilden die akzeptierten Ränge immer ein Anfangsintervall \(r=1,2,\dots,k_t\). Also wird jede Runde durch eine einzige Schwelle beschrieben:
$$k_t=\left\lfloor\frac{V_{t+1}}{s_t}\right\rfloor,$$
wobei natürlich
$$0\le k_t\le t$$
gelten muss. Bei \(k_t=0\) wird nie sofort gestoppt, bei \(k_t=t\) immer.
In einer zufälligen Permutation ist der relative Rang des aktuellen Objekts unter den ersten \(t\) Objekten gleichverteilt auf \(\{1,2,\dots,t\}\). Jeder Wert tritt also mit Wahrscheinlichkeit \(1/t\) auf.
Mit der Schwellenregel folgt die Bellman-Rekursion
$$V_t=\frac{1}{t}\left(\sum_{r=1}^{k_t} s_t r+\sum_{r=k_t+1}^{t} V_{t+1}\right).$$
Die zweite Summe ist \((t-k_t)V_{t+1}\), und für die erste nutzt man
$$\sum_{r=1}^{k_t} r=\frac{k_t(k_t+1)}{2}.$$
Daher erhält man
$$V_t=\frac{1}{t}\left(s_t\frac{k_t(k_t+1)}{2}+(t-k_t)V_{t+1}\right).$$
Genau diese Formel wird im Programm ausgewertet.
Beginnend mit \(V_n=(n+1)/2\) berechnet man der Reihe nach
$$V_{n-1},\ V_{n-2},\ \dots,\ V_1.$$
Für ein Update wird nur der Wert der nächsten Runde benötigt, deshalb genügt konstanter Speicher. Selbst für \(n=10^6\) ist keine große DP-Tabelle nötig.
Die Implementierungen schützen außerdem die Abrundung vor kleinen Rundungsfehlern, indem vor dem Floor eine winzige positive Toleranz addiert und das Ergebnis anschließend in das Intervall \([0,t]\) geklemmt wird.
Der Kontrollwert \(F(4)=15/8\) folgt direkt aus der Rekursion.
In der letzten Runde gilt
$$V_4=\frac{5}{2}.$$
Für \(t=3\) ist \(s_3=5/4\), also
$$k_3=\left\lfloor\frac{V_4}{s_3}\right\rfloor=\left\lfloor\frac{5/2}{5/4}\right\rfloor=\lfloor 2\rfloor=2.$$
Damit
$$V_3=\frac{1}{3}\left(\frac{5}{4}(1+2)+1\cdot\frac{5}{2}\right)=\frac{25}{12}.$$
Für \(t=2\) ist \(s_2=5/3\), also
$$k_2=\left\lfloor\frac{V_3}{s_2}\right\rfloor=\left\lfloor\frac{25/12}{5/3}\right\rfloor=\left\lfloor\frac{5}{4}\right\rfloor=1,$$
und damit
$$V_2=\frac{1}{2}\left(\frac{5}{3}\cdot 1+1\cdot\frac{25}{12}\right)=\frac{15}{8}.$$
Für \(t=1\) erhält man \(s_1=5/2\) und
$$k_1=\left\lfloor\frac{15/8}{5/2}\right\rfloor=\left\lfloor\frac{3}{4}\right\rfloor=0.$$
Die erste Runde wird also nie sofort angenommen, und es gilt
$$V_1=V_2=\frac{15}{8}.$$
Folglich ist
$$F(4)=\frac{15}{8},$$
genau wie im Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe kompakte Schleife. Zuerst wird der erzwungene Endwert \((n+1)/2\) als Wert der nächsten Runde gesetzt. Dann wird für jedes \(t\) von \(n-1\) bis \(1\) rückwärts die Steigung \(s_t=(n+1)/(t+1)\) berechnet, der Quotient aus nächstem Rundewert und dieser Steigung gebildet, mit kleiner Toleranz abgerundet und in das gültige Intervall \([0,t]\) eingegrenzt.
Danach berechnet die Implementierung den Stoppanteil mit der geschlossenen Formel \(1+2+\cdots+k_t=k_t(k_t+1)/2\), addiert den Fortsetzungsanteil \((t-k_t)V_{t+1}\), teilt durch \(t\) und überschreibt den gespeicherten Wert mit dem neuen \(V_t\). Auf diese Weise wird nur ein einziger Fließkomma-Zustand gehalten statt eines gesamten Feldes von Zuständen. Eine der Implementierungen prüft zusätzlich die kleinen Fälle \(n=3\), \(n=4\) und \(n=10\), bevor sie die Ausgabe für \(n=1{,}000{,}000\) erzeugt.
Jede Runde benötigt nur konstant viele arithmetische Operationen, und die Summe der akzeptierten relativen Ränge wird durch eine geschlossene Formel ersetzt. Daher beträgt die Laufzeit
$$O(n),$$
und der Speicherbedarf ist
$$O(1).$$
Für den Zieleingang besteht die gesamte Rechnung also aus genau einem Rückwärtsdurchlauf von \(t=n-1\) bis \(t=1\).
\(n\) tur vardır ve gizli mutlak sıralar \(1,2,\dots,n\) rastgele bir permütasyon halinde gelir; burada \(1\) en iyi sıradır. \(t\). turda, eldeki nesnenin mutlak sırası bilinmez; yalnızca şimdiye kadar görülen ilk \(t\) nesne arasındaki göreli sırası bilinir. Bu göreli sıra görüldükten sonra ya hemen durup bu nesneyi seçersiniz ya da bir sonraki tura devam edersiniz. Son tura kadar beklerseniz elde kalan son nesneyi almak zorundasınız.
Amaç, seçilen nesnenin beklenen mutlak sırasını en aza indirmektir. Bu minimum beklenen değeri \(F(n)\) ile gösterelim. Tüm karar ağaçlarını doğrudan incelemek pratik değildir; çözüm bunun yerine geriye doğru dinamik programlama ve durma maliyetinin göreli sıraya göre doğrusal olmasını kullanır.
\(V_t\), \(t\). turun başında, mevcut nesnenin göreli sırası henüz görülmeden önceki minimum beklenen nihai mutlak sıra olsun. Aradığımız değer böylece \(F(n)=V_1\) olur.
Son turda artık karar yoktur: eldeki nesne mutlaka seçilir. Son görülmeyen nesnenin mutlak sırası \(1\) ile \(n\) arasında eşit olasılıkla herhangi biri olabildiği için beklenen sıra tüm sıraların ortalamasıdır:
$$V_n=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.$$
Bu, geri dönüşlü yinelemenin başlangıç noktasıdır. Daha erken her tur, hemen durmanın değeri ile devam etmenin değeri \(V_{t+1}\) arasında karşılaştırma yapar.
\(t\). turda görülen nesnenin, o ana kadar görülen \(t\) nesne içindeki göreli sırası \(r\) olsun; yani \(1\le r\le t\). Şimdi bu nesnenin tüm \(n\) nesne içindeki beklenen mutlak sırasını bulmamız gerekir.
İlk \(t\) mutlak sırayı artan biçimde
$$1\le a_1<a_2<\cdots<a_t\le n$$
olarak yazalım. O zaman gözlenen nesnenin mutlak sırası \(a_r\) olur. Şimdi \(a_0=0\) ve \(a_{t+1}=n+1\) noktalarını ekleyelim. Böylece oluşan \(t+1\) boşluk
$$a_1-a_0,\ a_2-a_1,\ \dots,\ a_{t+1}-a_t$$
simetriktir ve toplamları \(n+1\)'dir. Bu yüzden her bir boşluğun beklenen değeri
$$\frac{n+1}{t+1}$$
olur. İlk \(r\) boşluğu toplayınca
$$\mathbb{E}[a_r]=\frac{r(n+1)}{t+1}$$
elde edilir. Demek ki \(t\). turda göreli sıra \(r\) görülüp hemen durulursa beklenen nihai mutlak sıra
$$S_t(r)=\frac{n+1}{t+1}\,r$$
olur. Şu kısaltma kullanışlıdır:
$$s_t=\frac{n+1}{t+1},\qquad S_t(r)=s_t r.$$
\(t\). turda \(r\) görüldükten sonra yalnızca iki maliyet vardır: durmanın maliyeti \(s_t r\), devam etmenin maliyeti ise \(V_{t+1}\)'dir.
Durmak tam olarak şu durumda en iyidir:
$$s_t r\le V_{t+1}.$$
\(s_t r\) ifadesi \(r\) ile doğrusal arttığı için kabul edilen göreli sıralar her zaman bir başlangıç aralığı oluşturur: \(r=1,2,\dots,k_t\). Böylece her turun kararı tek bir eşikle belirlenir:
$$k_t=\left\lfloor\frac{V_{t+1}}{s_t}\right\rfloor,$$
ve doğal olarak
$$0\le k_t\le t$$
olmalıdır. \(k_t=0\) ise daima devam edilir, \(k_t=t\) ise daima durulur.
Rastgele bir permütasyonda mevcut nesnenin ilk \(t\) nesne içindeki göreli sırası \(\{1,2,\dots,t\}\) üzerinde uniformdur. Dolayısıyla her \(r\) değeri \(1/t\) olasılıkla gelir.
Eşik kuralı kullanılırsa Bellman güncellemesi
$$V_t=\frac{1}{t}\left(\sum_{r=1}^{k_t} s_t r+\sum_{r=k_t+1}^{t} V_{t+1}\right)$$
olur. İkinci toplam \((t-k_t)V_{t+1}\) eder. İlk toplam için de
$$\sum_{r=1}^{k_t} r=\frac{k_t(k_t+1)}{2}$$
kullanılır. Sonuç olarak
$$V_t=\frac{1}{t}\left(s_t\frac{k_t(k_t+1)}{2}+(t-k_t)V_{t+1}\right)$$
elde edilir. Program tam olarak bu bağıntıyı uygular.
\(V_n=(n+1)/2\) ile başlayıp sırayla
$$V_{n-1},\ V_{n-2},\ \dots,\ V_1$$
hesaplanır. Her güncelleme yalnızca bir sonraki turun değerine ihtiyaç duyduğundan tüm dinamik program sabit bellekle çalışır. \(n=10^6\) olsa bile büyük bir tablo gerekmez.
Uygulamalar ayrıca floor işleminden önce çok küçük pozitif bir tolerans ekleyerek kayan nokta kaynaklı \(1.999999999\) türü sapmaları engeller, sonra da eşiği \([0,t]\) aralığına sıkıştırır.
Kontrol değeri \(F(4)=15/8\), yinelemeden doğrudan elde edilir.
Son turda
$$V_4=\frac{5}{2}.$$
\(t=3\) için \(s_3=5/4\) olduğundan
$$k_3=\left\lfloor\frac{V_4}{s_3}\right\rfloor=\left\lfloor\frac{5/2}{5/4}\right\rfloor=\lfloor 2\rfloor=2.$$
Böylece
$$V_3=\frac{1}{3}\left(\frac{5}{4}(1+2)+1\cdot\frac{5}{2}\right)=\frac{25}{12}.$$
\(t=2\) için \(s_2=5/3\) ve
$$k_2=\left\lfloor\frac{V_3}{s_2}\right\rfloor=\left\lfloor\frac{25/12}{5/3}\right\rfloor=\left\lfloor\frac{5}{4}\right\rfloor=1,$$
dolayısıyla
$$V_2=\frac{1}{2}\left(\frac{5}{3}\cdot 1+1\cdot\frac{25}{12}\right)=\frac{15}{8}.$$
\(t=1\) için \(s_1=5/2\) ve
$$k_1=\left\lfloor\frac{15/8}{5/2}\right\rfloor=\left\lfloor\frac{3}{4}\right\rfloor=0.$$
Yani ilk turda asla hemen kabul edilmez ve
$$V_1=V_2=\frac{15}{8}.$$
Sonuç olarak
$$F(4)=\frac{15}{8},$$
ki bu, uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı kısa döngüyü izler. Önce zorunlu son tur değeri \((n+1)/2\) “bir sonraki turun değeri” olarak alınır. Ardından \(t=n-1\)'den \(1\)'e kadar geri gidilir; eğim \(s_t=(n+1)/(t+1)\) hesaplanır, sonraki tur değeri bu eğime bölünerek eşik bulunur, küçük bir toleransla aşağı yuvarlanır ve sonuç \([0,t]\) aralığına sıkıştırılır.
Daha sonra uygulama, durma katkısını kapalı form \(1+2+\cdots+k_t=k_t(k_t+1)/2\) ile hesaplar, devam katkısı \((t-k_t)V_{t+1}\) ile toplar, \(t\)'ye böler ve depolanan değeri yeni \(V_t\) ile değiştirir. Böylece tüm \(V_t\) dizisini tutmak yerine yalnızca tek bir kayan nokta durumu saklanır. Uygulamalardan biri ayrıca \(n=3\), \(n=4\) ve \(n=10\) için küçük kontrol örnekleri yapıp sonra \(n=1{,}000{,}000\) sonucu basar.
Her tur yalnızca sabit sayıda aritmetik işlem yapar ve kabul edilen göreli sıraların toplamı kapalı formülle hesaplanır. Bu nedenle çalışma süresi
$$O(n),$$
bellek kullanımı ise
$$O(1)$$
olur. Hedef girdi için hesaplama, \(t=n-1\)'den \(t=1\)'e uzanan tek bir geri geçiştir.
Hay \(n\) rondas y los rangos absolutos ocultos \(1,2,\dots,n\) aparecen en orden aleatorio uniforme, donde el rango \(1\) es el mejor. En la ronda \(t\) no conocemos el rango absoluto del elemento actual; solo conocemos su rango relativo entre los primeros \(t\) elementos observados hasta ese momento. Después de ver ese rango relativo, debemos decidir si nos detenemos inmediatamente y aceptamos el elemento actual, o si seguimos a la siguiente ronda. Si llegamos a la ronda final, estamos obligados a aceptar el último elemento restante.
El objetivo es minimizar el rango absoluto esperado del elemento aceptado. Denotemos ese valor mínimo por \(F(n)\). Enumerar todos los árboles de decisión es inviable, así que la solución usa programación dinámica hacia atrás y el hecho de que el valor de detenerse depende solo del rango relativo observado.
Sea \(V_t\) el rango absoluto final esperado mínimo cuando está a punto de comenzar la ronda \(t\), antes de observar el rango relativo del elemento actual. Entonces la respuesta buscada es \(F(n)=V_1\).
En la última ronda ya no queda ninguna decisión: el elemento actual debe aceptarse. Como cualquier rango absoluto entre \(1\) y \(n\) puede ser el último elemento no visto con la misma probabilidad, el valor esperado en la ronda \(n\) es simplemente el promedio de todos los rangos:
$$V_n=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.$$
Éste es el caso base de la recurrencia hacia atrás. En cada ronda anterior se compara el valor de detenerse ahora con el valor \(V_{t+1}\) de posponer la decisión.
Supongamos que en la ronda \(t\) el elemento observado es el \(r\)-ésimo mejor entre los primeros \(t\) elementos vistos, con \(1\le r\le t\). Necesitamos el rango absoluto esperado de ese elemento entre los \(n\) elementos totales.
Si escribimos los \(t\) rangos absolutos revelados en orden creciente como
$$1\le a_1<a_2<\cdots<a_t\le n,$$
entonces el elemento observado tiene rango absoluto \(a_r\). Añadimos ahora \(a_0=0\) y \(a_{t+1}=n+1\). Los \(t+1\) huecos
$$a_1-a_0,\ a_2-a_1,\ \dots,\ a_{t+1}-a_t$$
son intercambiables y su suma es \(n+1\). Por simetría, cada hueco tiene esperanza
$$\frac{n+1}{t+1}.$$
Al sumar los primeros \(r\) huecos esperados obtenemos
$$\mathbb{E}[a_r]=\frac{r(n+1)}{t+1}.$$
Por tanto, si nos detenemos en la ronda \(t\) tras ver rango relativo \(r\), el rango absoluto final esperado es
$$S_t(r)=\frac{n+1}{t+1}\,r.$$
Es útil escribir
$$s_t=\frac{n+1}{t+1},\qquad S_t(r)=s_t r.$$
En la ronda \(t\), una vez conocido \(r\), solo hay dos costes relevantes: parar cuesta \(s_t r\), mientras que continuar cuesta \(V_{t+1}\).
Conviene detenerse exactamente cuando
$$s_t r\le V_{t+1}.$$
Como \(s_t r\) crece linealmente con \(r\), los rangos para los que se acepta forman siempre un prefijo \(r=1,2,\dots,k_t\). Así, cada ronda queda descrita por un único umbral
$$k_t=\left\lfloor\frac{V_{t+1}}{s_t}\right\rfloor,$$
con la restricción natural
$$0\le k_t\le t.$$
Si \(k_t=0\), nunca se para en esa ronda; si \(k_t=t\), siempre se acepta.
En una permutación aleatoria, el rango relativo del elemento actual entre los primeros \(t\) elementos es uniforme en \(\{1,2,\dots,t\}\). Por tanto, cada valor aparece con probabilidad \(1/t\).
Usando la regla umbral, la actualización de Bellman es
$$V_t=\frac{1}{t}\left(\sum_{r=1}^{k_t} s_t r+\sum_{r=k_t+1}^{t} V_{t+1}\right).$$
La segunda suma vale \((t-k_t)V_{t+1}\), y la primera usa la identidad triangular
$$\sum_{r=1}^{k_t} r=\frac{k_t(k_t+1)}{2}.$$
Así obtenemos
$$V_t=\frac{1}{t}\left(s_t\frac{k_t(k_t+1)}{2}+(t-k_t)V_{t+1}\right).$$
Ésta es exactamente la recurrencia implementada por el programa.
Partiendo de \(V_n=(n+1)/2\), calculamos sucesivamente
$$V_{n-1},\ V_{n-2},\ \dots,\ V_1.$$
Cada actualización necesita solo el valor de la ronda siguiente, así que toda la programación dinámica puede ejecutarse con memoria constante. Incluso para \(n=10^6\) no hace falta construir una tabla grande.
Las implementaciones también protegen la operación de redondeo hacia abajo frente a pequeños errores de coma flotante añadiendo una tolerancia positiva diminuta antes de aplicar \(\lfloor\cdot\rfloor\), y después ajustan el umbral al intervalo válido \([0,t]\).
El punto de control \(F(4)=15/8\) se recupera directamente a partir de la recurrencia.
En la ronda final,
$$V_4=\frac{5}{2}.$$
Para \(t=3\), tenemos \(s_3=5/4\), así que
$$k_3=\left\lfloor\frac{V_4}{s_3}\right\rfloor=\left\lfloor\frac{5/2}{5/4}\right\rfloor=\lfloor 2\rfloor=2.$$
Por lo tanto,
$$V_3=\frac{1}{3}\left(\frac{5}{4}(1+2)+1\cdot\frac{5}{2}\right)=\frac{25}{12}.$$
Para \(t=2\), \(s_2=5/3\), luego
$$k_2=\left\lfloor\frac{V_3}{s_2}\right\rfloor=\left\lfloor\frac{25/12}{5/3}\right\rfloor=\left\lfloor\frac{5}{4}\right\rfloor=1,$$
y entonces
$$V_2=\frac{1}{2}\left(\frac{5}{3}\cdot 1+1\cdot\frac{25}{12}\right)=\frac{15}{8}.$$
Para \(t=1\), \(s_1=5/2\) y
$$k_1=\left\lfloor\frac{15/8}{5/2}\right\rfloor=\left\lfloor\frac{3}{4}\right\rfloor=0.$$
Así que la primera ronda nunca se acepta inmediatamente y
$$V_1=V_2=\frac{15}{8}.$$
En consecuencia,
$$F(4)=\frac{15}{8},$$
en acuerdo con el valor de control usado por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo bucle compacto. Empiezan con el valor forzado de la ronda final \((n+1)/2\), interpretado como el valor de la siguiente ronda. Después, para cada \(t\) desde \(n-1\) hasta \(1\), calculan la pendiente \(s_t=(n+1)/(t+1)\), dividen el valor de la ronda siguiente por esa pendiente para obtener el umbral de parada, lo redondean hacia abajo con una pequeña tolerancia y lo ajustan al intervalo \([0,t]\).
Luego la implementación evalúa la contribución de parar con la forma cerrada \(1+2+\cdots+k_t=k_t(k_t+1)/2\), añade la contribución de continuar \((t-k_t)V_{t+1}\), divide entre \(t\) y reemplaza el valor almacenado por el nuevo \(V_t\). De ese modo solo se conserva un único estado en coma flotante en lugar de un arreglo completo con todos los valores \(V_t\). Una de las implementaciones también verifica los casos pequeños \(n=3\), \(n=4\) y \(n=10\) antes de imprimir la respuesta para \(n=1{,}000{,}000\).
Cada ronda realiza solo un número constante de operaciones aritméticas, y la suma triangular se sustituye por una fórmula cerrada. Por tanto, el tiempo total es
$$O(n),$$
y la memoria utilizada es
$$O(1).$$
Para la entrada objetivo, el cálculo completo no es más que una única pasada hacia atrás desde \(t=n-1\) hasta \(t=1\).
共有 \(n\) 轮，隐藏的绝对排名 \(1,2,\dots,n\) 以等概率随机排列的顺序出现，其中 \(1\) 表示最好。到第 \(t\) 轮时，我们并不知道当前对象在全部 \(n\) 个对象中的绝对排名，只知道它在前 \(t\) 个已出现对象中的相对排名。看到这个相对排名之后，必须立刻做出决定：要么现在停止并接受当前对象，要么继续到下一轮。如果一直拖到最后一轮，就只能接受最后剩下的那个对象。
目标是让最终接受对象的绝对排名期望值尽可能小。记这个最优期望为 \(F(n)\)。如果直接枚举所有可能的策略树，规模会迅速爆炸，因此程序采用逆向动态规划，并利用“立即停止的代价只取决于当前观察到的相对排名”这一结构。
设 \(V_t\) 表示在第 \(t\) 轮即将开始、但还没有看到这一轮相对排名之前，未来能够达到的最小期望绝对排名。那么最终所求就是 \(F(n)=V_1\)。
在最后一轮已经没有选择空间，当前对象必须被接受。由于最后那个尚未出现的对象可能是 \(1\) 到 \(n\) 之间任意一个绝对排名，而且每种情况等可能，因此最后一轮的期望值就是这些排名的平均数：
$$V_n=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.$$
这就是整个递推的起点。对于更早的轮次，我们都要把“现在停下来的期望代价”和“继续观察一轮的期望代价 \(V_{t+1}\)”进行比较。
假设在第 \(t\) 轮观察到当前对象在前 \(t\) 个已见对象中排第 \(r\) 名，其中 \(1\le r\le t\)。现在需要求的是：这个对象在全部 \(n\) 个对象中的绝对排名期望是多少。
把这 \(t\) 个已经出现的绝对排名按从小到大写成
$$1\le a_1<a_2<\cdots<a_t\le n,$$
那么当前对象的绝对排名就是其中的第 \(r\) 个，也就是 \(a_r\)。为了求它的期望，可以再补上两个端点 \(a_0=0\) 和 \(a_{t+1}=n+1\)。于是得到 \(t+1\) 个间隔：
$$a_1-a_0,\ a_2-a_1,\ \dots,\ a_{t+1}-a_t.$$
这些间隔在分布上是对称可交换的，而它们的总和恰好等于 \(n+1\)。因此每个间隔的期望都相同，必然为
$$\frac{n+1}{t+1}.$$
把前 \(r\) 个间隔的期望相加，就得到
$$\mathbb{E}[a_r]=\frac{r(n+1)}{t+1}.$$
所以，如果在第 \(t\) 轮看到相对排名 \(r\) 后立刻停止，那么最终得到的绝对排名期望为
$$S_t(r)=\frac{n+1}{t+1}\,r.$$
为了书写方便，记
$$s_t=\frac{n+1}{t+1},\qquad S_t(r)=s_t r.$$
在第 \(t\) 轮，一旦相对排名 \(r\) 已知，真正需要比较的只有两种代价：立即停止的代价是 \(s_t r\)，继续观察的代价是 \(V_{t+1}\)。
因此，当且仅当
$$s_t r\le V_{t+1}$$
时，立即停止才是最优选择。
注意 \(s_t r\) 随 \(r\) 线性增长，所以“应该停止”的那些相对排名必然构成一个前缀区间，即 \(r=1,2,\dots,k_t\)。于是每一轮都可以用一个单独的阈值来描述：
$$k_t=\left\lfloor\frac{V_{t+1}}{s_t}\right\rfloor,$$
并且显然要满足
$$0\le k_t\le t.$$
如果 \(k_t=0\)，说明这一轮无论看到什么相对排名都不应立即接受；如果 \(k_t=t\)，则说明这一轮无论看到什么都可以立刻停止。其余情况下，只有当相对排名不超过 \(k_t\) 时才停止。
在随机排列中，当前对象在前 \(t\) 个对象中的相对排名，在集合 \(\{1,2,\dots,t\}\) 上是均匀分布的，因此每个 \(r\) 的概率都是 \(1/t\)。
利用阈值策略，Bellman 递推可以写成
$$V_t=\frac{1}{t}\left(\sum_{r=1}^{k_t} s_t r+\sum_{r=k_t+1}^{t} V_{t+1}\right).$$
第二部分直接等于 \((t-k_t)V_{t+1}\)。第一部分则使用三角和公式
$$\sum_{r=1}^{k_t} r=\frac{k_t(k_t+1)}{2}.$$
于是可以化成
$$V_t=\frac{1}{t}\left(s_t\frac{k_t(k_t+1)}{2}+(t-k_t)V_{t+1}\right).$$
这正是程序中逐轮更新所使用的核心公式。
有了边界值 \(V_n=(n+1)/2\) 之后，就可以依次计算
$$V_{n-1},\ V_{n-2},\ \dots,\ V_1.$$
每一步只依赖于下一轮的值 \(V_{t+1}\)，因此根本不需要保存完整的状态数组，只要保留“下一轮的当前值”即可。这也是为什么即使 \(n=10^6\)，实现仍然只需要常数级内存。
另外，程序在取下整之前会先加上一个极小的正容差，用来抵消浮点数误差造成的边界抖动，例如理论上应为 \(2\) 却因为舍入变成 \(1.999999999\) 的情况。最后再把阈值裁剪到合法区间 \([0,t]\) 内。
实现中的一个检查点是 \(F(4)=15/8\)。这个值可以直接从递推式推出来。
最后一轮没有选择，所以
$$V_4=\frac{5}{2}.$$
接着看 \(t=3\)。这时
$$s_3=\frac{5}{4},\qquad k_3=\left\lfloor\frac{V_4}{s_3}\right\rfloor=\left\lfloor\frac{5/2}{5/4}\right\rfloor=2.$$
因此
$$V_3=\frac{1}{3}\left(\frac{5}{4}(1+2)+1\cdot\frac{5}{2}\right)=\frac{25}{12}.$$
再看 \(t=2\)。这时
$$s_2=\frac{5}{3},\qquad k_2=\left\lfloor\frac{V_3}{s_2}\right\rfloor=\left\lfloor\frac{25/12}{5/3}\right\rfloor=\left\lfloor\frac{5}{4}\right\rfloor=1.$$
于是
$$V_2=\frac{1}{2}\left(\frac{5}{3}\cdot 1+1\cdot\frac{25}{12}\right)=\frac{15}{8}.$$
最后看 \(t=1\)。有
$$s_1=\frac{5}{2},\qquad k_1=\left\lfloor\frac{15/8}{5/2}\right\rfloor=\left\lfloor\frac{3}{4}\right\rfloor=0.$$
这说明第一轮看到的唯一对象不应该立刻接受，因此
$$V_1=V_2=\frac{15}{8}.$$
最终得到
$$F(4)=\frac{15}{8},$$
与实现中使用的检查值完全一致。
C++、Python 和 Java 实现都使用同一个紧凑的逆向循环。它们先把强制接受的最后一轮期望值 \((n+1)/2\) 作为“下一轮状态值”保存下来。然后从 \(t=n-1\) 一直倒着循环到 \(1\)：先计算比例系数 \(s_t=(n+1)/(t+1)\)，再用“下一轮值除以这个系数”得到阈值位置，对结果加上很小的正容差后向下取整，并把它限制在 \([0,t]\) 范围内。
接下来，实现用闭式公式 \(1+2+\cdots+k_t=k_t(k_t+1)/2\) 计算立即停止部分的总贡献，再加上继续部分 \((t-k_t)V_{t+1}\)，最后除以 \(t\)，得到新的 \(V_t\)，并直接覆盖旧值。这样整个程序始终只维护一个浮点状态，而不需要存储所有轮次的数组。其中一个实现还会先验证 \(n=3\)、\(n=4\) 和 \(n=10\) 这几个小规模检查点，然后才输出 \(n=1{,}000{,}000\) 的结果。
每一轮只做常数次算术运算，三角求和也已经用闭式公式替代。因此总时间复杂度为
$$O(n),$$
空间复杂度为
$$O(1).$$
对于目标输入，整次计算本质上只是从 \(t=n-1\) 到 \(t=1\) 的一次单向逆推。
Есть \(n\) раундов, а скрытые абсолютные ранги \(1,2,\dots,n\) приходят в равновероятно случайном порядке; ранг \(1\) является наилучшим. В раунде \(t\) мы не знаем абсолютный ранг текущего объекта, а видим только его относительный ранг среди первых \(t\) уже появившихся объектов. После наблюдения этого относительного ранга нужно немедленно решить: остановиться и принять текущий объект или продолжить к следующему раунду. Если дойти до последнего раунда, придётся принять последний оставшийся объект.
Цель состоит в том, чтобы минимизировать математическое ожидание абсолютного ранга выбранного объекта. Обозначим этот оптимальный ожидаемый результат через \(F(n)\). Перебирать все деревья решений бессмысленно, поэтому решение опирается на обратную динамику и на то, что цена остановки определяется только увиденным относительным рангом.
Обозначим через \(V_t\) минимальный ожидаемый итоговый абсолютный ранг в момент, когда раунд \(t\) только начинается и относительный ранг текущего объекта ещё не раскрыт. Тогда искомый ответ равен \(F(n)=V_1\).
В последнем раунде выбора уже нет: текущий объект нужно принять обязательно. Поскольку последним невидимым объектом с одинаковой вероятностью может оказаться любой абсолютный ранг от \(1\) до \(n\), ожидаемое значение в раунде \(n\) равно среднему по всем рангам:
$$V_n=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.$$
Это база обратной рекурсии. Во всех более ранних раундах мы сравниваем стоимость немедленной остановки со стоимостью продолжения, равной \(V_{t+1}\).
Пусть в раунде \(t\) текущий объект оказался \(r\)-м по качеству среди первых \(t\) увиденных объектов, где \(1\le r\le t\). Нужно найти ожидаемый абсолютный ранг этого объекта среди всех \(n\) объектов.
Запишем уже появившиеся \(t\) абсолютных рангов в возрастающем порядке:
$$1\le a_1<a_2<\cdots<a_t\le n.$$
Тогда наблюдаемый объект имеет абсолютный ранг \(a_r\). Добавим фиктивные точки \(a_0=0\) и \(a_{t+1}=n+1\). Получаются \(t+1\) промежутков
$$a_1-a_0,\ a_2-a_1,\ \dots,\ a_{t+1}-a_t.$$
Они симметричны по распределению и в сумме дают \(n+1\). Значит, математическое ожидание каждого промежутка равно
$$\frac{n+1}{t+1}.$$
Суммируя первые \(r\) ожидаемых промежутков, получаем
$$\mathbb{E}[a_r]=\frac{r(n+1)}{t+1}.$$
Следовательно, если остановиться в раунде \(t\) после наблюдения относительного ранга \(r\), ожидаемый итоговый абсолютный ранг будет равен
$$S_t(r)=\frac{n+1}{t+1}\,r.$$
Удобно обозначить
$$s_t=\frac{n+1}{t+1},\qquad S_t(r)=s_t r.$$
После того как в раунде \(t\) известен ранг \(r\), остаются только две значимые цены: остановка стоит \(s_t r\), а продолжение стоит \(V_{t+1}\).
Останавливаться выгодно тогда и только тогда, когда
$$s_t r\le V_{t+1}.$$
Так как выражение \(s_t r\) линейно растёт по \(r\), множество принимаемых рангов всегда имеет вид начального отрезка \(r=1,2,\dots,k_t\). Значит, каждый раунд описывается единственным порогом
$$k_t=\left\lfloor\frac{V_{t+1}}{s_t}\right\rfloor,$$
который, разумеется, ограничивается условиями
$$0\le k_t\le t.$$
Если \(k_t=0\), нужно всегда продолжать. Если \(k_t=t\), нужно всегда останавливаться. Во всех промежуточных случаях мы принимаем текущий объект тогда и только тогда, когда его относительный ранг не превосходит \(k_t\).
В случайной перестановке относительный ранг текущего объекта среди первых \(t\) объектов равномерно распределён по множеству \(\{1,2,\dots,t\}\). Поэтому каждый \(r\) возникает с вероятностью \(1/t\).
Используя пороговое правило, получаем рекурсию Беллмана
$$V_t=\frac{1}{t}\left(\sum_{r=1}^{k_t} s_t r+\sum_{r=k_t+1}^{t} V_{t+1}\right).$$
Вторая сумма равна \((t-k_t)V_{t+1}\), а для первой используется формула треугольных чисел
$$\sum_{r=1}^{k_t} r=\frac{k_t(k_t+1)}{2}.$$
Итак,
$$V_t=\frac{1}{t}\left(s_t\frac{k_t(k_t+1)}{2}+(t-k_t)V_{t+1}\right).$$
Это и есть точная формула, которую реализует программа.
Начиная с \(V_n=(n+1)/2\), последовательно вычисляем
$$V_{n-1},\ V_{n-2},\ \dots,\ V_1.$$
Для каждого шага нужен только результат следующего раунда, так что вся динамика работает при постоянном объёме памяти. Даже при \(n=10^6\) не требуется хранить массив всех состояний.
Кроме того, реализации защищают операцию взятия целой части от погрешностей плавающей точки: перед применением \(\lfloor\cdot\rfloor\) добавляется очень маленький положительный допуск, а затем порог принудительно ограничивается интервалом \([0,t]\).
Контрольное значение \(F(4)=15/8\) напрямую получается из рекурсии.
В последнем раунде
$$V_4=\frac{5}{2}.$$
Для \(t=3\) имеем \(s_3=5/4\), поэтому
$$k_3=\left\lfloor\frac{V_4}{s_3}\right\rfloor=\left\lfloor\frac{5/2}{5/4}\right\rfloor=\lfloor 2\rfloor=2.$$
Отсюда
$$V_3=\frac{1}{3}\left(\frac{5}{4}(1+2)+1\cdot\frac{5}{2}\right)=\frac{25}{12}.$$
Для \(t=2\) имеем \(s_2=5/3\), следовательно
$$k_2=\left\lfloor\frac{V_3}{s_2}\right\rfloor=\left\lfloor\frac{25/12}{5/3}\right\rfloor=\left\lfloor\frac{5}{4}\right\rfloor=1,$$
и значит
$$V_2=\frac{1}{2}\left(\frac{5}{3}\cdot 1+1\cdot\frac{25}{12}\right)=\frac{15}{8}.$$
Для \(t=1\) получаем \(s_1=5/2\) и
$$k_1=\left\lfloor\frac{15/8}{5/2}\right\rfloor=\left\lfloor\frac{3}{4}\right\rfloor=0.$$
Значит, в первом раунде останавливаться нельзя, и
$$V_1=V_2=\frac{15}{8}.$$
Следовательно,
$$F(4)=\frac{15}{8},$$
что совпадает с контрольным значением в реализации.
Реализации на C++, Python и Java используют один и тот же компактный обратный цикл. Сначала они инициализируют значение следующего раунда величиной \((n+1)/2\), соответствующей обязательной остановке в конце. Затем для каждого \(t\) от \(n-1\) до \(1\) вычисляется коэффициент \(s_t=(n+1)/(t+1)\), делением следующего значения на этот коэффициент находится порог остановки, результат округляется вниз с маленьким запасом и ограничивается диапазоном \([0,t]\).
После этого реализация вычисляет вклад остановки через замкнутую формулу \(1+2+\cdots+k_t=k_t(k_t+1)/2\), добавляет вклад продолжения \((t-k_t)V_{t+1}\), делит сумму на \(t\) и заменяет сохранённое значение новым \(V_t\). Благодаря этому хранится только одно число с плавающей точкой вместо полного массива всех \(V_t\). Одна из реализаций также проверяет малые случаи \(n=3\), \(n=4\) и \(n=10\), а затем выводит ответ для \(n=1{,}000{,}000\).
На каждом раунде выполняется лишь постоянное число арифметических операций, а сумма первых \(k_t\) рангов заменена закрытой формулой. Поэтому время работы равно
$$O(n),$$
а расход памяти равен
$$O(1).$$
Для целевого значения \(n\) всё вычисление представляет собой один проход назад от \(t=n-1\) до \(t=1\).
لدينا \(n\) جولات، وتظهر الرتب المطلقة الخفية \(1,2,\dots,n\) بترتيب عشوائي منتظم، حيث تمثل الرتبة \(1\) أفضل عنصر. في الجولة \(t\) لا نعرف الرتبة المطلقة للعنصر الحالي، بل نعرف فقط رتبته النسبية بين أول \(t\) عناصر ظهرت حتى تلك اللحظة. بعد رؤية هذه الرتبة النسبية يجب أن نقرر فورًا: هل نتوقف الآن ونقبل هذا العنصر، أم نستمر إلى الجولة التالية؟ وإذا وصلنا إلى الجولة الأخيرة فنحن مجبرون على قبول العنصر الأخير المتبقي.
الهدف هو تصغير القيمة المتوقعة للرتبة المطلقة للعنصر المقبول. ولنرمز إلى هذه القيمة الدنيا بالرمز \(F(n)\). فحص جميع أشجار القرارات مباشرة غير عملي، لذلك يعتمد الحل على البرمجة الديناميكية العكسية وعلى أن كلفة التوقف تتحدد بالكامل من الرتبة النسبية المشاهدة.
لنرمز بـ \(V_t\) إلى أقل رتبة مطلقة متوقعة يمكن الوصول إليها عندما نكون في بداية الجولة \(t\)، قبل أن نرى الرتبة النسبية للعنصر الحالي. إذن الجواب المطلوب هو \(F(n)=V_1\).
في الجولة الأخيرة لا يبقى أي قرار: يجب قبول العنصر الحالي. وبما أن العنصر الأخير غير المرئي يمكن أن يكون ذا أي رتبة مطلقة من \(1\) إلى \(n\) باحتمال متساوٍ، فإن القيمة المتوقعة في الجولة \(n\) هي متوسط هذه الرتب:
$$V_n=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}.$$
هذا هو أساس العلاقة العكسية. وفي كل جولة أسبق نقارن بين قيمة التوقف الفوري وبين قيمة الاستمرار، وهي \(V_{t+1}\).
افترض أنه في الجولة \(t\) كانت رتبة العنصر الحالي هي \(r\) بين أول \(t\) عناصر تمت رؤيتها، حيث \(1\le r\le t\). نريد حساب الرتبة المطلقة المتوقعة لهذا العنصر بين جميع العناصر وعددها \(n\).
لنكتب الرتب المطلقة للعناصر \(t\) التي ظهرت حتى الآن بترتيب تصاعدي:
$$1\le a_1<a_2<\cdots<a_t\le n.$$
عندئذ تكون الرتبة المطلقة للعنصر الحالي هي \(a_r\). نضيف الآن النقطتين \(a_0=0\) و \(a_{t+1}=n+1\). عندها نحصل على \(t+1\) فجوة:
$$a_1-a_0,\ a_2-a_1,\ \dots,\ a_{t+1}-a_t.$$
هذه الفجوات متناظرة في التوزيع ومجموعها يساوي \(n+1\)، ولذلك يكون التوقع نفسه لكل فجوة، وهو
$$\frac{n+1}{t+1}.$$
وبجمع توقعات أول \(r\) فجوات نحصل على
$$\mathbb{E}[a_r]=\frac{r(n+1)}{t+1}.$$
إذن إذا توقفنا في الجولة \(t\) بعد رؤية الرتبة النسبية \(r\)، فإن الرتبة المطلقة النهائية المتوقعة تكون
$$S_t(r)=\frac{n+1}{t+1}\,r.$$
ومن المناسب أن نكتب
$$s_t=\frac{n+1}{t+1},\qquad S_t(r)=s_t r.$$
بعد معرفة \(r\) في الجولة \(t\)، لا يبقى إلا خياران فعليان: كلفة التوقف هي \(s_t r\)، وكلفة الاستمرار هي \(V_{t+1}\).
ويكون التوقف هو القرار الأمثل إذا وفقط إذا
$$s_t r\le V_{t+1}.$$
وبما أن \(s_t r\) يزداد خطيًا مع \(r\)، فإن الرتب التي نقبل عندها التوقف تشكل دائمًا مقطعًا أوليًا من الشكل \(r=1,2,\dots,k_t\). لذلك توصف كل جولة بعتبة واحدة فقط:
$$k_t=\left\lfloor\frac{V_{t+1}}{s_t}\right\rfloor,$$
مع الشرط الطبيعي
$$0\le k_t\le t.$$
إذا كان \(k_t=0\) فنحن لا نتوقف أبدًا في تلك الجولة، وإذا كان \(k_t=t\) فنحن نتوقف دائمًا. وفي الحالات الأخرى نتوقف فقط عندما لا تتجاوز الرتبة النسبية \(k_t\).
في ترتيب عشوائي، تكون الرتبة النسبية للعنصر الحالي بين أول \(t\) عناصر موزعة بانتظام على المجموعة \(\{1,2,\dots,t\}\). لذلك يظهر كل \(r\) باحتمال \(1/t\).
وباستخدام سياسة العتبة نحصل على علاقة بيلمان
$$V_t=\frac{1}{t}\left(\sum_{r=1}^{k_t} s_t r+\sum_{r=k_t+1}^{t} V_{t+1}\right).$$
المجموع الثاني يساوي \((t-k_t)V_{t+1}\)، أما المجموع الأول فيستخدم الصيغة المغلقة
$$\sum_{r=1}^{k_t} r=\frac{k_t(k_t+1)}{2}.$$
ومن ثم نحصل على
$$V_t=\frac{1}{t}\left(s_t\frac{k_t(k_t+1)}{2}+(t-k_t)V_{t+1}\right).$$
وهذه هي الصيغة نفسها التي تطبقها الشيفرة.
نبدأ من \(V_n=(n+1)/2\)، ثم نحسب تباعًا
$$V_{n-1},\ V_{n-2},\ \dots,\ V_1.$$
كل تحديث يحتاج فقط إلى قيمة الجولة التالية، ولذلك تكفي ذاكرة ثابتة ولا حاجة إلى تخزين جدول كامل للحالات، حتى عندما يكون \(n=10^6\).
كما أن التطبيقات تضيف مقدارًا موجبًا صغيرًا جدًا قبل أخذ الجزء الصحيح السفلي، حتى لا تؤدي أخطاء الفاصلة العائمة إلى تحويل قيمة ينبغي أن تكون عددًا صحيحًا تمامًا إلى قيمة أصغر بقليل. وبعد ذلك تُقيد العتبة ضمن المجال القانوني \([0,t]\).
إحدى نقاط التحقق هي \(F(4)=15/8\)، ويمكن اشتقاقها مباشرة من العلاقة السابقة.
في الجولة الأخيرة
$$V_4=\frac{5}{2}.$$
عند \(t=3\) يكون
$$s_3=\frac{5}{4},\qquad k_3=\left\lfloor\frac{V_4}{s_3}\right\rfloor=\left\lfloor\frac{5/2}{5/4}\right\rfloor=2.$$
إذًا
$$V_3=\frac{1}{3}\left(\frac{5}{4}(1+2)+1\cdot\frac{5}{2}\right)=\frac{25}{12}.$$
وعند \(t=2\) يكون
$$s_2=\frac{5}{3},\qquad k_2=\left\lfloor\frac{V_3}{s_2}\right\rfloor=\left\lfloor\frac{25/12}{5/3}\right\rfloor=\left\lfloor\frac{5}{4}\right\rfloor=1.$$
ومن ثم
$$V_2=\frac{1}{2}\left(\frac{5}{3}\cdot 1+1\cdot\frac{25}{12}\right)=\frac{15}{8}.$$
وأخيرًا عند \(t=1\) نجد
$$s_1=\frac{5}{2},\qquad k_1=\left\lfloor\frac{15/8}{5/2}\right\rfloor=\left\lfloor\frac{3}{4}\right\rfloor=0.$$
وهذا يعني أننا لا نقبل العنصر الأول مباشرة، وبالتالي
$$V_1=V_2=\frac{15}{8}.$$
إذن
$$F(4)=\frac{15}{8},$$
وهو تمامًا نفس مقدار التحقق المستخدم في التطبيق.
تتبع تطبيقات C++ وPython وJava الحلقة العكسية نفسها. فهي تبدأ بالقيمة المفروضة في الجولة الأخيرة \((n+1)/2\) وتتعامل معها على أنها قيمة الجولة التالية. بعد ذلك، ولكل \(t\) من \(n-1\) نزولًا إلى \(1\)، تحسب الميل \(s_t=(n+1)/(t+1)\)، ثم تقسم قيمة الجولة التالية على هذا الميل لاستخراج عتبة التوقف، وتأخذ الجزء الصحيح السفلي مع إضافة سماحية صغيرة، ثم تقيد النتيجة بين \(0\) و\(t\).
بعد ذلك تحسب الشيفرة مساهمة التوقف باستخدام الصيغة المغلقة \(1+2+\cdots+k_t=k_t(k_t+1)/2\)، وتضيف مساهمة الاستمرار \((t-k_t)V_{t+1}\)، ثم تقسم المجموع على \(t\) وتستبدل القيمة المخزنة بالقيمة الجديدة \(V_t\). وبذلك تحتفظ بحالة عددية واحدة فقط بدلًا من مصفوفة كاملة من القيم. كما أن أحد التطبيقات يتحقق أيضًا من الحالات الصغيرة \(n=3\) و\(n=4\) و\(n=10\) قبل طباعة الجواب للحالة \(n=1{,}000{,}000\).
كل جولة تحتاج إلى عدد ثابت فقط من العمليات الحسابية، كما أن مجموع الرتب المقبولة يُحسب بصيغة مغلقة. لذلك فإن زمن التنفيذ هو
$$O(n),$$
واستهلاك الذاكرة هو
$$O(1).$$
وبالنسبة إلى قيمة الإدخال المستهدفة، فالحساب كله ليس إلا مرورًا عكسيًا واحدًا من \(t=n-1\) حتى \(t=1\).