Omówienie zadania Przeglądarka (I etap XXXIII OI, tura szkolna)

Rozwiązanie brutalne

Ustalmy pewną kolejność odwiedzania stron internetowych. Chcielibyśmy wyznaczyć minimalną liczbę znaków, które Bajtosia musi wpisać, aby odwiedzić strony w dokładnie tej kolejności. Jeśli rozważymy wszystkie możliwe \(n!\) kolejności i dla każdej z nich obliczymy tę minimalną liczbę znaków, to, wybierając najmniejszy spośród tych wyników, otrzymamy rozwiązanie zadania.

Powiedzmy więc, że ta kolejność jest już ustalona. Zbudujmy drzewo trie składające się z napisów będących adresami stron, które ma odwiedzić Bajtosia. Jasne jest, że w optymalnym rozwiązaniu napis znajdujący się w pasku przeglądarki zawsze będzie prefiksem pewnego adresu strony do odwiedzenia. Wobec tego możemy patrzeć na rozwiązanie jako na przejście po wspomnianym drzewie trie z dodatkowymi krawędziami wynikającymi z możliwości wciśnięcia klawisza TAB. Postąpimy więc następująco: potraktujemy drzewo trie jako graf, w którym każdy wierzchołek posiada krawędzie wagi 1 do swoich dzieci oraz do swojego rodzica (co odpowiada odpowiednio wciśnięciu jakieś literki na klawiaturze lub klawisza BACKSPACE). Dodatkowo dla każdego wierzchołka będziemy utrzymywać specjalną krawędź, także wagi 1, odpowiadającą wciśnięciu klawisza TAB. Początkowo ta krawędź będzie prowadziła do tego samego wierzchołka, z którego wychodzi, gdyż przed pierwszym wyszukaniem strony, klawisz TAB nic nie robi. Następnie, aby wyznaczyć liczbę ruchów potrzebną do wyszukania pierwszej strony, wystarczy znaleźć najkrótszą ścieżkę w tym grafie z korzenia drzewa do wierzchołka odpowiadającego tej stronie. Możemy to zrobić za pomocą algorytmu BFS, gdyż wszystkie krawędzie w grafie mają jednakową wagę. Po wciśnięciu ENTER i wyszukaniu pierwszej strony zaktualizujemy krawędzie odpowiadające wciśnięciu klawisza TAB dla wszystkich wierzchołków na ścieżce od korzenia do wierzchołka odpowiadającego pierwszej stronie, tak aby teraz prowadziły one do tego wierzchołka, ponieważ dokładnie te wierzchołki odpowiadają prefiksom właśnie wyszukanej strony. Następnie powtarzamy ten proces dla drugiej strony - znajdujemy najkrótszą ścieżkę, aktualizujemy krawędzie odpowiadające klawiszowi TAB na ścieżce do drugiej strony i tak dalej, aż odwiedzimy wszystkie strony.

Powyższy algorytm możemy zaimplementować w złożoności czasowej \(O(n!\cdot S\cdot n)\), gdzie \(S\) to suma długości wszystkich stron do odwiedzenia (czyli także ograniczenie na rozmiar drzewa trie), ponieważ dla każdej z \(n!\) permutacji uruchamiamy algorytm BFS w grafie o rozmiarze \(O(S)\) dokładnie \(n\) razy (raz dla każdej strony do odwiedzenia).

Rozwiązanie wzorcowe

Aby przyspieszyć powyższe rozwiązanie, skorzystamy z następującej obserwacji:

Lemat: W optymalnym rozwiązaniu zadania kolejność stron odwiedzanych przez Bajtosię będzie odpowiadać pewnej kolejności preorder odwiedzania wierzchołków drzewa trie odpowiadających tym stronom.

