Krasnoludki

19.09.2009 - Tomasz Waleń
TrudnośćTrudność

Jednym z najciekawszych zadań spośród tych, nad którymi miałem okazję się chwilę zastanawiać, są Krasnoludki. Problem pochodzi z obozu treningowego na IOI drużyny reprezentującej Rumunię, a odnalazłem o nim informację poprzez wpis na blogu Mihai'a Pătraşcu (na którym można znaleźć także wiele innych ciekawych problemów!).

Zadanie

Historia zadania opowiada o $ n $ krasnoludkach, które w bliżej niewyjaśnionych okolicznościach wpadły do głębokiej na $ H $ metrów dziury. Niestety nie mają przy sobie żadnych narzędzi czy lin... mogą więc liczyć tylko na utworzenie żywej wieży, gdzie każdy krasnoludek staje na barkach poprzednika. Gdy krasnoludek dosięga ramionami powierzchni ziemi może się już uwolnić, niestety z niezrozumiałych, acz ściśle zastrzeżonych w treści zadania powodów, nie może już w takim przypadku udzielać żadnej pomocy pozostałym krasnoludkom (trzeba przyznać, że nie świadczy to o nich najlepiej...). Każdy krasnoludek jest charakteryzowany wysokością od ziemi do barków $ h_i $, oraz zasięgiem ramion $ l_i $. Naszym zadaniem jest na podstawie danej wysokości dziury $ H $ oraz opisów $ n $ krasnoludków $ h_i/l_i $ wyznaczyć ile maksymalnie krasnoludków może się uratować z tej opresji. Przykładowo, dla dziury o wysokości $ H=10 $ oraz czterech krasnoludków $ K_1=(h=3,l=5) $, $ K_2=(h=2,l=2) $, $ K_3=(h=5,l=1) $, $ K_4=(h=1,l=1) $ możemy uratować 3 krasnoludki ustawiając je w kolejności $ K_2, K_1, K_3, K_4 $, tak jak na rysunku:

Pierwsze podejście - algorytmy zachłanne

Pierwszy pomysłem, który próbowałem w tym zadaniu zastosować, to wyznaczenie strategii zachłannej. Niestety każde proste kryterium okazywało się w tym wypadku zawodne (np. uporządkowanie kolejności krasnoludków na wieży według malejących wartości $ h_i $ lub sum $ h_i+l_i $). Co ciekawe, gdyby krasnoludki były opisywane tylko przez jedną wartość $ h_i $ (czyli $ l_i=0 $), to zadanie staje się bardzo proste, wystarczy uporządkować je według malejących wartości $ h_i $ i wyznaczyć minimalny indeks $ k $ taki, że $ \sum_{i=1}^k h_i \ge H $.

Gdybyśmy dysponowali magiczną skrzynką, która potrafiłaby odpowiadać, czy w optymalnym rozwiązaniu dany krasnolud musi zostać "poświęcony" dla dobra ogółu (czyli zostanie na dnie dziury), czy też uda się go uratować, to do konstrukcji optymalnego rozwiązania możemy już zastosować algorytm zachłanny.

Wszystkie krasnoludy, których nie uda się uratować, możemy ustawić na dole wieży, pozostałe krasnoludki ustawiamy w kolejności malejących sum $ h_i+l_i $ (czyli krasnoludki o najwyższej sumie są najniżej w wieży, a te o najmniejszej sumie najwyżej). Konieczne jest wykazania, że dowolne rozwiązanie, możemy sprowadzić do równie dobrego (czyli ratującego ten sam zbiór krasnoludków), w którym uratowane krasnoludki uporządkowane są według malejących wartości $ h_i+l_i $.

Pierwsza część powyższego stwierdzenie jest dosyć oczywista, jeśli umieścimy krasnoludka, który musi zostać "poświęcony" w środku wieży, to równie dobrze możemy go przenieść na sam spód wieży, co spowoduje że:

  • uratowanie krasnoludków, które znajdowały się poniżej, będzie łatwiejsze, po zmianie będą znajdować się wyżej niż poprzednio,
  • pozycja krasnoludków, które znajdowały się powyżej pozostanie bez zmian.

Tak więc taka zmiana nie pogorszy obecnego rozwiązania (a może je nawet polepszyć).

Druga cześć twierdzenia wymaga dokładniejszej analizy, jednak dowód jest również bardzo prosty. Załóżmy, że jeśli w pewnym rozwiązaniu na wieży sąsiadują dwa krasnoludki o opisach $ K=(h,l) $ (na wysokości $ t $ w wieży) oraz $ K'=(h',l') $ (na wysokości $ t+h $ w wieży), takie, że $ h+l < h'+l' $. Ponieważ możemy uratować oba krasnoludki stąd: $ t+h+l \ge H $ oraz $ t+h+h'+l'\ge H $. Zamiana krasnoludków miejscami w żaden sposób nie wpływa na sytuację pozostałych krasnoludków, dodatkowo po tej zamianie nadal możemy uratować $ K $ i $ K' $:

