Omówienie zadania Zapobiegliwy student (I etap XXXI OI)

Prostszy problem

Postarajmy się najpierw rozwiązać nieco inny, prostszy problem. Załóżmy, że Bajtazar nie wymaga od nas, aby każdy wykład miał wykład zastępczy, czyli Bajtazar chce zwyczajnie wysłuchać najwięcej wykładów, jak się da. Dalej jednak nie mogą one kolidować ze sobą.

Co z tego mamy?

Powiedzmy, że znaleźliśmy w ten sposób zbiór \(k > 1\) wykładów. Możemy wziąć dowolny z tych wykładów - nazwijmy go \(z\). Pozostałe wykłady oczywiście nie kolidują z \(z\), więc jest on poprawnym wykładem zastępczym dla każdego z nich. W ten sposób uzyskujemy rozwiązanie rozmiaru \(k - 1\) oryginalnego problemu.

Z drugiej strony łatwo wywnioskować, że wynik oryginalnego problemu nie przekracza \(k\). To oznacza, że wynik wyciągnięty z prostszego problemu jest gorszy o co najwyżej \(1\).

Jak rozwiązać prostszy problem?

Zanim przejdziemy do dokończenia oryginalnego zadania, najpierw rozwiążmy ten prostszy problem. Mamy do czynienia z dosyć powszechnym problemem znalezienia najliczniejszego zbioru nieprzecinających się przedziałów. Warto o tym wiedzieć, ponieważ niejedno zadanie olimpijskie da się sprowadzić do niego (lub jego modyfikacji) - w szczególności to.

Posortujmy przedziały niemalejąco po ich prawych końcach - można do tego użyć funkcji sort na parach. Następnie będziemy zachłannie tworzyli szukany najliczniejszy zbiór. Iterujemy się po przedziałach w posortowanej kolejności. Gdy natrafiamy na przedział, który nie przecina się z ostatnio dodanym do zbioru wynikowego przedziałem, to dodajemy go. Zbiór wynikowy jest początkowo pusty, więc możemy dodać do niego pierwszy przedział. Ten algorytm produkuje poprawny zbiór, ponieważ po dostawieniu przedziału, nie przecina się on z ostatnim, więc w szczególności nie przecina się on z żadnym poprzednim - to wynika z tego, że posortowaliśmy przedziały po prawych końcach.

Dlaczego otrzymany zbiór jest najliczniejszy? Przez sprzeczność załóżmy, że istnieje liczniejszy zbiór. Posortujmy jego przedziały analogicznie. Będziemy porównywać ten zbiór ze zbiorem, który wyprodukował nasz algorytm. Weźmy pierwszy indeks, na którym te zbiory mają różny przedział. Jeśli w naszym zbiorze pod tym indeksem nie ma przedziału, to można go dodać - stąd wnioskujemy, że nie ma takiej sytuacji. Mamy więc indeks, pod którym są dwa różne przedziały, a na lewo są takie same przedziały. Nasz algorytm wybrał przedział, który kończy się nie później, więc w tym rzekomo lepszym rozwiązaniu możemy podmienić tamten przedział na nasz przedział, nie tworząc kolizji. Aplikując ten argument aż dojdziemy do końca tych zbiorów, musimy otrzymać sprzeczność.

Reszta rozwiązania

Teraz zastanawiamy się, czy możliwe jest uzyskanie wyniku \(k\). Wyobraźmy sobie rozwiązanie, które jest rozmiaru \(k\) i nie mogło ono być znalezione przez poprzednie podejście. Oznaczmy właściwe wykłady jako \(u_1, u_2, ..., u_k\), a wykłady zapasowe jako \(v_1, v_2, ..., v_k\) - oznaczenie jak z treści zadania. Każdy wykład \(v_i\) musi przecinać się z jakimś wykładem \(u_j\). Dlaczego? Jeśli wykład \(v_i\) nie przecinałby się z żadnym wykładem \(u_j\), to wcześniejsze rozwiązanie znalazłoby zbiór wielkości \(k + 1\), a także rozwiązanie wielkości \(k\). Z drugiej strony, jeśli wykład \(v_i\) przecinałby się z wykładem \(u_j\), dla \(i \neq j\), to zastępując \(u_i\) wykładem \(v_i\), będziemy mieć kolizję. Stąd wnioskujemy, że wykład \(v_i\) musi kolidować tylko i wyłącznie z wykładem \(u_i\) (chociaż może z innymi wykładami \(v\)). Jednakże jeśli ograniczymy się tylko do stwierdzenia, że \(v_i\) może kolidować z \(u_i\), to niczego nie stracimy, bo nasze poprzednie rozwiązanie wyłapie tę sytuację. Dlatego finalnie użyjemy obydwu rozwiązań i wybierzemy z nich to lepsze.

