Omówienie zadania Reprezentanci firmy (eliminacje do IOI 2020, dzień 1)

Formalnie - treść zadania

W zadaniu dany mamy ciąg \(n \leq 200\ 000\) liczb \(c_1, c_2, \dots c_n\) oznaczające koszt wybrania \(i\)-tego indeksu. Ponadto mamy dane \(m \leq 200\ 000\) wymagań postaci: na przedziale \([s_j, t_j]\) należy wybrać przynajmniej \(p_j\) indeksów (\(1 \leq j \leq m\)).

Podzadanie 1 – \(n, m \leq 20\)

W tym podzadaniu możemy przeglądać brutalnie wszystkie podzbiory indeksów oraz dla każdego wymagania sprawdzić, czy wybraliśmy odpowiednią liczbę indeksów na każdym z przedziałów. Wypisujemy minimalną sumę kosztów spośród podzbiorów spełniających warunki zadania. Złożoność: \(O(2^n mn)\).

Podzadanie 2 – \(n, m \leq 2500 \)

Zauważmy, że przedziały mają bardzo charakterystyczną strukturę - albo są rozłączne, albo się w sobie zawierają. To nasuwa pomysł, żeby spełniać wymagania dla krótszych przedziałów wcześniej. Wtedy przetwarzając jakikolwiek przedział \([l_j, r_j]\) wiemy, że wszystkie zawierające się w nim przedziały zostały już przetworzone (bo są krótsze), a więc ich wymagania spełnione.

Utrzymujmy aktualny zbiór wybranych indeksów \(I\). Posortujmy przedziały od najkrótszych do najdłuższych i spełniajmy wymagania w takiej właśnie kolejności. Dla ustalonego przedziału \([l_j, r_j]\) weźmy koszty wszystkich niewybranych jeszcze indeksów. Dopóki mniej niż \(p_j\) elementów na przedziale jest wybrane, znajdujmy niewybrany jeszcze indeks o minimalnym koszcie oraz dodajmy go do \(I\). Można to zrealizować poprzez posortowanie przedziału \([l_j, r_j]\) indeksów po kosztach oraz sprawdzenie wszystkich takich elementów w kolejności niemalejącej kosztów.

Dzięki posortowanej kolejności przedziałów wiemy, że zawsze w momencie przetwarzania przedziału \([l, r]\) wszystkie zawierające się w nim będą już przetworzone i ich wymagania - spełnione. Ponieważ wybrane indeksy w \(I\) tworzyły optymalne rozwiązanie w zawierających się przedziałach, to również to będzie optymalne w przedziale \([l, r]\). Następnie musimy dołożyć elementy, by przynajmniej \(p\) elementów było wybranych. Jasnym jest, że wybranie elementów o minimalnym koszcie powoduje, że suma kosztów będzie minimalna.

Otrzymujemy rozwiązanie działające w złożoności czasowej \(O(nm\log n)\), ponieważ przedział wymagania może mieć długość \(O(n)\), zatem sortowanie każdego takiego przedziału będzie działać w złożoności \(O(n \log n)\).

Podzadanie 3 – wystarczy wybrać jeden indeks, tzn. \(p_j = 1\)

Możemy tutaj usprawnić rozwiązanie poprzedniego podzadania - zamiast sortować cały przedział wystarczy znaleźć indeks \(i\) o minimalnym \(c_i\) oraz wybrać go, jeśli nie został jeszcze wcześniej wybrany. Zbiór \(I\) możemy trzymać jako \(\texttt{set}\). Wtedy sprawdzenie czy przynajmniej jeden indeks został już wybrany na przedziale \([l, r]\) sprowadza się do sprawdzenia czy pierwszy element w \(I\), który jest większy lub równy \(l\), jest także mniejszy od \(r\).

