Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona
Zadanie tygodnia [Runda 9] Gra w kości - testy 
Autor Wiadomość
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post Zadanie tygodnia [Runda 9] Gra w kości - testy
In:
Kod:

15
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
20 15 15 15 15 20
 

Out:
Kod:

20.57 16.48 13.21 10.59 8.49 6.81 5.46 4.38 3.52 2.82 2.27 1.82 1.46 1.17 0.94
 


Czy ktoś potwierdzi?


6 lut 2011, o 09:51
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Potwierdzam.
Sorry, że tak późno ale dopiero kilka minut temu skończyłem.
Niech ktoś rano (byle by nie przed północą) opisze sposób rozwiązania, bo męczyłem się z tym zadaniem całymi dniami i dalej nie wiem jak działa wzorcówka.


6 lut 2011, o 21:10
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Chętnie jutro opiszę wzorcówkę. Zadanie ma ciekawe rozwiązanie (przydatna technika w wielu problemach algorytmicznych) i myślę, że warto poznać, jeśli się go nie zna.


6 lut 2011, o 23:14
Zobacz profil
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Sprawdzarka jakoś dziwnie działa (dziwne wyniki czasowe). Poza tym odpalanie programu przez 150 rund nie jest wystarczające aby uzyskać dokładną odp. na 6 teście. W zgłoszeniu konkursowym odpalam przez 100 rund, a po odpaleniu przez 200 dostaje poprawne odpowiedzi wszędzie, ale tle na 2 ostatnich testach.


7 lut 2011, o 14:24
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
(przykładowo) W ostatnim teście mam czas 13.00s podczas gdy działa (zapewne) w 0.13s czyli czas wykonania programu jest podawany w złym formacie. "Przykładowo", bo jest tak we wszystkich testach, w zadaniu Szosa także.

Ja przeglądam 5000 (oznaczmy jako k) rund i mam czas 0.05-0.15s dla n=15 - O(k*n^2), mogłem nawet dać z 10000 albo i trochę więcej rund, ale dokładność (d) szacuję przez 0.99^k czyli k=5000 -> d=1.5*10^(-22) co daje jak najbardziej zadowalający wynik.
W każdym razie musimy mieć zupełnie różne algorytmy, więc opiszę mój:

n=nic (2-5), w=wygrana (6), p=przegrana (1)
Tworzymy tablice: pechowiec[n][k] i odpadl[n][k] (dynamicznie, O(n*k))
pechowiec[i][j] to szansa, że i-temu graczowi nie trafi się 6 w ciągu k rzutów (swoich) czyli od 1.0 odejmowałem szanse na takie serie rzutów: w, nw, nnw, nnnw, ..., n...nw (w ostatnim j razy wypadło nic, na końcu w)
odpadl[i][j] to prawd., że i-ty gracz odpadnie w ciągu j rzutów czyli p, np, nnp, ..., n...np

Teraz część właściwa

Dla każdego gracza:

:arrow: Jeśli n[i]=1.0 czyli zawsze rzuca coś z przedziału 2-5, to jedynym sposobem na wygraną i-tego jest wyrzucenie 1 przez każdego z pozostałych. Mamy do tego tablicę odpadl - wystarczy wymnożyć szanse na odpadniecie każdego z pozostałych w ciągu wystarczająco dużej ilości (stała k) rund. Złożoność liniowa po n.

