Runda 17 - omówienie zadań

Tutaj możesz uzyskać pomoc w rozwiązywaniu zadań dostępnych w ramach AlgoLigi

Runda 17 - omówienie zadań

Postautor: mario » 13 lip 2014, 20:20

Dziękujemy wszystkim za udział

Omówienie poszczególnych zadań pojawi się w tym wątku, ale dopiero jak nam się to uda opracować :)
Myślę, że w ciągu kilku dni zostaną omówione wszystkie zadania.

--
Mariusz Śliwiński
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 17 - omówienie zadań

Postautor: radarek » 13 lip 2014, 20:42

Niestety nie wyrobiłem się z ostatnim zadaniem. Myślałem, że czas jest do 21:00 ale o 20:30 próbując wysłać rozwiązanie zadanie przekonałem się, że byłem w błędzie :P. Z tego co kojarzę, to zadanie są dodawane do polskiej wersji SPOJa. Czy wszystkie zadania zostaną tam dodane? Chciałbym się jednak zmierzyć z tym zadaniem :P.

ps. dzięki za zadania. Dawano się tak dobrze nie bawiłem :).
radarek
 
Posty: 4
Rejestracja: 13 lip 2014, 20:37

Re: Runda 17 - omówienie zadań

Postautor: mario » 13 lip 2014, 20:51

Tak, zadania będą dodane jeszcze dzisiaj, chyba :)
Zadanie "spadające słówka" rzeczywiście nie jest takie łatwe. Moje rozwiązanie bazuje na rekurencji z powrotami, z dopasowaniem słów ze słownika logarytmicznie.
Gratuluję Maćkowi i Mateuszowi rozwiązanie tego zadania i czekam na rozwiązania pozostałych :)

Ponadto jest deklaracja Piotrka chęci omówienia części zadań, gdy ktoś chciał jeszcze podzielić się jakimś swoim rozwiązaniem dowolnego z zadań, nic nie stoi na przeszkodzie, zwłaszcza, że niektóre zadania rozwiązano na wiele sposobów.

--
Pozdrawiam
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 17 - omówienie zadań

Postautor: radarek » 13 lip 2014, 20:58

Moje rozwiązanie opiera się na permutowaniu kolejnych kolumn (rekurencyjnie). Nie schodzę jednak głębiej jeśli wygenerowany do tej pory prefix nie znajduje się w słowniku. Ta operacja zajmuje O(1) gdyż do każdego poziomu przekazywany jest wskaźnik do węzła w drzewie prefiksowym. Prefix oczywiście jest resetowany przy napotkaniu spacji. Generalnie wydaje się działać, ale nie miałem okazji puszczenia na wszystkich testach.

Update: po małych poprawkach moje rozwiązanie przeszło testy na SPOJu.
radarek
 
Posty: 4
Rejestracja: 13 lip 2014, 20:37

Re: Runda 17 - omówienie zadań

Postautor: mario » 15 lip 2014, 14:21

Ogród Jasia II

Niech będą punktami na płaszczyźnie. Koło nazwiemy minimalne, jeśli zawiera wszystkie punkty oraz nie istnieje koło zawierające wszystkie punkty o promieniu mniejszym niż .

Niech będzie minimalnym kołem. Wówczas co najmniej dwa punkty należą do okręgu .

Niech będzie minimalnym kołem takim, że co najmniej trzy punkty ze zbioru leżą na jego brzegu.
Oznaczmy te punkty jako . Wówczas istnieją takie trzy punkty , że trójkąt nie jest rozwartokątny.

Na podstawie powyższych lematów mamy, że minimalnym kołem zawierającym dwa dane punkty i jest koło, którego średnicą jest oraz, jeśli trójkąt nie jest rozwartokątny, wówczas okrąg opisany na tym trójkącie jest minimalnym kołem zawierającym punkty . Zatem koło o największym promieniu spośród kół, których średnicą jest oraz kół opisanych na nierozwartokątnych trójkątach jest minimalnym kołem zawierającym wszystkie punkty .

Oczekiwanym i wystarczającym algorytmem dla tego zadania jest algorytm oparty o powyższe spostrzeżenia o złożoności asymptotycznej , który sprawdzi wszystkie pary i trójki punktów w poszukiwaniu największego promienia.

//--------------------------------------------------------------------------------------------------

Spadające słówka

Rozwiązanie rekurencyjne (rekurencja z powrotami)
Poruszamy się od lewej do prawej strony w wierszu i sprawdzamy, czy słowo kandydat istnieje w słowniku. Jeśli istnieje i można dopasować znak spacji po danym słowie (za wyjątkiem ostatniego znaku w wierszu), to kontynuujemy poszukiwania kolejnych słów. Jeśli powstały ciąg znaków nie można dopasować do słowa w słowniku, to wracamy zamieniając litery w kolumnach tak długo, aż uda nam się dopasować dowolne słowo. Po dopasowaniu wszystkich słów w trzech wierszach, sprawdzamy, czy rozwiązanie jest leksykograficznie najmniejsze, jeśli tak to nadpisujemy je. Rekurencja musi wykonać się od początku do końca, ponieważ należy sprawdzić wszystkie kombinacje dopasowań. Konieczne jest także, aby przy sprawdzaniu, czy dane słowo istnieje w słowniku robić to w czasie logarytmicznym.
Można słownik wrzucić do mapy, seta lub po prostu szukać słów binarnie.

