Informatyczny kącik olimpijski

Gotówka, Startup

Tym razem omówimy dwa zadania, które na pierwszy rzut oka wyglądają podobnie, jednak w istocie są różne. Pierwsze z nich pochodzi z II etapu IX Olimpiady Informatycznej Gimnazjalistów, zaś drugie z Bałkańskiej Olimpiady Informatycznej Juniorów w 2015 roku.

Zadanie (Gotówka). Danych jest $n$ transakcji opisanych za pomocą ciągu liczb całkowitych $a = a1,a2,...,an$ (dodatnie liczby to wpływy, zaś ujemne to wydatki). Poprawnym ciągiem transakcji nazywamy taki, podczas którego stan konta nigdy nie spadnie poniżej zera. Ile jest permutacji ciągu $a,$ które są poprawnymi ciągami transakcji?

Rozwiązanie $|O n! n$ .
Pierwszy, najbardziej intuicyjny, pomysł polega na wygenerowaniu wszystkich $|n!$ permutacji ciągu $a$ oraz zliczeniu tych, które są poprawne. Sprawdzenie, czy dana permutacja transakcji jest poprawna, możemy wykonać w czasie liniowym od jej długości. Wystarczy, że sprawdzimy, czy suma każdego prefiksu jest nieujemna. Niestety, takie podejście jest czasochłonne i działa w czasie $O(n!$

Rozwiązanie $n |O n 2$ .
W tym rozwiązaniu wykorzystamy technikę programowania dynamicznego. Niech $P[s] D$ oznacza liczbę poprawnych ciągów transakcji, które są permutacją ciągu $s.$ Obliczmy wartość $P |D$ dla każdego podciągu $s = s1,s2,...,sm$ ciągu $a. |$ Jeśli $|s$ jest pusty lub suma elementów podciągu $s$ jest ujemna, wtedy $P[s]=0.D$ W przeciwnym przypadku istnieje przynajmniej jedna poprawna permutacja ciągu $s.$ Aby obliczyć $P[s], D$ rozważmy $|m$ możliwości wybrania transakcji, która zostanie wykonana jako ostatnia. Liczba poprawnych ciągów transakcji, przy założeniu, że ostatnia transakcja to $si, |$ wynosi $P[s1,...,si−1,si+1,...,sm] |D$ (liczba poprawnych uporządkowań $m$ pozostałych transakcji). Zatem:

m P[s]=QDP[s1,...,si−1,si+1,...,sm]. D i1

Liczba poprawnych permutacji dla całego ciągu to $P[a]. D$

Ciąg $a$ ma $2n$ podciągów. Obliczenie $P[s] D$ dla $|i$ -elementowego podciągu $|s$ kosztuje $i$ operacji, zaś $i$ -elementowych podciągów jest $n |(i).$ Zatem obliczenie wszystkich wartości $P |D$ wymaga wykonania

n Q (n )⋅i = n ⋅2n−1 i 1 i

operacji. Rozwiązanie działa w czasie $O(n$

Zadanie (Startup). Dany jest ciąg $n$ transakcji opisanych za pomocą ciągu liczb całkowitych $a = a1,a2,...,an$ (dodatnie liczby to wpływy, zaś ujemne to wydatki). Poprawnym ciągiem transakcji nazywamy taki, podczas którego stan konta nigdy nie spadnie poniżej zera. Ile jest rotacji ciągu $a,$ które są poprawnymi ciągami transakcji? Rotacją ciągu $a$ nazywamy $|n$ -elementowy ciąg, powstały poprzez konkatenację sufiksu i prefiksu ciągu $| a.$ Rotacjami ciągu $| (1,2,3,4)$ są: $| (1,2,3,4),$ $|(2,3,4,1),$ $(3,4,1,2)$ i $(4,3,2,y1).$

Rozwiązanie $O| n2$ .
Zauważmy, że wszystkich rotacji jest $|n$ (każdy element wyznacza początek rotacji). Wystarczy zatem każdą z nich rozpatrzyć niezależnie. Sprawdzenie, czy dana rotacja jest poprawnym ciągiem transakcji, możemy wykonać w czasie liniowym od jej długości. Wystarczy sprawdzić, czy suma każdego prefiksu jest nieujemna. W ten sposób otrzymujemy rozwiązanie, które działa w czasie $O(n2).$

Rozwiązanie $|O n log n$ . Zastanówmy się teraz, czy możemy przyspieszyć fazę sprawdzania, czy dana rotacja jest poprawnym ciągiem transakcji - oczywiście możemy. Zacznijmy od sklejenia dwóch kopii ciągu $a$ w jeden ciąg $b$ :

b = a1,a2,...,an,a1,a2,...,an.

Wówczas każda rotacja jest podsłowem ciągu $b.$

Niech $|p = p0,p1,p2,...,p2n$ będzie ciągiem sum prefiksowych dla ciągu $b$ (tzn. $pk = Pki 1bi$ ).

Załóżmy, że chcemy sprawdzić poprawność rotacji $|a ,a ,...,a ,a ,...,a . x x+1 n 1 x−1$ Odpowiadającym podsłowem słowa $b$ jest $|bx,bx+1,...,bx+n−1.$ Podsłowo jest poprawnym ciągiem transakcji, jeśli każdy prefiks ma nieujemną sumę:

i ∀ n ( b ⩾ 0). i 1 Q j 1 x+ j− 1

Powyższy warunek możemy równoważnie zapisać jako

∀n (p − p ⩾ 0) i 1 x+i− 1 x−1

oraz jako

n ∀ i 1(px−1⩽ px+i−1).

Zauważmy, że powyższy warunek jest prawdziwy wtedy i tylko wtedy, gdy

px−1 ⩽min(px, px+1,...,px+n−1).

W celu wyznaczenia minimum na przedziale możemy skorzystać ze struktury drzewa przedziałowego rozpiętego na ciągu $|p.$ Drzewo przedziałowe pozwala w czasie $O(log(n))$ znajdować minimum na przedziale - czyli sprawdzać, czy dana rotacja jest poprawna. Wszystkich rotacji jest $n, |$ zatem rozwiązanie działa w czasie $O(n$