Informatyczny kącik olimpijski

Fotoradary

W tym kąciku omówimy zadanie Fotoradary, które pojawiło się w 2013 roku na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

Zadanie. W Bajtogrodzie jest $|n$ skrzyżowań, połączonych $| n− 1$ dwukierunkowymi odcinkami dróg, które umożliwiają dotarcie z każdego skrzyżowania do wszystkich pozostałych. Burmistrz Bajtogrodu zamierza postawić na skrzyżowaniach jak najwięcej fotoradarów (na każdym co najwyżej jeden). Aby nie denerwować zbytnio bajtogrodzkich kierowców, przyjął on, że na każdej trasie może stać co najwyżej $k$ fotoradarów.

Innymi słowy, w zadaniu mamy dane drzewo o $n$ wierzchołkach i mamy zaznaczyć w nim jak najwięcej wierzchołków tak, by na każdej ścieżce prostej było zaznaczonych co najwyżej $k$ wierzchołków.

Zadanie ma całkiem proste rozwiązanie zachłanne. Podzielmy wierzchołki na warstwy (Rys. 1). W $| i$ -tej warstwie (licząc od 1) będą znajdować się wierzchołki, które zostają liśćmi po usunięciu warstw o numerach $|1,...,i− 1.$ Jeśli $k$ jest parzyste, to zaznaczamy wierzchołki na pierwszych $|k/2$ warstwach (oczywiście, jeśli jest mniej niż $|k/2$ warstw, to bierzemy wszystko). Jeśli $| k$ jest nieparzyste, to zaznaczamy $| ⌊k/2⌋$ warstw oraz dowolny inny wierzchołek (jeśli jakiś pozostał).

Powyższy pomysł można zrealizować w czasie $| O(n)$ : utrzymujemy kolejkę wierzchołków o stopniu 1 i usuwamy kolejne warstwy, uaktualniając stopnie wierzchołków.

Alternatywne rozwiązanie wyznacza numery warstw dla wierzchołków, korzystając z metody programowania dynamicznego. Numer warstwy dla wierzchołka $|v$ jest to druga co do wielkości wysokość poddrzewa zaczepionego w dziecku $| v$ plus 1.

Pozostaje nam pokazać poprawność algorytmu zachłannego. Zauważmy, że wystarczy badać, czy warunek poprawności (nie więcej niż $| k$ zaznaczonych wierzchołków na ścieżce) jest spełniony na każdej ścieżce prostej od liścia do liścia. Oczywiste jest, że nasz algorytm znajduje poprawny podzbiór wierzchołków, i należy wykazać, że jest on optymalny (najliczniejszy). Ponadto widać, że dołożenie dowolnego wierzchołka do znalezionego podzbioru powoduje, że podzbiór staje się niepoprawny.

Ustalmy $|k$ parzyste i oznaczmy przez $K$ zbiór wierzchołków z pierwszych $|k/2$ warstw. Weźmy dowolne rozwiązanie optymalne i załóżmy, że pewien wierzchołek $v ∈K$ nie został w tym rozwiązaniu zaznaczony (Rys. 2). Jeśli jest więcej takich wierzchołków, to weźmy ten z warstwy o najmniejszym numerze (i oznaczmy numer tej warstwy przez $ℓ$ ). Rozważmy pewien zaznaczony wierzchołek $u, |$ który jest na warstwie wyższej niż $|ℓ$ i taki, że pomiędzy $v$ i $u$ nie ma zaznaczonych wierzchołków (gdyby wierzchołek $| u$ nie istniał, to by znaczyło, że rozwiązanie ma za mało zaznaczonych wierzchołków, aby być optymalne). Pokażemy teraz, że usuwając ze zbioru zaznaczonych wierzchołków $u$ i dodając $|v,$ dostaniemy poprawne rozwiązanie.

Rozważmy zatem dowolną ścieżkę $p$ od liścia $|x$ do liścia $|x′$ i pokażmy, że po zamianie zawiera ona nadal nie więcej niż $|k$ zaznaczonych wierzchołków. Podejrzana ścieżka $| p$ musi zawierać wierzchołek $| v.$ Jeśli zawiera również wierzchołek $|u,$ to po zamianie liczba zaznaczonych wierzchołków w $p$ nie zmieni się. Załóżmy zatem, że $p$ nie zawiera $|u$ i rozważmy dowolną ścieżkę od liścia $| x$ do liścia $| y,$ która zawiera oba wierzchołki $|u$ i $v.$ Niech $w$ będzie wierzchołkiem pomiędzy $v |$ a $|u,$ który rozdziela te ścieżki. Ścieżka z $y$ do $w$ zawierała przed zamianą co najmniej $|ℓ− 1$ zaznaczonych wierzchołków na jej końcu (bo założyliśmy, że najmniejsza warstwa z niezaznaczonym wierzchołkiem to $| ℓ$ ) plus dodatkowo wierzchołek $|u.$ Z kolei ścieżka z $x$ do $w$ po zamianie zawiera dokładnie $ℓ$ wierzchołków (pamiętamy, że pomiędzy $v |$ a $|u$ nie ma zaznaczonych wierzchołków). Zatem poprawna przed zamianą ścieżka z $| ′ x$ do $| y$ zawierała co najmniej tyle zaznaczonych wierzchołków, co ścieżka $p$ po zamianie. To dowodzi poprawności ścieżki $p.$

Tak więc, korzystając wielokrotnie z udowodnionego faktu, stwierdzamy, że istnieje rozwiązanie optymalne, które zaznacza wszystkie wierzchołki z $K,$ zatem zbiór wierzchołków generowany przez nasz algorytm jest najliczniejszy. Dowód dla $k$ nieparzystego zostawiamy jako ćwiczenie dla Czytelnika.