Informatyczny kącik olimpijski

Wieża z siana

W tym miesiącu zadanie Tower of Hay, które pojawiło się na konkursie USACO Open Gold w roku 2009.

Rys. 1 Dla $n 6$ beli o kolejnych szerokościach 7, 6, 4, 2, 1, 4 można zbudować wieżę o wysokości 4

Zadanie. Z $|n$ prostopadłościennych beli siana, które mają tę samą wysokość, ale różne szerokości $w1,$ chcemy zbudować wielopoziomową wieżę. Na każdy poziom może się składać kilka beli, a sumaryczna szerokość każdego poziomu musi być nie większa niż sumaryczna szerokość poziomu znajdującego się bezpośrednio pod nim (o ile taki istnieje). Co więcej, żadna bela nie może znajdować się na wyższym poziomie niż inna bela o wyższym numerze (czyli należy je układać po kolei) i należy wykorzystać wszystkie bele. Jaka jest największa możliwa wysokość wieży, którą można zbudować przy takich założeniach (patrz Rys. 1)?

Dość naturalnym rozwiązaniem zachłannym, które może się nam narzucić, jest konstruowanie każdego poziomu z jak najmniejszej liczby beli siana, podczas budowania wieży od góry. Niestety, jest to rozwiązanie niepoprawne, jak można się przekonać, patrząc na rysunek 2.

Spróbujmy więc rozwiązania opartego o metodę programowania dynamicznego. Niech $|d[i, j]$ oznacza maksymalną wysokość wieży złożonej z beli o szerokościach $wi,$ jeśli dolny poziom wieży składa się z beli o szerokościach $wi,$ Wtedy mamy następującą rekurencję, w której iterujemy po wszystkich możliwościach zbudowania drugiego poziomu (przyjmujemy tu oznaczenie $w[i,$ ):

d[i, j] = maxj @kDn{1+ d[ j+ 1,k] w[i,

Czas wypełniania tablicy $d$ to $O(n3),$ a odpowiedź to $max1DjDn | d[1, j].$

Można nieco zmodyfikować powyższy pomysł, aby uzyskać rozwiązanie o złożoności czasowej $|O(n2).$ Oznaczmy przez $d2[i, | j]$ maksymalną wysokość wieży złożonej z beli $|wi,$ w której dolny poziom nie zawiera beli $w j+1$ Rekurencja przybierze postać

d2[i, j] = max(d2[i, j− 1],1+ d2[ j+ 1,ki, j]),

gdzie $ki, j$ jest maksymalnym indeksem, dla którego $w[i,$ Taki indeks możemy obliczać na bieżąco, jeśli ustalimy indeks $|i$ i będziemy wypełniać tablicę $|d2$ kolejno dla rosnących wartości indeksu $j.$ Odpowiedź to $|d2[1,n].$

Jeszcze lepsze rozwiązanie uzyskamy, korzystając z obserwacji, że najwyższa wieża będzie miała też najmniejszą szerokość dolnego poziomu. Udowodnijmy to przez indukcję: pokażemy to dla wieży zbudowanej z beli $|w$ przy założeniu, że teza jest spełniona dla wież zbudowanych z beli o szerokościach $wj,$ dla $j > i.$ Załóżmy, że wieża o najmniejszej szerokości dolnego poziomu ma go zbudowanego z beli $wi,$ Wtedy najwęższa wieża z beli $|wj+1,$ będzie miała (na mocy założenia indukcyjnego) największą wysokość $h$ (a zatem cała wieża wysokość $h + 1$ ). Teraz dowolna inna wieża mająca dolny poziom $|wi,$ dla $j′> j$ ma resztę zbudowaną z $|wj$ o wysokości $|h′$ (zatem cała wieża ma wysokość $h′ +1$ ). Ale wtedy istnieje wieża złożona z $w j+1$ o wysokości $h ′$ (bo wystarczy rozszerzyć dolny poziom), zatem $′ |h ⩽ h$ (z maksymalności $|h$ ). To kończy dowód.

Niech zatem $d3[i]$ oznacza taki indeks $j,$ że najwęższa wieża zbudowana z beli o szerokościach $wi,$ ma dolny poziom złożony z beli o szerokościach $wi,$ Wtedy mamy rekurencję:

d3[i] = miniDj Dn{ j w[i,

Wyznaczywszy tablicę $d3$ w czasie $O(n2),$ odpowiedź odzyskujemy, obliczając długość ciągu $|d [1],d [d [1]+ 1],... 3 3 3$ zawierającego końce kolejnych poziomów w najwęższej wieży.

Tablicę $d 3$ można wypełnić szybciej. Ustalmy indeks $j$ i niech $k j$ będzie maksymalnym indeksem, dla którego spełniona jest nierówność $|w[kj,$ Wiemy zatem, że $d3[i]⩽ j$ dla wszystkich $|i⩽ k j.$ Algorytm jest następujący: dla kolejnych indeksów $j$ wykonujemy przypisanie $|d [ j] = min(d [ j],d [ j + 1]), 3 3 3$ wyznaczamy wyszukiwaniem binarnym indeks $k j$ i wykonujemy $d3[kj ] = j.$ Złożoność czasowa tego algorytmu to $|O(n$

A Czytelników Dociekliwych zachęcamy do rozwiązania tego zadania w optymalnej złożoności czasowej $O(n).$