Jak już się skończyła runda, to muszę zapytać: czy da się to zadanie zrobić na więcej niż 6, ew. 7 punktów? No powiedzcie, bo nie wytrzymię

6/7?

xd

No da się, da się.

Xorujemy wejściowe ciągi z dwoma losowymi innymi maskami żeby móc założyć że ciągi są losowe. Zamieniamy ciągi na system trójkowy (można robić w blokach). Mamy dwa stany gry - remis i przewagę. Jeśli jest remis to obaj gracze wysyłają trit. Jeśli jest przewaga to jeden z graczy wysyła następującą informację: patrzy na następny trit i jeśli jest to 2 to robi zagranie, które pozostawi ich w przewadze (remisuje ruch), jeśli jest to 0 albo 1 to doprowadza stan do remisu. teraz ze stanu remisu są 2/3 szansy na zmianę stanu i podobnie w stanie przewagi. na koniec obaj gracze pozostają z niepewnymi tritami - tymi które mają wartość 0 albo 1 (zauważmy że można je teraz traktować jako bity). Zauważmy że wróciliśmy do analogicznego problemu z mniejszą ilością danych - wystarczy wywołać się rekurencyjnie na z ciągami niepewnych bitów
Rozwiązanie mieści się w limicie 5000 zapytań

Rozwiązanie Huberta można jeszcze ociupinkę przyżyłować. Zamiast robić tak, że stosunek przekazywanej informacji pomiędzy pozostaniem w przewadze a wyjściem z niej to 2:1, możemy sobie wybrać p:1 i wyliczyć sobie najlepsze p. Niestety wtedy jest implementacyjne dłużej, bo nie da się mieć liczby w systemie trójkowym.

Hm, zastanawiam się gdzie się pogubiłem w moich obliczeniach. Wg nich przekazanie w sytuacji przewagi całego bitu informacji i 50% szansy na powrót było maksimum funkcji ze średnią ~1,039 kroku na bit i miało tylko rosnąć do ~1,055 przy 100% powrocie :(

Nie przekazujesz "bitu". Strzelam, że najpopularniejszym "p" o którym wspomina Skyr było 3, bo dość blisko optymalnego podziału jest podział na 4 części. Jeśli jesteśmy w pierwszych trzech, to wracamy do równowagi, a jeśli w czwartej, to utrzymujemy przewagę - wtedy zawsze gdy nie wracamy do równowagi, to zawężamy liczbę możliwości czterokrotnie, więc przekazujemy dwa bity informacji.

W moim odczuciu trzeba było tutaj uważać co tak naprawdę chcemy maksymalizować. W pewnym momencie złapałem się na tym, że maksymalizuję E[ilość bitów przekazanych podczas powrotu do balansu]/E[ilość akcji wykonanych na powrót], co w sumie ma niejasny związek z szansą na sukces całego procesu. Ostatecznie napisałem sobie skrypcik w pythonie który randomizował stałe i liczył E[ilość przekazanych bitów] (co w sumie też nie jest jednoznaczne z szansą sukcesu, ale jest już subiektywnie bliżej), i w ten sposób wpadłem na rozwiązanie o którym wspomniał Mateusz.

Zrobić zadanie to jedno, a ja jestem ciekaw, czy komuś udało się sportować pknrun.py pod Windows?

Ja w stanie przewagi wysyłałem info, czy kolejne dwa bity to "11". W ten sposób z prawd. 3/4 wracałem do remisu, kiedy to mogłem dosłać info jak naprawdę te bity wyglądają (00,01 lub 10). Poza tym w remisie trit.

Dodatkowym challengem, który możemy zaproponować zawodnikom jest: jeśli używamy strategii opisanej powyżej z jakimś p, to jak sensownie oszacować od góry prawdopodobieństwo, że rozwiązanie przekroczy 5000 zapytań. Nie jest to dobre zadanie na potyczki (inaczej bym go tu nie dawał), bo "sensownie oszacować od góry" trudno ściśle zdefiniować; ale musieliśmy (opracowujący) rozwiązać to zadanie, żeby upewnić się, że szansa na to, że poprawne rozwiązanie nie dostanie maxa jest wystarczająco mała.

No ja to p wyznaczałem tak, że całą strategię charakteryzuję 7 liczbami łącznie: p że jak jest remis to pierwszy/drugi zagra papier/kamień/nożyce i siódmą jak mamy przewagę, to jakie jest pstwo, że wracamy do remisu, dostaję łańcuch Markova gdzie mam stany remis i wygrana, wyliczam ten graniczny rozkład i oczekiwaną liczbę bitów znaczy pstwo, że jesteśmy (po nieskończonej liczbie ruchów) w stanie remis razy oczekiwana liczba bitów z niego+pstwo, że jesteśmy w stanie przewaga razy oczekiwana liczba bitów z niego i pp próbujemy dużo konfiguracji dla jakiegoś zbioru tych p sensownie rozrzuconego, potem zbiór punktów mniej rozproszonych dookoła maksimum jakie do tej pory znalazłem itd. wyszło o dziwo, że ze stanu remis istotnie gramy wszystko z p=1/3, a z przewaga zostajemy w stanie przewaga z p≈23.9%, jakby mi się chciało to by wypisał wzorem tą oczekiwaną liczbę bitów, policzył pochodne po wszystkim i pewnie by wyszło, że oczywiście w remisie mamy 1/3, a w wygranej mamy miejsce zerowe jakiegoś syfu, które pewnie i tak się nie wyraża wzorem, ale nie potrzebowałem tego, by napisać działający rozw