akrasuski1 - writeup

Opis rozwiązania by akrasuski1

Oznaczmy przez E(M, V, N) oczekiwaną częstość wygrania, jeśli dotychczas wylosowaliśmy
pewną ilość liczb, z których największa to M, obecnie wylosowaliśmy liczbę V, a
pozostała ilość liczb (włącznie z obecną) to N.
Dodatkowo zdefiniujmy R(M, N) jako całkę od 0 do 1 z E(M, V, N)dV - jest to interpretowane
jako oczekiwaną wygraną przy ustalonych M i N, ale nieznanym jeszcze V.

Dla N=1, sytuacja jest oczywista - zawsze opłaca się brać wylosowaną liczbę, bo
dalszych i tak nie będzie. Szansa na to, że wylosowaliśmy liczbę większą niż wszystkie
dotąd wylosowane, to 1-M - bo dzieje się tak tylko dla V>M. Zatem R(M, 1)=1-M.

Ciekawiej się dzieje dla N>1. Wówczas mamy dwie konkurujące strategie: "brać" i "czekać".
A) Jeśli wybierzemy strategię "brać":
Jeśli V<M, to od razu przegrywamy, bo wybraliśmy liczbę mniejszą od już widzianych.
W przeciwnym razie, prawdopodobieństwo wygranej to V^(N-1), bo każda z pozostałych
liczb musi zawierać się w przedziale <0, V>.
B) Strategia "czekać":
Wówczas sytuacja sprowadza się do mniejszego problemu, i oczekiwana wygrana to:
R( max(V, M), N-1)

Oczywiście wybieramy lepszą z obu strategii. Algorytm wybrania strategii w tym momencie to:

if( V<M ){ czekać! }
else if( V^(N-1) > R( V, N-1 ) ){ brać! }
else{ czekać! }

Policzenie R dla odpowiednich argumentów sprowadza się do zasymulowaniu powyższego algorytmu
wyboru dla N pomniejszonego o 1 dla wielu możliwych wartości V - de facto, scałkowanie numeryczne
E(M, V, N). Naiwnie można to zrobić w czasie wykładniczym (bo potem trzeba całkować dla N-2 itd.),
ale umiejętnie spamiętując wyniki, da się uzyskać rozwiązanie w sensownym czasie.