Wielka Przesmycka Reloaded 2011 - omówienie zadań

22.11.2011

E Drużyna

Po usunięciu z treści profesora M. otrzymujemy dość krótkie sformułowanie: dla danych dwóch napisów $ s $ i $ t $ chcemy policzyć (modulo $ 10^{9}+7 $) ile jest różnych napisów $ x $, które są podciągami (niekoniecznie spójnymi) $ t $, ale jednocześnie $ s $ jest podciągiem $ x $. Limity wersji basic ($ 100 $) sugerują rozwiązanie sześcienne, a wersji professional ($ 1000 $) kwadratowe.

Rozwiązywanie warto zacząć od uproszczonej wersji zadania, w której $ s $ jest pusty. Zacznijmy od prostej obserwacji: jeśli ktoś poda nam $ x $, można bardzo łatwo sprawdzić czy jest on podciągiem $ t $. Wystarczy tylko znaleźć pierwsze wystąpienie $ x[1] $ w $ s $, na prawo od niego wyszukać pierwsze wystąpienie $ x[2] $, i tak dalej... Oczywiście nie ma co liczyć na to, że ktoś poda nam chociaż jedno prawidłowe $ x $ (bo właściwie po co miałby to robić?). Widać jednak, że warunek, który musimy sprawdzać, jest w pewnym sensie lokalny. A dokładniej, aby policzyć różne podciągi $ t $ możemy wysumować po wszystkich literach $ c $ (występujących w $ t $) liczbę różnych podciągów sufiksu $ t $ zaczynającego się tuż za pierwszym wystąpieniem $ c $ ! Co od razu nasuwa proste rozwiązanie używające programowania dynamicznego, które działa w czasie $ \mathcal{O}(|t||\Sigma|) $, gdzie $ |\Sigma| $ jest rozmiarem alfabetu. Dość łatwo zmniejszyć jego złożoność do $ \mathcal{O}(|t|) $ zauważając, że suma, którą liczymy dla $ t $ różni się co najwyżej dwoma składnikami od sumy, którą już policzyliśmy dla $ t[2..|t|] $ (być może trzeba wykreślić jeden z nich i dodać nowy).

No dobra, ale przecież $ s $ wcale nie musi być pusty (a właściwie to zgodnie z treścią zadania nigdy taki nie będzie, co sprawia, że powyższe rozumowanie może wydawać się lekko bezużyteczne). Na szczęście nawet w ogólnym przypadku możemy użyć bardzo podobnego pomysłu. Jeśli znamy pierwszą literą $ x $, to oczywiście najlepiej dopasować ją do pierwszego wystąpienia w $ t $. Mamy dwie możliwe sytuacje:

  • $ x[1]=s[1] $, wtedy $ x[2..|x|] $ musi zawierać $ s[2..|s|] $.
  • $ x[1]\neq s[1] $, wtedy $ x[2..|x|] $ musi zawierać całe $ s $.

Widać więc, że zgadnięcie $ x[1] $ pozwoliłoby by nam zredukować oryginalny problem do podobnego, tyle że mniejszego. Zgadywać nie umiemy, ale możemy wysumować odpowiedzi po wszystkich możliwych $ x[1] $. Wszystkie pojawiające się problem mają taką samą strukturę: $ s $ jest sufiksem oryginalnego $ s $, a $ t $ oryginalnego $ t $. A więc znowu możemy użyć programowania dynamicznego, tym razem uzyskując rozwiązanie działające w czasie $ \mathcal{O}(|s||t||\Sigma|) $, co w zupełności wystarczało do pokonania wersji basic. W zależności od szczegółów implementacji dla wersji professional taki pomysł kończył się komunikatem Accepted lub Time Limit Exceeded. Naszą intencją było tak naprawdę zachęcenie Was do zaimplementowania rozwiązania o złożoności $ \mathcal{O}(|s||t|) $ używając podobnego pomysłu jak ten użyty do zmniejszenia czasu działania w prostszej wersji. Można zauważyć, że sumy liczone dla kolejnych podproblemów są tak naprawdę bardzo podobne do siebie, a w związku z tym zamiast liczyć je za każdym razem od początku, możemy uaktualnić poprzednio wyznaczoną wartość. Szczegóły pozostawiamy domyślności Czytelnika.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com