Informatyczny kącik olimpijski

Wiercenia

W tym kąciku omówimy zadanie Wiercenia, które pojawiło się na Potyczkach Algorytmicznych w roku 2009.

Ekipa poszukująca złóż ropy wykonała dwa odwierty: w punkcie $|A= 0$ natrafiono na ropę, zaś w punkcie $|B = n + 1$ ropy nie znaleziono. Wiedząc, że złoże ropy zajmuje pewien spójny fragment odcinka $|AB,$ ekipa chce zlokalizować najdalszy punkt spośród punktów o współrzędnych $1,2,...,n,$ w którym występuje ropa. Wykonanie odwiertu w punkcie $|i$ zajmuje czas $|t[i]$ ; ekipa może wykonywać tylko jeden odwiert naraz. Należy wyznaczyć taki plan wierceń, aby czas potrzebny na ustalenie, dokąd sięga złoże ropy, był w pesymistycznym przypadku jak najkrótszy.

Na początek zauważmy, że jeśli wykonanie każdego z odwiertów zajmuje taki sam czas, to wtedy, stosując wyszukiwanie binarne, uzyskamy odpowiedź, wykonując optymalną liczbę $⌈log2n⌉ +1$ odwiertów. Zróżnicowanie czasów istotnie komplikuje zadanie; spróbujemy je rozwiązać, korzystając z programowania dynamicznego.

Oznaczmy przez $d[a, b]$ optymalny czas lokalizacji granicy złoża na odcinku od punktu $|a$ do punktu $|b$ (włącznie), przy założeniu, że wiemy, iż w punkcie $a − 1$ jest ropa, a w punkcie $b + 1$ jej nie ma. Aby wyznaczyć granicę złoża na odcinku $|[a, b],$ musimy zacząć od wykonania odwiertu w jednym z punktów $i$ tego odcinka. Jeśli znajduje się tam ropa, to granicy złoża będziemy poszukiwać na odcinku $[i + 1,b],$ w przeciwnym przypadku granica jest na odcinku $[a,i −1].$ Dostajemy zatem wzór rekurencyjny

d[a,b] = minaDi Db(t[i]+ max(d[a, i− 1],d[i + 1,b])).

(*)

Zakładamy, że $d[a, b] = 0$ dla $a > b.$ Rozwiązaniem jest wartość $|d[1,n].$ Obliczenie jej wprost z powyższej rekurencji da nam algorytm o złożoności czasowej $3 O(n )$ i pamięciowej $2 |O(n ).$ Algorytm będzie miał $|n$ faz, w $|ℓ$ -tej fazie będziemy wypełniać komórki tablicy odpowiadające odcinkom o długości $ℓ$ :

$for ℓ = 0to n −1 do fora = 1to n −ℓ do b = a + ℓ;d[a, b] = ∞ ; fori = a to b do d[a, b] = min(d[a, b],t[i] +max(d[a, i− 1],d[i + 1,b]));$

Aby przyspieszyć powyższy algorytm, będziemy potrzebowali kilku obserwacji. Zauważmy, że jeśli przedłużymy jakiś odcinek, to czas szukania w nim granicy złoża jest zawsze nie mniejszy niż w oryginalnym odcinku. Zatem wraz ze wzrostem $|i$ we wzorze $(∗)$ wartość $| d[a,i− 1]$ nie zmniejsza się, a wartość $| d[i +1,b]$ nie rośnie. Istnieje więc taki indeks $|s[a, b]∈ [a− 1,b],$ że spełnione są nierówności

d[a,i−1] ⩽d[i+1,b] dla i ⩽s[a,b] oraz d[a,i− 1] > d[i+1,b] dla i > s[a, b].

Możemy zatem przepisać wzór $(∗ )$ w równoważnej formie, pozbywając się liczenia maksimum:

d[a,b] = min (minaDi Ds a,b (t[i]+ d[i + 1,b]),mins a,b @i Db(t[i]+ d[a,i− 1])).

(**)

Skorzystamy również z tego, że tablica $s$ jest monotoniczna względem każdej współrzędnej, dzięki czemu wartość $|s[a,b]$ jest ograniczona przez wartości dla krótszych odcinków:

s[a,b − 1]⩽ s[a, b]⩽ s[a +1,b].

Istotnie, jeśli weźmiemy dowolne $i⩽ s[a,b −1]$ i znowu skorzystamy z tego, że przedłużenie odcinka nie zmniejsza czasu poszukiwania granicy złoża, to dostaniemy $d[a, i− 1] ⩽ d[i + 1,b − 1]⩽ d[i + 1,b],$ zatem $|i⩽ s[a, b],$ co dowodzi lewej nierówności (prawej dowodzimy analogicznie). Ponieważ $s[a,a] = a,$ to możemy dla wygody przyjąć $s[a,b] = b$ dla $|a > b.$ Zatem, aby wyznaczyć $|s[a, b],$ wystarczy przejrzeć wartości od $s[a,b −1]$ do $s[a+ 1,b].$ Dzięki temu wyznaczenie ich dla wszystkich odcinków $s[a,a + ℓ]$ o ustalonej długości $ℓ$ zajmie sumarycznie czas liniowy:

n−ℓ (s[a +1,a + ℓ]+ 1− s[a, a+ ℓ −1]) = s[n − ℓ+ 1,n]− s[1,ℓ] +n − ℓ ⩽2n. Qa 1

W końcu pokażemy, jak szybko wyliczać minima we wzorze $|(∗∗).$ Załóżmy, że mamy strukturę danych, która przechowuje pary (indeks, wartość) i udostępnia operacje jak na kolejce: wstawienie pary na koniec kolejki (push) oraz usunięcie pary z początku kolejki (pop). Dodatkowo operacja first będzie zwracać indeks pary z początku kolejki, a kluczowa operacja min będzie zwracała minimum ze wszystkich wartości w kolejce. Będziemy korzystać z $|2n$ kolejek, które nazwiemy $A[i]$ oraz $|B[i]$ dla $1 ⩽i ⩽ n.$

Podczas wyliczania $d[a,b]$ w $ℓ$ -tej fazie algorytmu będziemy zakładać, że wszystkie wartości z lewego minimum w $(∗∗ )$ znajdują się w kolejce $B[b]$ (w kolejności malejących indeksów $|i$ ), a wszystkie wartości z prawego minimum w kolejce $A[a]$ (w kolejności rosnących indeksów). Kolejka $A[a]$ w fazie $ℓ− 1$ była wykorzystywana podczas obliczeń dla komórki $|d[a,b −1],$ zatem zawiera pary $|(i,t[i]+ d[a,i −1])$ dla indeksów $s[a,b −1] < i ⩽ b − 1.$ Ponieważ $|s[a, b− 1]⩽ s[a,b],$ więc wystarczy usunąć z niej pary o indeksach nie większych niż $s[a,b]$ oraz dodać parę o indeksie $b.$ Analogicznie uaktualniamy pary w kolejce $B[b].$ Pseudokod całego algorytmu jest następujący (zakładamy, że dla pustej kolejki pętla while nie wykonuje się, a operacja min zwraca $|∞$ ):

$for ℓ = 0to n −1 do fora = 1ton − ℓdo b = a + ℓ; fori = s[a,b −1] to s[a+ 1,b] do ifd[a, i− 1]⩽ d[i + 1,b]then s[a, b] = i; A[a].push(b, t[b]+ d[a, b− 1]); whileA[a]. first ⩽ s[a, b]do A[a].pop; B[b].push(a, t[a]+ d[a + 1,b]); while B[b]. first > s[a,b]do B[b].pop; d[a,b] = min(A[a]. min,B[b]. min);$

Kolejki możemy zaimplementować tak, aby wszystkie udostępniane operacje działały w zamortyzowanym czasie stałym. Zauważmy, że tuż przed wykonaniem operacji $push(i,v)$ możemy usunąć z końca kolejki wszystkie pary o wartościach nie mniejszych niż $v,$ gdyż para $|(i,v)$ będzie lepszym kandydatem na minimum. Dzięki temu pary znajdujące się w kolejce będą zawsze posortowane rosnąco według wartości, zatem operacja $|min$ po prostu zwróci wartość pary z początku kolejki. Ostatecznie złożoność czasowa algorytmu wyniesie $O(n2).$