SHARE
TWEET

akrasuski1 - writeup

a guest Jul 11th, 2016 16 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Opis rozwiązania by akrasuski1
  2.  
  3. Oznaczmy przez E(M, V, N) oczekiwaną częstość wygrania, jeśli dotychczas wylosowaliśmy
  4. pewną ilość liczb, z których największa to M, obecnie wylosowaliśmy liczbę V, a
  5. pozostała ilość liczb (włącznie z obecną) to N.
  6. Dodatkowo zdefiniujmy R(M, N) jako całkę od 0 do 1 z E(M, V, N)dV - jest to interpretowane
  7. jako oczekiwaną wygraną przy ustalonych M i N, ale nieznanym jeszcze V.
  8.  
  9. Dla N=1, sytuacja jest oczywista - zawsze opłaca się brać wylosowaną liczbę, bo
  10. dalszych i tak nie będzie. Szansa na to, że wylosowaliśmy liczbę większą niż wszystkie
  11. dotąd wylosowane, to 1-M - bo dzieje się tak tylko dla V>M. Zatem R(M, 1)=1-M.
  12.  
  13. Ciekawiej się dzieje dla N>1. Wówczas mamy dwie konkurujące strategie: "brać" i "czekać".
  14. A) Jeśli wybierzemy strategię "brać":
  15. Jeśli V<M, to od razu przegrywamy, bo wybraliśmy liczbę mniejszą od już widzianych.
  16. W przeciwnym razie, prawdopodobieństwo wygranej to V^(N-1), bo każda z pozostałych
  17. liczb musi zawierać się w przedziale <0, V>.
  18. B) Strategia "czekać":
  19. Wówczas sytuacja sprowadza się do mniejszego problemu, i oczekiwana wygrana to:
  20. R( max(V, M), N-1)
  21.  
  22. Oczywiście wybieramy lepszą z obu strategii. Algorytm wybrania strategii w tym momencie to:
  23.  
  24. if( V<M ){ czekać! }
  25. else if( V^(N-1) > R( V, N-1 ) ){ brać! }
  26. else{ czekać! }
  27.  
  28. Policzenie R dla odpowiednich argumentów sprowadza się do zasymulowaniu powyższego algorytmu
  29. wyboru dla N pomniejszonego o 1 dla wielu możliwych wartości V - de facto, scałkowanie numeryczne
  30. E(M, V, N). Naiwnie można to zrobić w czasie wykładniczym (bo potem trzeba całkować dla N-2 itd.),
  31. ale umiejętnie spamiętując wyniki, da się uzyskać rozwiązanie w sensownym czasie.
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top