Runda 19 - omówienie zadań

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

Runda 19 - omówienie zadań

Postautor: macbon » 30 lis 2014, 21:55

Suchary

Rozwiązanie naiwne tego zadania polega na liniowym wyszukaniu pierwszego dowcipu, z którego zaśmieje się Karol oraz pierwszego dowcipu z którego zaśmieje się Tadeusz, a następnie porównaniu ich numerów. Złożoność tego rozwiązania wynosi zatem O(m*n). Dla maksymalnych wartości n i m jest ono zdecydowanie za wolne i z całą pewnością otrzyma werdykt przekroczenia limitu czasu.

Przejdźmy zatem do omówienia rozwiązania wzorcowego. Oznaczmy sobie przez pr(i) poziom rozbawienia jaki musimy przekroczyć żeby zaśmiać się z dowcipu o numerze i. Jeżeli mamy sytuację, w której pr(i) < pr(j) i jednocześnie i < j to mamy pewność, że nigdy nie zaśmiejemy się z dowcipu j, bo wcześniej będziemy pękać ze śmiechu z kawału i. W związku z tym w tablicach, które przechowują poziomy rozbawienia, które Karol i Tadeusz muszą przekroczyć żeby zaśmiać się z danego dowcipu możemy wyeliminować opisaną powyżej sytuację nadpisując pr(j) wartością min(pr(1), pr(2), ..., pr(j)). Możemy zatem w czasie liniowym przerobić w ten sposób tablice Karola (A) i Tadeusza (B) z poziomami rozbawienia dla poszczególnych dowcipów. Wartość dla 1 dowcipu A[1] pozostaje bez zmian natomiast wartości kolejnych będą równe A[i]=min(A[i - 1], A[i]). To samo robimy dla tablicy B. W ten sposób uzyskamy tablice z wartościami uporządkowanymi nierosnąco. Następnie wczytujemy poziomy rozbawienia c i d dla kolejnych dni. Teraz musimy dla nich znaleźć pierwsze wystąpienie wartości <=c-1 w tabeli A i wartości <=d-1 w tabeli B. Ponieważ wartości w tabelach są uporządkowane nierosnąco możemy do tego celu użyć wyszukiwania binarnego, które to działa w czasie logarytmicznym. Kiedy już znajdziemy dane wartości wynik ustalamy porównując indeksy, na których wystąpiły. Rozwiązanie to ma złożoność czasową O(m*log n) i bez problemu mieści się w ustalonym limicie czasu.

Fast IO 2

Zadanie sprowadza się do rozwiązania wartości makra i wyszukania w niej podciągu unlocked. W rzeczywistości jednak generowanie wartości makra jest zbędne. Możemy zauważyć, że makra i powiązania między nimi tworzą drzewo. Wystarczy zatem rekurencyjnie przejść wszystkie wierzchołki drzewa i sprawdzać czy w liściach występują kolejne litery unlocked. Ponieważ makra na wejściu występują w dowolnej kolejności jedyną trudnością na jaką napotykamy jest szybkie wygenerowanie drzewa. Do przechowywania i wyszukiwania makr możemy użyć zbalansowanego drzewa binarnego, które to umożliwia wstawianie i wyszukiwanie w czasie logarytmicznym. W języku C++ zamiast implementować własne drzewo możemy wykorzystać kontener map z biblioteki STL. Kluczem w mapie jest oczywiście nazwa makra zaś wartością struktura zawierająca cztery pola: dwa pola tekstowe oraz dwa wskaźniki na inne makra. W przypadku makr w postaci NAZWA = wartość wykorzystywane jest tylko jedno pole tekstowe do przechowywania wartości. W przypadku makr łączących dwa inne, w polach tekstowych przechowujemy nazwy makr, które łączymy. Wskaźniki na inne makra ustawiamy wyszukując je w naszej mapie, rozwiązanie ma zatem złożoność O(n*log n).

Macierz