$$t+h'+l' \ge t+h+l \ge H$$
$$t+h'+h+l \ge t+h+l \ge H$$
Niestety nie dysponujemy taka magiczną skrzynką (jeszcze!), koniecznie jest więc dalsze poszukiwanie rozwiązania. Jednak poprzednia obserwacja będzie bardzo przydatna w konstrukcji poprawnego rozwiązania.

Drugie podejście - programowanie dynamiczne

Skoro użycie strategii zachłannej zakończyło się porażką, to może warto spróbować programowania dynamicznego. Niestety musimy zmierzyć się z dwoma problemami:

  • Po pierwsze, treść zadania nie nakłada żadnych ograniczeń na wartości $ h_i/l_i $, czyli w szczególności mogą to być liczby rzeczywiste, co wyklucza możliwość budowania programowania w oparciu o wysokości wież, którą mogą otworzyć krasnoludki.
  • Drugim problemem jest brak prostego kryterium pozwalającego rozszerzać już wyznaczone rozwiązanie o kolejne krasnoludki. Niekiedy nawet dodanie jednego krasnoludka powoduje duże zmiany w rozwiązaniu.

Niestety powyższe problemy powodują, że i w tym przypadku trzeba przyznać się do porażki.

Połączenie obu rozwiązań

Zazwyczaj w programowaniu dynamicznym nie ma znaczenia w jakim porządku analizujemy dane (czyli w naszym wypadku krasnoludki), jednak w tym zadaniu jest to kluczowe.

W pierwszym kroku porządkujemy malejąco krasnoludki według sum $ h_i+l_i $, czyli od tego momentu może zakładać, że $ h_i+l_i \ge h_{i+1}+l_{i+1} $ dla $ 1\le i < n $. Dzięki takiemu postępowaniu będzie możliwe rozszerzanie już wyznaczonych rozwiązań o kolejne krasnoludki.

Zdefiniujmy wartości $ M[i,u] $, dla $ 0 \le i,j \le n $ oznaczające maksymalną wysokość dziury, dla której możliwe jest uratowanie $ u $ krasnoludków spośród krasnoludków o numerach $ 1,..,i $. Wartości brzegowe możemy zdefiniować zakładając, że $ M[i,0]=\infty $, oraz $ M[0,u]=-\infty $ (co oznacza brak rozwiązania), dla $ u>0 $.

Szczęśliwie wartości $ M[i,u] $ dla $ i,j>0 $ można wyznaczyć na podstawie wartości $ M[i-1,u] $ oraz $ M[i-1,u-1] $. Otóż dla $ M[i,u] $ musimy podjąć decyzję czy krasnoludek o numerze $ i $-tym powinien zostać uratowany czy też niestety nie. Jeśli nie decydujemy się na jego uratowanie, to $ i $-tego krasnoludka możemy ustawić na spodzie wieży, stąd nowe rozwiązanie będzie miało wysokość $ m_1 = M[i-1,u]+h_i $. Natomiast jeśli chcemy jednak uratować $ i $-tego krasnoludka, to powinniśmy umieścić go na szczycie wieży (tutaj korzystamy z obserwacji z algorytmu zachłannego!). Wysokość wieży będzie taka sama jak w przypadku $ M[i-1,u-1] $ jeśli krasnoludek dosięga do szczytu dziury, lub $ l_i + \sum_{j=1}^i h_j $ w przeciwnym przypadku, stąd wartość rozwiązania w tym przypadku wynosi $ m_2 = \min(M[i-1,u-1], l_i+\sum_{j=1}^i h_j) $. Łącząc te dwa przypadki otrzymujemy: $ M[i,u]=\max(m_1,m_2) $.

Maksymalną liczbę krasnoludków, którą można uratować można odczytać z tablicy $ M $ wybierając maksymalny indeks $ u $, taki, że $ M[n,u]\ge H $.

Pełen opis algorytmu wyznaczającego tablicę $ M $ znajduje się poniżej. Łatwo sprawdzić, że jego złożoność czasowa to $ O(n^2) $.

  1. uporządkuj krasnoludki, malejąco, według wartości $ h_i+l_i $
  2. wyznacz wartości $ H[i]=\sum_{j=1}^i h_i $ dla $ i=0,\ldots,n $
  3. for $ i=0,..,n $ $ M[i,0]=\infty $, $ M[0,u]=-\infty $ dla $ u>0 $
  4. for $ i=1,..,n $
        for $ u=1,..,n $ do
           $ m_1 = M[i-1,u]+h_i $ jeśli $ M[i-1,u]\ge 0 $ lub $ -\infty $
           $ m_2 = \min(H[i]+l_i, M[i-1,u-1]) $ jeśli $ M[i-1,u-1]\ge 0 $, lub $ -\infty $
           $ M[i,u] = \max(m_1,m_2) $
  5. return $ \max\{ u : M[n,u] \ge H $ dla $ 0 \le u \le n\} $
4.5
Twoja ocena: Brak Ocena: 4.5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com