Informatyczny kącik olimpijski

Yet Another Substring Reverse

Tym razem omówimy zadanie Yet Another Substring Reverse, które pojawiło się na portalu www.codeforces.com.

Zadanie. Dane jest słowo $s = s s ...s 12 n$ o długości $n,$ zawierające wystąpienia części liter alfabetu angielskiego $A.$ W słowie $s |$ należy odwrócić jedno podsłowo, tzn. zastąpić je zapisem od prawej do lewej, aby otrzymać możliwie najdłuższe różnorodne podsłowo, czyli takie, które nie zawiera powtórzeń liter. Jaka jest długość najdłuższego różnorodnego podsłowa, które można uzyskać? Przykładowo dla $|s = „bbaacc ”$ wynikiem jest 3. Po odwróceniu fragmentu od trzeciej do szóstej litery otrzymujemy $„bbacca ”,$ którego najdłuższy różnorodny fragment to $„bac ”.$

Niech $|sl p$ oznacza podsłowo $slsl+1...sp.$

Na samym początku zauważmy, że długość różnorodnego podsłowa nie przekroczy $A$

Najdłuższe różnorodne podsłowo $O$
Załóżmy przez chwilę, że nie wykonujemy odwrócenia i chcemy znaleźć długość najdłuższego różnorodnego podsłowa. Dla każdej pozycji początkowej wyznaczmy najdłuższe różnorodne podsłowo, które się w niej zaczyna. Formalnie dla ustalonego $|1⩽ i⩽ n$ znajdźmy takie największe $|ki,$ że $si ki$ jest różnorodne. Zacznijmy od jednoliterowego podsłowa $|si$ i rozszerzajmy je o kolejne litery, dopóki nie nastąpi powtórzenie. Do sprawdzania, czy jakaś litera wystąpiła wcześniej, można wykorzystać tablicę zliczającą, którą po każdym rozszerzeniu aktualizujemy. Opisane rozwiązanie działa w czasie $O(n$ gdyż od każdej pozycji początkowej wykonamy co najwyżej $| A$ rozszerzeń w prawo.

Najdłuższe różnorodne podsłowo $O |$
W tym rozwiązaniu, podobnie jak wcześniej, dla każdej pozycji $|1⩽ i⩽ n$ chcemy wyznaczyć takie największe $ki,$ że $si ki$ jest różnorodne. Skorzystajmy z metody gąsienicy. Otóż, tym razem nie będziemy dla każdej pozycji początkowej rozpoczynali przeszukiwania od słów jednoliterowych. Zauważmy, że jeśli $|s i− 1 ki 1$ jest różnorodne, to również $s i ki 1$ jest różnorodne. Zatem nie ma potrzeby sprawdzania słów, które kończą się wcześniej niż $|ki− 1.$ Do sprawdzania powtórzeń wykorzystujemy tablicę zliczającą. Przy rozszerzaniu słowa z prawej strony dodajemy literę, a przy przejściu do kolejnej pozycji początkowej usuwamy literę z tablicy zliczającej. Rozwiązanie działa w czasie $O(n$ gdyż każda litera zostanie dokładnie raz dodana i raz usunięta z tablicy zliczającej.

Rozwiązanie $|O$
Opisaliśmy metody znajdowania najdłuższego różnorodnego podsłowa, zatem możemy przejść do pierwszego rozwiązania zadania. Rozważmy odwrócenie każdego z $|n 1+n- 2$ podsłów. Dla każdego przypadku znajdźmy najdłuższe różnorodne podsłowo za pomocą jednej z wyżej opisanych metod i wybierzmy najlepszy wynik. W zależności od wykorzystanej metody otrzymamy rozwiązanie $O(n3$ lub $O(n2(n$

Rozwiązanie $|O$
Zauważmy, że możemy zredukować zadanie do znalezienia dwóch różnorodnych podsłów, które mają rozłączne zbiory liter oraz największą sumaryczną długość. Formalny dowód tego faktu pozostawiamy Czytelnikowi, a teraz pokażemy, jak dwa podsłowa, $sl1 p1$ oraz $|sl2 p2,$ niemające wspólnych liter umieścić obok siebie za pomocą jednego odwrócenia. Załóżmy bez straty ogólności, że $s l1 p1$ występuje na lewo od $s , l2 p2$ wówczas należy odwrócić $|sp1+1 p2.$ Teraz $sl1 p1+p2−l2+1$ jest różnorodne.

Znajdźmy wszystkie różnorodne podsłowa, których jest $O(n$ Następnie rozważmy każdą z $|O(n$ par takich podsłów. Jeśli podsłowa mają rozłączne zbiory liter, wtedy razem tworzą różnorodne podsłowo. Sprawdzenie, czy zbiory liter są rozłączne, możemy wykonać metodą zliczenia w czasie $|O($ Spośród par tworzących różnorodne podsłowa wybieramy tę, której sumaryczna długość fragmentów jest największa. Otrzymaliśmy rozwiązanie o złożoności czasowej $|O(n2$

Rozwiązanie $|O$
Zauważmy, że kolejność liter w podsłowie nie ma znaczenia, zatem każde różnorodne podsłowo możemy rozważać jako zbiór liter. Spośród wszystkich podsłów o długości co najwyżej $A$ znajdźmy te, które są różnorodne, i zbiory ich liter oznaczmy jako zbiór $R. |$ Przykładowo dla $′ ′ ′ ′ ′ ′′ ′ |s = „bab”,R = {{ a },{b },{ a ,b }}.$ Wyznaczenie $R$ zajmuje czas $|O(n$ zaś moc $R$ wynosi co najwyżej $|2SAS.$ Zadanie redukuje się teraz do znalezienia dwóch rozłącznych zbiorów w $R,$ których suma ma największą moc.

Dla każdego zbioru $r∈ R$ znajdźmy taki zbiór $|r′ ∈R,$ że $r ∩r′ =∅$ oraz $| r∪ r′$ jest maksymalne. Innymi słowy dla każdego zbioru znajdźmy inny zbiór, który tworzy z nim najlepszy wynik. Wówczas odpowiedzią w zadaniu jest maksimum z rozważonych przypadków. Niech $W[a]$ dla każdego $|a ⊆A$ oznacza moc największego takiego zbioru $r |∈ R,$ że $|r⊆ a.$ Teraz $|r∈ R$ tworzy najdłuższe różnorodne podsłowo o długości $- | r + W[r],$ gdzie $- r$ oznacza dopełnienie $|r.$

Pozostało nam jeszcze wyznaczyć wartości $W,$ które będziemy obliczali w kolejności niemalejących mocy zbiorów. Załóżmy, że obliczamy $|W[a]$ i mamy obliczone $|W[b]$ dla wszystkich $b ⊆a.$ Jeśli $a ∈ R,$ wówczas $|W[a] = a .$ W przeciwnym przypadku $W[a] < a ,$ czyli największy podzbiór $a$ należący jednocześnie do $R$ nie zawiera jakiegoś elementu $|a,$ zatem $W[a] = maxe> aW[a ∖ e] .$ Obliczenie $W[a]$ zajmuje czas $|O($ wartości tablicy $W$ jest $|O(2SAS),$ zatem czas potrzebny do obliczenia $W$ wynosi $O(2SASA$ Całe rozwiązanie działa w czasie $|O($