Omówienie zadania Prawnicy (I etap XXV OI)

W zadaniu mamy dane \(n\) przedziałów. Chcielibyśmy wybrać \(k\) takich przedziałów, by ich przecięcie tworzyło jak najdłuższy przedział.

Najprostsze podejście

Skoro interesuje nas najlepszy podzbiór \(k\)-elementowy, to aby rozwiązać zadanie jak najprościej, możemy sprawdzić, jaki jest wynik dla każdego \(k\)-elementowego podzbioru. Jest ich \(\binom{n}{k}\), a sprawdzenie wykonujemy w czasie \(O(k)\), więc otrzymujemy złożoność \(O\left(\binom{n}{k} \cdot k\right)\). To wystarczy, by rozwiązać pierwsze podzadanie.

Co możemy się z tego dowiedzieć?

Zastanówmy się, gdzie znajduje się początek, a gdzie koniec przecięcia przedziałów, jeżeli jest ono niepuste. Początek znajduje się tam, gdzie najpóźniejszy początek spośród rozpatrywanych przedziałów. Koniec analogicznie, lecz tym razem interesuje nas najwcześniejszy spośród końców przedziałów.

Czy pomaga nam to w zredukowaniu liczby operacji?

Okazuje się, że bardzo. Mianowicie, powyższy fakt mówi nam, że zarówno liczba początków, jak i liczba końców przedziału wynikowego jest z góry ograniczona przez \(n\). W takim razie liczba przedziałów, które są kandydatami na wynik, jest z góry ograniczona przez \(n^2\).

Rozwiązanie wielomianowe

Dla każdego przedziału będącego kandydatem (opisanego przez początek jakiegoś przedziału i koniec potencjalnie innego), jeżeli na spotkaniu może być co najmniej \(k\) prawników, to jest to dobry przedział i możemy rozpatrzeć go w wyniku. Rozwiązanie to działa w złożoności czasowej \(O(n^3)\) i przechodzi pierwsze dwa podzadania.

Dalsze optymalizacje

Chcielibyśmy jeszcze bardziej zredukować liczbę kandydatów. Zadajmy sobie w tym momencie ważne pytanie – ile potencjalnych końców musimy rozpatrywać dla założonego początku? Aby odpowiedzieć na to pytanie, na początku zobaczmy, że interesują nas jedynie końce tych przedziałów, których początki znajdują się nie później niż założony początek. Spójrzmy więc na te końce w kolejności niemalejącej. Zauważmy, że im dalszy koniec rozpatrujemy, tym mniej prawników mamy do dyspozycji do naszego spotkania (kolejni prawnicy przestają być dostępni).

Wróćmy więc do naszego pytania. Jeżeli wraz z rozważaniem coraz dalszych końców, liczba prawników do dyspozycji maleje, to interesuje nas dokładnie jeden koniec! Ten, dla którego liczba prawników do dyspozycji jest równa dokładnie \(k\).

Znajdywanie optymalnego końca

Pozostało nam jedynie zaimplementować nasze rozwiązanie. Przeglądając początki przedziałów w kolejności rosnącej, możemy trzymać w pamięci \(k\) najdalszych końców przedziałów, które zaczynają się nie później niż przedział obecnie rozpatrywanego prawnika. Możemy to zrobić za pomocą struktury std::set w języku C++. Osiągamy zatem złożoność czasową \(O(n \log n)\) oraz pamięciową \(O(n)\).