W zadaniu występują dwa przypadki proste, dla których wynik możemy obliczyć bez wykonywania wyszukiwania liczby dysków i kontrolerów. Pierwszy z nich to sytuacja, w której przepustowość kontrolera k jest mniejsza od szybkości zapisu danych na dysku d. W takim wypadku żeby uzyskać macierz o przepustowości co najmniej p potrzebujemy sufit(p/k) dysków i tyle samo kontrolerów. Drugi przypadek to sytuacja, w której przepustowość kontrolera jest podzielna bez reszty przez szybkość zapisu danych na dysku. Tym razem liczba potrzebnych dysków wynosi sufit(p/d) zaś liczba kontrolerów sufit(p/k/d). We wszystkich pozostałych przypadkach musimy przeprowadzić wyszukiwanie wyniku. Na początek zauważmy, że liczba potrzebnych dysków jest nam de facto znana i będzie wynosiła sufit(p/d). Zadanie sprowadza się zatem do wyszukania minimalnej liczby kontrolerów, która po podpięciu danej liczby dysków zapewni nam przepustowść co najmniej p. Poszukiwana wartość zawsze będzie nie mniejsza niż sufit(p/k) i nie większa niż sufit(p/d). Rozwiązaniem naiwnym jest sprawdzanie kolejnych liczb kontrolerów z danego przedziału. Niestety dla maksymalnych danych takie sprawdzenie trwa zdecydowanie za długo i powoduje otrzymanie werdyktu przekroczenia limitu czasu. W związku z powyższym żeby zmieścić się w ustalonym limicie wymaganą liczbę kontrolerów musimy znaleźć wykorzystując wyszukiwanie binarne.

Pojedynek

Zadanie możemy rozwiązać za pomocą funkcji rekurencyjnej, która pobiera cztery parametry: identyfikator wieszcza, który będzie wypowiadał wyraz, literę na jaką kończyło się poprzednie słowo oraz zbiory wyrazów, które pozostały do wykorzystania Juliuszowi i Adamowi. Funkcja powinna zwracać prawdę jeżeli istnieje taka sekwencja ruchów, która gwarantuje zwycięstwo w bieżącej sytuacji albo fałsz w przeciwnym wypadku. Ponieważ liczba wyrazów, które przygotował każdy z poetów nie przekracza 10 to informacje o tym które wyrazy są dostępne, a które nie, możemy przechowywać na bitach zmiennej całkowitoliczbowej. Funkcję wywołujemy rekurencyjnie dla każdego wyrazu jaki zaczyna się na taką samą literę na jaką kończył się poprzedni. Jeżeli przynajmniej dla jednego z tych wywołań otrzymaliśmy wartość fałsz (przeciwnik przegrał) to znaczy, że istnieje strategia wygrywająca i bieżące wywołanie może zwrócić wartość prawda. Z racji tego, że wywołania rekurencyjne mogą się powtarzać zapamiętujemy ich wyniki w tablicy wielowymiarowej. W momencie wywołania funkcji najpierw sprawdzamy czy wynik dla danego zestawu parametrów nie został już wcześniej obliczony. Jeżeli tak, to zwracamy wartość zapisaną w tablicy.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 19 - omówienie zadań

Postautor: witman » 01 gru 2014, 01:57

1. Enigma w wersji średnio trudnej http://www.spoj.com/ALGOLIGA/problems/AL_19_01/
Prosty szyfr podstawieniowy. W treści zadania są dwie wyraźne podpowiedzi.

2. Nowa fontanna http://www.spoj.com/ALGOLIGA/problems/AL_19_02/
Potrzebna wiedza: szybkie potęgowanie modularne, programowanie dynamiczne.

Wykonujemy potrzebne obliczenia dla kolejnych poziomów fontanny zaczynając oczywiście od góry.
Dla każdej misy liczymy jej pojemność według wzoru z zadania i mnożymy przez szybkość napełniania. Czas potrzebny do jej napełnienia to pojemność pomnożona przez odpowiednią dla danego poziomu potęgę dwójki. Jeśli do tego dodać czas jaki minął od początku napełniania fontanny do wypełnienia misy znajdującej się powyżej, otrzymamy czas, jaki po jakim dana misa będzie wypełniona.
Najważniejsze jest, żeby przy obliczaniu pojemności mis, nie wykonywać wielokrotnie takiego samego potęgowania. Wystarczy obliczyć tylko b potęg. Przy takim podejściu otrzymamy algorytm o złożoności .

3. Franek doodler http://www.spoj.com/ALGOLIGA/problems/AL_19_03/
Potrzebna wiedza: elementarna arytmetyka.

Poszukiwana liczba prostokątów odpowiada liczbie całkowitoliczbowych rozwiązań równania: .
Efektywny algorytm o złożoności można znaleźć na oeis.org/A006218.

4. Szlakiem bajtockich zamków http://www.spoj.com/ALGOLIGA/problems/AL_19_04/
Potrzebna wiedza: programowanie dynamiczne.

