Omówienie zadania Miasta partnerskie (eliminacje do IOI 2020, dzień 3)

W zadaniu na wejściu dostajemy liczbę naturalną \(n\) i dwa ciągi liczb naturalnych \(a_1, a_2, \dots, a_n\) oraz \(b_1, b_2, \dots, b_n\) oznaczające odpowiednio kody pocztowe miast z Bajtocji i Bitocji z treści zadania. Naszym zadaniem jest stwierdzić, czy istnieje połączenie elementów ciągów w pary \((a_i, b_j)\) tak, aby spełnione były następujące warunki:

• w każdej parze jeden z elementów należy do ciągu \(a_1, a_2, \dots, a_n\), natomiast drugi do ciągu \(b_1, b_2, \dots, b_n\),
• każdy element z ciągów \(a_1, a_2, \dots, a_n\) oraz \(b_1, b_2, \dots, b_n\) należy do dokładnie jednej pary,
• w każdej parze co najmniej jeden element jest zadowolony. Zadowlenie elementu definiujemy następująco: jeśli \((a_i, b_j)\) są w parze oraz element \(a_i\) jest zadowolony, to dla dowolnego \(1 \leq k \leq n\) musi zachodzić \(a_i \oplus b_j \leq a_i \oplus b_k\), gdzie \(\oplus\) oznacza alternatywe wykluczającą (XOR). Analogicznie \(b_j\) jest zadowolony z \(a_i\), jeśli dla każdego \(1\leq k\leq n\) mamy \(a_i\oplus b_j\leq a_k\oplus b_j\)

Podzadanie 1 – \(n \leq 8\):

Ze względu na małe ograniczenia na wartość \(n\) możemy rozważyć wszystkie możliwe połączenia elementów w pary, a następnie sprawdzić dla każdej pary, czy co najmniej jeden element jest zadowolony. Jako, że pierwszy element możemy połączyć na \(n\) sposobów, drugi na \(n-1\), trzeci na \(n-2\) itd. to otrzymany w ten sposób algorytm można zaimplementować w złożoności czasowej \(O(n! \cdot n^2)\).

Podzadanie 2 – \(n \leq 3000\):

Weźmy dowolny element \(a_i\) z ciągu \(a_1, a_2, \dots, a_n\). Wtedy istnieje dokładnie jeden element (oznaczmy go \(b_j\)) z ciągu \(b_1, b_2, \dots, b_n\), który minimalizuje wartość \(a_i \oplus b_j\). Aby to wykazać, załóżmy nie wprost, że istnieją takie dwa różne elementy \(b_j\) oraz \(b_k\), że \(a_i \oplus b_j = a_i \oplus b_k\). W takim razie mamy \(b_j = a_i \oplus (a_i \oplus b_j) = a_i \oplus (a_i \oplus b_k) = b_k\), co prowadzi do sprzeczności, ponieważ elementy ciągu \(b_1, b_2, \dots, b_n\) są parami różne. Analogiczny dowód możemy przeprowadzić, by wykazać, że dla każdego \(b_j\) istnieje dokładnie jedno \(a_i\), które minimalizuje wartość \(b_j \oplus a_i\). Widzimy więc, że dla każdego elementu z obu zbiorów istnieje dokładnie jeden element w przeciwnym zbiorze, z którym będzie on zadowolony. Jeden taki element możemy znaleźć brutalnie w czasie \(O(n)\), więc dla wszystkich elementów znajdziemy je sumarycznie w złożoności \(O(n^2)\).

Możemy teraz skonstruować graf dwudzielny o \(2n\) wierzchołkach. Wierzchołki z jednej strony grafu odpowiadają elementom ciągu \(a_1, a_2, \dots, a_n\), a wierzchołki z drugiej strony elementom ciągu \(b_1, b_2, \dots, b_n\). Krawędź między wierzchołkami \(a_i\) i \(b_j\) będzie istnieć wtedy i tylko wtedy, gdy co najmniej jeden element z pary \(a_i, b_j\) będzie zadowolony po sparowaniu ich ze sobą. W ten sposób sprowadzamy nasz problem do znanego zagadnienia znalezienia maksymalnego skojarzenia w grafie dwudzielnym (bipartite matching).

