19761. Trzyliterówka [FR_01_M5]

Zadanie:
https://spoj.com/FRAKTAL/problems/FR_01_M5
https://pl.spoj.com/problems/FR_01_M5

Skrócony opis problemu:

Dla $n$ 3-literowych słów złożonych z małych liter alfabetu łacińskiego (o długości ilości liter - $d$) sprawdź, czy da się połączyć wszystkie słowa w jedno. Słowo $A$ można połączyć ze słowem $B$, jeśli pierwsza litera słowa $A$ jest taka sama jak ostatnia litera słowa $B$ lub na odwrót. Np. "algoliga algorytm" da się połączyć w słowo algoligalgorytm.

Rozwiązanie naiwne:

Można spróbować wszystkich możliwych kombinacji połączeń i w przypadku połączenia wszystkich $n$ słów przerwania algorytmu i wypisanie TAK.

Złożoność: $O(n! \cdot n)$. Dlaczego? Ano musimy się zastanowić ile jest możliwych kombinacji połączeń między wszystkimi słowami. Jest ich $n!$ ($n$ silnia), gdyż dokładnie tyle jest permutacji ciągu $n$-elementowego. Ustawmy sobie słowa tak jak były na wejściu i potraktujmy indeksy owych słów jako permutację. Dla każdej takiej permutacji musimy wykonać $2n$ operacji - musimy najpierw sprawdzić czy wszystkie $n$ słów się łączą ze swoimi sąsiadami, a następnie wygenerować następną permutację (w czasie $O(n)$).

Rozwiązanie sprytne:

By rozwiązać to zadanie trzeba zauważyć, że jedyne co się liczy to ilość liter początkowych i końcowych. Jeśli bowiem mamy jedną literę 'a' na końcu i dwie 'a' na początku to nie ma różnicy, które z nich połączymy. Tak więc musimy mieć tyle liter początkowych, co końcowych, dla każdej litery od 'a' do 'z'. Możemy sobie pozwolić jedynie na 2 niedopasowania - możemy mieć np. jedną początkową literą 'g' więcej niż liczba końcowych liter 'g', bo wtedy jeden wyraz z początkową literą 'g' pójdzie na początek (a początek i koniec nie muszą mieć tej samej litery). Analogicznie, możemy mieć jedną dodatkową literę końcową np. 'p' - wtedy jeden z wyrazów z 'p' na końcu pójdzie na koniec ciągu, dzięki czemu nie będzie potrzebował pary.

Musimy jeszcze rozpatrzeć przypadki szczególne. Pierwszy z nich to palindromy. Przykładowy test to "ala olo". Dla takiego testu dostajemy tyle samo liter końcowych 'a' i 'o' co początkowych, a jednak nie da się z nich utworzyć jednego wyrazu. Jak to naprawić? Ano wystarczy zrobić sobie tablicę $palindrome$, w której będziemy trzymali dla każdej litery czy jest jakiś palindrom zaczynający i kończący się na nią. Jeśli jest to musi być też jakieś słowo, które nie jest palindromem, a zawiera ową liczbę - obojętnie czy na początku, czy na końcu. Jeśli jest to nie ma problemu. Jeśli jednak na daną literę zaczynają się jedynie palindromy, to już wiemy, że odpowiedzią będzie NIE.

Drugim i ostatnim problemem jest przypadek, kiedy słowa tworzą dwa cykle zamiast jednego łańcucha. Np. "abc cba def fed". Ilość liter znów nam się zgadza, ale jak widać mamy 2 cykle "abc-cba" oraz "def-fed" (cykle, bo pierwsza litera równa się końcowej w każdym z łańcuchów). Nie da się jednak połączyć ze sobą owych łańcuchów. Jak to naprawić? Ano tutaj zliczanie czegokolwiek nam już nie pomoże. Musimy utworzyć graf nieskierowany z liter i sprawdzić ile jest w nim spójnych składowych. Tak więc dla wspomnianego przykładu otrzymamy poniższy graf:

Możemy teraz go przeszukać i tym samym obliczyć ilość spójnych składowych (obojętnie czy algorytmem DFS czy BFS). Jeśli mamy 1 spójną składową, to wypisujemy TAK, a jeśli więcej - NIE. W praktyce przechodzimy po prostu graf zaczynając od jakiegoś wierzchołka (wierzchołkami są litery) i na końcu sprawdzamy czy wszystkie przeszliśmy.

Spostrzegawczy Kacper może powiedzieć: "Przecież przeszukanie grafu liter wyeliminuje również problem palindromów!". I będzie miał rację. We wspomnianej reprezentacji grafowej palindromy będę wierzchołkami odizolowanymi, więc ilość składowych będzie większa niż 1 (chyba że test będzie składał się z "palindromów tylko jednej litery").

Optymalizacja: Innym sposobem sprawdzania spójności grafu jest tablicowanie spójnych składowych. Ów algorytm opisałem tutaj: http://zadania-algorytmiczne.blogspot.com/2014/07/2379-swiateka-choinkowe-bipart.html.

Złożoność: $O(n + d)$, jako że dla każdego wyrazu sprawdzamy jego pierwszą i ostatnią literę i aktualizujemy tablice w czasie stałym. Potem wykonujemy DFSa albo BFSa na utworzonym grafie (a ilość krawędzi wynosi $2n$), a na końcu dla każdej litery z alfabetu o wielkości $d$ ($d = 26$ w naszym przypadku - uogólniłem to w razie gdyby powstało inne zadanie, z większym alfabetem) sprawdzamy czy ilość liter początkowych i końcowych się zgadza.

Algorytm:

void dfs(int v)
{
        visited[v] = 1;
        for(int i = 0; i < graph[v].size(); ++i)
                if(!visited[graph[v][i]])
                        dfs(graph[v][i]);
}
int main()
{
        int n = 0, m = 0, beg[29], end[29], visited[29];
        vector<int> graph[29];
        char in[9];

        get(n);
        if(n < 2)
        {
                get(in);
                print(TAK);
                return 0;
        }
        for(int i = 0; i < n; ++i)
        {
                get(in);
                *in -= 'a'; in[2] -= 'a'; // zamieniamy litery 'a'..'z' na liczby 0..25
                graph[*in].push_back(in[2]); // jedna krawędź w grafie
                graph[in[2]].push_back(*in); // i druga (bo to jest graf nieskierowany)
                ++beg[*in]; // zwiększamy ilość początkowych liter
                ++end[in[2]]; // i końcowych
        }
        dfs(*in); // przeszukujemy graf
        for(int i = 0; i < 26; ++i)
                if((beg[i] || end[i]) && !visited[i]) // jeśli jakaś litera wystąpiła, ale nie została odwiedzona w DFSie
                        n = 100; // to znaczy, że mamy wypisać NIE
                else if(beg[i] > end[i]) // zliczamy ile jest liter, które nie mają pary
                        m += beg[i]-end[i];
                else // tutaj tak samo
                        n += end[i]-beg[i];
        print(n > 1 || m > 1 ? NIE : TAK); // jeśli jest za dużo początków lub końców to wypisujemy NIE
}