Informatyczny kącik olimpijski

Theater Tickets

Tym razem omówimy zadanie "Theater Tickets", które pojawiło się w konkursie Zinc 2018 organizowanym przez firmę Codility.

Zadanie. Dany jest $n$ -elementowy ciąg liczb naturalnych $a = (a1,a2,...,an)$ z przedziału od 1 do $n.$ Oblicz, ile różnych trzyelementowych podciągów występuje w ciągu $a?$ Dwa podciągi uznajemy za różne, jeśli różnią się na przynajmniej jednej pozycji. Przykładowo $(1,2,1,1)$ ma trzy różne podciągi: $(1,2,1)$ (występujący dwa razy), $(1,1,1)$ (występujący raz) oraz $|(2,1,1)$ (występujący raz).

Niech $|a l p$ oznacza podsłowo $a ,a ,...,a . l l+1 p$

Rozwiązanie $|O$
Pierwsze rozwiązanie będzie polegało na prostym zliczeniu podciągów trzyelementowych. Zauważmy, że wszystkich trzyelementowych ciągów o wartościach z przedziału $|[1;n]$ jest $|n3,$ gdyż każdy z trzech elementów można wybrać na $n$ sposobów. Niech $|T[x][y][z] = 1,$ jeśli $|(x,y,z)$ jest podciągiem $a$ oraz $T [x][y][z] = 0$ w przeciwnym przypadku. Aby uzupełnić tablicę zliczającą $T ,$ wystarczy dla każdej trójki indeksów $|1⩽ i < j < k ⩽ n$ zaktualizować $T[ai][a j][ak] = 1.$ Ta faza zajmuje czas $|O(n3).$ Wynikiem jest liczba komórek tablicy zliczającej $T |$ o wartości 1. Rozwiązanie działa w czasie i pamięci $O(n3). |$

