Slajdy (omówienie)

30.11.2011

Podstawowe rozwiązanie

Zadanie polega na znalezieniu liczby różnych wspólnych niepustych podciągów trzech permutacji - kolejności slajdów wg Sławka, Hektora i Wiktora). Permutacja Sławka ma jednak postać $ (1,2,3,...,n) $, co sprowadza powyższe do znalezienia liczby różnych wspólnych niepustych podciągów rosnących dwóch permutacji $ p_1 $ i $ p_2 $.

Dla każdego $ i $ niech $ Q_i = (p_1(i), p_2(i)) $, czyli $ Q_i $ to para złożona z pozycji liczby $ i $ w obu permutacjach. Oznaczmy przez $ L_k $ liczbę różnych wspólnych podciągów rosnących permutacji $ p_1 $ i $ p_2 $, których ostatnim wyrazem jest liczba $ k $. Nietrudno zauważyć, że poszukiwana łączna liczba rosnących podciągów to $ \sum_{i} L_i $. Tak więc aby rozwiązać zadanie należy wyliczyć wartości $ L_i $ dla poszczególnych $ i $.

Zauważmy, że dla każdego $ k $:

$$ L_k = 1 + \sum{\substack{i < k \\ p_1(i) < p_1(k) \\ p_2(i) < p_2(k)}} L_i $$

Powyższe zachodzi, gdyż każdy z ciągów kończących się na $ k $ jest albo ciągiem jednoelementowym (stąd jedynka przed sumą) albo przedłużeniem jakiegoś ciągu wyliczonego już wcześniej. Z tej równości otrzymujemy od razu algorytm działający w czasie $ O(n^2) $, który wystarczał do zdobycia większości punktów (7 lub 8 w zależności od implementacji). Bardziej zaawansowani zawodnicy mogli spróbować (i niektórym się udało) zaimplementować szybsze rozwiązanie.

Szybsze rozwiązanie

Aby przyspieszyć powyższy algorytm skorzystamy z drzew przedziałowych. Właściwie same drzewa przedziałowe nie wystarczą, utworzymy drzewo przedziałowe drzew przedziałowych. W liściach drzewa nadrzędnego będziemy trzymać aktualne wartości $ L_i $ (na początku same zera) w kolejności posortowanej po pierwszej współrzędnej $ Q_i $ (czyli po $ p_1(i) $). Każdy wewnętrzny węzeł drzewa nadrzędnego niech będzie drzewem przedziałowym złożonym z tych elementów, których odpowiadające liście są potomkami (być może dalekimi) danego węzła. Elementy wewnątrz każdego węzła są posortowane po drugiej współrzędnej $ Q_i $, czyli po $ p_2(i) $.

Wartości $ L_i $ liczymy po kolei dla $ i=1,2,3,...,n $. Najpierw liczymy $ L_i $, a następnie obliczoną wartość $ L_i $ wstawiamy do drzewa nadrzędnego. Każda operacja wstawiania lub obliczania $ L_i $ kosztuje $ O(log^2 n) $, gdyż odwołujemy się do $ O(log n) $ węzłów, a w każdym z węzłów wykonujemy $ O(log n) $ operacji. Złożoność całego algorytmu wynosi więc $ O(n log^2 n) $.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com