Miasta

Ty razem proponuję ciekawe zadanie interaktywne prosto ze słonecznego Kazachstanu, czyli z IOI 2015. Naszym celem będzie wyznaczenie pewnych informacji na temat drzewa (dla niepoznaki jak zwykle nazwanego siecią dróg) zadając niewiele pytań o odległości między jego liśćmi.

Dostajemy (choć nie wprost) drzewo na n liściach i pewniej liczbie wierzchołków wewnętrznych. Wiemy, że każdy wierzchołek wewnętrzny na stopień przynajmniej 3, a każda krawędź drzewa ma pewną naturalną długość. Nie znamy struktury drzewa (ani nawet nie wiemy ile jest w nim tych wierzchołków wewnętrznych; znamy tylko n), ale możemy zapytać się o odległość między dowolną parą liści. Jesteśmy proszeni o znalezienie w tym drzewie wierzchołka centralnego, czyli takiego, który minimalizuje największą z odległości do liści (a dokładniej, powinniśmy zwrócić odpowiadającą mu odległość). Ale to nie wszystko! Aby otrzymać 100 punktów, musimy jeszcze stwierdzić, czy istnieje wierzchołek centralny, którego usunięcie powoduje rozpadnięcie się całego drzewa na mniejsze, z których każde zawiera co najwyżej \lfloor \frac{n}{2}\rfloor z tych oryginalnych liści. Żeby nie było za prosto, celujemy w zadanie tylko \lceil\frac{7n}{2}\rceil pytań. Oryginalną treść można znaleźć tutaj.

Zacznijmy od wyznaczenia wierzchołka centralnego. Gdyby tylko drzewo było podane wprost, moglibyśmy przejrzeć je w głąb i skorzystać z prostego programowania dynamicznego. Niestety, nie jest. Na szczęście istnieje też inne (może nawet częściej podawane) rozwiązanie. Niech d(u,v) oznacza odległość między liściami u oraz v, gdzie u,v\in\{1,2,\ldots,n\}. Wybierzmy liść, który jest najbardziej odległy od liścia 1 i oznaczmy go u. Następnie znajdźmy liść, który jest najbardziej odległy od liścia u i oznaczmy go v. Cała operacja wymaga zadania 2(n-1) pytań.
Teraz twierdzimy, że wierzchołek centralny musi leżeć na ścieżce między u oraz v. A nawet więcej: jeśli narysujemy sobie ścieżki odpowiadające d(1,u) oraz d(1,v) i oznaczymy przez c wierzchołek centralny, cała sytuacja musi wyglądać jakoś tak:

miasta1

to znaczy c leży na wspólnej części obydwu ścieżek. Jak to udowodnić? Trzeba tylko wyobrazić sobie ścieżkę miedzy 1 a u oraz wierzchołek centralny c. Krótka analiza możliwych przypadków prowadzi do wniosku, że jeśli c nie leży na tej ścieżce, to albo c wcale nie jest wierzchołkiem centralnym (dokładniej, można przesunąć się do jednego z jego sąsiadów zmniejszając największą z odległości do liści) lub u wcale nie jest najbardziej odległym liściem. Takie samo rozumowanie pokazuje, że c leży także na drugiej ścieżce.

Okazuje się także, że \max(d(u,c),d(v,c)) jest największą z odległości do liści. Załóżmy bowiem, że tak nie jest, czyli istnieje liść x (różny od u oraz v), dla którego d(x,c)>\max(d(u,c),d(v,c)). Jeśli ścieżka między c a x nie przechodzi przez pierwszy wierzchołek (po c) na ścieżce z c do 1 tak jak poniżej:

miasta2

to u wcale nie był liściem o największej odległości od 1. Jeśli zaś ścieżka nie przechodzi przez pierwszy wierzchołek (też po c) na ścieżce z c do v:

miasta3

to v nie był liściem o największej odległości od u. (Te dwa przypadki wyczerpują wszystkie możliwości.)

No dobrze, ale jak dobrać się do tego c? Przecież nie możemy zadawać żadnych pytań o wierzchołki wewnętrzne. No, nie możemy, ale możemy wyznaczyć wszystkie wierzchołki wewnętrzne (a dokładniej, ich położenie) na ścieżce między u oraz v o ile tylko znamy d(u,x) oraz d(v,x) dla każdego liścia x. Dostajemy bowiem, że każdy taki x generuje wierzchołek wewnętrzny na ścieżce w odległości \frac{1}{2}(d(u,x)+d(u,v)-d(v,x)) od v, i co więcej każdy wierzchołek wewnętrzny może zostać wygenerowany w taki sposób. Zauważmy, że znamy wszystkie d(x,v), wystarczy więc zapytać o d(x,u). Następnie wybieramy ten z wygenerowanych wierzchołków wewnętrznych, który minimalizuje \max(d(x,u),d(x,v)) (w tym momencie warto już zauważyć, że mogą być co najwyżej dwa takie wierzchołki). Niestety prowadzi to do zadanie aż 3(n-1) pytań, co nie pozostawia nam zbyt szerokiego pola manewru w drugiej (trudniejszej!) części zadania. Może więc trzeba jeszcze chwilę pomyśleć?

