Omówienie zadania Pociąg towarowy (I etap XXX OI)

O co chodzi w zadaniu

W zadaniu Pociąg towarowy trzeba się dobrze zastanowić, żeby zrozumieć, jaki dokładnie wynik mamy wyznaczyć. Mamy dane dwa ciągi liczb, \(a=(a_1,\ldots,a_n)\) i \(b=(b_1,\ldots,b_m)\). Wiemy, że ciąg \(b\) jest podciągiem ciągu \(a\), czyli że po usunięciu pewnej liczby elementów ciągu \(a\) otrzymamy ciąg \(b\). (Mamy zatem \(m \le n\).) Wyobrażamy sobie wszystkie możliwe sposoby, na jakie ciąg \(b\) może wystąpić jako podciąg ciągu \(a\). Innymi słowy, interesują nas wszystkie ciągi indeksów \(p=(p_1,\ldots,p_m)\) takie że \(1 \le p_1 < p_2 <\dots< p_m \le n\) oraz \(a_{p_i}=b_i\) dla wszystkich \(i \in [1,m]\). Każdy taki ciąg indeksów nazywamy wystąpieniem (ciągu \(b\) w ciągu \(a\)). W zadaniu mamy wypisać ciąg \(w=(w_1,\ldots,w_n)\) złożony z liczb 0 i/lub 1. Liczba \(w_i\) ma być równa 1 wtedy i tylko wtedy, gdy istnieje wystąpienie \(p=(p_1,\ldots,p_m)\) zawierające indeks \(i\) (czyli \(i=p_j\) dla pewnego \(j \in [1,m]\)). Polecenie jest dobrze zilustrowane w przykładzie w treści zadania.

Dodatkowo, w zadaniu mamy gwarancję, że elementy ciągów \(a\) i \(b\) są liczbami całkowitymi należącymi do przedziału \([1,k]\).

Trzecie podzadanie

Sprawdzenie, czy ciąg \(b\) jest podciągiem ciągu \(a\), możemy łatwo wykonać zachłannie w czasie liniowym. Wystarczy wybrać najpierw pierwszy element ciągu \(a\) równy \(b_1\), potem pierwszy kolejny element ciągu \(a\) równy \(b_2\) itd. W ten sposób znajdujemy też jedno wystąpienie.

W trzecim podzadaniu ciąg \(a\) składa się z parami różnych elementów. Tak więc ciąg \(b\) ma tylko jedno wystąpienie. W ciągu wynikowym \(w\) mamy \(w_i=1\) wtedy i tylko wtedy gdy pozycja \(i\) należy do tego wystąpienia. Otrzymujemy rozwiązanie podzadania o optymalnej złożoności \(O(n)\).

Zbyt wolne rozwiązanie

Zupełnie siłowe rozwiązanie polegałoby na wyznaczeniu wszystkich wystąpień i obliczeniu ciągu \(w\) z definicji. Wszystkich wystąpień może być aż \(\binom{n}{m}\) (w przypadku gdy ciągi \(a\) i \(b\) mają wszystkie litery jednakowe).

Pierwsze podzadanie

W kolejnych rozwiązaniach wykorzystujemy inne podejście polegające na wyznaczaniu kolejnych wartości wynikowych \(w_i\). Aby \(w_i\) było równe 1, musimy istnieć indeks \(j\) w ciągu \(b\) spełniający następujące warunki:

1. \(b_j=a_i\),
2. ciąg \(b_1,\ldots,b_{j-1}\) jest podciągiem ciągu \(a_1,\ldots,a_{i-1}\),
3. ciąg \(b_{j+1},\ldots,b_m\) jest podciągiem ciągu \(a_{i+1},\ldots,a_n\).

Najprostsze rozwiązanie sprawdza po kolei powyższe warunki. Dla każdego indeksu \(i\) istnieje co najwyżej \(m\) indeksów \(j\) spełniających warunek 1. Dla każdego takiego indeksu, warunki 2 i 3 możemy sprawdzić w czasie \(O(n)\). Otrzymujemy rozwiązanie o złożoności \(O(n^2m)\), które przechodziło pierwsze podzadanie.

Drugie podzadanie