Rozwiązanie problemu maksymalnego skojarzenia w skonstruowanym przez nas grafie dwudzielnym pozwoli wyznaczyć poszukiwane pary elementów \((a_i, b_i)\), w których przynajmniej jeden z elementów jest zadowolony. Dzieje się tak, ponieważ sparowanie \((a_i, b_j)\) w skojarzeniu jest możliwe tylko wtedy, gdy istnieje między nimi krawędź, co gwarantuje zadowolenie przynajmniej jednego z tych elementów w ramach takiego parowania. Po wyznaczeniu tego skojarzenia pozostaje jedynie sprawdzić, czy zbiór powstałych par zawiera wszystkie elementy z obu ciągów. Jeśli każdy element został uwzględniony w jakiejś parze, wypisujemy TAK. W przeciwnym przypadku wypisujemy NIE.

Problem maksymalnego skojarzenia w grafie dwudzielnym można efektywnie rozwiązać za pomocą algorytmu Hopcrofta–Karpa, który działa w złożoności \(O(\sqrt{n} \cdot m)\), gdzie \(n\) to liczba wierzchołków, a \(m\) to liczba krawędzi. W naszym grafie liczba krawędzi nie przekroczy \(2n\), więc złożoność czasowa algorytmu wyniesie \(O(n \cdot \sqrt{n})\). Dokładniejszy opis algorytmu możemy znaleźć np. w tym artykule.

Łączna złożoność czasowa programu wyniesie \(O(n^2 + n \sqrt{n}) = O(n^2)\), co mieści się w limicie dla podzadania.

Podzadanie 3 – jeżeli przyporządkowanie istnieje, to można tak wybrać miasta partnerskie, by w każdej parze oba miasta były zadowolone

Zgodnie z naszymi wcześniejszymi obserwacjami wiemy, że dla każdego elementu istnieje dokładnie jeden element, który go zadowala. Jeśli poprawne przyporządkowanie istnieje oraz dla każdego elementu bylibyśmy w stanie w szybki sposób wyznaczyć mu jego (jednoznacznie) odpowiadający element, to otrzymalibyśmy szukane parowanie.

Do rozwiązania tego problemu możemy wykorzystać drzewo Trie. Budujemy strukturę na elementach ciągu \(b_1, b_2, \dots, b_n\), a następnie znajdujemy dla każdego elementu \(a_i\) odpowiadający mu element \(b_j\), schodząc w dół drzewa po odpowiednich krawędziach, co jesteśmy w stanie wykonać w złożoności \(O(\log A)\), gdzie \(A\) jest ograniczeniem górnym na wartości elementów obu ciągów. Szczegółowy opis drzewa Trie, w tym algorytmy do jego implementacji, można znaleźć w tym artykule.

Drzewo Trie możemy zbudować w złożoności \(O(n \log A)\). Skoro dla każdego elementu jesteśmy w stanie znaleźć odpowiadający mu element z przeciwnego zbioru w czasie \(O(\log A)\), to złożoność czasowa całego programu wyniesie wtedy \(O(n\log A)\).

Podzadanie 4 – brak dodatkowych warunków

Aby rozwiązać to podzadanie, będziemy musieli wykorzystać struktury i obserwacje z poprzednich podpunktów. Wykorzystując drzewo Trie, możemy dla każdego elementu znaleźć odpowiadający mu element, który go zadowala, w sumarycznej złożoności czasowej \(O(n \log A)\). W ten sposób konstruujemy dwudzielny graf, na którym możemy wykonać opisany już wcześniej algorytm Hopcrofta–Karpa, co rozwiąże problem w złożoności \(O(n \sqrt{n})\). Całkowita złożoność wyniesie więc \(O(n\log A + n \sqrt{n}) = O(n (\sqrt{n} + \log A))\).