17137. DOMINO [AL_13_07]

Zadanie:
https://spoj.com/ALGOLIGA/problems/AL_13_07
https://pl.spoj.com/problems/AL_13_07

Skrócony opis problemu:

Dany jest ciąg $n$ kostek domina, których obie wartości zawierają się w przedziale 0..6. Kostki mogą się powtarzać. Należy obliczyć dla niego długość najdłuższego spójnego podciągu kostek, takiego że obracając (bez zamiany miejsc) w nim dowolną ilość kostek możemy otrzymać poprawny ciąg gry Domino, tj. taki, że każde 2 sąsiadujące kostki stykają się bokami o tej samej wartości. Np. dla poniższego ciągu odpowiedź to 3, bo jeśli obrócimy 2 i 4 kostkę to otrzymamy poprawny podciąg od kostki 2 do 4.

2|1 1|3 1|4 5|4

Rozwiązanie naiwne:

Możemy po prostu sprawdzić każdą możliwość. Ale jak to zrobić? Przecież jeśli wygenerujemy wszystkie podciągi to nadal musielibyśmy w nich próbować obracać różne kostki. Ano musimy po prostu wygenerować wszystkie możliwości obróceń kostek. Jak to zrobić? Generujemy po prostu wszystkie ciągi binarne o długości $n$. 0 na danej pozycji oznaczać będzie, że nie będziemy obracali owej kostki, a 1 odwrotnie. Dla jednego takiego ciągu będziemy generowali wszystkie możliwe podciągi (zaczynając od największych) i sprawdzali czy są poprawne. Jeśli któryś będzie poprawny, to przerywamy sprawdzanie i wypisujemy jego długość.

Złożoność: $O\left(2^n \cdot 2^n \cdot n\right) = O\left(4^n \cdot n\right)$, bo ciągów binarnych o długości $n$ jest $2^n$. Dla każdego z nich sprawdzamy wszystkie jego podciągi, a tych jest $2^{n-1}$. No i dodatkowo każdy z tych podciągów ma pesymistycznie długość $n$, a by sprawdzić poprawność ciągu musimy przejść wszystkie elementy.

Rozwiązanie naiwne minus $\epsilon$:

Możemy dla każdego ciągu binarnego wyznaczyć zachłannie najdłuższy poprawny spójny podciąg. Nie musimy przestawiać już bowiem kostek. A zatem idziemy od jednego końca do drugiego i sprawdzamy czy 2 kolejne kostki stykają się bokami z tą samą wartością. Jeśli tak, to inkrementujemy zmienną $len$, jeśli nie, to sprawdzamy czy $len > max\_len$ ($max\_len$ to długość najdłuższego poprawnego spójnego podciągu, jaki znaleźliśmy do tej pory) i jeśli tak, to przypisujemy $max\_len = len$. A następnie ustawiamy $x = 1$, bo mamy przerwę w podciągu, więc za początek nowego podciągu przyjmujemy dany element.

Złożoność: $O\left(2^n \cdot n\right)$, bo dla każdego z $2^n$ binarnych ciągów obliczamy wynik przechodząc wszystkie $n$ wyrazów ciągu raz.

Rozwiązanie sprytne:

Możemy rozwiązać to zadanie minimalną możliwą złożonością, a więc $O(n)$ (minimalną, bo mamy $n$ elementów, a naturalnie wszystkie musimy przejść). Liniówka w takim zadaniu sugeruje algorytm zachłanny.

A zatem, idziemy sobie od pierwszego elementu do ostatniego. Oznaczmy sobie $a$ i $b$ jako odpowiednio lewą i prawą część danej kostki, a $c$ i $d$ jako lewą i prawą część ostatniej kostki. No i jeśli 2 kolejne elementy nie mają wspólnej wartości na żadnej z części to oczywiście ustawiamy $x = 1$. Kolejnym oczywistym przypadkiem jest gdy dostajemy kostkę, dla której $a = d$ - wtedy nie obracamy jej nawet ($c = a$, $b = d$) i inkrementujemy $x$. Ostatnim łatwym przypadkiem jest gdy $b = d$. Wtedy po prostu obracamy nową kostkę ($c = b$, $d = a$) i również inkrementujemy $x$.