Możemy przyspieszyć powyższe rozwiązanie przez szybsze sprawdzanie warunków 2 i 3. Algorytm zachłanny sprawdzania, czy ciąg \(b\) jest podciągiem ciągu \(a\), wyznacza "pierwsze" wystąpienie tego ciągu; oznaczmy je jako \(\mathit{FirstOcc}\). Wystąpienie to spełnia warunek, że dla każdego \(j \in [1,m]\), najkrótszym prefiksem ciągu \(a\), którego podciągiem jest prefiks \(b_1,\ldots,b_j\) ciągu \(b\), jest \(a_1,\ldots,a_i\) dla \(i=\mathit{FirstOcc}_j\). (Łatwo to wykazać np. przez indukcję.) Podobnie algorytm zachłanny uruchomiony od końców ciągów \(a\) i \(b\) wyznacza takie "ostatnie" wystąpienie \(\mathit{LastOcc}\). Wtedy warunek 2 można zapisać równoważnie jako \[\mathit{FirstOcc}_{j-1} \le i-1.\] Podobnie 3 zapisuje się jako \[\mathit{LastOcc}_{j+1} \ge i+1.\]

Ciągi \(\mathit{FirstOcc}\) i \(\mathit{LastOcc}\) wyznaczamy raz, na samym początku, w czasie \(O(n)\). Wtedy warunki 2 i 3 możemy każdorazowo sprawdzać w czasie stałym. Otrzymujemy rozwiązanie działające w czasie \(O(nm)\), które wystarczało do zaliczenia drugiego podzadania.

Rozwiązanie wzorcowe

Aby otrzymać rozwiązanie działające w czasie \(o(nm)\), musimy w jakiś sposób zoptymalizować warunek 1. W szczególności nie możemy sobie pozwolić na przeglądanie wszystkich par indeksów \((i,j)\) takich że \(b_j=a_i\), gdyż takich par może być \(\Theta(nm)\) (np. gdy ciągi \(a\) i \(b\) zawierają bardzo dużo elementów równych 1).

Zamiast tego, spróbujmy dla danego elementu \(a_i\) dobrać jeden, w pewnym sensie najlepszy, element \(b_j\) taki że \(b_j=a_i\). Skorzystajmy tu z zachłanności algorytmu znajdowania podciągu. Intuicyjnie, najlepiej jest wybrać maksymalny indeks \(j\), taki że \(b_1,\ldots,b_{j-1}\) jest podciągiem ciągu \(a_1,\ldots,a_{i-1}\) oraz \(b_j=a_i\). Wystarczy wtedy sprawdzić, czy ciąg \(b_{j+1},\ldots,b_m\) jest podciągiem ciągu \(a_{i+1},\ldots,a_n\), co sprowadza się do sprawdzenia warunku 3 i można wykonać w czasie stałym (\(\mathit{LastOcc}_{j+1} \ge i+1\)).

