17211. Bajtomir na giełdzie [AL_12_08]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_08
http://pl.spoj.com/problems/AL_12_08

Skrócony opis problemu:

Dla danego ciągu składającego się z $n$ liczb naturalnych znaleźć najdłuższy podciąg alternujący (ang. longest alternating subsequence). Jest to taki ciąg, dla którego kolejne wyrazy są na przemian rosnące i malejące. Np. 2,3,1 lub 5,1,99,42.

Rozwiązanie naiwne:

Możemy sprawdzić wszystkie podciągi ciągu wejściowego, sprawdzić które są ciągami alternującymi i wybrać najdłuższy.

Złożoność: $O(2^n \cdot n)$, gdyż musimy sprawdzić wszystkie podciągi o długości $\ge 2$ (jest ich $\sum_{i=2}^n {n \choose i} = 2^n-n-1$), a każdy z nich może mieć pesymistycznie długość $n$.

Rozwiązanie sprytniejsze:

Możemy skorzystać z programowania dynamicznego. Dla każdego wyrazu rozpatrujemy wszystkie poprzednie. Mamy sobie 2 tablice: $inc$ i $dec$, przechowujące długości najdłuższych ciągów alternujących, w których ostatnia para liczb odpowiednio: rośnie i maleje. A więc jesteśmy sobie np. w $a_i$ i rozpatrujemy akurat jakiś wyraz $a_j$, który wystąpił wcześniej ($i > j$). Powiedzmy, że $a_i > a_j$. Skoro para ta rośnie, to możemy dołożyć wyraz $a_i$ do najdłuższego ciągu, który kończy się na $a_j$ i którego ostatnia para maleje. A więc jeśli $a_i > a_j$ to $inc[i] = \max\left(inc[i], dec[j]+1\right)$. Dla $a_j > a_i$ mamy analogiczny wzór: $dec[i] = \max\left(dec[i], inc[j]+1\right)$.

Rozważmy np. ciąg 3,2,1,3. Na początku wypełniamy obie tablice jedynkami i rozpoczynamy od drugiej liczby (gdyż dla pierwszej i tak nie mamy $a_j$). Dostajemy 2 i idziemy od początku. 2 < 3, więc sprawdzamy jaki był najdłuższy ciąg, którego ostatnie 2 elementy rosną. Widzimy, że $inc[0]=1$ (indeksując od 0). Dodając 1 do tego podciągu możemy otrzymać podciąg o długości 2. Aktualizujemy: $dec[1]=2$, jako że poprzednio mieliśmy $dec[1]=1$. Następnie dostajemy 1. Sprawdzamy pierwszy wyraz. 1 < 3, więc $dec[2]=inc[0]+1=2$. Następnie sprawdzamy drugi wyraz - 1 < 2, więc ponownie $dec[2]=inc[1]+1=2$. Kolejne jest 3. 3=3, więc przechodzimy dalej. 3 > 2. Sprawdzamy więc wartość $dec[1]+1=3$. Aktualizujemy $inc[3]$ i idziemy dalej. 3 > 1. Sprawdzamy $dec[2]+1=3$ - nie musimy nic aktualizować, gdyż przed chwilą otrzymaliśmy to samo. Na koniec przechodzimy tylko wszystkie komórki tablic $inc$ i $dec$ i wybieramy największą wartość - 3.

Złożoność: $O(n^2)$, bo dla każdego z $n-1$ wyrazów sprawdzamy wszystkie poprzednie. Złożoność pamięciowa: $O(n)$, gdyż mamy 2 tablice po $n$ elementów.

Algorytm:

int main()
{
    int t, n, x, i, j, tab[MAX_N], inc[MAX_N], dec[MAX_N];

    for(get(t); t--; )
    {
        get(n);
        for(x = -1, i = 0; i < n; ++i)
            inc[i] = dec[i] = 1;
        for(i = 0; i < n; ++i)
            get(tab[i]);
        for(i = 1; i < n; ++i)
            for(j = 0; j < i; ++j)
                if(tab[j] < tab[i] && inc[j]+1 > dec[i])
                    dec[i] = inc[j]+1;
                else if(tab[j] > tab[i] && dec[j]+1 > inc[i])
                    inc[i] = dec[j]+1;
        for(i = 0; i < n; ++i)
        {
            if(dec[i] > x)
                x = dec[i];
            if(inc[i] > x)
                x = inc[i];
        }
        print(x);
    }
}