:arrow:
Inaczej, tj. jeśli n[i]!=1.0 stwórzmy sobie zmienną idzmy_dalej_chociaz_nikt_nie_wola albo po prostu idziem na początku równą 1.0. Zmienna ta będzie szansą na to, że ten gracz jeszcze nie rzucił 1 ani 6 (seria nnnnnn). Od 0 do k powtarzamy:
{
x=idziem*w[i] // do tej pory mieliśmy same nic (2-5) i trafiamy 6
Chcemy sprawdzić jaka jest szansa, że żaden z pozostałych jeszcze nie wygrał czyli dla każdego z pozostałych
x*=pechowiec[j][ilosc_rzutow_wykonanych_przez_j-tego]
Wynik[i]+=x

Dzięki temu znamy szansę na wygraną przez wyrzucenie szóstki. Wlicza się tu też sytuacja, gdy pozostali odpadną wcześniej a i-ty będzie miał nnnnnnnnnnw, gdzie w pogrubionym momencie pozostali już odpadli. Na szczęście w jakiś magiczny sposób wyklucza to się z przeglądaniem następnej rundy i szansy na wygranej przez odpadnięcie pozostałych (co za moment) czyli wynik otrzymamy dobry i nie musimy niczego potem odejmować, bo policzyliśmy 2-krotnie.

Teraz wspomniana 2. część - wygrana przez eliminację pozostałych.
Jeśli w ogóle jest szansa, że pozostali odpadli czyli nie jest to zerowa runda lub i-ty gracz jest ostatni (inaczej ktoś jeszcze nie rzucał -> nie mógł odpaść) to robimy coś takiego:
x=idziem*p[i]
/* Czemu *p[i] ? Dlatego, że seria nn zawiera się w nnn czyli liczylibyśmy wszystko kilkukrotnie i potem musielibyśmy się bawić w odejmowanie jakichś tam przypadków.
A nnp w nnnp się nie zawiera. */
Chcemy sprawdzić jaka jest szansa, że pozostali odpadli, więc dla każdego z pozostałych:
x*=odpadl[j][ilosc_rzutow_wykonanych_przez_j-tego]
Wynik[i]+=x

I na koniec idziem*=n[i]
}

Uff... koniec.
Sorry za dublowanie nazwy zmiennej - n[] (prawd. na 2-5) i n (il. graczy), ale jeśli komuś będzie się chciało to czytać, to nie powinien mieć z tym problemów.
Damianie, czekam na opis wzorcówki, bo mój sposób nie za bardzo wygląda na taki, którym dałoby się rozwiązać jakieś inne problemy.


7 lut 2011, o 19:12
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Jeśli chodzi o czas, to mierzony jest obecnie w milisekundach - stąd różnice.
Przemku - można uzyskać poprawne odpowiedzi deterministycznie, moja wzorcówka działa na maksymalnym teście w 0.265s:)
Zauważyłem teraz, że rozwiązanie Kamila działa praktycznie w bezczasie, elegancko!
Opiszę za parędziesiąt minut:)


7 lut 2011, o 20:04
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Trochę dziwna sprawa, ale mój algorytm działa (daje AC) dla 400 przerobionych rund a jeszcze dla 1000 sprawdzarka wyrzuca czasy we wszystkich testach 0.00ms
To oznacza, że wzorcówka jest sporo wolniejsza (265ms a poniżej 1ms).
Oznacza to też, że nie rozumiem działania własnego algorytmu - szacowałem dokładność na 0.99^k czyli przy k=400 d=0.018, a powinno być mniejsze (tak z 10 razy najlepiej) od 0.0001, bo takiego zaokrąglenia wymaga zadanie.


7 lut 2011, o 20:24
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Przeczytałem rozwiązanie Kamila i wydaje mi się, że zrozumiałem - wygląda fajnie i unika wysokiej złożoności.

Moje rozwiązanie wygląda tak (najpierw parę oznaczeń):

