Runda 29 - omówienie zadań

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

Runda 29 - omówienie zadań

Postautor: adam_bak » 28 sie 2016, 19:48

Tutaj po zakończeniu rundy pojawią się omówienia zadań. Zachęcamy do lektury i jak zwykle dzielenia się swoimi rozwiązaniami ( oczywiście to też po zakończeniu rundy :) )
adam_bak
Koordynator AlgoLigi
 
Posty: 68
Rejestracja: 20 wrz 2012, 09:44

Re: Runda 29 - omówienie zadań

Postautor: adam_bak » 28 sie 2016, 20:00

SAT Solver
W zadaniu należy sprawdzić spełnialność formuły logicznej w postaci DNF. Łatwo zauważyć kiedy taka formuła jest spełnialna. Po prostu dowolna klauzula musi być niesprzeczna - nie może zawierać jednocześnie pewnego literału i jego zaprzeczenia. Złożoność liniowa od wejścia.


Konflikt
Na pierwszy rzut oka chciałoby się tutaj użyć klasycznego algorytmu na najbliższą parę punktów (zamiatanie lub divide and conquer). Kłopot jednak w tym, że w obu istnieje moment w którym sprawdzamy odległości pomiędzy dowolną parą kandydatów. Tych kandydatów jest tam na szczęście mała stała liczba, czego niestety nie zapewnimy w tej wersji zadania - przynależność punktów do dwóch różnych zbiorów psuje niezmiennik.

Spójrzmy najpierw na prostszą wersję zadania. Niech punkty jednego państwa spełniają oprócz y > 0 jeszcze x > 0, a drugiego: y < 0 i x < 0. Innymi słowy zbiory leżą w przeciwległych ćwiartkach układu współrzędnych. Metryka miejska ma to do siebie, że najkrótsza droga nie musi być wyznaczona jednoznacznie. W szczególności przy takim położeniu punktów dla każdej pary zawsze istnieje conajmniej jedna najkrótsza ścieżka przechodząca przez punkt (0,0). Wobec tego możemy minimalizować odległość między zbiorami poprzez minimalizowanie odległości obu zbiorów do punktu (0, 0), a więc znaleźć najbliższą parę punktów w O(n).

Ta obserwacja pozwala stworzyć algorytm O(nlogn) za pomocą techniki divide and conquer.
Wróćmy bowiem do oryginalnego zadania. Punkt (0,0) w powyższej obserwacji był szczególny tylko dlatego że dzielił oba zbiory zarówno w pionie jak i poziomie. Teraz tak nie musi być. Wiadomo jednak że prosta Y=0 dzieli oba zbiory. Wobec tego istnieje punkt postaci (a,0), który spełnia rolę punktu (0,0) z obserwacji. Znajdźmy więc ten punkt i podzielmy punkty obu zbiorów na te spełniające x<=a oraz x>=a. Opisaną wyżej metodą możemy dla powstałych dwóch par zbiorów które w pionie i poziomie dzieli punkt (a,0) znaleźć najbliższą parę punktów. Problem jednak w tym, że globalnie najbliższa para nie musiała leżeć po obu stronach tego punktu. Wobec tego musimy się wywołać rekurencyjnie dwa razy dla problemów o połowę mniejszych (punkty na lewo od wybranego oraz dla tych na prawo). Reasumując:

1. sortujemy wszystkie 2n punktów leksykograficznie (do każdego dodajemy informację o zbiorze do którego należy) - O(nlogn)
2. wywołujemy rekurencję T(n) = T(n/2) + T(n) = O(nlogn) na powstałej tablicy punktów aby znaleźć rozwiązanie.
3. Całość działa w O(nlogn).

Zadanie można rozwiązać na wiele sposobów co potwierdzają zgłoszenia podczas zawodów.


