https://spoj.com/ALGOLIGA/problems/AL_17_02
https://pl.spoj.com/problems/AL_17_02
Skrócony opis problemu:
Dla danego ciągu $n$ liczb wyznacz długość najdłuższego spójnego podciągu, który zawiera co najwyżej dwa różne wyrazy.
Rozwiązanie naiwne:
Dla każdego spójnego podciągu sprawdzić czy nie zawiera więcej niż 2 wyrazów i wypisać największy ze spełniających warunek.
Złożoność: $O(n^3)$, bo ilość spójnych podciągów ciągu o długości $n$ wynosi $\frac{n(n+1)}{2}$, a dla każdego z nich musimy sprawdzić czy nie zawiera więcej niż 2 różnych elementów, co pesymistycznie może nam zająć $O(n)$ czasu.
Rozwiązanie mniej naiwne:
Możemy wymyślić równie prosty, a trochę szybszy algorytm. Oczywistością jest, że nasz wynikowy podciąg ma początek i koniec. Kolejnym truizmem jest, że ostatni wynikowego podciągu jest albo ostatnim elementem ciągu, albo po nim następuje wyraz, który nie równa się żadnemu wyrazowi z podciągu (bo inaczej moglibyśmy przedłużyć ten podciąg, a jest on wynikowym, czyli najdłuższym możliwym podciągiem, który spełnia warunek zadania). A zatem co możemy zrobić? Ano możemy każdą z $n$ liczb traktować jako początek ciągu. Jeśli np. założymy, że czwarta liczba jest początkiem naszego ciągu to możemy z łatwością obliczyć długość tego ciągu. Po prostu sprawdzamy kolejne elementy, aż napotkamy koniec ciągu albo aż kolejny element będzie trzecią wartością w danym podciągu.
Optymalizacja:
Można przyspieszyć ten algorytm kończąc pętlę główną, gdy dla któregoś początku wyjdziemy poza koniec ciągu. To by oznaczało, że od tego elementu do końca mamy podciąg spełniający warunek zadania. Nie ma więc sensu sprawdzać kolejnych początków, bo na pewno otrzymamy mniejszy podciąg.
Złożoność: $O\left(n^2\right)$, bo każdą z $n-1$ liczb (oprócz ostatniej, bo to nie ma sensu) ustawiamy jako początek podciągu i przechodzimy pesymistycznie wszystkie pozostałe elementy ciągu.
Algorytm z optymalizacją:
int main()
{
int n, a, b, x, max = 0, tab[10009];
get(n, tab);
for(int i = 0; i < n; ++i)
{
a = tab[i]; b = -1; x = 1;
for(int j = i+1; j < n; ++j)
{
if(tab[j] == a || tab[j] == b)
{
++x;
if(x > max)
max = x;
}
else if(b < 0)
{
++x;
b = tab[j];
if(x > max)
max = x;
}
else
break;
}
if(j == n)
break;
}
print(max);
}
Rozwiązanie sprytne:
Możemy wyczuć, że da się znaleźć ten podciąg przechodząc otrzymany ciąg raz. I faktycznie, da się - wystarczy być zachłannym.
Na początku sprawdźmy 2 pierwsze elementy ciągu. Jeśli są takie same to sprawdźmy kolejny element i róbmy tak, aż otrzymamy wyraz, który będzie się różnił od poprzedniego, zliczając ile elementów przeszliśmy. Gdy to nastąpi, stwórzmy sobie następujące zmienne: $a$, $b$, $x$, $y$ oraz $max$. Pierwsze 2 przechowywać będą owe 2 różne liczby w naszym spójnym podciągu. $b$ będzie przechowywać tą, która wystąpiła ostatnia. $x$ będzie przechowywać długość spójnego podciągu, który uzyskaliśmy do danego momentu z liczb $a$ i $b$. $y$ natomiast będzie przechowywać długość podciągu spójnego, składającego się wyłącznie z liczb $b$ licząc od końca momentu do którego doszliśmy. $max$ to po prostu maksymalne $x$ jakie osiągnęliśmy. Np. dla ciągu: 3122121212123232323332222 wartości zmiennych to: $a = 3$, $b = 2$, gdyż ostatnią liczbą jest 2, a przedostatnią 3. $x = 14$, bo ciąg składający się z 2 i 3 począwszy od końca ma długość 14. $y = 2$, gdyż mamy 4 $b = 2$ na końcu. No i $max = 14$, bo akurat $x$ jest największe do tej pory (gdyby dodać 100 trójek na początku, to $max = 102$).
No i teraz jak modyfikujemy nasze zmienne. Jeśli kolejnym wyrazem będzie $b$ to po prostu zwiększamy $x$ oraz $y$. Jeśli następnym elementem będzie natomiast $a$, to co prawda również inkrementujemy $x$, ale $y$ ustawiamy na 1, bo mamy od końca spójny ciąg 1-elementowy o wszystkich wartościach równych. Musimy też zamienić $a$ z $b$ miejscami, jako że stare $a$ wystąpiło bliżej końca. Tak więc stare $a$ to teraz nowe $b$. Ostatni przypadek to sytuacja, gdy mamy nową liczbę, która nie jest równa ani $a$, ani $b$. Powiedzmy, że otrzymujemy $c$. $a$ będzie oczywiście wynosiło $b$, czyli ostatnią liczbę przed $c$, a $b$ będzie od teraz wynosiło $c$ (czyli $a = b; b = c$). Co z $x$? Ano po to właśnie mamy $y$! $x$ wyniesie $y+1$, bo mieliśmy spójny ciąg wyrazów o wartości starego $b$, a teraz doszło $c$, więc 1 wyraz więcej. $y$ natomiast będzie znów równe 1. Musimy w tym miejscu jeszcze zaktualizować $max$ - to jest zanim zaktualizujemy $x$, ale tylko jeśli $x > max$. Ot, cała filozofia!
Złożoność: $O(n)$, gdyż przechodzimy każdą liczbę tylko raz.
Algorytm:
int main()
{
int t, n, a, b, c, x = 2, y = 1, max = 0;
get(n, a);
if(n == 1)
{
print(1);
continue;
}
get(b); n -= 2;
while(a == b && n)
get(b),
++x,
--n;
if(!n) // jeśli cały ciąg składa się jedynie z 2 liczb
{
print(x);
continue;
}
while(n--)
{
get(c);
if(c == b)
++x,
++y;
else if(c == a)
++x,
y = 1,
a = b,
b = c;
else
{
if(x > max)
max = x;
x = y+1;
y = 1;
a = b;
b = c;
}
}
print(x > max ? x : max); // aktualizujemy maxa przy wypisaniu
}
Brak komentarzy:
Prześlij komentarz