Najlepsze elementy ciągu \(b\) w opisanym powyżej sensie wyznaczymy dla wszystkich indeksów \(i\) od lewej do prawej i zapamiętamy jako \(\mathit{Best}[i]=j\). Możemy to zrobić niejako przy okazji wyznaczania wystąpienia \(\mathit{FirstOcc}\) algorytmem zachłannym. Załóżmy, że w algorytmie zachłannym doszliśmy do elementu \(a_i\) w ciągu \(a\) i zarazem do elementu \(b_j\) w ciągu \(b\). Wtedy w tablicy \(\mathit{MaxInd}\) dla każdej możliwej wartości \(x \in [1,k]\) zapamiętamy najpóźniejszy indeks w ciągu \(b_1,\ldots,b_j\), pod którym jest element równy \(x\). Formalnie, dla każdego \(k \in [1,j]\), takiego że \(b_k \ne b_{k'}\) dla wszystkich \(k' \in [1,k-1]\), będziemy przechowywać \(\mathit{MaxInd}[b_k]=k\). Wszystkie pola tablicy, które odpowiadają wartościom \(x \in [1,k]\) niewystępującym w ciągu \(b_1,\ldots,b_j\), możemy ustawić np. na -1. Jeśli mamy już taką tablicę, wtedy po prostu \(\mathit{Best}[i]=\mathit{MaxInd}[a_i]\).

Trzeba jeszcze powiedzieć, w jaki sposób należy zmodyfikować tablicę \(\mathit{MaxInd}\), gdy w algorytmie zachłannym zwiększamy \(i\) o 1. Jeśli \(j < m\) oraz \(a_{i+1}=b_{j+1}\), wtedy na \(\mathit{MaxInd}[b_{j+1}]\) przypisujemy wartość \(j+1\). W przeciwnym przypadku nic się w tablicy \(\mathit{MaxInd}\) nie zmienia.

Ostatecznie dla każdego indeksu \(i\) wykonujemy w algorytmie zachłannym dodatkową stałą pracę, używając tablicy rozmiaru \(O(k)\), którą inicjujemy w czasie \(O(k)\). To pozwala nam wyznaczyć wszystkie indeksy \(\mathit{Best}[i]\) w czasie \(O(n+k)\). W czasie \(O(n)\) wyznaczamy wystąpienie \(\mathit{LastOcc}\). Wówczas \[w_i=1\ \Leftrightarrow\ (\mathit{Best}[i] \ne -1 \land \mathit{LastOcc}_{\mathit{Best}[i]+1} \ge i+1).\] To pozwala wyznaczyć ciąg wynikowy \(w\) w łącznym czasie \(O(n+k)\). Otrzymane rozwiązanie pozwalało zaliczyć wszystkie podzadania.

Na koniec wypadałoby formalnie uzasadnić poprawność powyższego rozwiązania. W tym celu udowodnimy następujący lemat.

Lemat. Dla każdego \(i \in [1,n]\) mamy \(w_i=1\ \Leftrightarrow\ (\mathit{Best}[i] \ne -1 \land \mathit{LastOcc}_{\mathit{Best}[i]+1} \ge i+1)\).

Dowód. Najpierw zauważmy, że jeśli \(\mathit{Best}[i]=-1\), to \(w_i=0\). Faktycznie, niech \(j\) będzie pierwszym indeksem w ciągu \(b\), takim że \(b_j=a_i\). Warunek \(\mathit{Best}[i]=-1\) oznacza, że ciąg \(b_1,\ldots,b_{j-1}\) nie jest podciągiem ciągu \(a_1,\ldots,a_{i-1}\). Gdyby pozycja \(i\) występowała w jakimś wystąpieniu \(p_1,\ldots,p_m\) jako \(p_k\), to musielibyśmy mieć \(k \ge j\), czyli \(p_1,\ldots,p_{j-1}\) byłoby podciągiem \(1,\ldots,i-1\), więc \(b_1,\ldots,b_{j-1}\) byłoby podciągiem \(a_1,\ldots,a_{i-1}\); sprzeczność.

Odtąd założymy, że \(\mathit{Best}[i]\ne -1\). Niech \(\mathit{FirstOcc}=\{q_1,\ldots,q_m\}\), \(\mathit{LastOcc}=\{r_1,\ldots,r_m\}\) i \(j=\mathit{Best}[i]\). Wykażemy, że wówczas \(w_i=1\ \Leftrightarrow\ r_{j+1} \ge i+1\).

\(\mathbf{(\Leftarrow)}\) Załóżmy, że \(r_{j+1} \ge i+1\). Wówczas ciąg pozycji \(q_1,\ldots,q_{j-1},i,r_{j+1},\ldots,r_m\) jest wystąpieniem zawierającym indeks \(i\), czyli faktycznie \(w_i=1\).

\(\mathbf{(\Rightarrow)}\) Załóżmy, że \(w_i=1\), czyli dla pewnego \(j' \in [1,m]\) mamy wystąpienie \(p_1,\ldots,p_m\) takie że \(p_{j'}=i\). Na mocy algorytmu zachłannego, dla wszystkich \(k \in [1,m]\) mamy \(q_k \le p_k \le r_k\). Stąd \(j \ge j'\) i \(r_{j'+1} \ge p_{j'+1} \ge i+1\). Mamy więc \(r_{j+1} \ge r_{j'+1} \ge i+1\). To kończy dowód lematu.

Epilog

Jeśli ciąg wynikowy \(w\) składa się z samych jedynek – innymi słowy, ciąg \(a\) można pokryć wystąpieniami ciągu \(b\) jako podciągi – powiemy, że ciąg \(b\) jest szablonem podciągowym ciągu \(a\). Rozwiązanie zadania daje algorytm liniowy (jeśli \(k=O(n)\)) sprawdzania, czy dany ciąg \(b\) jest szablonem podciągowym ciągu \(a\). Gdybyśmy jednak chcieli sprawdzić, czy dany ciąg \(a\) ma jakikolwiek szablon podciągowy krótszy niż ciąg \(a\), to nie wiadomo, czy da się to zrobić w czasie wielomianowym. Dla porównania, na XII OI pojawiło się zadanie Szablon, w którym szablon ciągu \(a\) był zdefiniowany jako ciąg \(b\) taki, że ciąg \(a\) można pokryć wystąpieniami ciągu \(b\) jako podsłowa (tj. spójne podciągi). Szablony w tym sensie są istotnie prostsze; w opracowaniu zadania Szablon przedstawiony jest algorytm liniowy znajdowania najkrótszego szablonu danego ciągu.