Rozmowa kwalifikacyjna
Zadanie można rozwiązać przy pomocy drzew przedziałowych, a fani drzew Fenwicka osiągną tutaj najlepsze czasy. Odpowiedź można policzyć trochę na zasadzie programowania dynamicznego. Zainicjujmy k drzew przedziałowych dla wejściowej permutacji. k-te drzewo będzie przetrzymywało informację dla każego elementu permutacji - ile jest malejących podciągów k elementowych kończących się na tym elemencie. Przejdźmy się teraz po permutacji i dla każdej napotkanej liczby uaktualnijmy wszystkie drzewa. Najniższe drzewo (dla k=1) odpowiada podciągom jednoelementowym, więc pod indeks wyznaczony przez napotkaną liczbę x wstawiamy 1. Dla każdego większego k liczymy odpowiedź na podstawie k mniejszego o jeden. Liczba malejących podciągów k-elementowych kończących się na x jest równa liczbie malejących podciągów k-1-elementowych kończących się na dowolnej liczbie większej od x. Ostateczną odpowiedź liczymy sumując przedział [1; n] na k-tym drzewie.

Zadanie wciąż można rozwiązać efektywnie dla dużych k. Polecam się nad tym zastanowić.


Ostatnia runda AlgoLigi
Zadanie bardzo łatwo zredukować do problemu maksymalnego przepływu. Poprawność będzie wynikała wprost z tej konstrukcji.
Stwórzmy po jednym wierzchołku dla każdego autora oraz po jednym wierzchołku dla każdej kategorii. Dodajmy źródło s oraz ujście t. Niech ze źródła s wychodzi krawędź o przepustowości z_i do i-tego autora, a od tego autora wychodzą krawędzie do opanowanych przez niego działów - przepustowości też z_i. Na koniec z każdej kategorii prowadzimy krawędź do ujścia t o przepustowości . Odpowiedź na postawione w treści zadania pytanie jest równoważna z odpowiedzią na pytanie czy maksymalny przepływ w tym grafie wynosi X. Trzeba uważać, bo wartość ta może się nie mieścić w zakresie inta. Mamy więc n+k+2 wierzchołków i potencjalnie sporo krawędzi. Trzeba zatem użyć jakiegoś bardziej przyzwoitego algorytmu jak na przykład algorytm Dinica.


Słowa, słowa, słowa
W takich trudniejszych zadaniach na algorytmy tekstowe, gdzie badamy dość wyszukaną własność, zwykle nie obejdzie się bez jakiejś bardziej skomplikowanej struktury danych. Opiszę rozwiązanie z użyciem grafu podsłów, chociaż nie widzę powodów dla których nie dałoby się tego rozwiązać za pomocą drzewa sufiksowego. Zaletą tego pierwszego jest jednak bajecznie prosta implementacja (struktury i całego rozwiązania). O tej strukturze można poczytać na przykład tu: http://smurf.mimuw.edu.pl/node/581

Stwórzmy graf podsłów dla słowa A#B$. Z każdym wierzchołkiem jest stowarzyszonych być może wiele podsłów. Policzmy więc dla każdego wierzchołka metodą bottom-up czy znak # jest z niego osiągalny (podsłowa A) oraz ile ścieżek prowadzi z niego do $, ale nie przez # (wystąpienia w B). Ten graf to tak naprawdę DAG (i to jeszcze w dodatku dość szczególny), więc możemy to zrobić liniowo dzięki spamiętywaniu wyników. Teraz dla każdego wierzchołka wiemy czy słowa przez niego reprezentowane są podsłowami A oraz ile razy występują w B. Zostało jedynie policzenie ile słów reprezentuje dany wierzchołek. Robimy to znów prawie tak jak na drzewie - tym razem top-bottom ze spamiętywaniem częściowych wyników. Nigdzie jednak rekurencji nie trzeba wykorzystywać (jeszcze by się stos przepełnił gdyby były większe dane) bo wystarczy wierzchołki DAGu posortować topologicznie i zauważyć że jedno obliczenie wykonuje się w kolejności zgodnej z tym sortowaniem, a drugie - w kolejności przeciwnej. Złożoność liniowa od wejścia.
adam_bak
Koordynator AlgoLigi
 
