Runda 23 - omówienie zadań

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

Runda 23 - omówienie zadań

Postautor: kaspro » 05 lip 2015, 20:07

Dziękuję w imieniu swoim i Mariusza za tak duża frekwencję na kolejnej rundzie Algoligi mimo tak „niekorzystnych” warunków pogodowych. Mam nadzieję, że zadania przypadły Wam do gustu i każdy znalazł tu coś dla siebie (mimo problemów z zadaniem Parzyste, nieparzyste II). Jeszcze dziś zostaną wrzucone zadania na polskiego spoja i wkrótce pojawią się do nich omówienia.
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 23

Postautor: zaro » 05 lip 2015, 20:35

Ja również się bardzo cieszę z frekwencji i myślę, że w imieniu wszystkich uczestników mogę podziękować Marcinowi i Mariuszowi za ciekawe zadania w tej rundzie. Ciężko o takich dobrych problem setterów :)
Podziwiam również poziom zawodników, niemalże połowa poradziła sobie z 5 zadaniami, a wszyscy z podium rozwiązali komplet zadań :ugeek:. Naprawdę się ciężko w Wami konkuruje ;)
Ostatnio zmieniony 06 lip 2015, 15:10 przez zaro, łącznie zmieniany 1 raz
Obrazek
zaro
 
Posty: 6
Rejestracja: 30 mar 2014, 22:30

Re: Runda 23 - omówienie zadań

Postautor: macbon » 05 lip 2015, 20:43

Ja bardzo żałuję, że Sebastian Toton nie rozwiązał ostatecznie zadania Fabryka czekolady. 75 prób to pokazuje wolę walki.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 23 - omówienie zadań

Postautor: sebastian05 » 06 lip 2015, 21:22

Pokazuję wolę walki, albo niedostateczne przygotowanie się zawodnika do turnieju. Tak czy siak, zadanie zostało wrzucone na spoja. Więc teraz zaczynam tam walkę z nim :) Pozdrawiam i gratuluję wyniku innym :)
sebastian05
 
Posty: 2
Rejestracja: 06 lip 2015, 21:20

Re: Runda 23 - omówienie zadań

Postautor: mario » 09 lip 2015, 20:51

Dekret
Zadanie elementarne, rozwiązać je można na wiele sposobów, bardzo łatwo korzystając z pomocniczej tablicy, bo maksymalne t wynosi 10^6. Powinienem tu zaproponować 10^9, by tego typu rozwiązania nie przepuścić, jednak nie pomyślałem o tym. Proponuję rozwiązanie z kolejką, za pomocą której rozwiązujemy ten problem tak jak należy, czyli otwieramy i zamykamy bramki w czasie rzeczywistym, a nie jak w przypadku preprocesingu po skończonym weekendzie :/

Poniżej prosty test, który dawał się we znaki niektórym uczestnikom podczas konkursu:
1
1 1 31 31

Oczekiwana złożoność O(n), gdzie n to liczba wyrazów ciągu
//----------------------------------------------------

Podział liczby II
Dla liczb nieparzystych n>1 otrzymujemy proste rozwiązanie n = n/2 + n/2+1
Dla liczb parzystych liczbę n traktujemy jako sumę ciągu arytmetycznego o różnicy 1 i musimy znaleźć pierwszy wyraz a1 o największej wartości, o ile istnieje.
Istnieje wtedy, gdy a1 = (2*n/d - d+1)/2 jest liczbą całkowitą dodatnią dla pewnego dzielnika d, 2 <= d <= sqrt(2*n), wyznaczającego liczbę składników.
Brak szukanego rozkładu mają kolejne potęgi liczby 2.

Oczekiwana złożoność O(sqrt(n))
//----------------------------------------------------

Łazik
Musimy obliczyć liczbę różnych ścieżek z punktu startu do punktu mety diagramu o wymiarze n. Jeśli przez S(x, y) oznaczymy liczbę rożnych ścieżek
w punkcie (x,y) diagramu, to należy zauważyć, że S(x,y) = S(x-1,y) + S(x,y-1). Rozpoczynając z S(1,1)=1, poruszając się po diagramie zgodnie z zasadami, omijając przeszkody, obliczamy wartości kolejnych sum pamiętając o modulacji. Rozwiązaniem jest wartość S(n,n).

