Wielka Przesmycka Reloaded 2011 - omówienie zadań

22.11.2011

F To może być toczeń

Na wejściu dostajemy dwa napisy $ s $ i $ t $, obydwa tej samej długości $ n $. Chcemy znaleźć ich najdłuższy wspólny niemalejący podciąg (niekoniecznie spójny). W wersji basic napisy składają się tylko z cyfr $ 0 $ i $ 1 $. Czyli szukamy największej możliwej sumy $ x+y $ dla której $ 0^{x}1^{y} $ jest podciągiem zarówno $ s $ jak i $ t $.

Zastanówmy się najpierw nad łatwiejszym pytaniem. Powiedzmy, że ktoś zdradził nam $ x $. Jak znaleźć najlepsze możliwe $ y $? Prosto: bierzemy pierwsze $ x $ zer z obydwu napisów, a następnie liczymy ile jest jedynek na prawo od nich (w obydwu napisach). Najlepsze możliwe $ y $ to maksimum z tych dwóch liczb jedynek. Jeśli wcześniej skonstruujemy listę wszystkich zer, a dla każdego sufiksu zapamiętamy liczbę jedynek, łatwo wyznaczymy $ y $ w czasie $ \mathcal{O}(1) $. Oczywiście tak naprawdę nie znamy $ x $, ale przecież możemy sobie pozwolić na sprawdzenie wszystkich $ n $ możliwości, otrzymując sumaryczną złożoność $ \mathcal{O}(n) $.

W wersji professional sytuacja robi się odrobinę bardziej interesująca: napisy składają się z cyfr $ 0 $, $ 1 $ i $ 2 $. Czyli szukamy największej możliwej sumy $ x+y+z $ dla której $ 0^{x}1^{y}2^{z} $ jest podciągiem obydwu napisów. Zakładając, że znamy $ z $, możemy użyć rozwiązania z wersji basic. Niestety złożoność takiego rozwiązania to $ \mathcal{O}(n^{2}) $, więc wyraźnie widać, że potrzebujemy jakiegoś dodatkowego pomysłu.

Spróbujemy sprawdzać kolejne wartości $ z $, zaczynając od $ \min(\#_{2}s,\#_{2}t) $, a kończąc na $ 0 $. Na cała sytuację warto popatrzeć w trochę inny sposób: przechowujemy dwa napisy, do których dopisujemy (na końcach) cyfry $ 0 $ i $ 1 $. Po każdym dopisaniu interesuje nas ich najdłuższy wspólny podciąg postaci $ 0^{x}1^{y} $. Czyli tak naprawdę chcemy skonstruować strukturę danych opisującą wszystkie (lub tylko te najbardziej interesujące) pary $ (x,y) $... co od razu podpowiada, że być może w całą historię jest zamieszana geometria (szczególnie, że jest to już ostatnie zadanie, w żadnym z poprzednich nie było nawet śladu punktów na płaszczyźnie, a przecież nie może tego zabraknąć na żadnych zawodach!).

Powiedzmy, że aktualne napisy to $ s' $ i $ t' $. Niech $ a(k) $ i $ b(k) $ będą liczbą jedynek na prawo od $ k $-tego zera w, odpowiednio, pierwszym i drugim z nich (jeśli w którymś napisie jest mniej niż $ k $ zer, $ \infty $). Interesuje nas wartość $ \max_{k} k + \min(a(k),b(k)) $. Czyli jeśli oznaczymy $ a'(k)=k+a(k) $ i $ b'(k)=k+b(k) $ i utworzymy dla każdego $ k $ punkt $ \left(a'(k),b'(k)\right) $, chcemy znaleźć największe $ t $, dla którego mamy punkt o obydwu współrzędnych nie mniejszych $ t $, patrz rysunek 7.

Rysunek 7: Redukcja oryginalnego problemu do pytan o punkty na płaszczyznie.

 

Pozostają dwa pytania:

  1. jak właściwie znaleźć takie $ t $
  2. czy trzeba budować ten zbiór punktów za każdym razem od początku?

Zacznijmy od tego drugiego. Dość łatwo zauważyć, że po dopisaniu do jednego z napisów jedynki wystarczy przesunąć aktualny zbiór punktów o jeden w pionie lub poziomie, a po dopisaniu zera być może trzeba dorzucić do niego jeden nowy punkt. Szukanie największego $ t $ wydaje się odrobinę bardziej skomplikowane. Na szczęście można zauważyć, że nie ma sensu przechowywać dwóch punktów $ (x,y) $ i $ (x',y') $, dla których $ x\leq x' $ i $ y\leq y' $: ten drugi będzie zawsze przynajmniej tak samo "dobry" jak pierwszy. Czyli bez straty ogólności możemy założyć, że aktualny zbiór to $ (x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{k},y_{k}) $, gdzie $ x_{1}<x_2<\ldots<x_k $, ale $ y_1>y_{2}>\ldots >y_{k} $. Chcemy zmaksymalizować $ min_{i}f(i) $, gdzie $ f(i)=\min(x_{i},y_{i}) $. Po chwili zastanowienia można zauważyć, że najpierw rośnie, a później maleje. Najprościej przekonać się o tym patrząc na rysunek 8.

Rysunek 8: $ f(i) $ jest bitoniczne.

 

Czyli tak naprawdę możemy wyznaczyć $ \min_{i} f(i) $ używając wyszukiwania binarnego (lub ternarnego, w zależności od tego jak spojrzeć na całą historię) w "okrojonym" zbiorze. Pozostaje więc tylko jedno (ale za to bardzo ważne) pytanie: jak właściwie przechowywać ten zbiór? Po dodaniu nowego punkty być może będziemy musieli usunąć z niego niektóre elementy (bo przestaną być interesujące). Z drugiej strony, chcielibyśmy móc przeszukiwać go binarnie. Okazuje się, że dość łatwo rozwiązać ten problem przechowując zbiór w dowolnym drzewie zrównoważonym. A co najlepsze, wcale nie trzeba implementować go samemu, wystarczy użyć set<pair<int,int>>! Wymaga to jednak jednej nietrywialnej obserwacji: wyszukiwanie binarne tak naprawdę nie ma tutaj sensu. O wiele lepiej za każdym razem przesuwać się w lewo lub prawa tak długo, jak prowadzi to do polepszenia wyniku. Na pierwszy rzut oka wydaje się to potencjalnie zabójcze czasowo, ale po chwili zastanowienia okazuje się, że możemy zamortyzować wszystkie ruchy liczbą wszystkich przesunięć o jeden w pionie i poziomie. Przy odrobinie staranności czas działania takiego rozwiązania to $ \mathcal{O}(n\log n) $.

Zadanie dedykujemy wszystkim fanom doktora House'a i polskiej służby zdrowia. Warto też wspomnieć, że powyższy pomysł może posłużyć do skonstruowania rozwiązania liniowego. Szczegóły pozostawiamy (jak zwykle) domyślności Czytelnika.

 

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com