Runda 20 - omówienie zadań

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

Runda 20 - omówienie zadań

Postautor: mario » 28 gru 2014, 22:11

Dziękuję w imieniu własnym i Marcina za tak liczny udział i gratuluję Mateuszowi Puczelowi wygranej. Zadań 14, rozkład jaki był planowany i jaki się potwierdził to 5 zadań łatwych, 5 średnich i 4 trudne.

Alfabet Morse'a
-/---//--../.-/-../.-/-./.././/-./.././/.--/-.--/--/.-/--./.-//.--/.././-.-/.../--.././--./---//-.-/---/--/./-./-/.-/.-./--../.-/

Trening biegowy
Nietrudne zadanie zegarowe. Problemem w zadaniach, gdzie występują liczby zmiennoprzecinkowe, jest ich przybliżanie. Wbudowane funkcje round, ceil czy floor różnie przybliżają w zależności od przyjętego standardu. Np. niektóre języki przybliżają standardem IEEE 754 http://en.wikipedia.org/wiki/IEEE_floating_point#Rounding_rules, w którym dla funkcji round wartości 1.5 i 2.5 zaokrąglane są do wartości 2. Pisząc program trzeba na to zwrócić uwagę, zawsze można własną funkcję napisać lub użyć pewnego epsilona.

Gra w klasy
Rozwiązaniem jest Tribonacci modulo. Potrzebny jest preprocesing tak, aby na zapytania odpowiadać w czasie stałym.

Najmniejsza wspólna suma
Dla liczb a i b (a<=b) otrzymujemy równanie diofantyczne ax + by = c, gdzie c = b*(b+1)/2-a*(a+1)/2, które należy rozwiązać. W przypadku, gdy c%nwd(a,b)!=0, równanie ax + by = c nie ma rozwiązań. W pozostałych przypadkach można skorzystać z rozszerzonego algorytmu Euklidesa, nie ma jednak takiej potrzeby, wystarczy sprytna pętla z tablicą boolowską szukająca najmniejszej sumy.

Stawy i grobla
Po zapoznaniu się z łamigłówką i specyfikacją zadania wiadomo co trzeba zrobić, trzeba to tylko zrobić :) Najprościej na macierzy sąsiedztwa sprawdzić wszystkie warunki, uruchamiając dla grobli i stawów przeszukiwanie w głąb lub wszerz.

Wycinka drzew
Potrzebny jest tu algorytm najdłuższego podciągu rosnącego z wyszukiwaniem binarnym o złożoności nlogn, który należy zmodyfikować tak, aby znajdował długość najdłuższego podciągu nierosnącego lub niemalejącego, jak kto woli. Należy go uruchomić dwukrotnie, dla podanego ciągu (a) i ciągu w odwrotnej kolejności (b). Rozwiązaniem jest n-max(a,b).

Klucz
Łamigłówka niełatwa, ale z pomocą maszyny liczącej można znaleźć taki klucz wykorzystując rekurencję. Podpowiedź, długość takiego klucza dla n liter równy jest n^n+(n-1), a pierwsze n znaków i ostatnie n-1 znaków to wyłącznie znaki złożone z litery A. Tutaj zadanie w wersji łatwiejszej, klucz możliwy do znalezienia z kartką i ołówkiem: http://www.math.edu.pl/problem,zadanie,367,0.

Laserowy system bezpieczeństwa
Rozwiązanie: http://www.math.edu.pl/rozwiazanie.php?dzial=rozne&id=334
Należało stworzyć pewien preprocesing dla funkcja phi Eulera tak, aby na zapytania odpowiadać w czasie stałym lub wykorzystać zasadę włączeń i wyłączeń dla różnych czynników pierwszych jednej z liczb m+1, n+1 iterując liniowo po długości drugiej (dla liczb mniejszych od 1000 maksymalnie cztery różne czynniki), uzyskując podobną złożoność czasową.

Diament
Zadanie można rozwiązać na kilka sposobów. Mamy układ współrzędnych, w którym na podstawie podanych punktów wyznaczających proste należy wyznaczyć punkty ich przecięcia i odcinki. Punktu diamentu szukamy zamiatając odcinki z każdej z czterech stron lub sprytnie sortując. Można także rozwiązać zadanie za pomocą grafu, ale chyba nikt nie pokusił się o takie rozwiązanie. Gdyby któryś z uczestników chciał podzielić się swoim rozwiązaniem, proszę bardzo.
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 20

Postautor: flashion » 29 gru 2014, 01:59

Zadanie Diament zrobiłem trochę inaczej:
Jeśli mamy jakiś punkt X, to ilość promieni, jakie musimy pokonać z tego punktu do diamentu równa się ilości prostych, które oddzielają nas od niego (tzn. diament jest po jednej stronie prostej, my po drugiej).
Sprawdziłem powyższe wyniki dla wszystkich punktów na obwodzie równo w połowie pomiędzy początkami wiązek (jest ich ok. 4*n) i wziąłem minimum.
flashion
 
