CERC 2010: Szkice rozwiązań

28.11.2010

D: Defense Lines

Treść (pdf) | wyślij rozwiązanie.

Niech A[1..n] bedzie danym ciągiem wysokości wież. Przez podciąg będziemy rozumieli podciąg spójny. Na początku wykonamy działający w czasie liniowym preprocessing: dla każdego i obliczymy wartość starting[i] będącą długością najdłuższego podciągu rosnącego zaczynającego się na miejscu i oraz ending[i] będącą długością najdłuższego podciągu kończącego się na miejscu i.

Następnie przeglądamy tablicę A od lewej do prawej. Kiedy przetwarzamy wpis A[i] = y, potencjalne rozwiązanie to długość najdłuższego ciągu rosnącego w A[1..i-1] kończącego się na wartości mniejszej niż y (długość tę oznaczamy przez best(y)) dodana do starting[i].

Aby obliczyć wartość best(y) utrzymujemy zbiór M składający się z par (x,len) posortowany po pierwszych elementach. Przykładowo może być on zaimplementowany jako drzewo binarne lub set z biblioteki STL. Para (x,len) oznacza, że istnieje podciąg rosnący (w przetworzonym już prefiksie tablicy A) o długości len kończący się na wartości x. Dla każdej wartości x, przechowujemy tylko długość najdłuższego takiego podciągu.

Następnie zaobserwujmy, że nie musimy pamiętać wszystkich takich par, skoro niektóre z nich są na pewno lepsze niż inne. Konkretnie dla dwóch par (x1, len1) i (x2, len2), gdzie x1 ≤ x2 and len1 ≥ len2, mówimy, ze para (x1, len1) dominuje parę (x2, len2) Łatwo zauważyć, że nie ma sensu przechowywać w M żadnych zdominowanych par. Dlatego też możemy założyć, że jeśli pary są posortowane w kolejności zwiększających się wartości x, odpowiadające im wartości len są również ciągiem rosnącym.

Żądana para może być znaleziona w zbiorze M za pomocą wyszukiwania binarnego. Dodatkowo, zbiór M może być następnie zaktualizowany w następujący sposób. Kiedy przetwarzamy wysokość A[i], próbujemy wstawić parę p = (A[i], ending[i]) do zbioru M biorąc pod uwagę dwa aspekty: (i) nie wstawiamy pary p, jeśli jest ona zdominowana przez elementy z M, (ii) wyrzucamy z M wszystkie pary, które są zdominowane przez p. Dostęp do elementu z M jest logarytmiczny; ponieważ wszyscy kandydaci do usunięcia stanowią ciągły podzbiór M, ich usunięcie może być wykonane w zamortyzowanym czasie stałym.

Sumarycznie całe rozwiązanie może być zaimplementowane w czasie O(n log n).

Informacje dodatkowe

Można też obliczać wartości best(y) w bardzie bezpośredni sposób. W tym celu przechowujemy pary (x,len) w liściach drzewa, jako klucza używając x a jako wartości len. Liście te są posortowane w kolejności wzrastających wartości x. Nie przejmujemy się tutaj tym, że niektóre pary dominują inne: po prostu dla danego x przechowujemy najlepszą (czyli największą) wartość len. Znalezienie best(y) to po prostu znalezienie największej wartości len dla x z przedziału [1,y-1]. Aby szukanie takiego maksimum wykonywało się w czasie logarytmicznym wykorzystujemy wewnętrzne wierzchołki drzewa, przechowując w danym wierzchołku maksimum z wartości w liściach leżących w jego poddrzewie.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com