Omówienie zadania Sabotaż (I etap XXIV OI)

Zacznijmy od zrozumienia, w jaki sposób przebiega proces buntu opisany w treści zadania. Załóżmy, że morale w organizacji wynoszą \(x\) \((0 \leq x \leq 1)\), zaś sabotażystą jest pracownik o numerze \(v\). Zastanówmy się, kto może dołączyć do buntu jako następny. Na pewno musi to być któryś z przełożonych¹ pracownika \(v\), gdyż pozostali mają wśród swoich podwładnych zero zbuntowanych (czyli na pewno nie więcej niż \(x\) wszystkich podwładnych). Zauważmy, że jeśli którykolwiek z przełożonych \(v\) może się zbuntować, to na pewno może się też zbuntować bezpośredni przełożony \(v\) – oznaczmy go przez \(u\). Jest tak, ponieważ wszyscy przełożeni \(v\) mają tyle samo zbuntowanych podwładnych (jednego sabotażystę), natomiast \(u\) ma najmniej wszystkich podwładnych. Jeśli zatem \(1\) stanowi więcej niż \(x\) wszystkich podwładnych któregoś z przełożonych \(v\), to warunek ten jest też w szczególności prawdziwy dla bezpośredniego przełożonego, czyli \(u\).

¹ Za każdym razem, gdy używamy słowa „przełożony" lub „podwładny" bez dodatkowego określenia, mamy na myśli zarówno bezpośrednich jak i pośrednich przełożonych lub podwładnych.

Dla każdego \(v \in \{1,2,\ldots,n\}\), poddrzewem \(v\) będziemy nazywać wszystkich podwładnych pracownika \(v\) wraz z nim samym, zaś przez \(rozmiar[v]\) oznaczymy liczbę pracowników w tym poddrzewie. Korzystając z faktu, że przełożony ma zawsze mniejszy numer od podwładnego, tablicę \(rozmiar\) możemy wyliczyć prostą pętlą w kolejności malejących wartości \(v\).

Wróćmy do rozważanej sytuacji, w której morale wynosi \(x\), sabotażystą jest pracownik \(v\) i zastanawiamy się, czy jego bezpośredni przełożony \(u\) dołączy do buntu. Jeżeli \(1 \leq x \cdot (rozmiar[u] - 1)\), to \(u\) (oraz nikt inny) nie dołączy do buntu. W przeciwnym wypadku do buntu na pewno dołączy \(u\) wraz ze wszystkimi swoimi podwładnymi. Powtarzając wcześniejsze rozumowanie, dochodzimy do wniosku, że jeśli jeszcze jacyś pracownicy dołączą do buntu, to na pewno będzie wśród nich bezpośredni przełożony \(u\) – oznaczmy go przez \(w\). Znów więc, jeżeli \(rozmiar[u] \leq x \cdot (rozmiar[w] - 1)\), to nikt więcej nie dołączy do buntu, zaś w przeciwnym wypadku do buntu dołączy \(w\) wraz z podwładnymi. Takie rozumowanie możemy kontynuować w górę drzewa, śledząc przebieg buntu.

Potrafimy zatem, w czasie \(O(n^2)\), rozstrzygnąć dla dowolnej ustalonej wartości \(x\), czy utrzymanie morale na tym poziomie pozwala ograniczyć bunt do dopuszczalnych rozmiarów. Aby to zrobić, wystarczy dla każdej spośród \(n\) możliwych tożsamości sabotażysty przeprowadzić opisaną powyżej symulację i sprawdzić, czy w którymś przypadku bunt objął więcej niż \(k\) pracowników.

Przedstawiona procedura w połączeniu z wyszukiwaniem binarnym pozwala znaleźć szukaną wartość morale. Zaczynamy wyszukiwanie w przedziale \([0;1]\). W danej iteracji, jeżeli przy morale \(x\) może zbuntować się \(k\) pracowników, to w kolejnej iteracji wyszukiwania binarnego wartość morale \(x\) powinna stać się dolnym krańcem przedziału, w przeciwnym przypadku – górnym.