Rozwiązanie jeszcze sprytniejsze:

Możemy również rozwiązać to zadanie zachłannie. Trzeba zauważyć, że nie interesują nas de facto owe liczby, lecz jedynie ich spadki (0) lub wzrosty (1). Zamieńmy je więc! Cóż prostszego. Dla ciągu 3,2,1,1,3,2,1 otrzymamy 0,0,0,1,0,0. Jeśli dwie kolejne liczby są takie same to nie ma znaczenia czy zaklasyfikujemy ową parę jako spadek czy wzrost. Jak widzimy, mamy o 1 element mniej. Przechowujemy teraz bowiem nie wyrazy, ale ich pary. Mając taki ciąg 0 i 1 możemy bez problemu obliczyć wynik. Wystarczy zliczyć ilość spójnych ciągów 0 i 1. Oznaczamy $wynik=1$ (bo musimy uwzględnić dodatkowy wyraz, który straciliśmy zmieniając wyrazy na pary wyrazów) oraz $last=-1$. Napotykamy pierwsze 0. Widzimy, że $0 \ne last$, więc inkrementujemy wynik i aktualizujemy $last=0$. Następnie znów mamy 0. $0 = last$, więc nie inkrementujemy wyniku. I tak do końca.

Złożoność: $O(n)$, gdyż najpierw zamieniamy $n$ liczb na 0 i 1, a następnie przechodzimy wszystkie obliczając wynik. Złożoność pamięciowa: $O(n)$.

Algorytm:

int main()
{
    int t, n, x, i, x2, tab[MAX_N];

    for(get(t); t--; )
    {
        get(n);
        for(i = 0; i < n; ++i)
        {
            get(x);
            if(i) // mamy tylko n-1 par; dla pierwszego elementu nie mamy poprzedniego elementu do pary
                tab[i] = x2 > x; // x2 < x też zadziała, będziemy mieli wtedy na odwrót 0 i 1
            x2 = x;
        }
        for(x = i = 1; i < n; ++i)
            if(i < 2 || tab[i] != tab[i-1]) // dla pierwszego wyrazu lub gdy wyraz nie jest równy poprzedniemu inkrementuj wynik
                ++x;
        print(x);
    }
}

Rozwiązanie najsprytniejsze:

Czemu poprzednie rozwiązanie nie jest najsprytniejsze (i nie przechodzi w zadaniu)? Przecież nie da się uzyskać lepszej złożoności, jako że mamy taką złożoność, jaka jest ilość danych wejściowych. Owszem, nie da się, lecz da się uzyskać lepszą złożoność pamięciową. Nie musimy bowiem tablicować owych 0 i 1, lecz na bieżąco je wykorzystywać. Załóżmy, że mamy ciąg 3,2,1,2. Dostajemy pierwszy wyraz, zapamiętujemy go następnie mamy 2. Mamy więc pierwszą parę, którą również zapamiętujemy jako 1 (gdyż 3>2). Następnie mamy 1. 2>1, więc znów mamy 1 - nie inkrementujemy wyniku. Dalej jest 2. 1<2, więc tym razem mamy 0, a zatem inkrementujemy wynik.

Złożoność: $O(n)$. Złożoność pamięciowa: $O(1)$.

Algorytm:

int main()
{
    int t, n, x, i, x2, y, z;

    for(get(t); t--; )
    {
        get(n);
        for(y = i = 0; i < n; ++i)
        {
            get(x);
            if(i < 2 || z != (x2 > x))
                ++y;
            z = x2 > x;
            x2 = x;
        }
        print(y);
    }
}

Uwaga: W zadaniu jest przyjęte, że każde 2 kolejne wyrazy różnią się od siebie. Powyższe programy nie działają zatem dla przypadków gdzie $a_i = a_{i+1}$ dla jakiegoś $i$.