Omówienie zadania Telefony (II etap XXXI OI)

Najważniejsze spostrzeżenie

Dla \(i\)-tego mieszkańca, przez \(N(i)\) oznaczmy zbiór mieszkańców, których numery telefonu przechowuje \(i\)-ty mieszkaniec. Są to dokładnie te numery, które podaje \((i+1)\)-wszy wiersz wejścia. Dalej, przez \(N^+(i)\) oznaczamy zbiór \(N(i)\) po wstawieniu elementu \(i\) (tj. \(N^+(i)=N(i)\cup\{i\}\)). Załóżmy, że liczba miast \(m\) spełnia \(m > 2\). Okazuje się, że wówczas mieszkańcy \(i\) i \(j\) mieszkają w tym samym mieście wtedy i tylko wtedy, gdy \(N^+(i)=N^+(j)\). Przykładowo, w teście przykładowym do zadania mamy \(N^+(1)=N^+(4)=\{1,2,4,6\}\).

Spróbujmy to uzasadnić. Jeśli mieszkańcy \(i\) i \(j\) mieszkają w jednym mieście, to numery telefonu, które przechowują, to numery do pozostałych mieszkańców tego miasta oraz do wszystkich mieszkańców każdego miasta połączonego z nim drogą. W takim razie zbiory \(N(i)\) oraz \(N(j)\) różnią się tylko tym, że w \(N(i)\) nie ma elementu \(i\), a w \(N(j)\) nie ma elementu \(j\). Czyli rzeczywiście mamy \(N^+(i)=N^+(j)\).

Załóżmy teraz, że dla mieszkańców \(i\) i \(j\) zachodzi \(N^+(i)=N^+(j)\). Zastanówmy się, czy jest możliwe, że w tej sytuacji mieszkańcy \(i\) i \(j\) mieszkają w różnych miastach. Spróbujemy tak założyć, co doprowadzi nas do sprzeczności. Nie mogą to być miasta niepołączone bezpośrednio drogą, gdyż wtedy zbiór \(N^+(j)\) nie zawierałby elementu \(i\), a siłą rzeczy taki element należy do zbioru \(N^+(i)\). W takim razie mieszkańcy \(i\) i \(j\) musieliby mieszkać w dwóch różnych miastach, powiedzmy, odpowiednio, mieście \(a\) i mieście \(b\), takich że \(a\) i \(b\) są połączone drogą. Założyliśmy, że \(m > 2\), więc to oznacza, że co najmniej jedno z miast \(a\), \(b\) – dla ustalenia uwagi niech będzie to miasto \(a\) – jest połączone z jakimś jeszcze innym miastem \(c\). Wówczas miasto \(c\) nie może być połączone drogą z miastem \(b\), gdyż wtedy z miasta \(a\) do miasta \(b\) można byłoby dojechać dwiema drogami bez zawracania – jedną bezpośrednią, drugą przez miasto \(c\). W mieście \(c\) mieszka co najmniej jeden mieszkaniec; niech będzie to mieszkaniec \(k\). Wówczas \(k\) należy do zbioru \(N^+(i)\), ale nie należy do zbioru \(N^+(j)\), co daje nam żądaną sprzeczność.

Co jeśli \(m \le 2\)

Jeśli \(m=1\), to dla każdego mieszkańca \(i\) zbiór \(N^+(i)\) zawiera po prostu wszystkich mieszkańców \(\{1,\ldots,n\}\). Dokładnie tak samo jest w przypadku \(m=2\). Tak więc te dwa przypadki są nierozróżnialne. Natomiast jeśli \(m \ge 3\), łatwo zauważyć, że któryś ze zbiorów \(N^+(i)\) nie zawiera jakiegoś elementu.

Jeśli \(n=1\), to musi być tylko \(m=1\) miasto, gdyż w każdym mieście jest co najmniej jeden mieszkaniec. Jeśli zaś \(n \ge 2\), to w tej sytuacji mieszkańców możemy podzielić jakkolwiek na dwa miasta. Jest to wymagane, gdyż powinniśmy maksymalizować w wyniku liczbę \(m\).

Wyznaczanie wartości \(m\)

Aby uzyskać 50% punktów, wystarczyło poprawnie odtworzyć liczbę miast \(m\). W tym celu wystarczy posortować zbiory \(N^+(i)\) i zliczyć, ile wśród nich pojawia się różnych zbiorów. Jeśli okaże się, że wszystkie zbiory są takie same, wiemy, że \(m \le 2\). Wypisujemy wtedy \(m=1\), jeśli \(n=1\), a w przeciwnym razie \(m=2\). W przeciwnym razie liczba różnych zbiorów to właśnie szukana wartość \(m\).

Jak szybko sortować?

Elementy zbioru \(N^+(i)\) możemy reprezentować w postaci uporządkowanego ciągu liczb. Wystarczy skorzystać z ciąg liczb reprezentującego zbiór \(N(i)\), który mamy na wejściu, a następnie wstawić we właściwe miejsce element \(i\). W ten sposób zbiory \(N^+(i)\) możemy sortować jak ciągi liczb, porównując je leksykograficznie (jak napisy).