Dowód: Załóżmy, że dla pewnego wierzchołka \(v\) w drzewie trie wiemy, że wierzchołki odpowiadające stronom do odwiedzenia w jego poddrzewie stanowią spójny fragment w całej kolejności odwiedzania stron (przy czym jeśli \(v\) ma zostać odwiedzony, to zostanie odwiedzony jako pierwszy). Pokażemy, że wówczas dla dzieci \(v\) także tak jest. Stąd otrzymamy tezę, ponieważ takie rozumowanie możemy prowadzić od korzenia do liści drzewa trie. Załóżmy, że \(v\) nie jest liściem, gdyż w takim wypadku teza oczywiście zachodzi. Najpierw pokażmy, że jeśli \(v\) odpowiada pewnej stronie do odwiedzenia, to w pewnym optymalnym rozwiązaniu \(v\) zostanie odwiedzony jako pierwszy w swoim poddrzewie. Załóżmy, że mamy pewne optymalne rozwiązanie, w którym najpierw odwiedzamy pewne inne wierzchołki w poddrzewie \(v\), a następnie \(v\). Zobaczmy, że aby odwiedzić jakiekolwiek wierzchołki w poddrzewie \(v\), musimy najpierw znaleźć się w \(v\). Wchodząc do \(v\) po raz pierwszy, możemy od razu wcisnąć ENTER i kolejno TAB, aby natychmiast wrócić do \(v\) i następnie postępować tak, jak w rozważanym oryginalnym rozwiązaniu, pomijając odwiedzenie \(v\). Wystarczy teraz pokazać, że w ten sposób, nie odwiedzając \(v\) później, zaoszczędzimy przynajmniej dwa wciśnięcia klawiszy. Rozważmy dwa przypadki:

\(v\) poprzednio nie był ostatnim odwiedzonym wierzchołkiem w swoim poddrzewie. Wówczas istniały wierzchołki \(u\) oraz \(w\) w poddrzewie \(v\) takie, że odwiedziliśmy kolejno \(u\), następnie \(v\), a następnie \(w\). Zobaczmy, że skoro teraz nie musimy odwiedzać \(v\), to oszczędzamy wciśnięcie ENTER dla \(v\). Zobaczmy dalej, że w poprzednim rozwiązaniu po odwiedzeniu \(v\), chcąc dostać się do \(w\), musieliśmy najpierw jakoś wrócić do \(v\) (ponieważ po odwiedzeniu \(v\) wciśnięcie TAB na jakimkolwiek przodku \(v\) przenosi nas do \(v\), więc nie możemy go przeskoczyć), co wymaga przynajmniej jednego wciśnięcia klawisza (bo \(v\) nie jest korzeniem, gdyż odpowiada niepustemu słowu), którego teraz nie musimy wykonywać. W ten sposób łącznie oszczędzamy przynajmniej dwa wciśnięcia klawiszy.
\(v\) był ostatnim odwiedzonym wierzchołkiem w swoim poddrzewie. Wówczas istnieje wierzchołek \(u\) w poddrzewie \(v\), który odwiedziliśmy jako przedostatni. W nowym rozwiązaniu \(u\) jest ostatnim odwiedzonym wierzchołkiem w poddrzewie \(v\). Skoro nie musimy już odwiedzać \(v\) jako ostatni, oszczędzamy wciśnięcie ENTER dla \(v\). Ponadto, nie musimy już wracać korzenia z do \(v\) po wciśnięciu ENTER dla \(u\), co wymagało przynajmniej jednego wciśnięcia klawisza (bo, znów, \(v\) nie jest korzeniem). W ten sposób łącznie oszczędzamy przynajmniej dwa wciśnięcia klawiszy.

Teraz, wiedząc, że istnieje optymalny sposób odwiedzania stron, w którym \(v\) jest odwiedzony jako pierwszy w swoim poddrzewie, jeśli ma zostać odwiedzony, pokażemy, że istnieje także rozwiązanie optymalne, w którym ten warunek nadal jest spełniony, a ponadto wierzchołki w poddrzewach dzieci \(v\) są odwiedzane kolejno, bez przeplatania ich ze sobą.