Pozostały nam przypadki, gry któraś z wartości nowej kostki jest równa $c$ - musimy wtedy obrócić starą kostkę i zastanowić się jak bardzo zepsuł się nasz stary poprawny podciąg. Ale przecież nie pamiętamy starych kostek. Jak możemy bez nich obliczyć ile starych kostek będzie w nowym poprawnym podciągu? A może tracimy po obróceniu cały stary podciąg i powinniśmy ustawić $x = 2$ biorąc tylko 2 najnowsze kostki? Ano nie. Zastanówmy się jaka musiałaby być kostka, by po zamianie jej następnika mogłaby być wliczona do poprawnego podciągu? Ano skoro wcześniej była w poprawnym podciągu to musiałaby mieć taką samą wartość na prawym boku, co jej następnik na lewym boku. A skoro obracamy jej następnika to musiałaby mieć na dowolnym boku wartość z prawego boku jej następnika. Co to oznacza? Ano że te kostki muszą być takie same! Np. dla 2|6 jedynie 2|6 (lub 6|2) będziemy mogli obrócić nie wyrzucając jej z podciągu poprawnego. Skoro tak, to nie musimy pamiętać starych kostek, a jedynie ilość takich samych kostek licząc od danego momentu w lewo. Gdy pojawi się nowa kostka, to po prostu ustawimy ową ilość na 1.

Musimy jeszcze pamiętać, by po każdej kostce aktualizować nasz wynik, czyli $max\_len$.

Złożoność: $O(n)$, bo każdą kostkę przechodzimy tylko raz.

Algorytm:

int main()
{
        int n, a, b, x = 1, y = 1, z = 1, c, d;

        get(n,c|d);
        while(--n)
        {
                get(a|b);
                if(a != c && a != d && b != c && b != d) // jeśli kolejne kostki są zupełnie różne
                        x = 1,
                        y = 1,
                        c = a,
                        d = b;
                else if((a == c && b == d) || (a == d && b == c)) // jeśli kostki są takie same - inkrementujemy y; poprzednią kostkę ustawiamy jako odwróconą, bo np. po 4|2 będzie 2|4
                        ++y,
                        ++x,
                        c ^= d ^= c ^= d;
                else if(a == d || b == d) // jeśli nowa kostka ma wartość równą d (czyli prawego boku starej kostki)
                        ++x,
                        y = 1,
                        c = a == d ? a : b,
                        d = a == d ? b : a;
                else // jeśli nowa kostka ma wartość równą c (czyli lewego boku starej kostki)
                        x = y+1, // x będzie równe ilości kostek takich samych + 1
                        y = 1,
                        c = a == c ? a : b,
                        d = a == c ? b : a;
                if(x > z) // aktualizujemy max_len, czyli z
                        z = x;
        }
        print(z);
}

Optymalizacje:
Nie da się tego zadania zrobić szybciej niż liniowo, bo mamy liniową ilość danych. Co zatem można zoptymalizować? Ano możemy nie wczytywać wszystkich danych! Wydaje się to absurdalne, ale są sytuacje, w których dalsze dane nie zmienią nam wyniku. Powiedzmy, że wczytaliśmy o 5 kostek więcej niż połowa danych. No i do poprzedniej kostki mieliśmy od początku poprawny podciąg, ale ta 5 kostka po połowie jest zupełnie różna od poprzedniej. Ustawiamy więc $x=1$. Ale chwila. Nawet jeśli wszystkie dalsze kostki utworzą poprawny podciąg, to i tak nie przebijemy starego wyniku, bo jest on większy niż połowa ciągu. Tak więc jeśli w dowolnym momencie $x$ powiększone o ilość kostek, które nam zostały będzie mniejsze lub równe $max\_len$, to przerywamy wczytywanie i wypisujemy $max\_len$.

Możemy wprowadzić jeszcze jedną optymalizację, która jednak będzie trochę oszukiwaniem. Możemy przerwać wyszukiwanie, jeśli osiągniemy wartość $z$, gdzie $z$ jest stałą wartością, którą sobie wybierzemy. Powiedzmy, że w testach maksymalna długość poprawnego podciągu to milion. Jeśli więc otrzymamy milion, to nie będzie sensu dalej wczytywać danych. No ale jak poznać to $z$? Ano za pomocą wyszukiwania binarnego po... statusie. $\ddot\smile$ Wybieramy $z = 10^6$ i jeśli dostaniemy AC, to możemy zmniejszyć $z$. Jeśli WA, to go ustawiamy na 15e5 itd. Okazuje się jednak, że testy są dobrze przygotowane (brawo, Marcin!) i $z$ byłoby równe albo bardzo bliskie maksymalnemu $n$, więc nie warto stosować tej "optymalizacji" w tym zadaniu.