Ponadto strukturą danych, która pozwala nam na znalezienie minimum na przedziale, jest przykładowo drzewo przedziałowe. W takim drzewie w \(i\)-tym liściu możemy trzymać parę \((c_i, i)\) oraz zastępować ją parą \((\infty, i)\), jeśli \(i\)-ty indeks zostanie wybrany (żeby nie wybrać tego samego indeksu drugi raz).

Przedstawione rozwiązanie działa w złożoności \(O((n+m)\log n + m\log m)\).

Podzadanie 4 – dla każdego indeksu \(c_i = 1\)

W tym zadaniu również będziemy usprawniać rozwiązanie z podzadania 2 - ponieważ wszystkie koszty są równe, to nie trzeba ich sortować i wystarczy jedynie pamiętać, ile indeksów zostało już wybranych na przedziale \([l_j, r_j]\). Zauważmy, że to nie ma znaczenia, które dokładnie indeksy dołożymy do zbioru \(I\) w trakcie wykonywania algorytmu. Dzieje się tak dlatego, że wszystkie dłuższe przedziały \([l_k, r_k]\), które zostaną rozpatrzone później, będą rozłączne z \([l_j, r_j]\) lub będą całkowicie zawierać w sobie przedział \([l_j, r_j]\), zatem kumulatywna ilość wybranych indeksów w \([l_k, r_k]\) jest taka sama niezależnie od tego, jakie indeksy zostaną wybrane wewnątrz przedziału \([l_j, r_j]\).

\(I\) możemy aktualizować przykładowo poprzez utrzymywanie drzewa przedziałowego, w którym w \(i\)-tym liściu będzie \(1\), jeśli \(i\) należy do \(I\) oraz \(0\) w przeciwnym przypadku. Wówczas liczba indeksów uprzednio wziętych będzie sumą na przedziale. Utrzymując dodatkowo \(\texttt{set}\) z niewybranymi indeksami możemy znajdować pierwszy niewybrany indeks \(k \geq l_j\) oraz dokładać go do zbioru \(I\). Alternatywnie, taki indeks można znaleźć za pomocą wyszukiwania binarnego na drzewie przedziałowym (zaczynając od korzenia schodzimy w dół drzewa szukając pierwszego zera na ustalonym przedziale).

Pełne rozwiązanie

Wykorzystajmy pomysły z poprzednich podzadań: na drzewie przedziałowym możemy utrzymywać zbiór \(I\) i w ten sposób jesteśmy w stanie szybko się dowiedzieć, ile jest już wybranych indeksów na ustalonym przedziale \([l_j, r_j]\), więc wiemy, ile jeszcze elementów należy dołożyć, by spełnić wymaganie (na podstawie podzadania 4).

Pozostaje problem znajdowania niewybranego indeksu o najmniejszym koszcie na przedziale. Ale ten problem rozwiązaliśmy już w podzadaniu 3, korzystając z drzewa przedziałowego (przedział-punkt) znajdującego minimum na przedziale. Skorzystajmy z tego pomysłu. W \(i\)-tym liściu drzewa trzymajmy parę liczb \((c_i, i)\), jeśli indeks \(i\) nie był jeszcze wybrany oraz parę \((\infty, i)\) w przeciwnym przypadku. Wówczas jesteśmy w stanie szybko znaleźć minimalny koszt \(c_m\) oraz jego indeks \(m\). Następnie możemy w drugim drzewie przedziałowym utrzymującym zbiór \(I\) ustawić indeks \(m\) jako wybrany (czyli ustawić \(1\)) oraz w drzewie minimów pod indeksem \(m\) ustawić sztuczny "koszt" \(\infty\), żeby nie wybierać tego samego indeksu więcej niż raz.

Opisane rozwiązanie ma złożoność \(O((n+m)\log n)\), co wynika z sortowania przedziałów po długościach oraz utrzymywania dwóch drzew przedziałowych.

Alternatywne rozwiązanie – "mniejszy do większego"