Posty: 68
Rejestracja: 20 wrz 2012, 09:44

Re: Runda 29 - omówienie zadań

Postautor: macbon » 28 sie 2016, 20:01

Negative split
Było to jedno z najprostszych zadań w całym zestawieniu. Zadanie tak naprawdę sprowadzało się do zamiany wczytanych czasów na sekundy i odpowiedniego ich porównania. Jedyną trudność stanowiła właśnie zamiana czasów na sekundy. W przypadku języków C/C++ można było ułatwić sobie życie korzystając z funkcji scanf, w której to możemy określić format wczytywanych danych i od razu do osobnych zmiennych wczytać wartości dla godzin, sekund i minut. Przykład:
Kod: Zaznacz cały
int h, m, s, t;
scanf("%d:%d:%d", &h, &m, &s);
t = h * 60 * 60 + m * 60 + s;


Ozdoby choinkowe
W związku z tym, że k było małe w zadaniu spokojnie mogliśmy skonstruować każde z n drzew poszukiwań binarnych. Po skonstruowaniu drzewa należało w jakiś sposób określić jego kształt. Rozwiązanie wzorcowe przechodziło drzewo poszukiwań binarnych algorytmem DFS zapisując ścieżkę jako łańcuch znaków. W momencie zejścia do lewego albo prawego poddrzewa dodawana była do łańcucha odpowiednio litera L albo P. W przypadku powrotu do rodzica litera G. Przy przejściu drzewa DFSem albo już przy jego konstrukcji mogliśmy policzyć sobie jego koszt. Mając wszystkie kształty i koszty możemy wyznaczyć najtańszą ozdobę każdego kształtu np. wrzucając wszystko do struktury, umożliwiającej dostęp do danych po kluczu będącym dowolnym typem danych. W naszym wypadku kluczem będzie łańcuch znaków zawierający ścieżkę zaś wartością znajdującą się pod tym kluczem koszt ozdoby. Przy analizowaniu kolejnych ozdób aktualizujemy koszt jeżeli trafiliśmy na tańsze drzewo.

Czarno białe
Zadanie to możemy rozwiązać wykorzystując programowanie dynamiczne. Oznaczmy przez S[x] liczbę smakowitych ustawień składających się z x lodów. Rozważmy sytuację, w której mama pozwoliła zakupić Jasiowi x lodów. Łatwo zauważyć, że jeżeli x jest z przedziału [0;k) to S[x] = 1. W takim wypadku albo nie możemy kupić żadnych lodów albo możemy kupić jedynie lody w czarnej polewie, gdyż nie mamy jak uzyskać wielokrotności k. Co w przypadku gdy x >= k? Tutaj sytuacja robi się ciekawsza, ponieważ mamy dwie możliwości. Jeżeli ostatnim lodem, czyli tym na pozycji x, jest lód w czarnej polewie to lody będące przed nim możemy ustawić na S[x-1] smakowitych ustawień. Jeżeli chcemy żeby ostatnim lodem był lód w białej polewie, to tak naprawdę musimy ustawić k ostatnich lodów jako białe żebyśmy mieli gwarancję, że ustawienie będzie smakowite. W związku z powyższym liczbą smakowitych ustawień w tym wypadku będzie S[x-k]. Podsumowując gdy x >= k to liczbą smakowitych ustawień jest S[x]=S[x-1]+S[x-k]. Pierwszym etapem rozwiązania jest zatem policzenie wszystkich wartości S[x] dla x z przedziału [0;b]:
  • Dla x z przedziału [0;k) S[x] = 1
  • Dla x z przedziału [k;b] S[x] = S[x-1] + S[x-k]