Algorytm

Mając już trochę wiedzy o tym, jakich zbiorów \(u\) oraz \(v\) szukamy, przechodzimy do właściwego rozwiązania. Wykorzystamy poprzedni algorytm do znajdowania najliczniejszego zbioru nieprzecinających się przedziałów i nieco go zmodyfikujemy. Niech \(prawy(x)\) oznacza prawy koniec przedziału \(x\). Dla wygody oznaczmy \(u_0 = v_0 = 0\) oraz \(prawy(0) = 0\). Ponownie posortujemy przedziały niemalejąco po ich prawych końcach i będziemy stopniowo budować nasze rozwiązanie. Iterujemy się po przedziałach i natrafiamy na przedział \([l, r]\). Zastanawiamy się, czy próbować go dodać do zbioru \(u\), czy do zbioru \(v\). Niech \(i = |u|\), a \(j = |v|\) (jako \(|u|\) oznaczamy rozmiar zbioru \(u\)). Aby to rozstrzygnąć, musimy rozważyć kilka przypadków.

Przypadek \(i + 1 = j\)

Zbiór \(u\) ma mniejszy rozmiar. Gdybyśmy dodali teraz nasz przedział do zbioru \(v\), to nie będzie można już dodać żadnego następnego przedziału do \(u\), ponieważ

albo będzie kolidował z \([l, r]\),
albo będzie kolidował z którymś późniejszym przedziałem z \(v\),
albo będzie niezależny, co sprowadzi nas do wyniku poprzedniego algorytmu.

Z tego powodu stwierdzamy, że jeśli możemy, to nie gorzej będzie dodać przedział \([l, r]\) do \(u\). Zatem sprawdzamy, czy \(prawy(u_i) \le l\) oraz \(prawy(v_j) \le l\) i jeśli obydwa są spełnione, to dodajemy.

Przypadek \(i = j + 1\)

Zbiór \(v\) ma mniejszy rozmiar. Na podstawie podobnego argumentu stwierdzamy, że nie gorzej będzie próbować dodać ten przedział do \(v\). Musimy sprawdzić, czy \(prawy(u_i) \le l\). Nie porównujemy się z \(v_j\), ponieważ przedziały z \(v\) mogą się przecinać.

Przypadek \(i = j\)

W tej sytuacji próbujemy najpierw dodać przedział do zbioru \(u\), a jeśli nie jest to możliwe, to próbujemy go dodać do zbioru \(v\). Argument jest taki, że w każdej sytuacji porównujemy się z ostatnim przedziałem z \(u\), więc chcemy, aby \(prawy(u_i)\) było jak najmniejsze. Formalny argument jest następujący: jeżeli istniałoby lepsze rozwiązanie, które w takim momencie dodałoby przedział \([l, r]\) do \(v\) zamiast do \(u\), to weźmy pierwszy przedział \(p\), który dodaliśmy do \(u\) po tym wydarzeniu. Jeśli takiego nie ma, to to rozwiązanie nie było lepsze, a jeśli jest, to możemy zamienić ze sobą \(p\) oraz \([l, r]\) i dalej otrzymujemy poprawne rozwiązanie. Warto samodzielnie przyjrzeć się dlaczego taka zamiana jest możliwa i dlaczego nie moglibyśmy wysunąć podobnego rozumowania na rzecz zbioru \(v\). Ten argument możemy stosować wielokrotnie, aż okaże się, że znalezione przez nas rozwiązanie jednak było nie gorsze.

Podsumowanie - złożoność

W obydwu algorytmach musimy posortować przedziały, co zajmuje nam czas \(O(n \log n)\) - na przykład przy użyciu funkcji sort. Dalsza iteracja i obliczenie wyniku trwa zaledwie \(O(n)\).