Informatyczny kącik olimpijski

Egzamin

Tym razem omówimy zadanie Egzamin, które pojawiło się w 2010 roku na Junior Balkan Olympiad in Informatics w Szumen (Bułgaria).

Zadanie. Egzamin: Dany jest ciąg $|a = (a1,a2,...,an),$ złożony z $|n$ liczb naturalnych, oraz liczba $s.$ Ile jest podciągów ciągu $a,$ których suma elementów wynosi przynajmniej $|s?$ Dla przykładu, $a = (2,5,3,5)$ ma $|6$ podciągów, które mają sumę przynajmniej $s = 10.$ Są to podciągi: $(2,5,3,5), -- --$ $|(2,5,3,5), ----$ $(2,5,3,5), -- --$ $|(2,5,3,5),$ $(2,5,3,5)$ oraz $(2,5,3,5).$

Rozwiązanie $|O$
Pomysł, który jako pierwszy nasuwa się na myśl, polega na obliczeniu sumy każdego podciągu, a następnie zliczeniu tych sum, których wartość jest nie mniejsza niż $|s.$

Zastanówmy się teraz, jaka jest złożoność opisanego rozwiązania. Ciąg $|a$ ma $n |(1)$ podciągów długości $1,$ $n (2)$ podciągów długości $|2,...,$ wreszcie $|(n) n$ podciągów długości $n.$ Zatem, suma długości wszystkich podciągów wynosi: $n n n n−1 |1⋅(1)+ 2 ⋅( 2) + ...+n ⋅(n) = n ⋅2 .$ Powyższą sumę można zinterpretować nieco inaczej: każdy z $n$ elementów ciągu $|a$ należy do $|2n−1$ podciągów (dla ustalonego elementu $|n− 1$ pozostałych elementów tworzy $2n−1$ podciągów). Zatem liczba składników we wszystkich sumach wynosi $n−1 |n⋅2 ,$ co daje nam złożoność czasową $|O(n$

Rozwiązanie $|O$
Spróbujmy przyspieszyć powyższe rozwiązanie. Będziemy obliczali sumy podciągów w kolejności niemalejących długości (najpierw podciągi długości jeden, potem długości dwa, trzy, itd.). Załóżmy, że obliczamy sumę podciągu $ai1,ai2,...,aim$ (podciąg ma długość $m,$ indeksy kolejnych elementów tworzą ciąg $i1,i2,...,im$ ). Suma elementów tego ciągu to suma podciągu $ai1,ai2,...,aim 1$ (którą obliczyliśmy wcześniej, ponieważ przeglądamy podciągi od najkrótszych do najdłuższych) powiększona o $aim .$ W tym podejściu obliczenie sumy każdego z $|2n− 1$ podciągów odbywa się w czasie stałym, co daje nam złożoność czasową $|O(2n).$

Rozwiązanie $|O$
W tym rozwiązaniu skorzystamy z techniki Meet in the middle.

Podzielmy ciąg $|a$ na dwa ciągi równej długości (jeśli długość ciągu jest nieparzysta, wtedy niech pierwszy ciąg zawiera o jeden element więcej): lewy $|L = (a ,a ,...,a n ) 1 2 2$ oraz prawy $|P = (a n ,a n ,...,a ). 2 +1 2 +2 n$ Następnie, dla każdego z nich, obliczmy sumy podciągów. Możemy to zrobić w czasie $O$ korzystając z algorytmu opisanego w poprzedniej sekcji. Niech $|SL = (SL1 ,SL2,...,SLl )$ oznacza sumy podciągów $|L,$ i niech $|SP = (SP,SP ,...,SP ) 1 2 p$ oznacza sumy podciągów $|P.$

Zauważmy teraz, że dowolny podciąg $|q$ ciągu $|a$ spełnia jeden z trzech poniższych warunków:
Warunek (I): wszystkie elementy $q$ należą do $L.$
Aby obliczyć liczbę podciągów o sumie przynajmniej $s,$ których wszystkie elementy należą do $L,$ wystarczy zliczyć te elementy ciągu $|SL,$ które mają wartość przynajmniej $|s.$ Formalnie jest to moc zbioru: $L |{i∈ {1,2,...,l} Si ⩾s}.$ Sprawdzenie tego warunku odbywa się w czasie liniowym od liczby podciągów $L,$ czyli $O$

Warunek (II): wszystkie elementy $|q$ należą do $|P.$
Analogicznie jak warunek (I).

Warunek (III): część elementów $|q$ należy do $|L,$ część należy do $|P.$
W tym przypadku chcemy obliczyć liczbę takich par $(i, j)$ dla $|i∈{1,2,...,l}$ oraz $j∈ {1,2,...,p},$ że $|SL+ SP ⩾ s. i j$ Ten problem rozbijemy na $l$ podproblemów. Dla każdego $i∈ {1,2,...,l}$ obliczymy, ile jest takich $j ∈{1,2,...,p},$ że $SLi +SP j⩾ s.$

W tym celu posortujmy ciąg $P S$ i otrzymany ciąg nazwijmy $′ P |S .$ Załóżmy, że obliczamy wynik dla ustalonego $i∈ {1,2,...,l}.$ Za pomocą wyszukiwania binarnego szukamy takiego najmniejszego $k ∈ {1,2,...,p},$ że $L ′P S i + Sk ⩾ s.$ Jeśli takie $|k$ istnieje, wtedy dla każdego $| j∈{k, k+ 1,...,p}$ zachodzi $|SLi + S′ jP⩾ s,$ ponieważ $S ′P$ jest niemalejący. Stąd, $SLi$ należy do $|p− k + 1$ par, które mają sumę przynajmniej $s.$ Jeśli zaś takie $k$ nie istnieje, to $L |Si$ nie tworzy żadnej pary o sumie przynajmniej $|s.$

Faza sortowania zajmuje czas $|O$ Wyznaczenie liczby poprawnych par, dla ustalonej wartości, za pomocą wyszukiwania binarnego zajmuje czas $|O(n).$ Wszystkich wartości do sprawdzenia jest $l |$ ( $l$ jest rzędu $|O$ ), co daje całkowitą złożoność $O$

Przykład. Prześledźmy opisany algorytm na przykładzie ciągu $|a = (2,5,3,4,2,4),$ w którym szukamy liczby podciągów o sumie przynajmniej $10.$ Najpierw dzielimy ciąg $|a$ na dwa ciągi i dla każdego z nich obliczamy sumy wszystkich jego podciągów:

$pict$

Z warunku (I) mamy $1$ podciąg, z warunku (II) również $|1.$ Przechodzimy do warunku (III). Najpierw sortujemy $SP,$ otrzymując $| ′ P S = (2,4,4,6,6,8,10).$ Teraz wyznaczamy wyniki dla kolejnych elementów $|SL$ : $(2,4,2,6,4,7,7).$ Ostatecznym wynikiem jest:

(1)+ (1)+ (2+ 4 +2 + 6+ 4 +7 + 7) = 1+ 1+ 32 = 34.