Jak nietrudno wyliczyć, skończyłem tuż przed zamknięciem konkursu. Przez ten cały czas skończyłem i zoptymalizowałem "Zapytania" tak, aby mieściły się w sensownych granicach czasu, napisałem "Osie symetrii" z liniową złożonością; zdążyłem jeszcze dopisać naiwne rozwiązanie dla "Drzew", pospiesznie zmienić sposób alokacji pamięci na dynamiczny (tak na wszelki wypadek - ktoś na forum pisał, że mu się program wysypuje przy próbie użycia 100000-elementowej tablicy, a moje Osie alokują aż 16 MB :D). Tuż po tym szybkie pakowanie i... do szkoły :). Po powrocie przespałem 11 godzin do dzisiejszego ranka, ale mimo to i tak dalej byłem senny. Kude, czemu największa mobilizacja przychodzi zawsze tuż przed samym terminem? :) Z Diversity było tak samo - 75% projektu, w tym caluteńki kod PHP, zrobiliśmy w ostatnich sześciu dniach konkursu.
Natomiast ad. samych zadanek z olimpiady: najlepiej wypadły mi, jak już wspomniałem, "Osie symetrii" i "Zapytania". Aby rozwiązać pierwsze, wystarczyło przeanalizować, w jakich sytuacjach figura może mieć oś symetrii. Wydzieliłem trzy obszary moich zainteresowań:
- Figura jest wielokątem foremnym - wtedy wypisujemy liczbę od razu.
- Figura ma środek symetrii - osi jest przynajmniej dwie i kąt między wszystkimi musi być identyczny.
- Figura ma jakąś "tradycyjną" oś symetrii.
Później selekcjonowałem na tej podstawie tzw. "kandydatów do osi symetrii" - wypada ich relatywnie niewielu, bo akurat osie są na tyle specyficzne, że nie można w tej materii wykombinować zbyt dużo. Na koniec wystarczyło sprawdzić ich wszystkich, przy czym jeśli stwierdzono pasowanie dwóch prostopadłych do siebie osi symetrii, to znaczy, że figura ma środek symetrii i do sprawdzenia kolejnych prostopadłych kandydatów trzeba było przejechać coraz mniej wierzchołków.
Zadanie "Zapytania" - nietrudno było zauważyć, że po podzieleniu "a" i "b" przez "d" z własności największego wspólnego dzielnika, problem sprawdzał się do zliczania liczb względnie pierwszych, tj. dane z jednego zapytania mogły być użyte do policzenia całej reszty. Powstawała tutaj dwuwymiarowa tabelka "a x b", ale jak na warunki zadania, nie dało się jej całej wprowadzić do pamięci. Obliczenie pojedynczej kolumny, np. 5a, polega u mnie na określeniu wszystkich czynników pierwszych "a", a następnie zastosowanie do nich zasady włączeń i wyłączeń. Czynniki pierwsze wyznaczałem w czasie liniowym, gdyż w kodzie programu na sztywno wpisałem wszystkie liczby pierwsze do 50000 :D - fajnie to wygląda, nawiasem mówiąc. Obliczenie "a x b" trwało O(min(a, b)) - "b" razy kolumny "a" lub "a" razy kolumny "b". Jednak dla dużych zestawów taka operacja trwała ładnych parę minut, więc dodałem pewną optymalizację. Kiedy program wykrył, że ma do czynienia ze sporym zestawem, obliczał tzw. kamienie milowe - na wstępie dokonywał wyliczenia takich sum "a x b", gdzie "a" i "b" były wielokrotnościami liczby 500. Wtedy program do uzyskania wyniku brał odległość z najbliższego kamienia milowego i co najwyżej doliczał brakujące kolumny. Dzięki temu dla hardcore losowego testu skrócony został do 30 sekund. Nie jest to wprawdzie rozwiązanie wzorcowe, ale tam jestem zadowolony. I tak bym już dalej nie robił, bo mnie szlag mało przy tym zadanku nie trafił :).
Jeszcze "Drzewa" - te zrobiłem algorytmem naiwnym, gdyż zwyczajnie zabrakło mi czasu na sprawdzenie i uzupełnienie mojego pomysłu. Współczynnik był zawsze najniższy dla danych posortowanych, więc trzeba było tak przestawić drzewa, aby uzyskany ciąg był "bardziej posortowany" od pierwszego. Tu miałem patent, żeby wprowadzić go do drzewa czerwono-czarnego według jakiegośtam kryterium tak, żeby pewna, łatwa do odgadnięcia ścieżka zaprowadziła nas do rozwiązania. Drzewo czerwono-czarne jest odmianą binarnego drzewa wyszukiwań, które posiada zawsze wysokość logarytmiczną.
Tyle mojego, czekam na wyniki. Może się dostanę, może nie, ale w każdym razie dotychczasowa zabawa była niezła i bez względu na rezultat dalej będę bawić się algorytmami :). Rada dla uczestników przyszłych edycji: naprawdę, siądźcie do kodowania ZNACZNIE wcześniej, niż ja to zrobiłem :D.
Napisał dasko w wtorek, 21 listopada 2006 o 20:13
Tera się Adam pochwali... :p
OSI - zadanie raczej najprostsze, wystarczylo szukac palindromow (kąt,odległość od środka ciezkosci) dla osi przechodzacych przez wierzcholki, (bok,dwa kąty) dla osi przechodzących przez krawędzie. Liniowo, np. za pomocą Algorytmu Manachera.
BIU - nie ma się co wysilać, rozwiązanie w internecie - nietrudno znaleźć pdfa. Aczkolwiek bardzo proste. Liniowo.
DRZ - brut - n*n/2, co się będę, jak najlepsi nie mogli wymyśleć... :p
ATR - pomysł z wzorcówki, złożoność wzorcowa, zle zaimplementowane. Mianowinie O(k*(m log n)+k^2*2^k). Zadanie typowo Topcoderowe, klasyczna rekurencja ze spamietywaniem. Niestety bylem tak pewien szybkosci rozwiazania, ze nie sprawdzialem dla najgorszych testow - za wolno. Wszystko przez to, ze sam mechanizm rekurencji jest wolny. Pięć minut roboty więcej i mielbyśmy dynamika wstępującego, bez rekurencji, na tablicach. :) Poleci pewnie z połowa punktów... :/ Jednak satysfakcja, ze pomysl rozwiazania wzorcowy. ;)
ZAP - mniej wiecej O(n*(sqrt(max(a,b))). Troche kombinatoryki, zasada włączania-wyłączania. Pomysł polega na tym, zeby zobaczyć, jak sie zmienia wartosc podloga(x/a)*podloga(y/a), w miare wzrostu dzielnika a. Około 4,5s dla maksymalnych danych - na moim słabym kompie. ;)
Mam nadzieję, że przejdę... :) Good luck Zyx. :)