Posty: 8
Rejestracja: 24 lis 2013, 22:50

Re: Runda 20

Postautor: flashion » 29 gru 2014, 16:50

@up:
myślę, że można to zbić do O(nlogn) używając drzewka przedziałowego.

Klucz:
Po czym idzie rekurencja? Dokładam literkę i schodzę niżej?
flashion
 
Posty: 8
Rejestracja: 24 lis 2013, 22:50

Re: Runda 20

Postautor: rr_ » 29 gru 2014, 21:50

Wreszcie runda, w której troche lepiej mi poszło :) Gratuluję autorom, bo wydaję mi się, że bardzo dobrze wyszło Wam dobranie poziomu trudności zadań. Chyba widać to też po liczbie uczestników - nawet początkujący mieli co rozwiązywać, więc i wzięli udział :)

Czekam na rozwiązania zadań Cube II i Rejestr by przekonać się co w nich mam nie tak.

Co do zadania Najmniejsza wspólna suma to nie wiem czy dobrze zrozumiałem z "tablicą boolowską", ale można je zrobić w stałej pamięci (przynajmniej ja tak zrobiłem i dostałem AC :) ) - wystarczy przejść pętlą z x od 1 do b sprawdzając czy ax = c (mod b).

A z kolei z Kluczem podpowiem, że można sobie też poczytać o cyklach De Bruijna (właściwie to to czego tutaj szukamy) :) Kiedyś zapamiętałem jako "taką fajną ciekawostkę", a tu niespodziewanie mogłem jej użyć :)

EDIT:
@flashion - zrobiłem Diament prawie tak samo - nie trzeba męczyć się ze sprawdzaniem pomiędzy punktami, bo można sprawdzić w punktach "zaczepnych" i dla danego punktu nie brać po prostu pod uwagę promieni jakie z niego wychodzą :) Z drzewem przedziałowym ciekawy pomysł, właściwie wystarczyłaby tylko funkcja dobrze zamieniająca końce linii na punkty - indeksy w drzewie, no i odpowiednie sprawdzanie, dla której strony zrobić +1.
Ale jeśli tak to chyba można nawet jeszcze lepiej, tzn. trzymać punkty w tablicy jak wcześniej, a nie drzewie i dodawać +1 w pierwszym, dla którego trzeba to +1 zrobić oraz -1 dla pierwszego, którego ta linia juz nie dotyczy. Na końcu tylko przejść po tablicy i sumować. Wydaję się, że problemem może być tu to, że ta tablica jest poniekąd cykliczna i to mogłoby zaburzyć sumowanie, ale to też można rozwiązać. Można bowiem zrobić 2 tablice złożone z 4n punktów, skleić je i dodawać przedziały na zasadzie "początek wśród pierwszych 4n punktów, koniec dalej (jeśli nie miesci się w pierwszej tablicy (czyli trzebaby zawinąć do początku) to robimy -1 już w drugiej 4n części)". Potem znów sumowanie od pierwszej pozycji do pozycji 8n. Wynik dla danego punktu to suma jego wyników z pierwszej i drugiej części. A potem już tylko przejście w poszukiwaniu minimum.
I w ten sposób mamy nawet jeszcze lepsze O(m + n) w pamięci 8*n (2 razy po 4n punktów) + epsilon na zmienne do liczenia :). Tak troche na intuicję to analizowalem tylko, więc się zastanawiam jeszcze czy to na pewno działa, więc jęsli ktoś to w ogóle czyta to poproszę o ocenę czy gdzieś nie ma błedu :)

EDIT2:
Dzięki flashion. Tak miałem, ale błąd z obliczaniem przesunięcia się wplątał (zamiast robić +kierunek*nwd robiłem +nwd, echh...) :)
Ostatnio zmieniony 30 gru 2014, 06:44 przez rr_, łącznie zmieniany 2 razy
rr_
 
Posty: 4
Rejestracja: 31 gru 2013, 04:56

Re: Runda 20

Postautor: flashion » 30 gru 2014, 00:51

@rr_: dzięki za hinta do Klucza.
a Cube II to zwykły BFS:
http://ideone.com/PlnsML
flashion
 
Posty: 8
Rejestracja: 24 lis 2013, 22:50

Re: Runda 20

Postautor: mateusz95 » 08 sty 2015, 00:27

W zadaniu rejestr wystarczy zaszyfrować szyfrogram metodą opisaną w treści zadania.
mateusz95
 
Posty: 5
Rejestracja: 15 wrz 2013, 21:05


Wróć do Zadania

Kto jest online

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

cron