Możemy znowu skorzystać z charakterystycznej struktury przedziałów, które albo są rozłączne, albo zawierają się w sobie. Budzi to skojarzenia ze strukturą drzewa, w której zbiory wierzchołków znajdujących się w jednym poddrzewie również są albo parami rozłączne, albo zawierają się w sobie. Stwórzmy zatem las drzew, którego wierzchołki będą reprezentować przedziały, a krawędzie będą pomiędzy dwoma wierzchołkami \(a, b\) wtedy i tylko wtedy, gdy:

• przedział \(b\) zawiera się w przedziale \(a\) lub przedział \(a\) zawiera się w przedziale \(b\) - załóżmy bez straty ogólności ten pierwszy przypadek
• nie istnieje przedział \(c\) taki, że przedział \(b\) zawiera się w przedziale \(c\) i przedział \(c\) zawiera się w przedziale \(a\)

Taki las możemy zbudować techniką zamiatania. Sortujemy początki i końce przedziałów wymagań oraz przechodzimy je od lewej do prawej, za każdym razem pamiętając na stosie zbiór otwartych przedziałów. Jeśli w trakcie przeglądania punktów trafimy na początek pewnego przedziału, to albo jest to korzeń, albo przypisujemy mu rodzica będącego indeksem przedziału na górze stosu oraz dodajemy ten przedział na stos. Jeśli trafimy na koniec przedziału, to usuwamy przedział ze stosu. Jednocześnie, każdemu indeksowi przypisujemy numer najmniejszego przedziału, w jakim on się zawiera (czyli po prostu tego na górze stosu).

Znajdowanie wymagań możemy rozwiązać niezależnie dla każdego drzewa w takim lesie. Wówczas możemy w trakcie wykonywania algorytmu DFS obliczać, jaki jest minimalny koszt spełnienia wymagania dla przedziału \([l, r]\) odpowiadającemu wierzchołkowi w drzewie. Wystarczy w tym celu znać utrzymywać sumę kosztów wybranych w poddrzewie (przedziałach zawierających się w \([l, r]\)) oraz utrzymywać (np. na strukturze multiset koszty niewybranych jeszcze indeksów na przedziale \([l, r]\).

Ustalmy wierzchołek \(v\) odpowiadający przedziałowi \([l, r]\). By znaleźć wszystkie niewybrane jeszcze koszty na przedziale \([l, r]\) należy do naszej struktury dodać:

• koszty indeksów, które nie należały do żadnego mniejszego przedziału wewnątrz \([l, r]\) - indeksy te policzyliśmy w trakcie konstruowania drzewa. Dodawanie takich kosztów ma zamortyzowany koszt liniowy, ponieważ każdy indeks rozpatrzymy maksymalnie raz.
• niewybrane koszty z multisetów dzieci wierzchołka \(v\).

Skupmy się zatem na tym drugim przypadku. Brutalne łączenie multisetów dzieci spowoduje, że pesymistyczna złożoność czasowa algorytmu stanie się kwadratowa, np. w przypadku \(O(m)\) przedziałów parami zawierających się w sobie. Dlatego w celu poprawy złożoności, skorzystajmy z techniki "small to large". Polega ona na tym, że największy multiset zamienimy miejscami z multisetem wierzchołka \(v\) (wykorzystując \(\texttt{swap}\) działający w złożoności \(O(1)\)) i dodamy do niego elementy z mniejszych multisetów. W ten sposób każdy koszt \(c_i\) zostanie przeniesiony do multiseta rodzica tylko \(O(\log n)\) razy (bo za każdym razem wielkość multiseta zawierającego \(c_i\) się zwiększy co najmniej dwukrotnie). Więcej o tej technice można przeczytać np. w tym artykule.

Finalna złożoność czasowa rozwiązania to \(O((n+m)\log^2 n)\), gdzie \(O(\log n)\) to złożoność każdej operacji przeniesienia na strukturze multiset, a drugi czynnik logarytmiczny wynika z wykonania techniki "mniejszy do większego".