English
Ostatnie posty
Nie wiem czy zauważyliście, ale w prawym dolnym rogu na sio pojawił się jakiś czas temu nowy przycisk. Pozwala on na włączenie dark mode'a!! Jest to zasługa skromnego Wojtka Raczuka, który ciężko pracował cały semestr na przedmiocie Tworzenie Aplikacji z Gwiazdką na najlepszej uczelni w Polsce (być może na świecie) - MIM UW.
Zapraszam wszystkich do podziękowania w tym wątku za ten feature i kibicowania użytkownikowi "wraczuk"!
Zapraszam wszystkich do podziękowania w tym wątku za ten feature i kibicowania użytkownikowi "wraczuk"!
Nie potwierdzam bo zbugowałem
Podobno chodziło o to, że normalnie jak Ci się wyszarzają wierzchołki, to wyobrażasz sobie dodanie krawędzi między każdą parą sąsiadów i zunionowanie ich jeśli ta nowa krawędź łączy dwa wierzchołki o tym samym kolorze, to można chcieć to robić bez słów "jeśli ta nowa krawędź łączy dwa wierzchołki o tym samym kolorze" (czego zrobienie dla krawędzi z wejścia po prostu zunionowałoby cały graf (czy raczej spójną składową) od razu).
Nie nazywaj tego blefem Wojtek, blef powinien mieć zalążek sensu.
Na czym polegał blef?
Ten kompletny blef, którym były generowane testy z tej paczki wchodzi na 8 pkt mimo tego, że losowe testy radzą sobie z nim raczej bez problemu :/...
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
Korzystam z faktu, że n <= 10^6, więc O(m * log(n)) = O(m).
A jednak nie, ja je sumuję w O(m*log(n)) - robisz bez loga Marek, czy to skrót myślowy?
kropka w kropkę, jakby wyszedł z fabryki
Skupiając się tylko na jednym graczu:
dp[x] = prawdopodobieństwo, że ten jeden gracz w trakcie rozgrywki stanie na wartości dokładnie x
Takiego dynamika można bezpośrednio obliczyć w O(m * k) lub odrobinę sprytniej w O(m).
above[x] = prawdopodobieństwo, że ten jeden gracz w trakcie rozgrywki stanie na jakiejś wartości z przedziału [x, m-1]
Takiego dynamika można bezpośrednio obliczyć w O(m * k * k) korzystając z dp lub odrobinę sprytniej również w O(m).
W treści jest powiedziane, że jeśli wiele graczy ma najmniejszą liczbę punktów, to rusza się losowy. Natomiast dla ułatwienia przyjmijmy, że rusza się ten o najmniejszym numerze (nie losowy). Nie zmienia to wyniku. Wynikiem będzie E[suma po X_(x,i) gdzie x=0...m-1, i=0...n-1] a zmienna X_(x,i) przyjmuje wartość 1 jeśli gracz nr i w trakcie rozgrywki wykonał ruch stojąc na wartości x, lub 0 w przeciwnym przypadku. Więc trzeba posumować prawdopodobieństwa X_(x,i) = 1.
P(X_(x,i) = 1) = dp[x] * above[x+1]^i * above[x]^(n-1-i)
dp[x] - prawdopodobieństwo, że ten gracz stanie na x.
above[x+1]^i - prawdopodobieństwo, że gracze o numerach mniejszych niż i staną kiedyś na wartości z przedziału [x+1,m-1], pozwalając graczowi i się ruszyć z wartości x.
above[x]^(n-1-i) - prawdopodobieństwo, że gracze o numerach większych niż i staną kiedyś na wartości z przedziału [x,m-1], pozwalając graczowi i się ruszyć z wartości x.
Te prawdopodobieństwa też można posumować w O(m * log(n)).
dp[x] = prawdopodobieństwo, że ten jeden gracz w trakcie rozgrywki stanie na wartości dokładnie x
Takiego dynamika można bezpośrednio obliczyć w O(m * k) lub odrobinę sprytniej w O(m).
above[x] = prawdopodobieństwo, że ten jeden gracz w trakcie rozgrywki stanie na jakiejś wartości z przedziału [x, m-1]
Takiego dynamika można bezpośrednio obliczyć w O(m * k * k) korzystając z dp lub odrobinę sprytniej również w O(m).
W treści jest powiedziane, że jeśli wiele graczy ma najmniejszą liczbę punktów, to rusza się losowy. Natomiast dla ułatwienia przyjmijmy, że rusza się ten o najmniejszym numerze (nie losowy). Nie zmienia to wyniku. Wynikiem będzie E[suma po X_(x,i) gdzie x=0...m-1, i=0...n-1] a zmienna X_(x,i) przyjmuje wartość 1 jeśli gracz nr i w trakcie rozgrywki wykonał ruch stojąc na wartości x, lub 0 w przeciwnym przypadku. Więc trzeba posumować prawdopodobieństwa X_(x,i) = 1.
P(X_(x,i) = 1) = dp[x] * above[x+1]^i * above[x]^(n-1-i)
dp[x] - prawdopodobieństwo, że ten gracz stanie na x.
above[x+1]^i - prawdopodobieństwo, że gracze o numerach mniejszych niż i staną kiedyś na wartości z przedziału [x+1,m-1], pozwalając graczowi i się ruszyć z wartości x.
above[x]^(n-1-i) - prawdopodobieństwo, że gracze o numerach większych niż i staną kiedyś na wartości z przedziału [x,m-1], pozwalając graczowi i się ruszyć z wartości x.
Te prawdopodobieństwa też można posumować w O(m * log(n)).
To co jak robiło się te kostki? Muszę przyznać zadania wczytaj trzy liczby policz coś modulo to moje ulubione
Potwierdzam