Rozwiązanie działa w czasie \(O(n^2)\) z dużą stałą \(M = \log_2(10^6)\), oznaczającą liczbę iteracji wyszukiwania binarnego, potrzebną do uzyskania wymaganej precyzji 6 miejsc po przecinku. Niestety, jest to zbyt wolne rozwiązanie, aby zdobyć komplet punktów. Zanim jednak przejdziemy do rozwiązania wzorcowego, zastanówmy się, jak można rozwiązać zadanie w czasie kwadratowym bez dużej stałej wynikającej z wyszukiwania binarnego.

Rozwiązanie wolne w czasie \(O(n^2)\)

Spróbujmy powtórzyć powyższą symulację buntu, w dalszym ciągu ustalając na początku tożsamość sabotażysty \(v\). Tym razem jednak nie będziemy precyzowali wartości morale. Rozpoczniemy od maksymalnej możliwej wartości \(x=1\) i będziemy ją w trakcie symulacji obniżać – skłaniając do buntu kolejnych przełożonych – tak, aby proces się nie zatrzymał, dopóki nie zbuntuje się więcej niż \(k\) pracowników.

Powyższa funkcja oblicza morale, jakie trzeba zapewnić, żeby w sytuacji, gdy sabotażystą jest pracownik o numerze \(v\), rozmiar buntu nie przekroczył \(k\). Uruchamiając tę funkcję dla \(v = 1, 2, \ldots, n\) oraz obliczając maksimum ze zwróconych wartości otrzymujemy rozwiązanie zadania.

Uważny Czytelnik zwrócił już zapewne uwagę, że przy takiej implementacji pętla while wykona się nie więcej niż \(k\) razy. Wszak za każdym razem wartość \(\ell\) rośnie co najmniej o jeden. Przedstawione rozwiązanie działa zatem w czasie \(O(nk)\). W pesymistycznym przypadku to wciąż jest \(O(n^2)\), ale z opisu podzadań w treści zadania wynika, że taka uważna implementacja algorytmu kwadratowego pozwala zdobyć o 13 punktów więcej.

Rozwiązanie wzorcowe w czasie \(O(n)\)

Zauważmy, że jeśli potencjalny sabotażysta ma podwładnych, to gdyby którykolwiek z nich był sabotażystą zamiast niego, to bunt objąłby tych samych pracowników i być może dodatkowo jeszcze jakichś. Możemy więc bez straty ogólności zakładać, że sabotażysta nie ma żadnych podwładnych, czyli jest liściem w drzewie.

Aby otrzymać algorytm działający w czasie \(O(n)\), wykorzystamy technikę programowania dynamicznego. Oznaczmy przez \(D[i]\) najmniejsze morale, jakie trzeba utrzymać, żeby nie dopuścić do buntu całego poddrzewa \(i\) w sytuacji, gdy sabotażysta znajduje się w tym poddrzewie.

Zastanówmy się, jak obliczać wartości tablicy \(D\) dla kolejnych pracowników \(i\). Zacznijmy od rozważenia przypadku brzegowego, w którym \(i\) nie ma żadnych podwładnych. W takiej sytuacji nie jesteśmy w stanie zapobiec buntowi jednoosobowego poddrzewa, jeśli to \(i\) okaże się sabotażystą, a zatem \(D[i]=\infty\). Jak wygląda sytuacja w ogólnym przypadku, gdy \(i\) ma podwładnych? Załóżmy przez chwilę, że wiemy, kto jest sabotażystą. Oznaczmy przez \(j\) tego bezpośredniego podwładnego \(i\), w którego poddrzewie znajduje się sabotażysta.