Oczekiwana złożoność O(n^2)
//----------------------------------------------------

Klocki Jasia
Porządkując ciąg według reguł podanych w treści zadania jesteśmy w stanie zawsze uporządkować rosnąco wszystkie wyrazy pomijając dwa ostatnie.
Jeśli te dwa ostatnie wyrazy są w złej kolejności, to nie jesteśmy w stanie uporządkować tego ciągu. Do rozstrzygnięcia dylematu Jasia wystarczy, że
policzymy liczbę inwersji w ciągu. Jeśli jest parzysta to uporządkowanie jest możliwe, w przeciwnym razie - nie.

Oczekiwana złożoność O(n*log(n))
//----------------------------------------------------

Długość trasy
Przy pomocy narzędzi geometrycznych w układzie współrzędnych i za pomocą programowania dynamicznego poszukujemy łamanej o najkrótszej długości, której początek to punkt startu, a koniec należy do odcinka ostatniej bramki. Łamana ta musi zawierać się w wielokącie jaki wyznaczają punkt startu i punkty bramek. Z punktu startu wyznaczamy kolejno odcinki widoczności z lewej i prawej strony. Dopóki odcinki te nie przecinają odcinka ostatniej bramki poruszamy się po wierzchołkach wielokąta zapamiętując je i aktualizując minimalną długość. Należy zwrócić uwagę, że w niektórych przypadkach ostatni najkrótszy odcinek będzie prostopadły do odcinka linii mety. Należy więc sprawdzić jeszcze, czy istnieje wierzchołek należący do łamanej, z którego można poprowadzić prostą prostopadłą do odcinka mety. Jeśli istnieje, to aktualizujemy wynik.

Oczekiwana złożoność O(n^2)
//----------------------------------------------------

Na koniec dziękuję Maćkowi Bonieckiemu, za pomoc w organizacji rundy :-)
Gdyby któryś z uczestników chciał podzielić się innym rozwiązaniem niż tu wymienione, proszę pisać śmiało.

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

Re: Runda 23 - omówienie zadań

Postautor: spectral_ » 09 lip 2015, 22:00

Klocki Jasia można zrobić w O(n) za pomocą listy dwukierunkowej i przestawiania ciągów klocków.
spectral_
Organizator AlgoLigi
 
Posty: 18
Rejestracja: 15 lip 2014, 15:27

Re: Runda 23 - omówienie zadań

Postautor: narbej » 12 lip 2015, 09:51

Łazik
Zamiast "pełnej" matrycy n x n, można użyć pojedyńczego wektora n, a lepiej n + 1, przetwarzanego na bieżąco, w miarę wczytywania kolejnego wiersza danych. Kod do wglądu na stronie Mariusza.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 23 - omówienie zadań

Postautor: pm12 » 13 lip 2015, 12:20

Jak należało zrobić zadanie o modułach ?
pm12
 
Posty: 3
Rejestracja: 09 lip 2015, 13:53

Re: Runda 23 - omówienie zadań

Postautor: narbej » 08 sie 2015, 11:14

24058. Wartość bezwzględna
Za chwilę napiszę małą ciekawostkę, na forum SPOJ'a. Jak rozwiązać to zadanie? Wprawdzie nie rozwiązałem go [jeszcze], ale czy nie najlepiej jednak całkowicie samodzielnie spróbowaćje rozwiązać to zadanie? Dlatego tu tylko mała podpowiedź
Zachęcam do "rysowania" tej funkcji dla różnych wartości parametrów [ http://devel.sphere-research.com/phpBB3 ... 99ce64f943 ] i kombinowania i myślenia.
[y icśotraw ćawocilbats]


[EDIT]
Właśnie udało mi się uzyskać AC ;-)
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51


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