W momencie gdy mamy już policzone wszystkie wartości S[x] pozostaje nam tylko zsumowanie wszystkich wartości S[x] dla x z przedziału [a;b]. Obliczona suma jest liczbą smakowitych ustawień szukaną przez Jasia. To na co dodatkowo należało zwrócić uwagę w tym zadaniu, to że liczba smakowitych ustawień bardzo szybko rośnie i wynik może nie zmieścić się w żadnym całkowitoliczbowym typie danych. W związku z powyższym należało zaimplementować własną arytmetykę dużych liczb albo użyć języka, który ma ją wbudowaną (np. PHP, Python).

DOS completion
Do rozwiązania zadania można było wykorzystać drzewo TRIE. Jest to drzewo, w którym każda krawędź odpowiada jednej literze, zaś każdy wierzchołek jest prefiksem słowa będącego połączeniem liter znajdujących się na krawędziach od korzenia do danego wierzchołka. Na każdym wierzchołku naszego drzewa powinniśmy przechowywać dwie dodatkowe informacje: czy dany wierzchołek jest końcem jakiegoś polecenia oraz ile poleceń znajduje się w poddrzewie ukorzenionym w danym wierzchołku. W momencie zapytania wystarczyło dojść do wierzchołka odpowiadającego szukanemu prefiksowi, a następnie np. DFS przejść jego poddrzewo wypisując maksymalnie m poleceń znajdujących się w nim. Liczbę pozostałych poleceń możemy wyciągnąć z wierzchołka drzewa.

Nowa walut 3
Rozwiązaniem zadania jest skorzystanie z lekko zmodyfikowanego drzewa przedziałowego. Zauważmy, że przy każdej modyfikacji wartości w drzewie przedziałowym zmienianych jest zawsze log n wierzchołków. W związku z powyższym nie ma sensu trzymanie pełnego drzewa przedziałowego dla każdego historycznego momentu (dla każdej z wykonywanych zmian). Zamiast tego powinniśmy tworzyć tylko log n nowych wierzchołków, które są aktualizowane, zaś do nich dołączać wierzchołki z istniejącego wcześniej drzewa. Jak to zrobić? Wystarczą nam do tego celu 4 tablice o odpowiednio dużym rozmiarze:
W[x] - przechowuje wartość węzła x
L[x] - przechowuje indeks węzła będącego lewym potomkiem węzła o indeksie x
P[x] - przechowuje indeks węzła będącego prawym potomkiem węzła o indeksie x
K[i] - przechowuje indeks korzenia drzewa po i-tej zmianie
W momencie dokonywania zmiany tworzymy log n nowych wierzchołków (wpisów w tabeli W) i podczepiamy do nich (uzupełniamy tablice L i P) wierzchołki z drzewa poprzedniej zmiany.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 29 - omówienie zadań

Postautor: Crucian » 28 sie 2016, 20:40

W zadaniu Nowa walut 3 takie drzewo nazywane jest "trwałym drzewem przedziałowym" (persistent segment tree po angielsku). W internecie (po angielsku) jest trochę tutoriali na ten temat.


Zadanie Konflikt można zrobić też w inny sposób. Złożoność to też O(n log n) ale nie licząc sortowania algorytm działa w czasie liniowym.
Najpierw sortujemy (oddzielnie dla obu stron) miasta po współrzędnej X. Następnie z jednej ze stron, powiedzmy tej poniżej osi X chcemy usunąć wszystkie miasta które są bezużyteczne. Jeśli sprawdzamy czy miasto na współrzędnych (x1, y1) jest bezużyteczne to musimy sprawdzić czy istnieje jakieś inne miasto z tej samej strony konfliktu które jest bliżej punktu (x1, 0). Jeśli istnieje to miasto jest bezużyteczne. Sprawdzić to można liniowo w taki sposób:
Kod: Zaznacz cały
int start = 0;
   for(int i = 1; i < n; i++) {
      if(B[i].first - B[start].first + abs(B[start].second) <= abs(B[i].second)) {
         useless[i] = true;
      } else {
         start = i;
      }
   }
   start = n - 1;
   for(int i = n - 2; i >= 0; i--) {
      if(B[start].first - B[i].first + abs(B[start].second) <= abs(B[i].second)) {
         useless[i] = true;
      } else {
         start = i;
      }
   }


