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.



Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 10 ] 
Gra na grafie 
Autor Wiadomość
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post Gra na grafie
Czy ktoś mógłby napisać, jak należało zrobić to zadanie? :)


14 lut 2011, o 15:27
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post 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
Zobacz profil
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post 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
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post 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
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post 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
Zobacz profil
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post Re: Gra na grafie
7


14 lut 2011, o 20:18
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Gra na grafie
Czy opis wzorcówki ujrzy światło dzienne?


17 lut 2011, o 10:36
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: Gra na grafie
Owszem, dziś się o to postaram:)


17 lut 2011, o 11:21
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: Gra na grafie
Hmm.. Odświeżam.


21 lut 2011, o 16:44
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post 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
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ 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

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