Omówienie zadania Zawody sportowe (II etap XXIV OI)

Sytuację opisaną w zadaniu przedstawimy jako graf dwudzielny: lewy zbiór zawierać będzie \(n\) wierzchołków reprezentujących poszczególnych zawodników, natomiast prawy zbiór zawierać będzie \(n\) wierzchołków odpowiadających kolejnym miejscom w klasyfikacji zawodów. Z wierzchołka reprezentującego \(i\)-tego zawodnika poprowadzimy jedną lub dwie krawędzie do wierzchołków odpowiadających miejscom, które mógł on zająć zgodnie z relacją dziennikarza.

Grafy przedstawiające testy przykładowe.

Przypomnijmy, że skojarzeniem w grafie nazywamy każdy taki podzbiór krawędzi, że każdy wierzchołek jest końcem co najwyżej jednej krawędzi z tego podzbioru. Z kolei, skojarzenie doskonałe to taki podzbiór krawędzi, że każdy wierzchołek jest końcem dokładnie jednej krawędzi z tego podzbioru.

Na skojarzenia doskonałe można też patrzyć w inny sposób: skojarzenie takie reprezentuje przyporządkowanie każdemu wierzchołkowi z lewej strony pewnego wierzchołka z prawej, w taki sposób, że żaden wierzchołek nie jest przyporządkowany więcej niż jeden raz. Zauważmy, że postawione w zadaniu pytanie sprowadza się do policzenia liczby skojarzeń doskonałych w powyższym grafie.

Rozwiązanie wzorcowe w czasie \(O(n)\)

Jeżeli w rozważanym grafie istnieje wierzchołek o stopniu równym \(1\), to mamy pewność, że jedyna krawędź, której jest końcem, musi należeć do każdego skojarzenia doskonałego. Możemy więc bezpiecznie, nie zmieniając odpowiedzi, usunąć z grafu ten wierzchołek wraz z krawędzią, jej drugim końcem i wszystkimi innymi wychodzącymi z tego końca krawędziami. Operację tę powtarzamy tak długo, jak długo w grafie są wierzchołki o stopniu równym \(1\). Pamiętajmy, że w trakcie tego procesu kolejne wierzchołki mogą stawać się wierzchołkami o stopniu \(1\).

Jeżeli w tak powstałym grafie znajduje się wierzchołek o stopniu \(0\), to skojarzenie doskonałe nie może istnieć, czyli relacje dziennikarzy były sprzeczne i możemy od razu wypisać odpowiedź „NIE 0".

Zastanówmy się, jak teraz może wyglądać rozważany graf. Wyjściowy graf miał po \(n\) wierzchołków w lewym i prawym zbiorze, a za każdym razem, gdy usuwaliśmy wierzchołki, usuwaliśmy po jednym z każdego zbioru. Zatem dalej w obu zbiorach jest taka sama liczba wierzchołków. Oznaczmy tę liczbę przez \(n'\). Początkowo wszystkie wierzchołki w lewym zbiorze miały stopień co najwyżej \(2\), stopnie mogły jedynie maleć, a obecnie żaden wierzchołek nie ma stopnia \(0\) ani \(1\). Zatem, wierzchołki, które zostały w lewym zbiorze, mają stopień równy dokładnie \(2\). W takim razie, w grafie jest dokładnie \(2n'\) krawędzi, czyli suma stopni \(n'\) wierzchołków po prawej stronie wynosi \(2n'\). Skoro każdy z nich również ma stopień co najmniej \(2\), to znaczy, że wszystkie te wierzchołki muszą mieć stopień równy dokładnie \(2\).

Graf, w którym wszystkie wierzchołki są stopnia \(2\) ma bardzo specyficzną strukturę: jest zbiorem rozłącznych wierzchołkowo cykli. Każdy z tych cykli jest cyklem Eulera w danej spójnej składowej grafu. Na marginesie, znalezienie cyklu Eulera możemy wykonać np. za pomocą algorytmu Fleury'ego.

Ponieważ rozważany graf jest dwudzielny, to każdy cykl jest parzystej długości. Każdy z cykli ma dokładnie dwa różne skojarzenia doskonałe — jedno składające się ze wszystkich „parzystych" krawędzi (na rysunku oznaczone kolorem niebieskim), drugie z „nieparzystych" (oznaczone kolorem czerwonym).

Przykładowy graf będący zbiorem dwóch cykli. Krawędzie niebieskie i czerwone tworzą dwa różne skojarzenia doskonałe w każdym z cykli.

Aby otrzymać skojarzenie doskonałe w całym grafie, w każdym cyklu możemy niezależnie wybrać jedno z tych dwóch skojarzeń. Zatem, liczba wszystkich skojarzeń doskonałych wynosi \(2^{\mathrm{liczba\ cykli}}\).

Implementacja opisanego powyżej algorytmu (np. w oparciu o kolejkę wierzchołków ze stopniem jeden) daje rozwiązanie działające w czasie \(O(n)\).

Inne rozwiązania

Rozwiązanie wolne \(O(n! \cdot n)\)

Jednym z najbardziej intuicyjnych rozwiązań jest wygenerowanie wszystkich potencjalnych klasyfikacji, których jest \(n!\). Następnie każdą z tych klasyfikacji sprawdzamy, czy jest zgodna z relacjami dziennikarzy. Takie sprawdzenie zajmuje czas \(O(n)\), zatem całe rozwiązanie działa w czasie \(O(n! \cdot n)\) i przechodzi podzadanie 1.

Rozwiązanie wolne \(O(2^n \cdot n)\)

Zastanówmy się przez chwilę nad sytuacją, kiedy każdy z dziennikarzy wskazuje dokładne miejsce, które zajął reprezentowany przez niego zawodnik. W tej sytuacji odpowiedź to 0 lub 1. Wystarczy sprawdzić, czy dziennikarze wskazali wszystkie miejsca od \(1\) do \(n\). Takie sprawdzenie możemy wykonać za pomocą metody zliczania w czasie \(O(n)\).

W oryginalnym zadaniu są jednak dziennikarze, którzy wskazali dwa potencjalne miejsca w klasyfikacji. Zatem dla każdego z nich wybierzmy jedną z dwóch opcji. Wszystkich takich wyborów jest \(O(2^n)\), więc całe rozwiązanie działa w czasie \(O(2^n \cdot n)\) i przechodzi podzadanie 1.

Rozwiązanie wolne \(O(n^2)\)

Wróćmy do rozwiązania wzorcowego, w którym szukanie wierzchołków o stopniu \(1\) realizujemy za pomocą kolejki. Rozwiązanie, które naiwnie szuka takich wierzchołków (zawsze przegląda wszystkie wierzchołki) działa w czasie \(O(n^2)\) i przejdzie podzadania 1 i 2.