1. Maska bitowa zbioru P - liczba, której i-ty bit jest równy 1 wtedy i tylko wtedy, gdy liczba i należy do P. (jeśli ktoś się nie spotkał z tą techniką, polecam http://informatyka.wroc.pl/node/227 :))
2. Niech P[x][y][M] - prawdopodobieństwo, że gdy obecnie rzuca gracz x a w grze pozostali gracze oznaczeni przez maskę M, wygra gracz y.

Innymi słowy x oraz M wskazują nam sytuację, w jakiej znalazła się gra (kto teraz rzuca i kto jeszcze pozostał w grze), a y mówi nam, czyjego zwycięstwa prawdopodobieństwo liczymy. Przy tej interpretacji zależy nam, aby policzyć dla każdego gracza x wartość P[0][x][(1<<n)-1] - rzuca gracz pierwszy i grają wszyscy (maska jest pełna - na wszystkich pozycjach jedynki) a więc sytuacja z początku gry - a wygrywa gracz x. Jeśli policzymy to dla wszystkich iksów, mamy rozwiązanie.

Niech dla każdego gracza x W[x] oznacza szansę, że rzuci szóstkę, a K[x], że rzuci jedynkę (jak wygrana i klęska:D).

Oczywiście liczymy P[x][y][M] tylko dla x-ów i y-ków, których bity są równe 1 w masce M (są w grze, tylko tacy mogą rzucać lub wygrywać).

Teraz zauważmy, że jeśli chcielibyśmy obliczyć ile wynosi P[x][y][M] mamy trzy sytuacje (dwie bardziej i jedną mniej przyjemną):
1. Z prawdopodobieństwem W[x] gracz x wyrzucił szóstkę w swoim rzucie. Jeśli y = x, to należy wliczyć to prawdopodobieństwo do P[x][y][M] (miał wygrać i wygrał). Wtedy P[x][y][M] += W[x]. Jeśli x != y, to niestety y nie zwycięży w tym scenariuszu i nic nie dodajemy.
2. Z prawdopodobieństwem K[x] gracz x wyrzucił jedynkę. To oznacza, że odpadł z gry. Jeśli x = y, to w tym scenariuszu nic nie dodajemy do P[x][y][M]. Jeśli zaś x != y, to jest szansa, że y zwycięży po odpadnięciu x. Ile ona wynosi? Jeśli następnym po x-ie graczem jest v (łatwo wyznaczyć tego gracza z maski bitowej), to szansa, że y wygra w tym scenariuszu jest równa P[v][y][M ^ (1<<x)] - a więc teraz gra v, grają wszyscy z M poza "odpadniętym" graczem x. (Skoro x występował w masce M to M ^ (1<<x) to tyle samo co M - (1<<x)).
Zauważmy, że maska M ^ (1<<x) reprezentuje mniejszą liczbę niż M, zatem jeśli będziemy liczyć P w kolejności rosnących masek, tę wartość będziemy mieli policzoną.

3. Gracz x wyrzucił coś innego (z prawdopodobieństwem 1 - K[x] - W[x]). Zatem nic nie zmieniło się w stanie osobowym, kolej przechodzi do następnego gracza. Ale i on może wyrzucić 2-5 i następny i tak dalej... być może bardzo długo. Jest na to sposób. Oznaczmy:
N - liczba graczy z maski M.

X[i] = P[x(i)][y][M] , gdzie x(i) to i-ty w kolejności gracz z maski M (x0 to nasz x, x1 kolejny po nim i tak dalej)

B[i] = prawdopodobieństwo, że y zwycięży, gdy x(i) wyrzuci 1 lub 6 (coś się zmieni w sytuacji w grze) - to suma ważona znanego nam prawdopodobieństwa P[x(i+1)][y][M ^ (1<<x(i))] (tutaj v z podpunktu 2. to po prostu x(i+1) - następny gracz po x(i), przy tym, że x(N) = x(0)) oraz prawdopodobieństw jakie znamy z podpunktu 1. Jej wyliczenie to prosty wzór, biorący pod uwagę, czy x = y czy też x != y.

A[i] = (1-K[x(i)]-W[x(i)]) - prawdopodobieństwo, że tura przechodzi do kolejnego gracza bez zmiany sytuacji osobowej.

Mamy:
X[0] = B[0] + A[0]X[1]
X[1] = B[1] + A[1]X[2]
...
X[N-2] = B[N-2] + A[N-2]X[N-1]
X[N-1] = B[N-1] + A[N-1]X[0]

Jest to prosty układ cykliczny, z którego łatwo w liniowym względem N czasie wyliczyć ile równe jest X[0]. Potem "od tyłu" możemy obliczyć X[N-1], X[N-2] do X[1]. (Albo równie dobrze od przodu) Ujmujemy tu sytuację "zapętlania się rund".

Nie wiem, czy ładnie to opisałem - proszę o komentarze, chętnie opiszę dokładniej jakieś niejasności.

W ogóle to zadanie powstało zainspirowane z jednej strony jednym z dawnych zadań z Potyczek Algorytmicznych o wynikach rzutów kością, a z drugiej z pięknego zadania Shoot-Out z zawodów Nordic Collegiate Programming Contest (http://ncpc.idi.ntnu.no/ncpc2006/), które można rozwiązać niemal identyczną techniką, choć w mojej opinii jest znacznie trudniejsze. (Z rankingów na ich stronie wynika, że na samych zawodach nikt go nie zrobił, mi zajęło trochę czasu).

Myślę, że ciekawe w tym zadaniu jest radzenie sobie z długimi, zapętlającymi się scenariuszami, gdy "nic się nie zmienia". Wasze rozwiązania radziły sobie poprzez szybkie i skuteczne przybliżanie rozgrywki, moje bazuje na dokładnym obliczeniu (oczywiście co do precyzji double'a:D) ale kosztem dużej przestrzeni stanów. Zaprezentowana technika (liczenie pewnych grup stanów, które są od siebie wzajemnie zależne, "cyklicznie") pojawia się od czasu do czasu w zadaniach, zwłaszcza z prawdopodobieństwem. Ciekawe jest to, że gdyby nasz układ z X[0],X[1],...,X[N-1] nie był taki prosty, czyli każdy zależałby od wszystkich pozostałych z pewnymi współczynnikami, to i tak Eliminacja Gaussa dałaby rozwiązanie (zwłaszcza, że jest ono jednoznaczne) - mogłoby być tak w wersji tego zadania, w której kolejnego gracza wybiera się losowo (z pewnymi ustalonymi, albo zmiennymi zależnie od sytuacji prawdopodobieństwami), a nie po kolei.


7 lut 2011, o 20:54
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Jeszcze w poniedziałek robiłem to zadanie w bardzo podobny sposób, ale otrzymałem za dużą złożoność. No cóż - najważniejsze, że działało dla danych przykładowych.
Już nie pamiętam co zmieniłem (chyba maski wprowadziłem), w każdym razie udało mi się trochę go przyspieszyć. Wszystko ładnie i pięknie, sprawdzam sobie znowu dla przykładów i co? Wyniki bardzo bliskie ale jednak mniejsze. I sumowały się w jakieś 95% zamiast 100%. Jako że nie usunąłem kodu sprzed przyspieszenia sprawdziłem wyniki dla niego raz jeszcze i okazało się, że też dawał te drobne wychylenia, a ja ich nie zauważyłem. Parę godzin przyspieszania niedziałającego algorytmu.
Próbowałem naprawiać, debugować, a nawet pisać od nowa i nic.
W końcu zacząłem robić na inne sposoby i wpadłem na moje rozwiązanie (czyli w skrócie: dla każdego policz szanse na wygraną postaci 1) w,nw,nnw,... 2) p,np,nnp,... ale z wcześniejszym odpadnięciem rywali 3) nnnn... z odpadnięciem rywali, które miało wartość niepomijalnie małą tylko dla n[i]=1.0; działa bo te sytuacje się wykluczają).
Rozwiązanie zadziałało, więc stare usunąłem. I teraz się dowiaduje, że było wzorcowym - i już nigdy się nie dowiem, co tam było źle :|
Jeszcze pytanie - ile linijek ma rozwiązanie wzorcowe? Bo moje "podobne" było strasznie długie i jakby to powiedzieć... brzydkie. Po prostu nawet nie wyglądało na "eleganckie rozwiązanie wzorcowe".


7 lut 2011, o 22:22
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: Zadanie tygodnia [Runda 9] Gra w kości - testy
Rozwiązanie ma (bez definów,includów) jakieś 30 linijek dosyć wąskiego kodu, całkiem krótkie w każdym razie. Maski bitowe mają swoją subtelną krótkość implementacji:D Chętnie podeślę, jeśli ktoś zechce.
Faktycznie złożoność wydaje się być odstraszająca, ale można to w paru miejscach zoptymalizować (ja na przykład w układzie równań liczę odpowiedź osobno dla każdego X[i], a można liczyć raz, ale tak jest bardziej przejrzyście), poza tym większość zależy od liczby bitów maski, a ta jest w średnim przypadku równa n/2, więc stała mocno spada.


7 lut 2011, o 22:55
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL