Runda 14 - omówienie zadań

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

Runda 14 - omówienie zadań

Postautor: Ostry » 16 lut 2014, 23:45

Mam nadzieję, że zabawa z zadaniami była przednia ;) Oto krótkie omówienie moich zadań z 14 rundy Algoligi:

Literki (http://pl.spoj.com/ALGOLIGA/problems/AL_14_01)

Najprostsze zadania nie wymagające specjalnego komentarza. Należało wykorzystać technikę zliczania wystąpień literek w tablicy. Koszt rozwiązania liniowy.


Potęgi (http://pl.spoj.com/ALGOLIGA/problems/AL_14_03/)

W zadaniu należało wykorzystać fakt, że niezerowe potęgi dwójki, które dają resztę jeden modulo p, muszą być dzielnikami liczby p-1. Po wyznaczeniu takich dzielników należało użyć algorytmu szybkiego potęgowania modulo, by znaleźć najmniejszą z potęg dwójki przystających do jednego w modulo p.


Spływ kajakowy (http://pl.spoj.com/ALGOLIGA/problems/AL_14_05/)

Z racji tego, że każda odnoga rzeki prowadziła tylko w dół, cały układ tworzył graf skierowany bez cykli. Liczba ścieżek rozpoczynających się w wierzchołku i (nazwijmy ją S(i)) to liczba krawędzi wychodzących z wierzchołka i plus liczba ścieżek rozpoczynających się we wszystkich następnikach wierzchołka i. Oczywiście jeżeli z wierzchołka i nie wychodzi żadna krawędź, to S(i) wynosi zero. Globalnym rozwiązaniem jest suma S(1)+S(2)+...+S(n). Należało tu również pamiętać o redukcji modulo. Trzeba było skorzystać z tej zależności rekurencyjnej, ale jednocześnie spamiętywać już obliczone wyniki w tablicy, co pozwala uniknąć eksplozji obliczeń (i złożoności wykładniczej). W takim przypadku złożoność czasowa to O(n+m).


Najjaśniejsza gwiazda (http://pl.spoj.com/ALGOLIGA/problems/AL_14_07/)

W zadaniu należało użyć dwuwymiarowego drzewa przedziałowego. Wystarczała pamięciożerna wersja statyczna takiego drzewa. Jeden wymiar (deklinację) można zamienić na liczbę całkowitą z zakresu od 1 do 10799, natomiast drugi wymiar (rektascencję) na liczbę całkowitą z zakresu od 0 do 1439. W drzewie przedziałowym wystarczało porównywać same jasności względne (które również dało się zamieniać na liczbę całkowitą), a dopiero później szukać nazwy gwiazdy wykorzystując fakt, że jest co najwyżej 150 gwiazd o danej jasności. Również drzewo przedziałowe z porównywaniem po dwóch kryteriach (jasność i nazwa) powinno być akceptowane pod względem czasu wykonania. Złożoność takiego rozwiązania to O((n+m)*log(A)*log(B)), gdzie A i B to zakresy deklinacji i rektascencji.


Wybitność szczytu (http://pl.spoj.com/ALGOLIGA/problems/AL_14_09/)

Do problemu istnieje parę podejść. W rozwiązaniu wzorcowym każde zapytanie w tym zadaniu można interpretować jako zmodyfikowany problem najkrótszych ścieżek z jednego źródła (czyli z punktu, którego wybitność mamy policzyć) do wszystkich innych punktów. Zamiast używać pojęcia "najkrótszej" należy jednak użyć terminu najwyższej ścieżki. Przez wysokość ścieżki z punktu x do punktu y rozumiemy wysokość najniżej położonego punktu na tej ścieżce. Należało użyć algorytmu Dijkstry ze zmienioną definicją odległości:

1) Wysokość najwyższej ścieżki z wierzchołka startowego do samego siebie jest równa jego wysokości nad poziomem morza:
d(xS, yS) = h(xS, yS)

2) Jeżeli w algorytmie przetwarzamy punkt (x1, y1) i okazuje się, że jednym z jego sąsiadów jest (x2, y2) to przeprowadzamy następujące przypisanie (ale tylko wtedy gdy d(x2, y2) nie jest jeszcze ustawione):
d(x2, y2) -> min(h(x2, y2), d(x1, y1))
a następnie wierzchołek (x2, y2) wrzucamy do naszej kolejki priorytetowej

Jak widać, w tym problemie jako taka relaksacja nie jest konieczna, gdyż raz przypisana wartość d już się nie zmienia (analizujemy coraz niższe ścieżki dochodzące do danego wierzchołka). Kluczowy jest fakt, że wysokości są niewielkimi liczbami całkowitymi. W związku z tym standardową implementację kolejki priorytetowej (kopiec lub drzewo) można zastąpić tablicą list (albo wektorów), które indeksujemy wysokościami ścieżek i oczywiście umieszczamy w niej wierzchołki. Przechodzimy taką tablicę od największych wysokości do najmniejszych i w momencie wykrycia w niej punktu wyżej położonego (nazwijmy go z) niż punkt startowy przerywamy algorytm. Wynikiem (a więc wybitnością punktu startowego s) jest różnica między jego wysokością, a wysokością najwyższej ścieżki z s do z. Dzięki takiemu podejściu algorytm jest liniowy od liczby punktów na mapie. Koszt całkowity wszystkich zapytań wynosi więc O(k*8*n*m).

W rozwiązaniach pojawiły się także inne podejścia. Jednym z nich był zmodyfikowany algorytm przeglądania grafu wszerz, który z każdego punktu przeglądał tylko punkty położone nie niżej niż on sam. Odwiedzane punkty były dodatkowo przechowywane w tablicy wektorów (indeksowanej wysokościami punktów), a cały algorytm przeglądał tablicę od najwyższych punktów do najniższych (analogicznie do omówionej wyżej wersji "zmutowanej" Dijkstry). Innym rozwiązaniem było zastosowanie struktury zbiorów rozłącznych. W poszczególnych zbiorach były punkty, między którymi istniały ścieżki nie niższe od zadanego progu wysokości. Próg ten był stopniowo obniżany. Proces analizy punktów przebiegał od najwyższych do najniższych i następowało w nim łączenie przeglądanych sąsiadów (o ile byli nie niżej położeni niż bieżący punkt). Dodatkowo zapamiętywano najwyższy punkt z każdego podzbioru. W ten sposób przy każdej iteracji można było analizować jednocześnie wszystkie zapytania. Przy większej liczbie zapytań to rozwiązanie byłoby najszybsze.


Plansza (http://pl.spoj.com/ALGOLIGA/problems/AL_14_11/)

W zadaniu należało wykorzystać fakt, że na prawdopodobieństwo stanięcia pionka na polu x w y+i kolejce (0<=i<=2) wpływa bezpośrednio prawdopodobieństwo stanięcia tego pionka na innych polach w kolejce y. Prawdopodobieństwa stanięcia na danych polach powiązane są prostymi zależnościami: pole zwykłe wpływa na 6 pól położonych bezpośrednio za nim (w kolejce następnej), natomiast pola z przesunięciami wpływają tylko na pole, gdzie przesuwa się pionek (ale już w bieżącej kolejce), a pole tracące kolejkę wpływa na 6 pól przed nim ale dopiero za dwie kolejki. Rozwiązanie należało zaimplementować używając programowania dynamicznego i dwuwymiarowej tablicy prawdopodobieństw (jeden wymiar to liczba kolejek, a drugi to liczba pól). Ważne było jednak, by dla każdej kolejki najpierw przetwarzać podproblemy dla pól z przesunięciami, gdyż wpływają one na pola zwykłe w tej samej kolejce. Kolejny haczyk był taki, by po wyznaczeniu całej tablicy, wyliczać oddzielnie prawdopodobieństwo wygranej jednego gracza i prawdopodobieństwo wygranej drugiego gracza. Wynika to stąd, że czasem mogli się znudzić i ogłosić remis ;) A prawdopodobieństwo remisu mogło nie być zerowe.
Ostatnio zmieniony 17 lut 2014, 08:57 przez Ostry, łącznie zmieniany 2 razy
Ostry
Organizator AlgoLigi
 
Posty: 5
Rejestracja: 18 sty 2014, 10:53

Re: Runda 14 - omówienie zadań

Postautor: witman » 17 lut 2014, 01:45

No to jeszcze moje zadania:

Taksówka na Manhattanie - reaktywacja http://www.spoj.com/ALGOLIGA/problems/AL_14_02/
Potrzebna wiedza: metryka Manhattan, wyszukiwanie minimum.

Niewiele do tłumaczenia. Liczymy odległości pomiędzy kolejnymi punktami w metryce Manhattan i wybieramy najmniejszą (tu trzeba uwzględnić, że maksymalna długość lotu przekracza zakres 32bitowego typu całkowitego). Przy okazji liczymy w ilu wymiarach kolejne punkty mają różne wartości i sumujemy te liczby.


Enigma w wersji nieco mniej light http://www.spoj.com/ALGOLIGA/problems/AL_14_04/
Niech to zadanie pozostanie łamigłówką ;). Podpowiem tylko, że szyfr jest wyłącznie przestawieniowy.
Co do umiejętości programowawania potrzebnych do rozwiązania tego zadania - wystarczą podstawowe.


Przechadzka króla http://www.spoj.com/ALGOLIGA/problems/AL_14_06/
Potrzebna wiedza: elementarna arytmetyka.

W przypadku szachownicy klasycznej rozwiązanie jest trywialne i wynosi max(abs(k1-k2),abs(w1-w2)).

Znacznie trudniej jest w przypadku szachownicy heksagonalnej. Żeby nie pozbawiać nikogo przyjemności samodzielnego rozwiązania, podpowiem tylko trochę. Limit czasowy wymaga oczywiście znalezienia wzoru, który w stałym czasie wyznaczy szukaną odległość. Szczerze przyznam, że kiedy to zadanie wpadło mi do głowy, sam miałem problem z jego znalezieniem (ale nie spodziewałem się, że to będzie najtrudniejsze zadanie w konkursie). W końcu wyszło mi coś takiego:
1. Najpierw oczywiście sprawdzam, czy oba pola leżą na planszy.
2. W zależności od numeru kolumny przeliczam numer wiersza, tak aby "pozbyć się" załamanych wierszy.
3. Określam różnicę pomiędzy polami w każdym z trzech kierunków, które można wyróżnić na planszy: według kolumn, wg wierszy leżących na kierunku NE-SW i wg wierszy leżących na kierunku NW-SE (suma tych trzech liczb wynosi 0)
4. Szukany wynik zależy od różnicy pomiędzy największa a najmniejszą z trzech wyznaczonych liczb. Jak? To pozostawię czytelnikom do samodzielnego wymyślenia. ;)


Generator liczb prawie pseudolosowych http://www.spoj.com/ALGOLIGA/problems/AL_14_08/
Potrzebna wiedza: algorytm wyszukiwania lidera (można poczytać tu lub tu).

Zadanie byłoby proste, gdyby wygenerowane liczby można byłoby posortować. Fabuła zadania jest jednak taka, żeby odróżnić algorytm z wykorzystaniem sortowania o złożoności O(n log n) od wzorcowego algorytmu wyszukiwania lidera, który ma złożoność O(n). Do tego potrzeba dużo danych. Jednakże dużo danych wejściowych pozwalałoby na "przejście" rozwiązań o złożoności O(n log n) z wykorzystaniem szybkiego wczytywania. Dlatego z treści zadania wynika, że liczby trzeba wyznaczyć "samemu" (tzn. w trakcie działania programu).
Zadanie można też rozwiązać bez wykorzystania algorytmu wyszukiwania lidera a z sortowaniem :shock: , co wykazał Krzysiek Ostrowski testując zadanie. Jak? Trzeba zastosować sortowanie pozycyjne przez zliczanie, które ma przecież złożoność O(n).


Powrót Jasia włamywacza http://www.spoj.com/ALGOLIGA/problems/AL_14_10/
Potrzebna wiedza: rekurencja lub kod Graya.

Rozwiązanie tego zadania to jednocześnie rozwiązanie klasycznej łamigłówki znanej jako Baguenaudier lub Chinese Rings.

Rozwiązanie pierwsze: rekurencja.
Żeby podać rozwiązania na tacy, podpowiem tylko, że należy zdefiniować dwie funkcje. Jedną, której zadaniem będzie doprowadzić do otwarcia n początkowych zasuwek oraz drugą, która ma je zamknąć. Każda z tych funkcji powinna, w zależności od ustawienia n-tej i (n-1) zasuwki, wywoływać siebie lub tę drugą funkcję, tak aby doprowadzić do sytuacji, w której można zmienić położenie n-tej zasuwki. Po tej zmianie pozostają znów tylko rekurencyjne wywołania tych funkcji z odpowiednio zmniejszonym parametrem n.
Oczywiście rekurencję trzeba przerwać, jeśli liczba wykonanych ruchów przekracza dopuszczalną.

Rozwiązanie drugie: kod Graya.
Można zauważyć, że układ zasuwek odpowiada pewnej wartości w kodzie Graya, a aby doprowadzić do otwarcia zamka, należy przechodzić przez kolejne wartości w kodzie Graya odpowiadające zmniejszającym się wartościom naturalnego kodu binarnego.
Najpierw, za pomocą metody, którą można znaleźć tu, możemy się dowiedzieć ile ruchów trzeba wykonać. Jeśli zmieścimy się w limicie, to kolejne wartości kodu można generować za pomocą znanego wzoru: g = n xor (n div 2). Na wyjściu należy wyświelać literę, odpowiadającą pozycji, na której nastąpiła zmiana. Oczywiście wielkość litery zależy od tego czy dany bit zmienił się z 0 na 1, czy odwrotnie.


Kto narysuje większy kwadrat? http://www.spoj.com/ALGOLIGA/problems/AL_14_12/
Potrzebna wiedza: własności ciągu Fibonacciego, algorytm Euklidesa, arytmetyka modularna, szybkie potęgowanie.

Przyjmijmy P=1000000103.
Przede wszystkim zauważmy, że największe kwadraty Antek i Basia będą uzyskiwać, jeśli boki tych kwadratów utworzą ciąg Fibonacciego. Aby dane na wejściu liczby ruchów wykonanych przez graczy odpowiadały numerom liczb w ciągu Fibonaciego, dla ułatwienia dalszych obliczeń, zwiększmy najpierw każdą z nich o 1 (a=a+1, b=b+1). Dalej potrzebna jest ciekawa własność ciągu Fibonacciego: gcd(fib(a),fib(b))=fib(gcd(a,b)). Po obliczeniu największego wspólnego dzielnika liczb a i b algorytmem Euklidesa, wartości x=fib(a), y=fib(b) oraz d=fib(gcd(a,b)) możemy wyznaczyć szybką metodą potęgowania macierzy Fibonacciego, (oczywiście wykonując obliczenia modulo P). Aby skrócić liczby x i y przez d, musimy obliczyć odwrotność liczby d modulo P, która jest równa d^(P-2). Po skróceniu, licznik i mianownik podnosimy do kwadratu.
Trzeba jednak uważać na pewien szczególny przypadek, gdy wyznaczony największy wspólny dzielnik d (mod P) = 0. Wtedy nie możemy wyznaczyć jego odwrotności. Na szczęście są tylko dwie takie wartości w zakresie <1;P-1>, gdy liczba wykonanych ruchów wynosi 333333367 lub 666666735 (bo fib(333333368)=fib(666666736)=0 (mod P) ). Jeśli wtedy a=b, to wynikiem jest oczywiście '1/1'. Jeśli a=2*b lub b=2*a, to trzeba skorzystać z kolejnej własności ciągu Fibonacciego, która mówi że fib(2n)/fib(n)=fib(n-1)+fib(n+1).
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Re: Runda 14 - omówienie zadań

Postautor: m99 » 18 lut 2014, 22:19

Hej,

nie mogę napisać PW to piszę tutaj

@witman, czy mógłbyś sprawdzić moje zgłoszenie 11089676(zadanie Kto narysuje większy kwadrat), dlaczego mam WA, podczas zawodów nie łapałem przypadku gdy gcd(a,b)=0. Teraz dodałem poprawę, a nadal błąd ;/
m99
 
Posty: 2
Rejestracja: 18 lut 2014, 22:06

Re: Runda 14 - omówienie zadań

Postautor: witman » 19 lut 2014, 18:09

@m99
Jest prawie dobrze ;) . Zapomniałeś tylko, że w tym szczególnym przypadku też trzeba obliczyć pole, a nie bok kwadratu.
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Re: Runda 14 - omówienie zadań

Postautor: m99 » 19 lut 2014, 19:49

Ehh, super blad :) Dzięki bardzo jest AC
m99
 
Posty: 2
Rejestracja: 18 lut 2014, 22:06

Re: Runda 14 - omówienie zadań

Postautor: narbej » 19 lut 2014, 20:03

Bo sam tak napisałeś: ;-)
witman pisze:Po skróceniu, możemy licznik i mianownik podnieść do kwadratu.

Zamiast "możemy już", lub po prostu "podnosimy" ;-)

========== edit by me
Oczywiście, dostanie WA, ale to już szczegół ;-)
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 14 - omówienie zadań

Postautor: witman » 19 lut 2014, 20:47

No tak. Nikt nie musi. Tylko wtedy dostanie WA ;)
Jednak uwzględniłem sugestię i zmieniłem na "podnosimy"
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03


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