https://pl.spoj.com/problems/AL_05_04
Skrócony opis problemu:
Dla $t$ danych stringów znajdź dla każdego stringa $s_i$ jego krotność palindromiczną $k_i$, a następnie znajdź i wypisz medianę zbioru $k_i$.
Krotność palindromiczna jest zdefiniowana następująco:
- jeśli wyraz nie jest palindromem, to jego krotność wynosi 0 - jest palindromem 0-krotnym
- jeśli wyraz ma jedną literę, to jest palindromem 1-krotnym
- jeśli wyraz $s$ jest palindromem $k$-krotnym, to wyrazy $s + s$ (+ oznacza konkatenację, czyli sklejanie stringów) oraz $s + c + s$ (gdzie $c$ to jakiś znak) są palindromamy $n+1$-krotnymi
Np. "abc" ma krotność 0, "kajak" ma krotność 1, "oko" ma krotność 2, "oooo" ma krotność 3, a "aabaacaabaa" ma krotność 4.
Rozwiązanie:
Możemy rozwiązać to zadanie rekurencyjnie. W każdym wywołaniu musimy najpierw sprawdzić czy wyraz jest palindromem. Jeśli jest, to zwiększamy jego krotność (na początku na krotność 0) i wywołujemy funkcję kolejny raz, ale dla pierwszej (albo drugiej) połowy stringa. Nie musimy bowiem sprawdzać obu części, gdyż jeśli wyraz, który rozpatrujemy jest palindromem, to jego połowy są sobie równe. Gdy dojdziemy do jedno-znakowego stringa, to zwracamy 1.
Jak już obliczymy wszystkie $t$ krotności, to możemy znaleźć medianę w czasie liniowym korzystając np. z algorytmu magicznych piątek albo... wbudowanej funkcji nth_element.
Złożoność: $O(t \cdot n)$, bo dla $t$ wyrazów obliczamy ich krotność w czasie liniowym, a następnie w czasie $O(t)$ obliczamy medianę. Skąd wiemy, że obliczamy krotność liniowo? Wychodzi nam to z rozwiązania równania rekurencyjnego:
$$T(n) = T\left(\frac{n}{2}\right) + n$$
Tutaj podałem 2 wzory na rozwiązania równań rekurencyjnych.
Algorytm:
int tab[500009], dl;
char tmp[5000009];
int pal(int i) // i oznacza ostatnią pozycję wyrazu, który aktualnie sprawdzamy
{
if(!i) // dla wyrazu jednoliterowego
return 1;
if(i == 1) // dla wyrazu dwuliterowego - taka mała optymalizacja
return tmp[0]==tmp[1] ? 2 : 0;
int j, ok = 1;
for(j = 0; j <= (i-1)/2; ++j) // sprawdzamy czy wyraz jest palindromem
if(tmp[j] != tmp[i-j])
{
ok = 0;
break;
}
if(ok)
return pal((i-1)/2)+1;
else
return 0;
}
int main()
{
int t, i;
get(t);
for(i = 0; i < t; ++i)
{
get(tmp);
dl = strlen(tmp);
tab[i] = pal(dl-1);
}
nth_element(tab, tab+(t-1)/2, tab+t);
print(tab[(t-1)/2]);
}
Wersja iteracyjna o takiej samej złożoności:
int main()
{
int t, i, j, dl, ok, tab[t], tmp[dl];
get(t);
for(i = 0; i < t; ++i)
{
get(tmp);
dl = strlen(tmp)-1;
tab[i] = 0;
while(1)
{
for(ok = j = 0; j <= (dl-1)/2; ++j)
if(tmp[j] != tmp[dl-j])
{
ok = 1;
break;
}
if(ok)
break;
++tab[i]; // jeśli tu doszło to znaczy, że mamy kolejny palindrom, bo nie wyszło z pętli w warunku powyżej
if(!dl) break;
dl = (dl-1)/2;
}
}
nth_element(tab, tab+((t-1)/2), tab+t);
print(tab[(t-1)/2]);
}
Rozwiązanie nr 2:
Algorytm:
Możemy lekko zmodyfikować powyższy algorytm. Mianowicie, skorzystamy z haszowania wielomianowego. Przedstawimy wyraz w postaci liczb. Dzięki temu będziemy mogli porównywać podwyrazy w czasie stałym, a nie liniowym. Będziemy musieli za to obliczyć dwie tablice z haszami dla każdego wyrazu, w czasie liniowym.
O haszowaniu.
Haszowanie polega na zamianie stringa na liczbę, a raczej na ciąg liczb. Przedstawiamy po prostu stringa w systemie pozycyjnym o podstawie np. 29. Czemu 29? Gdyż alfabet ma 26 liter, a chcemy mieć liczbę pierwszą w podstawie, żeby zmniejszyć prawdopodobieństwo, że nam się coś przekłamie (o tym zaraz). No więc będziemy mieli dla każdego $s_i$ jego haszowy odpowiednik $h_i$.
$$h_i = s_i + x \cdot s_{i+1} + x^2 \cdot s_{i+2} + ... + x^{n-1-i} \cdot s_{n-1}$$
Tak więc żeby to szybko zrobić możemy zacząć od tyłu i skorzystać z wzoru $h_i = h_{i+1} \cdot 29 + s_i$. Przy czym $s_i$ zamieniamy na liczbę. 'a' zamieniamy na 1, 'b' na 2, itd. (wzór to zatem $s_i-'a'+1$).
Jak już mamy tę tablicę haszy to możemy dzięki nim obliczyć w czasie stały hasz dowolnego podciągu naszego stringa. Dzięki temu możemy sprawdzić czy 2 stringi (albo podstringi) są sobie równe w czasie stałym.
Jak to zrobić? Ano żeby dostać podciąg $s$ od $a$ do $b$ korzystamy ze wzoru nr 1 $h_a-h_{b+1} \cdot 29^{b-a+1}$. Czemu tak? Ano temu, że $h_i$ to są de facto sumy prefiksowe. Więc odejmujemy od początku przedziału (bo im mniejszy indeks, tym większe $h_i$, bo sumowaliśmy od tyłu) odejmujemy wartość o 1 za końcem przedziału, ale przemnożoną przez odpowiednią potęgę naszej bazy (29), aby się potęgi zgadzały (w przeciwnym wypadku 'a' na pozycji wcześniejszej nie będzie równe 'a' na pozycji późniejszej).
Ostatnią rzeczą, o której należy pamiętać jest wielkość tych liczb. Będę one ogromne. Korzystanie z bignumów nie ma sensu, gdyż zepsuje nam złożoność i skomplikuje program. Będziemy więc po prostu wykonywali operację modulo jakaś duża liczba pierwsza $p$ na pośrednich wynikach. Dzięki temu zmieścimy się w standardowych typach danych. Wadą tego rozwiązania jest to, że nie ma 100% pewności, że program zwróci dobre wyniki. Prawdopodobieństwo, że tak będzie jest jednak na tyle wielkie przy odpowiednio dużych liczbach pierwszych, że często się z tego korzysta.
W naszym przypadku potrzebujemy dwóch takich tablic, gdyż chcemy sprawdzić czy pierwsza połowa jest równa odwróconej drugiej połowie. Będziemy przechowywać zatem hasze i odwrócone hasze. I dla każdego wywołania rekurencyjnego sprawdzać pierwszą połowę ze wzoru nr 1 z drugą połową ze wzoru nr 2. Wzór nr 2 to odpowiednik wzoru nr 1, ale dla odwróconych haszy. Wygląda on tak: $rh_{b}-rh_{a-1} \cdot 29^{b-a+1}$. W poniższym programie będziemy korzystali z modyfikacji tego wzoru: $rh_{b+1}-rh_{a} \cdot 29^{b-a+1}$, gdyż dla odwrotnych haszy będziemy indeksować od 1, aby wstawić do pierwszego hasza 0 (w zwykłych haszach wstawiamy 0 do $h_n$).
Złożoność: $O(n)$, bo najpierw obliczamy liniowo 2 tablice $h$ i $rh$, wszystkie potęgi 29 (modulo $p$) również obliczamy liniowo, no i sama rekurencja będzie działała szybciej, bo w czasie logarytmicznym (bo najpierw wywołujemy funkcję dla $n$, potem dla $\frac{n}{2}$, potem dla $\frac{n}{2^2}$, itd.). Okazuje się jednak, że w tym zadaniu jest to wolniejsze od pierwszego algorytmu.
Algorytm:
#define SIZE 5000009
const unsigned long long MOD = 4611686018427387847LL;
const int BASE = 29;
int tab[500009], dl;
char tmp[SIZE];
unsigned long long hash[SIZE], revhash[SIZE], pot[SIZE];
int pal(int i)
{
if(!i)
return 1;
if(i == 1)
return tmp[0]==tmp[1] ? 2 : 0;
if(hash[0]-(hash[(i-1)/2+1]*pot[(i-1)/2+1])%MOD == revhash[i+1]-(revhash[i/2+1]*pot[i-i/2])%MOD)
return pal((i-1)/2)+1;
else
return 0;
}
int main()
{
int t, i, j, x, max;
pot[0] = max = 1;
get(t);
for(i = 0; i < t; ++i)
{
get(tmp);
dl = strlen(tmp);
if(dl > max) // żeby nie obliczać niepotrzebnie SIZE potęg jeśli stringi w teście będą długości 10
{
for(j = max; j < dl; ++j)
pot[j]= pot[j-1]*BASE%MOD;
max = dl;
}
for(j = dl-1, hash[dl] = 0; j >= 0; --j)
hash[j] = ( (hash[j+1]*BASE)%MOD + (tmp[j]-'a'+1) )%MOD;
for(j = 1, revhash[0] = 0; j <= dl; ++j)
revhash[j] = ( (revhash[j-1]*BASE)%MOD + (tmp[j-1]-'a'+1) )%MOD;
tab[i] = pal(dl-1);
}
nth_element(tab, tab+(t-1)/2, tab+t);
print(tab[(t-1)/2]);
}
Brak komentarzy:
Prześlij komentarz