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 \leq 2$

Jeśli $m = 1$ , to dla każdego mieszkańca $i$ zbiór $N^{+} (i)$ zawiera po prostu wszystkich mieszkańców ${1, \dots, n}$ . Dokładnie tak samo jest w przypadku $m = 2$ . Tak więc te dwa przypadki są nierozróżnialne. Natomiast jeśli $m \geq 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 \geq 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 \leq 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}) + \dots + min (k_{n}, k_{j}) \leq k_{1} + k_{2} + \dots + 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 \leq 2$ , równe zbiory $N^{+} (i)$ to równe numery miast. Niech $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 $numer (i)$ i $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.