Oznaczmy przez W(d) na ile sposobów można dostać się do zamku nr d.
.

Rozwiązanie zadania będzie obliczenie wartości W(n+1).

Wykorzystanie powyższej zależności wymaga jednak wielokrotnego sumowania tych samych wartości i da nieefektywny algorytm o złożoności .
Trzeba zauważyć, że wartość W(d) można wyznaczyć ze wzoru:
, co da nam algorytm o złożoności .

Uwaga 1. Aby otrzymać żądany w zadaniu wynik modulo 18446744073709551616, wystarczy wykorzystać 64-bitowy typ całkowity.
Uwaga 2. Limit pamięci narzucony w zadaniu, wymaga zastosowania odpowiednio małej tablicy do przechowywania ostatnich (k+2) wartości, i cyklicznego wykorzystywania jej komórek.

9. Kolonizacja galaktyki http://www.spoj.com/ALGOLIGA/problems/AL_19_09/
Potrzebna wiedza: wielowymiarowe drzewo przedziałowe, wielowymiarowe drzewo Fenwicka.

Aby efektywnie realizować występujące w zadaniu polecenia należy zaimplementować trójwymiarowe drzewo przedziałowe lub drzewo indeksowane binarnie. To drugie rozwiązanie jest nieco efektywniejsze zarówno czasowo jak i pamięciowo.
Nie dało się tak dobrać limitów czasowych, żeby przechodziły tylko drzewa 3D. Można zastosować tablicę drzew indeksowanych binarnie 2D , posiadającą 52 komórki (liczba możliwych odległości sektorów).

10. Gra w czterech wymiarach http://www.spoj.com/ALGOLIGA/problems/AL_19_10/
Potrzebna wiedza: algorytm Euklidesa.

Rozwiążmy najpierw uproszczoną wersję zadania dla dwóch wymiarów.
Bez straty ogólności możemy przyjąć, że analizujemy wykonywanie ruchu w punkcie (0,0) (w innym wystarczy przesunąć środek układu współrzędnych, przeliczając odpowiednio współrzędne wszystkich pionków).
Rozpatrzmy przykład jak na rysunku poniżej. Mamy na planszy pionki czarne i czerwone (białe słabo byłoby widać ;) ), i zastanawiamy się jaki będzie efekt postawienia czarnego punktu w punkcie (0,0).
Obrazek
Zauważmy najpierw, że punkty kratowe leżące na tej samej półprostej rozpoczynającej się w punkcie (0,0) mają pewną wspólną cechę: taki sam stosunek współrzędnych. Jeżeli podzielić obie współrzędne dowolnego punktu przez ich największy wspólny dzielnik, otrzymamy współrzędne punktu kratowego leżącego najbliżej punktu (0,0). Ten punkt jednoznacznie identyfikuje daną półprostą, a jeśli jego odległość od początku układu przyjąć jako jednostkę, to punkt o współrzędnych (x,y) leżący na tej półprostej znajduje się w odległości wynoszącej NWD(x,y) od punktu (0,0). Na rysunku, na zielonej półprostej takim punktem jednostkowym jest punkt J, na niebieskiej B, a na pomarańczowej G. Wyznaczone w opisany wyżej sposób odległości wynoszą: B(1), C(2), D(3), E(3), F(4), I(6), K(7), G(1), H(2).
Aby obliczyć liczbę pionków które zostaną zbite, przeglądamy najpierw wszystkie swoje (w przykładzie czarne) punkty i zapamiętujemy odległość najbliższego na danej półprostej (w przykładzie punkty C, I, G). Następnie sprawdzamy pionki przeciwnika i jeżeli obliczona na danej półprostej odległość jest mniejsza od tej, którą ma nasz najbliższy punkt, to ten pionek zostanie zbity (w przykładzie będą to punkty: B, E, F).

Przejście do przestrzeni cztero (lub więcej) wymiarowej, można wykonać prawie "mechanicznie". Wystarczy uwzględnić to, że każdy punkt ma cztery współrzędne, więc do wyznaczenia półprostej, na której leży (i odległości na niej) trzeba obliczać NWD z czterech współrzędnych.
Jeśli do zapamiętania naszych najbliższych na każdej półprostej punktów wykorzystamy mapę i przyjmiemy stały koszt obliczania NWD współrzędnych (można to obliczyć wstępnie), to wyznaczenie wyniku dla każdego analizowanego ruchu czarnego gracza będzie miało złożoność . Jeśli zastosować funkcję mieszającą to .
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