Kontekst:
Samotny miliarder stworzył teleturniej, aby przyciągnąć najlepszych i najzdolniejszych programistów na świecie. W poniedziałki o północy wybiera jedną osobę z grupy kandydatów na uczestnika tygodnia i zapewnia im grę. Jesteś szczęśliwym uczestnikiem tego tygodnia!
Gra w tym tygodniu:
Host zapewnia dostęp API do stosu 10 000 cyfrowych kopert. Te koperty są losowo sortowane i zawierają w nich wartość dolara od 1 do 10 000 USD (żadne dwie koperty nie zawierają tej samej wartości w dolarach).
Do dyspozycji masz 3 polecenia:
Czytaj (): Przeczytaj cyfrę dolara w kopercie u góry stosu.
Take (): dodaj cyfrę dolara z koperty do portfela teleturnieju i zdejmij kopertę ze stosu.
Pass (): Zdejmij kopertę na górze stosu.
Zasady:
Jeśli użyjesz Pass () na kopercie, pieniądze wewnątrz zostaną utracone na zawsze.
Jeśli użyjesz Take () na kopercie zawierającej $ X, od tego momentu nie możesz nigdy używać Take () na kopercie zawierającej <$ X. Take () na jednej z tych kopert doda 0 USD do Twojego portfela.
Napisz algorytm, który kończy grę z maksymalną kwotą pieniędzy.
Jeśli piszesz rozwiązanie w Pythonie, możesz użyć tego kontrolera do testowania algorytmów, dzięki uprzejmości @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca
Jeśli używasz kontrolera, nie masz dostępu do globałów, możesz użyć tylko 3 podanych komend API i zmiennych o zasięgu lokalnym. (Rozpad bety)
Uwagi: „Maksymalne” w tym przypadku oznacza medianę w portfelu po N> 50 uruchomieniach. Oczekuję, choć chciałbym, aby udowodniono, że się mylę, że wartość mediany dla danego algorytmu zbiegnie się, gdy N wzrośnie do nieskończoności. Spróbuj zamiast tego zmaksymalizować średnią, ale mam wrażenie, że średnia jest bardziej narażona na wyrzucenie przez małe N niż mediana.
Edycja: zmieniono liczbę kopert na 10k dla łatwiejszego przetwarzania i uściślono Take ().
Edycja 2: Warunek nagrody został usunięty w świetle tego postu na stronie meta.
Aktualne najlepsze wyniki:
PhiNotPi - 805 479 USD
Reto Koradi - 803 960 USD
Dennis - 76 272 USD (zmienione)
Alex L. - 714,962 USD (zmieniony)
źródło
Odpowiedzi:
CJam,
87143$ 700,424$ 720327727,580$ 76272$Ten program symuluje całą grę wiele razy i oblicza medianę.
Jak biegać
Oceniłem swoje zgłoszenie, wykonując 100 001 testów:
Podejście
Dla każdej koperty wykonujemy następujące czynności:
Oszacuj kwotę pieniędzy, którą nieuchronnie stracisz, biorąc kopertę.
Jeśli R jest zawartością, a M jest maksymalną, która została podjęta, kwotę można oszacować jako R (R-1) / 2 - M (M + 1) / 2 , co daje pieniądze wszystkim kopertom z zawartością X w przedział (M, R) zawiera.
Gdyby nie przekazano jeszcze kopert, ocena byłaby idealna.
Oblicz kwotę pieniędzy, która nieuchronnie zostanie utracona przez przekazanie koperty.
To po prostu pieniądze, które zawiera koperta.
Sprawdź, czy iloraz obu jest mniejszy niż 110 + 0,016E , gdzie E jest liczbą pozostałych kopert (nie licząc kopert, których nie można już zabrać).
Jeśli tak, weź. W przeciwnym razie podaj.
źródło
Python,
680646 714962USDCoraz większe kwoty w krokach wielkości od 125 do 190 USD. Biegłem z N = 10 000 i otrzymałem medianę 714962 $. Te rozmiary kroków pochodzą z prób i błędów i na pewno nie są optymalne.
Pełny kod, w tym zmodyfikowana wersja kontrolera @ Maltysen, który drukuje wykres słupkowy podczas działania:
Adres BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7
Wow dostarczony OP! Dzięki @LivingInformation!
źródło
max_taken
własnego kodu, ponieważ nie jest on częścią oficjalnego interfejsu API gry. Ale to trywialne.read()
,take()
apass()
metody w kodzie dydaktyczna, ponieważ są to „3 komend do Państwa dyspozycji” na podstawie definicji zawartej w pytaniu.C ++, 803,960 USD
Podany wynik to mediana z 10 001 gier.
źródło
C ++, ~ 815 000 USD
Oparty na rozwiązaniu Reto Koradi, ale przełącza się na bardziej wyrafinowany algorytm, gdy pozostało 100 (prawidłowych) kopert, tasując losowe permutacje i obliczając największa rosnącą ich podsekwencję. Porównuje wyniki pobrania i nie zabrania koperty i zachłannie wybierze najlepszy wybór.
źródło
Java, 806,899 USD
To pochodzi z próby 2501 rund. Nadal pracuję nad optymalizacją. Napisałem dwie klasy, opakowanie i odtwarzacz. Opakowanie tworzy instancję odtwarzacza z liczbą kopert (zawsze 10000 w rzeczywistości), a następnie wywołuje metodę
takeQ
z wartością najwyższej koperty. Następnie gracz powraca,true
jeśli go weźmie,false
jeśli go spasuje.Gracz
Obwoluta
Bardziej szczegółowe wyjaśnienie pojawi się wkrótce po zakończeniu optymalizacji.
Podstawową ideą jest możliwość oszacowania nagrody za grę z danego zestawu kopert. Jeśli bieżący zestaw kopert wynosi {2,4,5,7,8,9}, a górna koperta to 5, wówczas istnieją dwie możliwości:
Jeśli obliczymy oczekiwaną nagrodę w wysokości {7,8,9} i porównamy ją z oczekiwaną nagrodą w wysokości {2,4,7,8,9}, będziemy mogli stwierdzić, czy warto wziąć 5.
Teraz pytanie brzmi, biorąc pod uwagę zestaw kopert, takich jak {2,4,7,8,9}, jaka jest oczekiwana wartość? Odkryłem, że oczekiwana wartość wydaje się proporcjonalna do całkowitej kwoty pieniędzy w zestawie, ale odwrotnie proporcjonalna do pierwiastka kwadratowego z liczby kopert, na które pieniądze są podzielone. Wynika to z „perfekcyjnego” grania w kilka małych gier, w których wszystkie koperty mają prawie identyczną wartość.
Kolejnym problemem jest określenie „ efektywnej liczby kopert”. We wszystkich przypadkach liczba kopert jest dokładnie znana dzięki śledzeniu tego, co widziałeś i zrobiłeś. Coś takiego jak {234,235,236} to zdecydowanie trzy koperty, {231,232,233,234,235} to zdecydowanie 5, ale {1, 224 233 23636} naprawdę powinno się liczyć jako 3, a nie 5 kopert, ponieważ 1 i 2 są prawie bezwartościowe, i nigdy NIE PASUJESZ na 234, więc możesz później odebrać 1 lub 2. Miałem pomysł, aby użyć entropii Shannona do określenia efektywnej liczby kopert.
Swoje obliczenia skierowałem na sytuacje, w których wartości obwiedni rozkładają się równomiernie w pewnym przedziale czasowym, co dzieje się podczas gry. Jeśli wezmę {2,4,7,8,9} i potraktuję to jako rozkład prawdopodobieństwa, jego entropia wynosi 1,50242. Następnie robię,
exp()
aby uzyskać 4,49254 jako efektywną liczbę kopert.Szacunkowa nagroda z {2,4,7,8,9} to
30 * 4.4925^-0.5 * 4/3 = 18.87
Dokładna liczba to
18.1167
.To nie jest dokładne oszacowanie, ale tak naprawdę jestem naprawdę dumny z tego, jak dobrze to pasuje do danych, gdy koperty są równomiernie rozmieszczone w odstępie czasu. Nie jestem pewien poprawnego mnożnika (na razie używam 4/3), ale oto tabela danych z wyłączeniem mnożnika.
Regresja liniowa między oczekiwaną a rzeczywistą daje wartość R ^ 2 wynoszącą 0,999994 .
Moim następnym krokiem do poprawy tej odpowiedzi jest poprawienie oszacowania, kiedy liczba kopert zaczyna się zmniejszać, czyli wtedy, gdy koperty nie są w przybliżeniu równomiernie rozmieszczone i kiedy problem zaczyna się granulować.
Edycja: Jeśli jest to warte bitcoinów, właśnie dostałem adres na(To było tutaj, od kiedy autor konkursu rozdawał nagrody.)1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg
. Dzięki!źródło