Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 40 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4
[Dlaczego Oni Śpiewają] Testy 
Autor Wiadomość
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post 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


Ostatnio edytowano 15 kwi 2011, o 21:50 przez Damian Dyńdo, łącznie edytowano 4 razy



15 kwi 2011, o 20:54
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post Re: [Dlaczego Oni Śpiewają] Testy
I to nie jest n^2?


15 kwi 2011, o 21:37
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post 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.


15 kwi 2011, o 22:02
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 20:19
Posty: 69
Post Re: [Dlaczego Oni Śpiewają] Testy
No ja miałem ostatni 59ms, ale coś musiałem tym przebałaganie pomylić i mam 9 WA :D


15 kwi 2011, o 22:08
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post 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ć..


15 kwi 2011, o 22:10
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post 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 ;)).


15 kwi 2011, o 22:16
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 24 lis 2009, o 15:59
Posty: 47
Post 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.


15 kwi 2011, o 22:27
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 20:19
Posty: 69
Post 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ł?


15 kwi 2011, o 22:30
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 30 lis 2010, o 16:01
Posty: 25
Post 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.


16 kwi 2011, o 19:21
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 11 paź 2010, o 17:26
Posty: 100
Post 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 ;)).


16 kwi 2011, o 19:35
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 40 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4


Kto przegląda forum

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


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