Wątki bez odpowiedzi | Aktywne wątki
Regulamin działu
Zachęcamy do dyskusji na temat zadań z konkursu Zadanie Tygodnia. Można dzielić się uwagami i np. testami do zadań. Pamiętaj, aby nie publikować metody ani samego rozwiązania zadania z bieżącej rundy.
|
Strona 1 z 1
|
[ Posty: 10 ] |
|
Autor |
Wiadomość |
Dołączył(a): 17 lis 2009, o 02:37 Posty: 141
|
Gra na grafie
Czy ktoś mógłby napisać, jak należało zrobić to zadanie?
|
14 lut 2011, o 15:27 |
|
|
Dołączył(a): 27 maja 2009, o 18:20 Posty: 126
|
Re: Gra na grafie
Twoje rozwiązanie wydaje się w pełni poprawne, jest tylko trochę za wolne, pewnie usunięcie rekurencji na rzecz iteracyjnego przeglądania stanów nieźle by to przyspieszyło. Jeśli wcześniej nie znajdzie się chętny, opiszę moje rozwiązanie po wieczór:)
|
14 lut 2011, o 15:41 |
|
|
Dołączył(a): 17 lis 2009, o 02:37 Posty: 141
|
Re: Gra na grafie
Bez rekurencji dostaje 1 pkt więcej. W sumie miałem rozw. bez rekurencji, ale myślałem, że nie działa przeglądanie stanów od końca i zmieniłem na rekurencję. Okazało się, że błąd był w czym innym, ale zapomniałem wyrzucić rekurencji. Mój czas działania to O(2^n*n^2) czy taki sam ma wzorcówka?
|
14 lut 2011, o 15:56 |
|
|
Dołączył(a): 27 maja 2009, o 18:20 Posty: 126
|
Re: Gra na grafie
Owszem, wzorcówka ma ten sam czas działania. Zatem problem musi leżeć w stałej.
|
14 lut 2011, o 16:35 |
|
|
Dołączył(a): 11 paź 2010, o 21:22 Posty: 163
|
Re: Gra na grafie
Hmm.. Ja dostałem 8 pkt. (8. test 2.5s czyli już prawie przekroczyło limit) za O(n^2*2^n) ze stałą dość małą (upraszczając, mam (n/2)^2 a nie n^2) i widzę możliwość przyspieszenia tego o jakieś... 5-15%. Czyli niewiele. Damianie, czekam na opis wzorcówki. Przemku, ile punktów?
A robiłem to jak najzwyklejszy problem komiwojażera, tyle że bez ostatniej krawędzi i z odejmowaniem wyniku od wagi krawędzi (zamiast dodawania).
|
14 lut 2011, o 17:33 |
|
|
Dołączył(a): 17 lis 2009, o 02:37 Posty: 141
|
Re: Gra na grafie
7
|
14 lut 2011, o 20:18 |
|
|
Dołączył(a): 11 paź 2010, o 21:22 Posty: 163
|
Re: Gra na grafie
Czy opis wzorcówki ujrzy światło dzienne?
|
17 lut 2011, o 10:36 |
|
|
Dołączył(a): 27 maja 2009, o 18:20 Posty: 126
|
Re: Gra na grafie
Owszem, dziś się o to postaram:)
|
17 lut 2011, o 11:21 |
|
|
Dołączył(a): 11 paź 2010, o 21:22 Posty: 163
|
Re: Gra na grafie
Hmm.. Odświeżam.
|
21 lut 2011, o 16:44 |
|
|
Dołączył(a): 27 maja 2009, o 18:20 Posty: 126
|
Re: Gra na grafie
Wzorcówka działa z grubsza tak jak Wasze rozwiązania:
Algorytm jest dynamiczny - przestrzeń stanów składa się z informacji, które wierzchołki można jeszcze odwiedzić i w którym wierzchołku obecnie znajduje się gracz, którego ruch rozważamy. Obliczamy "od tyłu" - wykonujemy taki ruch, aby w następnym posunięciu przeciwnik "zarobił" jak najmniej, gdy dołożymy do tego wagę krawędzi, której użyliśmy - wartością dla danego stanu jest różnica pomiędzy wynikami graczy. W takim razie w ostatniej kolejności obliczymy wyniki dla całego wolnego grafu - wtedy wybieramy (względem wierzchołka, z którego wykonany jest pierwszy ruch) najlepsze rozwiązanie.
Być może warto popracować nad poprawieniem swoich implementacji masek bitowych;) Wzorcówka działa na maks-testach 2049ms, a są opcje do lekkich optymalizacji, których celowo nie żyłowałem. Niski limit czasowy zachęca do inwencji;) Mi pomaga w przypadku masek na przykład taka sztuczka - skoro mamy dla ustalonej maski zrobić coś co wymaga wyznaczenia jej zapalonych i zgaszonych bitów (na przykład uznajemy, że wyróżnionym wierzchołkiem, tym w którym "jesteśmy" obecnie, może być tylko wierzchołek spoza maski, za to następnym na trasie wierzchołek z maski) to przeglądamy maskę raz i zapisujemy w pomocniczych tablicach (byle nie pushbackować na wektorach, stała się liczy!) indeksy zapalonych i zgaszonych bitów. Później dwie zagnieżdżone pętle - jedna po zgaszonych (wyróżnione) druga po zapalonych (możliwe kroki) - nigdy nie sprawdzamy wtedy pary wyróżniony-kolejny, która nie daje szans na wykonanie ruchu:)
|
21 lut 2011, o 19:58 |
|
|
|
Strona 1 z 1
|
[ Posty: 10 ] |
|
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
|
|