Jak już usunęliśmy wszystkie bezużyteczne miasta z dołu to wystarczy dla każdego miasta z górnej strony konfliktu znaleźć odległość do dwóch miast z dołu. Tego, którego współrzędna X jest największa możliwa lecz mniejsza lub równa współrzędnej X tego miasta z góry oraz miasta, którego współrzędna X jest najmniejsza lecz nie mniejsza niż tego miasta z góry. To też można zrobić liniowo w chyba dość oczywisty sposób (2 pointery).
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07

Re: Runda 29 - omówienie zadań

Postautor: Stonefeang » 28 sie 2016, 21:02

Zadanie tekstowe da się rozwiązać również z pomocą tablicy sufiksowej (jeśli do jej konstrukcji użyjemy algorytmu KS, to złożoność jest liniowa). Chcemy uzyskać tablicę sufiksową drugiego słowa z lekką modyfikacją, mianowicie chcemy, by dla każdego sufiksu znać jeszcze długość najdłuższego jego prefiksu występującego w pierwszym słowie. Można to łatwo zrobić mając policzoną tablicę dla połączonych słów. Dla dowolnego sufiksu drugiego słowa optymalnymi kandydatami są najbliższy sufiks pierwszego słowa na prawo i na lewo (w posortowanej tablicy). Mając policzone te wartości "przycinamy" tablicę drugiego słowa zmniejszając długości sufiksów w niej występujących (i odpowiednio zmniejszając wartości w tablicy lcp). Teraz, gdy każde słowo z drugiej tablicy występuje gdzieś w pierwszym słowie nasze zadanie brzmi "mając daną tablicę sufiksową (zmodyfikowaną, więc być może nieistniejącego słowa) policz ile słów z niej występuje w niej dokładnie k razy". Jeśli jakieś słowo ma występować k razy, to na pewno zawiera k sąsiednich pozycji w tablicy sufiksowej. Iterujemy się teraz po tym gdzie umiejscowimy nasz przedział. Znamy najdłuższy wspólny prefiks wszystkich sufiksów z danego przedziału biorąc minimum z tablicy lcp (używamy kolejki monotonicznej, by utrzymać liniową złożoność). Możliwe jest jednak, że znaleziony prefiks występuje więcej niż k razy. Dzieje się to wtedy, gdy rozszerzenie przedziału o jeden na prawo lub na lewo nie zmniejszy długości najdłuższego wspólnego prefiksu. Jeśli jednak dzieje się tak, że najdłuższy wspólny prefiks na przedziale ma długość x, rozszerzenie przedziału na lewo zmniejszy go do a (a<x), a na prawo do b (b<x), to owa "nadwyżka" (czyli x-max(a, b)) występuje dokładnie k razy, więc liczymy ją do wyniku.
Stonefeang
 
Posty: 1
Rejestracja: 28 sie 2016, 20:39

Re: Runda 29 - omówienie zadań

Postautor: Crucian » 28 sie 2016, 21:41

@Stonefeang:
Ajj. Moje niedokończone rozwiązanie do tego zadania było podobne do Twojego z tym, że najpierw rozwiązałem "mając daną tablicę sufiksową policz ile słów z niej występuje w niej dokładnie k razy", a dopiero potem z tych znalezionych słów występujących k razy chciałem wyznaczyć te które występują w pierwszym słowie (co mi nie wyszło), tak więc nie udało mi się zrobić tej części, którą "można łatwo zrobić", a zrobiłem to co trzeba zrobić po niej :lol:.
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07


Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Google [Bot] i 2 gości

cron