Taki podwładny zawsze istnieje, o ile sabotażystą nie jest sam \(i\), co jednak już wykluczyliśmy, bo \(i\) nie jest liściem. Żeby \(i\) wraz z całym swoim poddrzewem dołączył do buntu, muszą zostać spełnione dwa warunki. Po pierwsze, najpierw musi zbuntować się \(j\), czyli morale musi być niższe niż \(D[j]\). Po drugie, \(i\) musi dołączyć do buntu, czyli morale musi być niższe niż \(\frac{rozmiar[j]}{rozmiar[i] - 1}\). Wystarczy zatem utrzymywać morale na poziomie \(\min\!\left(D[j], \frac{rozmiar[j]}{rozmiar[i] - 1}\right)\), żeby zapobiec buntowi \(i\) w rozważanej sytuacji. Tak naprawdę nie znamy jednak tożsamości sabotażysty. Musimy więc zabezpieczyć się dla każdego możliwego wyboru \(j\) spośród bezpośrednich podwładnych \(i\). Podsumowując, kolejne wartości tablicy \(D\) możemy obliczać na podstawie równości:

\[ D[i] = \max \left\{\min\!\left(D[j], \frac{rozmiar[j]}{rozmiar[i] - 1}\right) \bigg\vert\ j \text{ bezpośredni podwładny } i\right\}. \]

Podobnie jak w przypadku tablicy \(rozmiar\), i tu możemy wykorzystać fakt, że przełożony ma zawsze mniejszy numer od podwładnego, aby wyliczyć tablicę \(D\), stosując powyższe równanie w prostej pętli w kolejności malejących wartości \(i\).

Na koniec musimy przeiterować się po wszystkich pracownikach, obliczając maksimum z wartości \(D[i]\) dla tych, dla których \(rozmiar[i]\) przekracza \(k\). Utrzymując morale na poziomie tak obliczonego maksimum, gwarantujemy, że potencjalny bunt może objąć co najwyżej poddrzewo zawierające \(k\) lub mniej pracowników.

Rozwiązanie działa w czasie \(O(n)\).

Rozwiązanie alternatywne

W tym rozwiązaniu wykorzystamy wyszukiwanie binarne, które pozwoli nam uprościć programowanie dynamiczne. Załóżmy, że wartość morale \(x\) jest ustalona i chcemy rozstrzygnąć, czy istnieje taki pracownik, który jako sabotażysta doprowadziłby do buntu ponad \(k\) pracowników.

Niech \(B[i]\) oznacza, czy przy morale \(x\), dojdzie do buntu całego poddrzewa \(i\), gdyby sabotażysta znajdował się w tym poddrzewie. Przeprowadzając rozumowanie podobne do wcześniejszego, możemy wyprowadzić następujący wzór: \[ B[i] = \exists_{j \text{ bezpośredni podwładny } i}\ (B[j]\ \land\ rozmiar[j] > x \cdot (rozmiar[i] - 1)). \]

Wyszukiwanie binarne zaczynamy dla przedziału \([0;1]\). W danej iteracji, jeżeli przy morale \(x\) może zbuntować się \(k\) pracowników (tzn. istnieje poddrzewo liczące więcej niż \(k\) wierzchołków, dla którego wartość w tablicy \(B\) jest równa true), to w kolejnej iteracji wyszukiwania binarnego wartość morale \(x\) powinna stać się dolnym krańcem przedziału, w przeciwnym przypadku – górnym.

Rozwiązanie to działa w czasie \(O(n)\), jednak ma dużą stałą równą liczbie iteracji wyszukiwania binarnego. Liczba iteracji jest stała, ponieważ w treści zadania została podana oczekiwana dokładność wyniku.

Wyszukiwanie binarne ma jednak jeszcze jedną wadę. Zauważmy, że z opisu rozwiązania wzorcowego łatwo wywnioskować, że poprawna odpowiedź jest zawsze liczbą wymierną, dającą się przedstawić jako ułamek z licznikiem i mianownikiem nie większymi niż \(n\). Co więcej, gdyby treść zadania tego od nas wymagała, łatwo moglibyśmy zmodyfikować rozwiązanie wzorcowe tak, żeby ten licznik i mianownik wyznaczać. W przypadku rozwiązania opartego o wyszukiwanie binarne, taka modyfikacja jest niemożliwa.