Omówienie zadania Taksówki (III etap XXV OI)

Początkowe obserwacje

Mamy dane \(n\) funkcji liniowych \(f_1(x),\ldots,f_n(x)\). Funkcja \(f_i(x)\) jest zadana wzorem \(xc_i+s_i\). Niech \(p_1,\ldots,p_n\) będzie permutacją zbioru \(\{1,\ldots,n\}\) określającą docelowy ranking, tzn. chcemy ustalić argument \(d\) taki, żeby \(f_{p_1}(d)\) było minimalne, \(f_{p_2}(d)\) drugie w kolejności itd. Warunek na liczbę \(d\) możemy przedstawić w postaci układu nierówności pomiędzy funkcjami:

\[ \begin{aligned} \left\{ \begin{array}{l} &f_{p_1}(d) \leq f_{p_2}(d) \\ &f_{p_1}(d) \leq f_{p_3}(d) \\ &\dots \\ &f_{p_1}(d) \leq f_{p_n}(d) \\ &f_{p_2}(d) \leq f_{p_3}(d) \\ &\dots \\ &f_{p_{n-1}}(d) \leq f_{p_n}(d) \end{array} \right. \end{aligned} \]

Tych nierówności jest jednak zbyt dużo. Rozważmy prostszy układ:

\[ \begin{aligned} \left\{ \begin{array}{l} &f_{p_1}(d) \leq f_{p_2}(d) \\ &f_{p_2}(d) \leq f_{p_3}(d) \\ &f_{p_3}(d) \leq f_{p_4}(d) \\ &\dots \\ &f_{p_{n-1}}(d) \leq f_{p_n}(d) \end{array} \right. \end{aligned} \]

Wszystkie nierówności z drugiego układu zawierają się w pierwszym. Co więcej, korzystając z przechodniości relacji \(\leq\), łatwo można otrzymać każdą nierówność z pierwszego układu na podstawie nierówności z drugiego. Z tego wynika, że układy są równoważne.

Wystarczy więc patrzeć na relacje między funkcjami \(f\), które odpowiadają sąsiednim pozycjom rankingu.

Podzadanie \(n, q \leq 2000\)

Dla dwóch funkcji liniowych \(f_i\), \(f_j\), chcemy ustalić dla jakich \(x\) zachodzi \(f_i(x) \leq f_j(x)\). Rozpisując nierówność, otrzymujemy \(x \cdot (c_i - c_j) \leq s_j - s_i\).

Nierówności podzielimy na trzy typy:

• \(c_i - c_j = 0\)
• \(c_i - c_j > 0\)
• \(c_i - c_j < 0\)

W pierwszym typie, jeśli \(s_j - s_i < 0\), to niezależnie od \(x\) nierówność nigdy nie zajdzie. Natomiast jeśli \(s_j - s_i \geq 0\), to \(x\) może być dowolny.

W drugim i trzecim typie otrzymujemy ograniczenia na \(x\), odpowiednio: \(x \leq \frac{s_j - s_i}{c_i - c_j}\) oraz \(x \geq \frac{s_j - s_i}{c_i - c_j}\). Jeśli żadna nierowność pierwszego typu nie stwierdzała braku rozwiązań, to mamy teraz pewną liczbę ograniczeń górnych i dolnych na \(x\).

Musimy wyliczyć najmniejsze ograniczenie górne i największe dolne. Jeśli ograniczenie górne jest mniejsze od dolnego, to odpowiedź jest negatywna. W przeciwnym razie odpowiedzią jest dowolna liczba z zadanego przez nie przedziału. Możemy zawsze wybrać początek przedziału - w ten sposób licznik i mianownik nigdy nie przekroczą \(10^9\). Ograniczenia możemy porównywać w sposób dokładny jak ułamki zwykłe; musimy wówczas skorzystać z typu 64-bitowego przy mnożeniu liczników i mianowników.

W taki sposób otrzymamy złożoność \(O(nq)\) – dla każdej aktualizacji przejdziemy po całym rankingu i wyznaczymy ograniczenie górne i dolne.

Pełne rozwiązanie

Zauważmy, że kiedy zamieniamy dwie pozycje \(i < j\) rankingu, to w układzie nierówności zmienia się niewiele. Są to co najwyżej 4 nierówności. Wystarczy, że z układu nierówności usuniemy:

\[ \begin{aligned} \left\{ \begin{array}{l} &f_{p_{i-1}}(d) \leq f_{p_i}(d) \\ &f_{p_i}(d) \leq f_{p_{i+1}}(d) \\ &f_{p_{j-1}}(d) \leq f_{p_j}(d) \\ &f_{p_j}(d) \leq f_{p_{j+1}}(d) \end{array} \right. \end{aligned} \]

i dodamy:

\[ \begin{aligned} \left\{ \begin{array}{l} &f_{p_{i-1}}(d) \leq f_{p_j}(d) \\ &f_{p_j}(d) \leq f_{p_{i+1}}(d) \\ &f_{p_{j-1}}(d) \leq f_{p_i}(d) \\ &f_{p_i}(d) \leq f_{p_{j+1}}(d) \end{array} \right. \end{aligned} \]

oraz zmodyfikujemy permutację. Trzeba jeszcze uważać na przypadek brzegowy \(j = i + 1\).

Możemy więc utrzymywać zarówno ograniczenia górne, jak i dolne na pewnej strukturze. W momencie zamiany \(i\) z \(j\), usuniemy i dodamy odpowiednie nierówności. Zapytanie będzie polegało na sprawdzeniu czy mamy nierówności pierwszego typu, które implikują brak rozwiązań, a następnie na sprawdzeniu maksymalnego ograniczenia dolnego i minimalnego górnego.

W C++ strukturą, której możemy użyć, jest multiset. Pozwala on dodać lub usunąć element oraz zapytać o maksimum w złożoności \(O(\log n)\) oraz zapytać o minimum w czasie \(O(1)\).

Aby uzyskać lepszą stałą możemy użyć drzewa przedziałowego. \(i\)-ty liść odpowiada \(i\)-tej nierówności z układu. W każdym wierzchołku trzymamy przedział liczb, które mogą być odpowiedzią, uwzględniając nierówności z liści z jego poddrzewa. Aktualizacja polega na przejściu od liścia do korzenia w czasie \(O(\log n)\), a zapytanie na sprawdzeniu przedziału w korzeniu w czasie \(O(1)\).

To pozwala nam na rozwiązanie zadania w złożoności \(O((n + q) \log n)\). Niezależnie od wykorzystanej struktury danych takie rozwiązanie pozwalało zaliczyć wszystkie podzadania.