Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 2 ] 
Rozwiązania runda 3. 
Autor Wiadomość
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 24 lis 2009, o 15:59
Posty: 47
Post Rozwiązania runda 3.
Chyba te zadania można było zrobić na wiele sposobów z tego co się dotychczas dowiedziałem. Pochwalcie się jak je zrobiliście.
Mi się udało tylko poprawnie w całości napisać Poezję.
Doszedłem najpierw do wniosku, że łatwo jest napisać w złożoności liniowej do sumy długości wyrazów w słowniku co było rządu n*s = 1000000 (s- długość słów), jeśli podane zapytania są tylko o wyrazy w takiej postaci:
qweqwr*
qww*
aaaa*
*
Czyli z gwiazdką na końcu, wystarczy zaimplementować drzewo trie (http://pl.wikipedia.org/wiki/Drzewo_trie), i w każdym wierzchołku mieć liczbę końcówek słów które kończą się w potomkach tego wierzchołka, i dla każdego zapytania podróżuję w dół drzewa po kolejnych literach zapytania aż dojdziemy do gwiazdki, która przypominam jest na końcu dotrzemy do wierzchołka i sczytujemy z niego wartość.
Teraz są jeszcze zapytania postaci takiej, że po gwiazdce w zapytaniu są 1,2,...,9 liter, tak więc gdyby przyjąć, że każde słowo zaczyna się nie na początku, a gdzieś w środku, inaczej mówiąc dla każdego słowa w słowniku uciąć jego odpowiedniej długości końcówkę i doczepić na początku, to robiąc to samo w zapytaniach wynik będzie dla każdego zapytania taki sam, a gwiazdka w niektórych za to wyląduje nam na końcu wyrazu, a na te zapytania łatwo odpowiadamy.
Mam zapytania 10 rodzajów (liczba liter po gwiazdce 0,1,..,9) tak więc można zrobić 10 drzew trie dla każdego rodzaju pytań osobne, co nam zabiera n*s^2 operacji, to na każde zapytanie odpowiadamy w czasie s. Pozostaje kwestia złożoności pamięciowej, bo stworzenie 10 drzew trie z milionem wierzchołków jest nieco drogie jeśli chcemy dla każdego wierzchołka nie trzymać wektora sąsiedztwa, ale 26-elementową tablicę intów, gdzie jeśli dany wierzchołek ma syna literkę ka-tą w alfabecie to w tablicy sąsiedztwa pod indeksem k będzie adres do tegoż syna. To nam daje w przeciwieństwie do wariantu z wektorami o wiele szybsze rozbudowywanie drzewa i odczytu dla zapytań, kosztem pamięci.
Moim pomysłem było więc nie budowanie 10 drzewo trie naraz tylko najpierw zbudowanie drzewa trie zapytań typu 0, odpowiedzieć na zapytania typu 0, potem dla 1, 2 itd.

Na ostatnim teście 262 ms 114064 kB


18 kwi 2011, o 00:16
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 30 lis 2010, o 16:01
Posty: 25
Post Re: Rozwiązania runda 3.
Poezja była prostsza niż się spodziewałem - tzn. testy są mało restrykcyjne.

http://ideone.com/XLcDf

Wystarczyło podzielić wszystkie słowa z poematu na 100 grup, w każdej jest inna liczba liter przed * i za *, np. ac*d to 2 litery przed i jedna po.

Potem 100 razy zamienić słowa języka na postacie typu danej grupy, posortować i za pomocą lower_bound i upper_bound zliczyć ile jest danych słów z odpowiadających sobie grup.

3300ms na największym teście, jednak jest to 10/10


18 kwi 2011, o 08:38
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: 2 ] 


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

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