Rozwiązanie $|O$
Policzmy dla każdego prefiksu, ile zawiera on różnych dwuelementowych podciągów. Niech $P 2[i]$ oznacza tę wartość dla $i$ -elementowego prefiksu $|a1 i.$ Wyniki będziemy obliczali od najkrótszych do najdłuższych prefiksów. Oczywiście $|P2[1] = 0.$ Zastanówmy się zatem, jak wyznaczyć $|P2[i]$ dla $|i > 1.$ Otóż $P2[i] = P 2[i− 1] +l,$ gdzie $|l$ oznacza liczbę takich dwuelementowych podciągów, które nie występują w $a1 i−1,$ ale występują w $a1 i,$ czyli takich, których drugim elementem jest $|ai.$ Rozważmy więc takie dwuelementowe podciągi $(a j,ai),$ że $|1⩽ j < i,$ i zliczmy te, które nie występują w $a1 i−1.$ Aby sprawdzić, które dwuelementowe podciągi wystąpiły wcześniej, można, podobnie jak w poprzednim rozwiązaniu, skorzystać z tablicy zliczającej. Wynik dla każdego prefiksu liczymy w czasie $O(n),$ prefiksów jest $O(n), |$ zatem $P | 2$ obliczamy w czasie $|O(n$

Przejdźmy teraz do wyznaczenia liczby różnych trzyelementowych podciągów $a.$ Na początku dla każdej wartości od 1 do $|n$ zapamiętajmy numer ostatniej pozycji, na której ta wartość występuje w $a.$ Niech $|ost[x]$ oznacza takie największe $i,$ że $ai = x.$ Podciągi będziemy zliczali grupami, biorąc pod uwagę wartość ostatniego elementu. Otóż policzymy, ile jest podciągów, których ostatni element to odpowiednio $1,2,...,n,$ a na koniec zsumujemy te wyniki. Zastanówmy się, jak dla ustalonego $|z$ wyznaczyć liczbę różnych podciągów w $|a$ postaci $(x, y,z)$ dla $|1⩽ x,y ⩽n.$ Jeśli $z$ nie występuje w $a,$ to nie ma takich podciągów. W przeciwnym przypadku weźmy ostatnie wystąpienie $|z$ w $a,$ które znajduje się na pozycji $|ost[z].$ Trzeci element mamy ustalony, zaś dwa pierwsze elementy możemy wybrać na $|P2[ost[z]− 1]$ sposobów, co jest równe liczbie różnych trzyelementowych podciągów kończących się liczbą $z.$ Całkowita liczba trzyelementowych podciągów to $n |P z 1P 2[ost[z] − 1],$ co możemy obliczyć w $O(n),$ znając $P | 2.$ Natomiast całe rozwiązanie działa w czasie i pamięci $|O(n2).$

Rozwiązanie $O |$
Spróbujmy przyspieszyć pierwszą fazę poprzedniego rozwiązania (obliczanie $|P2$ ). Na początku dla każdego prefiksu policzmy, ile zawiera on różnych wartości (podciągów jednoelementowych). Niech $|P1[i]$ oznacza tę wartość dla $i$ -elementowego prefiksu, czyli $a1 i.$ Wyniki będziemy wyznaczali w kolejności rosnącej długości prefiksów. Oczywiście $|P1[i] = 1$ (mamy tylko jeden element). Zastanówmy się teraz, jak wyznaczyć $P 1[i]$ dla $|i > 1.$ Jeśli $ai$ występowało wcześniej, wtedy $|P1[i] = P1[i− 1].$ W przeciwnym przypadku $|P1[i] = P1[i− 1]+ 1.$ Do sprawdzania, czy $ai$ występowało wcześniej, możemy wykorzystać tablicę zliczającą.

Przejdźmy teraz do obliczenia $|P2.$ Podobnie jak wcześniej, wartości tej tablicy będziemy obliczali od najkrótszych do najdłuższych prefiksów. Dodatkowo niech $pop[x]$ dla $|1⩽ x ⩽n$ oznacza numer ostatniej pozycji spośród przejrzanych elementów, na której wystąpił $|x.$

Najpierw dla jednoelementowego prefiksu ustawiamy $P2[1] = 0$ (nie ma podciągów dwuelementowych) oraz zapisujemy informację $pop[a ] = 1 1$ (ostatnie wystąpienie wartości $a1$ na pozycji numer 1). Następnie przeglądamy kolejne prefiksy. Załóżmy, że obliczamy $P 2[i]$ dla $i > 1.$ Otóż $P 2[i]$ to $|P2[i− 1]$ powiększone o liczbę takich dwuelementowych podciągów $|a , 1 i$ które nie występują w $a . 1 i−1$ Szukane podciągi są postaci $(x, a ) i$ - drugi element ma wartość $ai.$ Wszystkich takich podciągów w $|a1 i$ jest $|P1[i− 1],$ gdyż na tyle sposobów można wybrać $x.$ Powinniśmy jednak odjąć te podciągi, które występują również w $a1 i− 1.$ Jeśli $|a i$ występuje pierwszy raz, wtedy nie musimy nic odejmować. Jeśli natomiast $ai$ występowało wcześniej, to weźmy jego poprzednie wystąpienie na pozycji $|pop[ai].$ Zauważmy, że jest ono drugim elementem $|P1[pop[ai]− 1]$ podciągów (na tyle sposobów można wybrać element stojący przed poprzednim wystąpieniem $a i$ ). Zatem otrzymaliśmy, że: $|P2[i] = P2[i −1]+ P 1[i −1]− P 1[pop[ai] − 1].$ Po obliczeniu $P 2[i]$ możemy zaktualizować $pop[ai] = i.$ Wyznaczyliśmy $|P2$ w czasie $O(n).$ Druga faza algorytmu jest analogiczna do tej opisanej w sekcji Rozwiązanie $O(n2)$ i działa w czasie $|O(n),$ co daje nam pełne rozwiązanie o złożoności czasowej $O(n).$