Załóżmy, że mamy pewne optymalne rozwiązanie, w którym najpierw odwiedzamy \(v\), jeśli \(v\) ma zostać odwiedzony, a następnie odwiedzamy pewne wierzchołki w poddrzewach dzieci \(v\). Załóżmy dalej, że istnieje takie dziecko \(u\) wierzchołka \(v\), że wierzchołki do odwiedzenia w poddrzewie \(u\) nie są odwiedzane jako spójny segment w całej kolejności odwiedzania stron. Rozważmy ciąg wierzchołków odwiedzanych w poddrzewie \(v\) (poza \(v\), jeśli ma zostać odwiedzony) w kolejności ich odwiedzania. Niech ten ciąg to będzie \(w_1, w_2, \ldots, w_k\).

Zobaczmy, że za każdym razem, gdy mamy dwa wierzchołki \(w_i\) oraz \(w_{i+1}\) dla pewnego \(1\leq i\lt k \), które znajdują się w poddrzewach różnych dzieci \(v\), to przejście między pierwszym a drugim wymaga przejścia przez wierzchołek \(v\). Wynika to stąd, że jeśli chcemy dostać się do \(w_{i+1}\) tuż po odwiedzeniu \(w_i\) (czyli z korzenia), to wciśnięcie klawisza TAB na jakimkolwiek przodku \(v\) (włącznie z \(v\)) przenosi nas do \(w_i\). Jeśli już znajdziemy się w \(w_i\), to będziemy musieli cofnąć się do \(v\) za pomocą BACKSPACE, aby następnie zejść do \(w_{i+1}\), które jest w poddrzewie innego dziecka \(v\) niż \(w_i\). Alternatywnie, nie będziemy wciskać klawisza TAB na przodkach \(v\) i wówczas dojdziemy do \(v\) wpisując ręcznie literka po literce. Ostatecznie, po dostaniu się do \(v\), w jakiś sposób trafimy do \(w_{i+1}\), poruszając się w obrębie poddrzewa dziecka \(v\), w którym znajduje się \(w_{i+1}\). Widzimy więc, że przejście między \(w_i\) oraz \(w_{i+1}\) składa się z dwóch faz: dostanie się do \(v\) oraz zejścia z \(v\) do \(w_{i+1}\), przy czym ruchy wykonywane w obu fazach na siebie nie wpływają. Teraz rozważmy dwa przypadki:

\(w_k\) nie znajduje się w poddrzewie \(u\). Wówczas możemy rozważyć alternatywną kolejność odwiedzania wierzchołków, w której najpierw odwiedzamy wszystkie wierzchołki z poddrzewa \(u\), zachowując ich względną kolejność z oryginalnego rozwiązania, a następnie wszystkie pozostałe wierzchołki, ponownie zachowując ich względną kolejność z oryginalnego rozwiązania. Otrzymujemy więc nową kolejność \(w_1',w_2',\dots,w_k'\). Rozważmy dwa sąsiednie wierzchołki z tej kolejności \(w_i'\) oraz \(w_{i+1}'\) dla pewnego \(1\leq i\lt k\). Mamy dwa przypadki:
- \(w_i'\) oraz \(w_{i+1}'\) były obok siebie w oryginalnej kolejności. Wówczas, aby po odwiedzeniu \(w_i'\) dostać się do \(w_{i+1}'\), możemy wykonać dokładnie te same ruchy, co w oryginalnym rozwiązaniu. Możemy to zrobić, ponieważ w obrębie poddrzew dzieci wierzchołka \(v\) kolejności odwiedzanych wierzchołków się nie zmieniły, więc będziemy mogli posługiwać się przyciskiem TAB tak samo jak w oryginalnym rozwiązaniu.
- \(w_i'\) oraz \(w_{i+1}'\) nie były obok siebie w oryginalnej kolejności. Wówczas nietrudno zobaczyć, że oznacza to, że tuż po odwiedzeniu \(w_i'\) w oryginalnej kolejności odwiedziliśmy jakiś wierzchołek spoza poddrzewa dziecka \(v\), do którego należy \(w_i'\) oraz, także w oryginalnej kolejności, przed odwiedzeniem \(w_{i+1}'\) odwiedzaliśmy jakiś wierzchołek spoza poddrzewa dziecka \(v\), do którego należy \(w_{i+1}'\) lub \(w_{i+1}'\) był pierwszy do odwiedzenia w oryginalnej kolejności. W takim razie, w oryginalnym rozwiązaniu, po odwiedzeniu \(w_i'\) musieliśmy jakoś wrócić do \(v\) i stamtąd pójść dokądś dalej. Podobnie przed odwiedzeniem \(w_{i+1}'\) w oryginalnym rozwiązaniu musieliśmy jakoś znaleźć się w \(v\) i stamtąd zejść w dół do \(w_{i+1}'\). W nowej kolejności odwiedzin możemy wykonać te same ruchy - po odwiedzeniu \(w_i'\) wracamy do \(v\), a następnie schodzimy stamtąd do \(w_{i+1}'\). Wówczas wykonamy dokładnie te same ruchy, co w oryginalnym rozwiązaniu, jednak być może w zmienionej kolejności.
Zauważmy ponadto, że wierzchołek \(w_1'\) może być albo tym samym wierzchołkiem co \(w_1\) (jeśli \(w_1\) należy do poddrzewa \(u\)), albo pierwszym wierzchołkiem w poddrzewie \(u\) występującym w oryginalnej kolejności (jeśli \(w_1\) nie należy do poddrzewa \(u\)). W obu przypadkach aby dojść do \(w_1'\) w oryginalnej kolejności, najpierw musimy znaleźć się w wierzchołku \(v\) i stamtąd zejść do \(w_1'\). W nowej kolejności możemy wykonać dokładnie te same ruchy - gdy znajdziemy się w wierzchołku \(v\) po raz pierwszy, schodzimy do \(w_1'\) i kontynuujemy odwiedzanie wierzchołków zgodnie z nową kolejnością. Zobaczmy więc, że udało nam się udowodnić, że sumaryczny koszt przejścia odwiedzania kolejnych wierzchołków w nowej kolejności może być równy sumarycznemu kosztowi przejścia odwiedzania kolejnych wierzchołków w oryginalnej kolejności. Ponadto ostatni odwiedzony wierzchołek w obu kolejnościach jest ten sam (bo \(w_k\) znajduje się poza poddrzewem \(u\)). Wobec tego, otrzymaliśmy rozwiązanie, które jest nie gorsze od oryginalnego i zachowuje ten sam ostatni odwiedzony wierzchołek (co jest istotne, gdy rozważamy kolejne odwiedzane wierzchołki poza poddrzewem \(v\)).
\(w_k\) znajduje się w poddrzewie \(u\). Wówczas możemy postąpić podobnie do tego, co robiliśmy w poprzednim przypadku, jednak najpierw odwiedzamy wszystkie wierzchołki poza poddrzewem \(u\), zachowując ich względną kolejność z oryginalnego rozwiązania, a następnie odwiedzamy wszystkie wierzchołki z poddrzewa \(u\), ponownie zachowując ich względną kolejność z oryginalnego rozwiązania. Na mocy argumentu analogicznego do tego wyżej (ponownie korzystamy z tego, że ostatni odwiedzony wierzchołek jest ten sam, co w oryginalnej kolejności) otrzymujemy, że takie rozwiązanie jest nie gorsze od oryginalnego.

Możemy więc powtarzać powyższy proces pokazywania, że istnieją nie gorsze rozwiązania, w których kolejne wierzchołki w poddrzewach dzieci \(v\) są odwiedzane jako spójne segmenty, aż dojdziemy do rozwiązania, w którym jest tak dla wszystkich dzieci \(v\). To kończy dowód lematu \(\Box\).

Posługując się lematem, możemy ułożyć następujące programowanie dynamiczne. Dla każdego wierzchołka \(v\) w drzewie trie zdefiniujemy następujące wartości:

\(dp\_manual[v]\) - minimalna liczba wciśnięć klawiszy potrzebna do odwiedzenia wszystkich stron w poddrzewie \(v\) i powrotu do słowa odpowiadającego wierzchołkowi \(v\), przy czym ten powrót polega na ręcznym wpisywaniu liter (bez użycia TAB) po ostatnim wciśniętym klawiszu ENTER,
\(dp\_tab[v]\) - minimalna liczba wciśnięć klawiszy potrzebna do odwiedzenia wszystkich stron w poddrzewie \(v\) i powrotu do słowa odpowiadającego wierzchołkowi \(v\), przy czym ten powrót polega na wciśnięciu klawisza TAB po ostatnim wciśniętym klawiszu ENTER i następnie pewnej liczbie wciśnięć klawisza BACKSPACE.

gdzie w obu powyższych definicjach zakładamy, że zaczynamy od słowa odpowiadającego wierzchołkowi \(v\).

Powyższe wartości będziemy obliczać w kolejności od liści do korzenia drzewa. Jeśli wierzchołek \(v\) jest liściem, to oczywiście musi odpowiadać jednej ze stron, które mamy wyszukać, a więc mamy

\(dp\_manual[v]=depth[v]+1\), gdzie \(depth[v]\) to głębokość wierzchołka \(v\) w drzewie trie. Wzór ten wynika stąd, że będąc w wierzchołku \(v\) wciskamy ENTER (1 wciśnięcie), a następnie wpisujemy ręcznie wszystkie litery adresu strony (\(depth[v]\) wciśnięć),
\(dp\_tab[v]=2\), ponieważ po wciśnięciu klawisza ENTER (1 wciśnięcie) możemy natychmiast wcisnąć klawisz TAB (1 wciśnięcie), aby wrócić do słowa odpowiadającego wierzchołkowi \(v\).

Jeśli natomiast \(v\) nie jest liściem, to wartości będziemy wyliczać różnie w zależności od tego, czy \(v\) jest wierzchołkiem odpowiadającym jakiejś stronie do odwiedzenia czy nie. Załóżmy najpierw, że \(v\) nie odpowiada żadnej stronie do odwiedzenia. Wówczas dzięki lematowi wiemy, że najpierw odwiedzimy wszystkie poddrzewa dzieci \(v\) jedno po drugim, a następnie wrócimy do słowa odpowiadającego \(v\). Dla pewnego dziecka \(w\) wierzchołka \(v\) liczba operacji potrzebna do odwiedzenia wszystkich stron w poddrzewie \(w\) i powrotu do \(v\), zakładając, że zaczynamy z \(v\), to \(1+\min(dp\_manual[w]-1, dp\_tab[w] + 1)\), ponieważ najpierw musimy wejść z \(v\) do \(w\), co odpowiada jednemu wciśnięciu pewnej literki, a następnie możemy albo ręcznie (literka po literce) wrócić do \(v\) po ostatnim wciśniętym ENTER (koszt \(dp\_manual[w]-1\)), albo wrócić do \(w\) za pomocą klawisza TAB i pewnej liczby wciśnięć klawisza BACKSPACE i wcisnąć BACKSPACE raz jeszcze, by trafić do \(v\) (koszt \(dp\_tab[w] + 1\)). Zwróćmy uwagę, że w tym przypadku nie kontrolujemy sposobu powrotu do \(v\) po odwiedzeniu wszystkich wierzchołków w poddrzewie \(w\) (rozważamy obie opcje). Ostateczny sposób powrotu do \(v\) (po odwiedzeniu wszystkich dzieci \(v\)) będzie zależał wyłącznie od tego, które z dzieci \(v\) odwiedzimy jako ostatnie. Załóżmy, że tym dzieckiem jest \(u\). Jeśli wiemy, że do \(v\) chcemy wrócić ręcznie (literka po literce), to odwiedzenie poddrzewa \(u\), zakładając, że zaczynamy z \(v\) i chcemy wrócić do \(v\) będzie kosztować nas \(1 + dp\_manual[u] - 1\), natomiast jeśli chcemy wrócić do \(v\) za pomocą klawisza TAB, to koszt wyniesie \(1 + dp\_tab[u] + 1\). Aby wyliczyć odpowiednie wartości dla \(v\) wystarczy więc rozważyć wszystkie możliwości wyboru ostatniego dziecka \(u\) i wziąć najmniejszy. Mamy więc następujące wzory:

\[ dp\_manual[v] = \min_{u \in children(v)} \left(1+dp\_manual[u]-1+\sum_{w\in children(v)\land w\not=u}\left(\min(dp\_manual[w] - 1, dp\_tab[w] + 1) + 1\right)\right), \].
\[ dp\_tab[v] = \min_{u \in children(v)} \left(1+dp\_tab[u]+1+\sum_{w\in children(v)\land w\not=u}\left(\min(dp\_manual[w] - 1, dp\_tab[w] + 1) + 1\right)\right), \].

Jeśli natomiast \(v\) odpowiada pewnej stronie do odwiedzenia, to najpierw musimy odwiedzić tę stronę i dopiero wtedy odwiedzić wszystkie poddrzewa dzieci \(v\) jedno po drugim. Aby odwiedzić stronę odpowiadającą \(v\) możemy natychmiast wcisnąć ENTER (1 wciśnięcie) i następnie natychmiast wcisnąć TAB (1 wciśnięcie), aby wrócić do \(v\). Oczywiście nie jesteśmy w stanie odwiedzić \(v\) i do niego wrócić w mniejsze liczbie wciśnięć klawiszy (bo \(v\) nie jest korzeniem). W związku z tym, jeśli \(v\) odpowiada pewnej stronie do odwiedzenia, to obie powyższe wartości \(dp\) należy zwiększyć o 2.

Obliczywszy wartości \(dp\_manual[root]\) oraz \(dp\_tab[root]\), gdzie \(root\) jest korzeniem drzewa trie, otrzymamy ostateczną odpowiedź jako \(\min(dp\_manual[root], dp\_tab[root])\). Możemy stąd także odzyskać kolejność odwiedzania stron - podczas obliczania wartości \(dp\) wystarczy zapamiętywać, które dziecko najlepiej wybrać jako ostatnie i wybrać dowolną kolejność odwiedzin, w której to dziecko jest ostatnie, schodząc rekurencyjnie do dzieci i powtarzając w nich to samo. Należy przy tym pamiętać dla każdego wierzchołka, który wybór (ręczny powrót czy powrót za pomocą TAB) był lepszy dla danego stanu \(dp\).

Otrzymawszy kolejność odwiedzanych stron, możemy zasymulować działanie przeglądarki. Korzystając z tego, że lemat gwarantuje nam, że klawisz TAB będzie zawsze użyty do tego, aby wrócić do poprzednio odwiedzonego słowa, a nie żadnego wcześniejszego (bo to zawsze będzie miało najdłuższy wspólny prefiks), dla każdych dwóch kolejnych słów w wyznaczonej kolejności możemy porównać dwie możliwości: ręczne wpisanie liter drugiego słowa od początku lub użycie klawisza TAB, aby wrócić do pierwszego słowa, usunięcie z niego pewnej (być może zerowej) liczby liter za pomocą klawisza BACKSPACE i dopisanie brakujących liter drugiego słowa.

Takie rozwiązanie możemy zaimplementować w złożoności czasowej \(O(S)\), gdzie \(S\) to suma długości wszystkich stron do odwiedzenia.