Lepsze i szybsze rozwiązanie przedstawił powyżej Radosław Bułat, ale jest ono trudniejsze w implementacji :)

//--------------------------------------------------------------------------------------------------
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 17 - omówienie zadań

Postautor: spectral_ » 15 lip 2014, 15:29

Czy rozwiązanie zadania Jasio włamywacz po raz kolejny na czas 0.00 (http://www.spoj.com/ALGOLIGA/ranks/AL_17_04/) to heurystyka?
spectral_
Organizator AlgoLigi
 
Posty: 18
Rejestracja: 15 lip 2014, 15:27

Re: Runda 17 - omówienie zadań

Postautor: mario » 15 lip 2014, 16:49

W zadaniu Jasiu włamywacz autor zastosował metodę dziel i rządź w posortowanym ciągu.
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 17 - omówienie zadań

Postautor: kaspro » 16 lip 2014, 00:02

Bazy danych
To zadanie można rozwiązać tworząc tak zwane zbiory z historią. Dla drzewa BST opisałem to w tym miejscu: http://algorytm.edu.pl/bst-z-historia.html.

Wskaźnik szczęśliwości
Do badania zróżnicowania danych możemy posłużyć się wariancją lub odchyleniem standardowym. W tym zadaniu należy zwrócić uwagę na dwie rzeczy:
przy porównywaniu danych, które są liczbami rzeczywistymi musimy użyć epsilona oraz pamiętajmy, że jeśli jest kilka firm, które mają to samo odchylenie, to musimy je posortować (wiele zgłoszeń nie brało tego pod uwagę). Jeśli treść zadania jest nieścisła, mogę ją nieco zmodyfikować, żeby bardziej nakierować rozwiązującego.

Systemy liczbowe
Dla każdej trójki ustalamy kolejne podstawy (pamiętajmy, że nie może być ona mniejsza niż maksymalna wartość cyfry zwiększona o 1 (jest jeden wyjątek)), następnie zamieniamy te liczby na system dziesiętny i sprawdzamy równość.

HANOI
jutro
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 17 - omówienie zadań

Postautor: radarek » 16 lip 2014, 01:40

kaspro pisze:Bazy danych
To zadanie można rozwiązać tworząc tak zwane zbiory z historią. Dla drzewa BST opisałem to w tym miejscu: http://algorytm.edu.pl/bst-z-historia.html.


Ciekawe podejście jednak w tym wypadku można to zrobić o wiele prościej. Tworzymy BST z operacjami insert, delete i search. Wstawiamy do niego początkowe N elementów. Dodatkowo tworzymy sobie na boku osobną strukturę (np. tablica + obecna pozycja) na przechowywanie historii nowych "ruchów" (taki mechanizm undo-redo). I teraz gdy wstawiamy nowy element do drzewa to dodatkowo pamiętamy go w historii. Gdy dostajemy polecenie cofnięcia to patrzymy w historii na ostatni element i usuwamy go z drzewa (możemy to zrobić jeśli nie cofnęliśmy się już w historii do samego początku). Należy zauważyć że z drzewa będą usuwane zawsze liście, więc początkowa struktura z N elementami nigdy się nie zmieni.

Wstążki
Piszemy sobie funkcję, która dla zadanej wartości L sprawdzi czy można uzyskać co najmniej K odcinków o długości L z posiadanych wstążek. Sprawdzenie polega na zsumowaniu wartości Ri/L (dzielenie całkowite), gdzie Ri - długość i-tej wstążki. Jeśli otrzymana wartość jest większa bądź równa K to odpowiedź jest pozytywna.

Mają taką funkcję wystarczy już binarnie poszukać maksymalnej wartości L z której można uzyskać co najmniej K odcinków. Przedział który musimy sprawdzić pozostawiam do samodzielnego znalezienia.

Złożoność tego algorytmu to O(n log n). Czy ktoś wymyślił rozwiązanie liniowe?
radarek
 
Posty: 4
Rejestracja: 13 lip 2014, 20:37

Re: Runda 17 - omówienie zadań

Postautor: kaspro » 16 lip 2014, 09:22

Bazy danych
Oczywiście podałem przykładowe rozwiązanie, to które urzekło mnie najbardziej :) i które jest bardzo proste w implementacji. Wspomnę tylko, że przy rozwiązywaniu tego zadania należy przyjrzeć się dokładnie danym wejściowym. Kilka zgłoszeń nie maiło AC z tego powodu.
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Następna

Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 2 gości

cron