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

Dołączył(a): 20 lis 2009, o 19:33
Posty: 38
Post Re: Wyniki
A pamięciowo sie takie drzewo drzew mieściło?


17 kwi 2011, o 22:39
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post Re: Wyniki
No właśnie ja też napisałem takie drzewo, ale nie mogłem się pamięciowo zmieścić, więc zostawiłem bruta... miałeś złożoność O(nlog^2(n)) ?

EDIT: Ile masz punktów? :p


Ostatnio edytowano 17 kwi 2011, o 22:44 przez Paweł Michalak, łącznie edytowano 1 raz



17 kwi 2011, o 22:43
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 2 sie 2010, o 14:04
Posty: 11
Post Re: Wyniki
Poezja, niestety zbugowana ;(

0.out (test przykładowy) accepted 3 ms 9788
1.out accepted 3 ms 9788
2.out wrong answer 3 ms 9788
3.out wrong answer 56 ms 10584
4.out wrong answer 113 ms 10740
5.out wrong answer 182 ms 11912
6.out wrong answer 29 ms 9788
7.out wrong answer 65 ms 10844
8.out wrong answer 245 ms 10848
9.out wrong answer 312 ms 12464
10.out wrong answer 379 ms 21776

Złożoność n*log^2(n), pamięć n*log(n).


17 kwi 2011, o 22:44
Zobacz profil
Gwiazda 3

Dołączył(a): 20 lis 2009, o 10:05
Posty: 154
Lokalizacja: Bydgoszcz
Post Re: Wyniki
Maciej Kisiel napisał(a):
Zastanawiam się jakie rozwiązanie ma Aleksander Kramarz, że test z forum przechodził mu w 12s. Może się podzieli? :)


Ależ proszę bardzo, nie trzeba było używać mapy. Liczymy hashe, wrzucamy do tablicy i sortujemy. Potem zapytań szukamy binarnie. Oczywiście 10/10, max czas 482 ms. http://kaalex.pastebin.pl/40450
Sumarycznie 88, odpuściłem ostatnią rundę już totalnie.


17 kwi 2011, o 23:19
Zobacz profil YIM
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 24 lis 2009, o 15:59
Posty: 47
Post Re: Wyniki
Widzę, że w poezji wymyśliłem jakieś super rozwiązanie:
0.out (test przykładowy) accepted 0 ms 113356
1.out accepted 0 ms 113356
2.out accepted 0 ms 113356
3.out accepted 39 ms 113356
4.out accepted 56 ms 113548
5.out accepted 109 ms 113544
6.out accepted 12 ms 113356
7.out accepted 45 ms 113356
8.out accepted 92 ms 113676
9.out accepted 156 ms 113644
10.out accepted 262 ms 114064

Złożoność jednego przypadku testowego to n*s^2, gdzie s to długość najdłuższego słowa w słowniku.
Pamięć - n*s*a, gdzie a to liczba znaków w alfabecie.
Oczywiście w zadaniu było s <= 10, a = 26, co dawało tak szybki algorytm.


17 kwi 2011, o 23:47
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 16 lis 2009, o 22:34
Posty: 35
Post Re: Wyniki
Podgatunki:
0.out (test przykładowy) accepted 35 ms 42772
1.out accepted 36 ms 42772
2.out accepted 35 ms 42772
3.out accepted 35 ms 42772
4.out accepted 45 ms 42772
5.out accepted 129 ms 42772
6.out accepted 759 ms 42772
7.out accepted 1699 ms 42772
8.out accepted 1015 ms 42772
9.out accepted 1699 ms 42772
10.out accepted 1019 ms 42772

Szkoda tylko, że 10 minut po czasie :? Cóż, zabrałem się za sklecanie tego ze starych kodów o 17. Sortuje po pierwszej liczbie, drugą skaluję i robię po niej drzewo potęgowe, w którym trzymam drzewce.
Kod: http://ideone.com/UgbTt


18 kwi 2011, o 18:44
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post Re: Wyniki
Ładne rozwiązanie :idea: Będę musiał się przyjrzeć drzewom potęgowym, ich główna przewaga nad drzwami przedziałowymi to zmniejszenie zużycia pamięci?


18 kwi 2011, o 19:25
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 16 lis 2009, o 22:34
Posty: 35
Post Re: Wyniki
Paweł Michalak napisał(a):
Ładne rozwiązanie :idea: Będę musiał się przyjrzeć drzewom potęgowym, ich główna przewaga nad drzwami przedziałowymi to zmniejszenie zużycia pamięci?

Głównie tak, masz tylko n wierzchołków zamiast 2n. No i działa troszkę szybciej. Do tego według mnie implementuje się łatwiej niż drzewa przedziałowe. Chyba, że ktoś to robi na forze (Tom). :P


18 kwi 2011, o 19:59
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: 18 ]  Przejdź na stronę Poprzednia strona  1, 2


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 2 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