Omówienie zadania Konduktor (II etap XXV OI)

Mamy \(n\) odcinków na prostej, \(i\)-ty o końcach \([a_i, b_i]\). Należy zaznaczyć na prostej jak najmniej punktów o różnych współrzędnych całkowitych, tak by każdy odcinek zawierał co najmniej jeden punkt. Ile jest możliwych rozwiązań?

Pierwsza część: algorytm zachłanny

Zadanie wyznaczenia minimalnej liczby punktów jest dosyć klasycznym problemem i do jego rozwiązania można zastosować strategię zachłanną.

Przepatrujemy odcinki w kolejności prawych końców \(b_i\). Dla każdego odcinka, który nie zawiera żadnego wcześniej zaznaczonego punktu, umieszczamy nowy punkt w końcu \(b_i\) (tak by pokrył odcinek \(i\)-ty i możliwie dużo kolejnych odcinków).

W ten sposób umieścimy \(s\) punktów na końcach \(s\) rozłącznych odcinków \(\alpha_1, \ldots, \alpha_s\). Ten podzbiór jest jednocześnie świadkiem, że nasze rozwiązanie jest optymalne, bo potrzebujemy co najmniej \(s\) punktów by pokryć \(s\) rozłącznych odcinków.

Ten algorytm zadziała w czasie \(O(n \log n)\), bo wymagamy początkowego posortowania odcinków.

Uproszczenie

Zrobimy jeszcze pewne uproszczenie w naszych danych. Zauważmy, że jeżeli mamy odcinek, który w całości zawiera jakiś inny odcinek, to ten dłuższy odcinek można całkowicie pominąć (bo każdy punkt zawarty w krótszym odcinku będzie zawarty w dłuższym).

Kiedy pozbędziemy się takich przypadków, to odcinki będą miały ciekawą właściwość, a mianowicie sortowanie ich po końcach \(b_i\), będzie dawało dokładnie taką samą kolejność, jak sortowanie po początkach \(a_i\). Jako ćwiczenie zostawiamy zastanowienie się nad tym, w jaki sposób przeprowadzić tę operację usuwania w całkowitym czasie \(O(n \log n)\).

Druga część: programowanie dynamiczne

Ustalmy zbiór \(s\) odcinków \(\alpha_1, \ldots, \alpha_s\) znajdowany przez rozwiązanie zachłanne. Pozostałe odcinki dzielimy na zbiory \(A_1, \ldots, A_s\), gdzie \[A_i = \{ j \mid a_j < b_{\alpha_i} \le b_j \},\] czyli są to odcinki, których początek jest częściowo pokryty przez \(\alpha_i\). Z optymalności i warunku upraszczającego wynika, że to rzeczywiście jest podział.

Teraz oś liczbową dzielimy na sekcje. Miejscami podziału są punkty będące początkami i końcami odcinków (czyli każdy punkt w ustalonej sekcji należy do tych samych odcinków). Jest \(O(n)\) sekcji. Każdy odcinek \(\alpha_i\) też jest podzielony na odpowiednie sekcje i suma sekcji dla wszystkich \(\alpha_1, \ldots, \alpha_s\) jest też \(O(n)\).

Rozważmy wszystkie możliwości postawienia punktu \(x\) na odcinku \(\alpha_i\), aby wyznaczyć liczbę rozwiązań dla odcinków \(\alpha_i, \ldots, \alpha_s\). Zauważmy, że liczba rozwiązań \(\alpha_{i+1}, \ldots, \alpha_s\) zależy tylko od sekcji w której leży \(x\), więc wystarczy rozważać sekcje (i liczbę rozwiązań dla sekcji przemnożyć przez jej długość).

Jeśli punkt leży w \(x\), to wszystkie odcinki z \(A_i\), które mają \(a_j \leq x\) są pokryte, a pozostałe będą musiały być pokryte przez punkt z \(\alpha_{i+1}\). Tak więc jeśli \(x_R = \max\{ b_j \mid a_j > x, j \in A_i \}\), to bierzemy liczbę rozwiązań dla odcinków \(\alpha_{i+1}, \ldots, \alpha_s\) przy założeniu, że punkt z odcinka \(\alpha_{i+1}\) leży w przedziale \([a_{\alpha_{i+1}}, x_R]\).

Obliczamy zatem rozwiązanie od końca dla \(\alpha_s, \ldots, \alpha_1\). Po policzeniu rozwiązań dla \(\alpha_{i+1}\) robimy sumy prefiksowe dla jego sekcji (do wykorzystania przez \(\alpha_i\)). Jeśli odcinki w \(A_i\) rozpatrujemy malejąco po \(a_j\), to licząc sekcje \(\alpha_i\) od końca, możemy na bieżąco wyznaczać \(x_R\).

Całość rozwiązania będzie działać w czasie \(O(n\log n)\).

Podzadanie 2

Można uprościć implementację rozwiązania wzorcowego przez nieuwzględnienie sum prefiksowych. Wówczas otrzymujemy rozwiązanie o złożoności \(O(n^2)\).

Podzadanie 4

W podzadaniu ,,część wspólna dowolnych trzech odcinków jest pusta”, jeśli wyrzucimy wszystkie odcinki, które zawierają jakieś inne odcinki (a więc są na pewno pokryte), to zbiór odcinków dzieli się na rozłączne grupy – w każdej grupie mamy ciąg odcinków, z których każda kolejna para się przecina. Jeśli grupa ma liczność parzystą, to musimy zrobić kontrole na przecięciach odcinków na pozycjach \(2i-1\) oraz \(2i\). Jeśli grupa ma liczność nieparzystą, to mamy trochę więcej swobody (ale radzimy sobie prostym programowaniem dynamicznym). Całość jest nietrudna i działa w czasie \(O(n\log n)\).