Jakiego algorytmu użyć do sortowania ciągów liczb? Najprościej skorzystać z algorytmu std::sort z biblioteki standardowej C++, który automatycznie sortuje takie ciągi (przechowywane np. w kontenerze vector) w kolejności leksykograficznej. Okazuje się, że jest to dostatecznie szybkie rozwiązanie. Można to stwierdzić w praktyce albo spróbować przeanalizować złożoność takiego algorytmu.

Przyjmijmy, że algorytm std::sort opiera się w dużej mierze na algorytmie QuickSort. W algorytmie tym wybieramy element dzielący i pozostałe elementy grupujemy na podstawie porównania z elementem dzielącym. W naszym przypadku elementami są ciągi liczb o łącznej długości \(p\). Koszt porównania leksykograficznego dwóch ciągów o długościach, odpowiednio, \(k_i\) i \(k_j\), to \(O(\min(k_i,k_j))\). Łączny czas porównań, w przypadku, gdy elementem dzielącym jest ciąg o długości \(k_j\), jest więc proporcjonalny do \(\min(k_1,k_j)+\min(k_2,k_j)+\ldots+\min(k_n,k_j) \le k_1+k_2+\ldots+k_n=p\).

W kolejnej fazie algorytmu mamy wywołanie rekurencyjne na elementach, które okazały się być mniejsze od elementu dzielącego, i na pozostałych elementach. Łatwo zauważyć, że podzielenie obu tych części również zajmie łącznie czas \(O(p)\). Algorytm QuickSort w oczekiwanym przypadku ma głębokość rekursji \(O(\log p)\), co łącznie daje oczekiwany czas \(O(p \log p)\).

Powyższa analiza jest zgrubna o tyle, że nie zakłada dogłębnej wiedzy o tym, jak działa algorytm std::sort. Jeśli chcielibyśmy przyspieszyć powyższy algorytm sortowania, moglibyśmy np. przypisać sortowanym ciągom hasze, będące małymi liczbami całkowitymi, i sortować te hasze. Można w tym celu użyć metody randomizowanej (hasze wielomianowe) lub deterministycznej (słownik podsłów bazowych). Obie te metody są opisane np. w książce Przygody Bajtazara. 25 lat Olimpiady Informatycznej. Wybór zadań.

Do sortowania napisów równej długości można użyć algorytmu sortowania pozycyjnego (RadixSort), opisanego np. w książce Cormena i in. Wprowadzenie do algorytmów. Algorytm ten działa w czasie liniowym od sumy długości napisów, zakładając, że alfabet, z którego pochodzą symbole napisów, jest niezbyt duży. Okazuje się, że po pewnym namyśle algorytm ten można przystosować do sortowania zbiorów \(N^+(i)\) w naszym zadaniu w łącznym czasie \(O(p)\). Pozostawiamy to jako ciekawe ćwiczenie dla Czytelnika.

Wyznaczanie dróg

Przy okazji wyznaczania liczby miast \(m\) możemy od razu przypisywać kolejnym mieszkańcom numery miast. Pomijając przypadek \(m \le 2\), równe zbiory \(N^+(i)\) to równe numery miast. Niech \(\mathit{numer}(i)\) oznacza numer miasta przypisany w ten sposób mieszkańcowi \(i\).

Aby odtworzyć połączenia między miastami, dla każdego mieszkańca \(i\) i każdego mieszkańca \(j\) należącego do zbioru \(N(i)\), tworzymy drogę między miastami \(\mathit{numer}(i)\) i \(\mathit{numer}(j)\), jeśli tylko te dwa miasta są różne. Następnie wystarczy posortować wszystkie drogi i wypisać je bez duplikatów, dbając o to, aby drogę łączącą miasta \(a\) i \(b\) reprezentować za pomocą pary liczb \(\min(a,b)\) i \(\max(a,b)\). Można do tego użyć algorytmów std::sort i std::unique, otrzymując czas \(O(p \log p)\). Pary można też posortować pozycyjnie w czasie \(O(p)\), co w praktyce nie zmienia zbytnio czasu działania.

Zauważmy, że nie musimy sprawdzać, czy sieć dróg jest oszczędna zgodnie z warunkiem z treści zadania. Jest tak dlatego, że podobnie jak liczba miast, sieć dróg jest wyznaczona jednoznacznie na podstawie wejścia (o ile \(m > 2\)), a w zadaniu mamy gwarancję, że wejście jest poprawne.

Drzewo

Warto choć na koniec przedstawić interpretację treści zadania w języku teorii grafów. Miasta reprezentują wierzchołki grafu, a dwukierunkowe drogi to krawędzie nieskierowane łączące pary wierzchołków. Warunek z treści zadania, że z każdego miasta do każdego innego można dojechać za pomocą sieci dróg bez zawracania na dokładnie jeden sposób, oznacza, że graf jest drzewem.