Można. Nie musimy generować wierzchołków wewnętrznych na całej ścieżce. Wystarczą nam te, które leża również na ścieżce między 1 a u. Proste rachunki pokazują, że w związku z tym możemy zastąpić \frac{1}{2}(d(u,x)+d(u,v)-d(v,x)) przez \frac{1}{2}(d(u,x)+d(u,v)-d(1,x)). Nie zmieni to wyniku dla wierzchołków wewnętrznych, które leżą na obydwu ścieżkach, a dla tych „dalszych” dadzą nam po prostu pierwszy wspólny wierzchołek wewnętrzny. Zmniejsza to liczbę pytań do 2(n-1). Przejdźmy więc do właściwej części zadania.

Chcemy sprawdzić, czy usunięcie danego c prowadzi do podzielenia wszystkich liści na małe grupy. Wyliczenie wszystkich \frac{1}{2}(d(u,x)+d(u,v)-d(1,x)) pozwala nam na podzielenie liści względem wierzchołka, w którym „podpinają” się one do ścieżki między c a u tak jak na poniższej ilustracji.

miasta4

Wszystkie liście podpięte na prawo (to jest bliżej u) znajdą się po usunięciu c w tej samej składowej. Jeśli jest ich więc więcej niż \lfloor \frac{n}{2}\rfloor, nie ma nad czym myśleć. Jeśli tak nie jest, trzeba jednak trochę pomyśleć: nie wiemy bowiem które z liści podpiętych do c znajdą się w tych samych składowych.

Ale przecież możemy zapytać. d(x,u)+d(y,u)=d(x,y)+d(c,u) dokładnie wtedy gdy dwa takie liście x oraz y znajdą się w różnych składowych. Znamy wszystkie odległości od u, czyli wykonanie takiego testu kosztuje nas tylko jedno pytanie. Zredukowaliśmy więc całe zadanie do następującego problemu: mając dane co najwyżej n obiektów stwierdzić, czy któryś z nich powtarza się więcej niż \lfloor \frac{n}{2}\rfloor razy zadając pytania postaci „czy te dwa obiekty są identyczne?”. Brzmi znajomo?

Brzmi znajomo. Powiedzmy, że mamy dokładnie n elementów. Wtedy element, który pojawia się więcej niż \lfloor \frac{n}{2}\rfloor, nazywa się majority element. Wikipedia podaje bardzo elegancki algorytm, który wykrywa taki element w czasie \mathcal{O}(n) i pamięci \mathcal{O}(1). Algorytm jest na tyle prosty, że od razu widać, że wykonuje on co najwyżej 2(n-1) porównań elementów (i, co ważniejszej, są to dokładnie takie porównania, jakie wolno nam wykonywać). Dostajemy więc rozwiązanie całego zadania, które zadaje co najwyżej 4(n-1) pytań. Czyli… jeszcze nie koniec.

W tym momencie trochę nie wiadomo co zrobić. Być może należy wrócić do pierwszej części rozwiązania i próbować zmniejszyć 2(n-1), a być może lepiej skupić się na problemie znajdowania majority element. Ten drugi wydaje się bardziej elegancki, spróbujmy więc tak.

Po zasymulowaniu kilku przebiegów algorytmu podanego na Wikipedii (lub chwili uważnego wpatrywania się w kod napisany w Javie) można wyobrazić sobie cały proces w następujący sposób. Budujemy listę elementów, na której każde dwa elementy są różne. Dodatkowo mamy trochę „zapasowych” elementów identycznych z tym ostatnim na liście (ta lista nie jest zapisywana w algorytmie, ale zapasowe elementy to dokładnie utrzymywany licznik). Łatwo się przekonać, że gdy tylko dostaniemy nowy element potrafimy uaktualnić listę oraz „zapas” tak, aby utrzymać wspomniany niezmiennik kosztem jednego porównania. Powiedzmy więc, że przetworzyliśmy już wszystkie elementy. Zauważamy, że majority element (o ile istnieje) musi być ostatnim elementem na liście. Trzeba tylko stwierdzić, czy ostatni element na liście występuje dostatecznie wiele razy.

Przeformułujmy pytanie w następujący sposób: mamy dany pewien element x i listę elementów, na której każde dwa sąsiednie są różne. Chcemy stwierdzić, czy na liście jest więcej niż \lfloor \frac{n}{2}\rfloor elementów różnych od x. Popatrzmy na ostatni element listy: jeśli jest on różny niż x, zwiększamy licznik i usuwamy ostatni element listy. Jeśli jest on taki sam, to także zwiększamy licznik, ale usuwamy dwa ostatnie elementy (chyba, że lista ma długość 1). Gdy tylko zauważymy, że licznik przekracza \lfloor \frac{n}{2}\rfloor, kończymy pracę mówiąc, że x nie jest majority element. Łatwo zauważyć, że każde porównanie w tej części algorytmu zwiększa licznik o jeden, czyli nigdy nie wykonamy ich zbyt dużo. Biorąc pod uwagę porównania potrzebne na skonstruowanie listy, zużywamy co najwyżej \lfloor \frac{3n}{2}\rfloor porównań, co pozwala na rozwiązanie całego zadania.

Jako ciekawe (choć chyba trudne) zadanie proponuję zastanowienie się, czy te \lfloor \frac{3n}{2}\rfloor jest rzeczywiście konieczne. (A raczej pokazanie, że właściwie tak.)

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s