Wrocławski Portal Informatyczny
http://informatyka.wroc.pl/forum/

[Dlaczego Oni Śpiewają] Testy
http://informatyka.wroc.pl/forum/viewtopic.php?f=83&t=1140
Strona 4 z 4

Autor:  Damian Dyńdo [ 15 kwi 2011, o 20:54 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

Ja jeszcze inaczej to napisałem.

Sprawdzałem posortowane kolejno (od lewej strony) okręgi czy aby są styczne z którymś z poprzednich (który zaś styka się z lewą ścianą (bez)pośrednio). Dla każdego okręgu szukałem (dopóki nie znajdę, lub dopóki prawa ściana poprzedniego jest dalej lub na równi z lewą ścianą aktualnego) wszystkie okręgi. Jeśli było tak - sprawdzałem czy są styczne, jeśli były - sprawdzałem czy tamten był połączony z lewą ścianą. Oczywiście trochę optymalizacji coby nie szło jako k^2. Po zakończeniu spr. (jeśli udało się połączyć bądź z jakimś poprzednim (który łączy się z lewą ścianą) bądź z samą lewą ścianą) spr. czy łączy się aktualny z prawą - jeśli tak to nie można przejść i koniec pętli, jeśli nie to jedzie dalej lub - jeśli to koniec okręgów - można przejść.

Maxymalny czas: x (po 22)

@Paweł Michalak - Może i wygląda na k^2, ale praktycznie k^2 nigdy nie osiągnę w samym algorytmie, nawet blisko niego nie podejdę. Zapomniałem jedynie policzyć sortowania - k*log(k) (dla max testu to 3000 obrotów). Zakładając że każdy jest połączony z poprzednim mam 4k obrotów - czyli do 1mln trochę brakuje ;) Do tego dochodzi jeszcze to, że w zależności od pozycji kolejnych okręgów badam tylko kilka okręgów ostatnich, więc szczerze wątpię aby dla maksymalnych danych zrobiło ten milion obrotów.

Przynajmniej tak mi się wydaje i rzucając kilka "najgorszych" testów dla algorytmu wykazuje, że łącznie z posortowaniem robi mniej obrotów niż k^2 ;) A jak z czasem - zobaczymy, zawsze mogłem coś "zepsuć" :P

Autor:  Paweł Michalak [ 15 kwi 2011, o 21:37 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

I to nie jest n^2?

Autor:  Damian Dyńdo [ 15 kwi 2011, o 22:02 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

I tak jak mówiłem - kolega ma k^2 z FIND i UNION (z tego co zrozumiałem) i ma ponad 2* wolniej :)

U mnie wszystko 0ms, a 3 ostatnie testy 3ms, 3ms i 9ms ;) Pamięć stała 1052 dla każdego testu.

Autor:  Michał Zezyk [ 15 kwi 2011, o 22:08 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

No ja miałem ostatni 59ms, ale coś musiałem tym przebałaganie pomylić i mam 9 WA :D

Autor:  Paweł Michalak [ 15 kwi 2011, o 22:10 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

Jeśli już się chwalimy to ja mam na ostatnim 36ms z rozwiązaniem O(n^2log*n). To przecież tylko kosmetyczna różnica, limity były na tyle małe, że można było sobie pozwolić..

Autor:  Damian Dyńdo [ 15 kwi 2011, o 22:16 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

Źle to odebrałeś, po prostu stwierdziłem, że miałem rację mówiąc, iż nie jest to bliskie k^2. :) Za to z 2giej strony napisane od niechcenia trasy w miarę wolno czasem by przeszły, ale w 9 przypadkach dostałem WA (czekam na testy jak na razie, żeby zweryfikować błąd) :).
Ale co racja to racja - limity były naprawdę duże w porównaniu do testów (lub testy małe ;)).

Autor:  Michał Kownacki [ 15 kwi 2011, o 22:27 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

Wystarczyło stworzyć graf gdzie wierzchołkami są 2 boczne ściany "mapy" i koła, a krawędź łączy 2 koła lub koło i ścianę gdy mają punkty wspólne. Jeśli da się przejść z wierzchołka "ścianowego" lewego do prawego to odp jest nie, w przeciwnym wypadku tak.

Autor:  Michał Zezyk [ 15 kwi 2011, o 22:30 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

Damian Dyńdo napisał(a):
Źle to odebrałeś, po prostu stwierdziłem, że miałem rację mówiąc, iż nie jest to bliskie k^2. :) Za to z 2giej strony napisane od niechcenia trasy w miarę wolno czasem by przeszły, ale w 9 przypadkach dostałem WA (czekam na testy jak na razie, żeby zweryfikować błąd) :).
Ale co racja to racja - limity były naprawdę duże w porównaniu do testów (lub testy małe ;)).


Czyżby Ciebie też siódmy test honorowym punktem uraczył?

Autor:  Marek Bardoński [ 16 kwi 2011, o 19:21 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

U mnie podobnie jak u Michała Z. Zrobiłem super wierzchołki lewą i prawą krawędź, graf gdzie ścieżka to stykające lub przecinające się okręgi. Potem dfs od lewego super wierzchołka.

Mam zero z powodu małego buga, ale teraz już działa 10/10.

Autor:  Damian Dyńdo [ 16 kwi 2011, o 19:35 ]
Tytuł:  Re: [Dlaczego Oni Śpiewają] Testy

@Up w 1szej rundzie też kilkanaście osób miało 3/10 tylko dlatego, że modulo mogło przyjmować wartość ujemną :P (a gdyby policzyć osoby, które nie wiedziały o tym, a po prostu się udało bo inaczej to napisali - ponad połowa pewnie miała by 3/10 ;)).

Strona 4 z 4 Strefa czasowa: UTC + 1 [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/