Przeskocz do treści

Delta mi!

Loading

Informatyczny kącik olimpijski

Flagi

Jacek Tomasiewicz

o artykule ...

  • Publikacja w Delcie: wrzesień 2016
  • Publikacja elektroniczna: 1 września 2016
  • Wersja do druku [application/pdf]: (261 KB)
obrazek

W tym miesiącu, chcąc polecić Czytelnikom kącika książkę Zaprzyjaźnij się z algorytmami, przedstawimy jedno zadanie z tej pozycji. Wybieramy się na wyprawę w góry.

obrazek

Rys. 1

Rys. 1

Zadanie. Na mapie trasy zaznaczyliśmy |n kolejnych miejsc o wysokościach a0,a1,...,an−1. Podczas wędrówki chcemy rozmieścić jak największą liczbę flag na szczytach, czyli takich miejscach, dla których dwa sąsiednie miejsca są położone niżej (zakładamy, że pierwsze i ostatnie miejsce nie są szczytami). Jest jedno ograniczenie: jeśli rozmieszczamy |k flag, to odległość pomiędzy dwiema dowolnymi flagami powinna być równa co najmniej k.

Przykładowo dla trasy opisanej tablicą a = [1,5,3,4,3,4,1,2,3,4,6,2] mamy dokładnie cztery szczyty (Rys. 1]).

Na tej trasie możemy rozmieścić 3 flagi (np. na szczytach 1, 5 i 10). Nie możemy jednak rozmieścić 4 flag, tak aby odległość pomiędzy nimi była równa co najmniej 4.

Wynik może być znaleziony przy użyciu wyszukiwania binarnego. Jeśli wiemy, że x flag może zostać rozmieszczonych na szczytach, to również wiemy, że każda ich mniejsza liczba może też być rozmieszczona. Z drugiej strony, jeśli x flag nie może zostać rozmieszczonych, to każda większa liczba flag również nie może być rozmieszczona. W ten sposób, używając wyszukiwania binarnego, redukujemy problem do sprawdzenia, czy można rozmieścić na szczytach ustaloną liczbę |x flag. Taki problem możemy rozwiązać już zachłannie: idziemy trasą i zawsze ustawiamy flagę na najbliższym dozwolonym szczycie. Całe rozwiązanie działa w czasie (nlogn) O ze względu na czas wyszukiwania binarnego.

Zadanie da się rozwiązać szybciej, w czasie liniowym. Na początku, dla każdego miejsca, jeśli nie jest szczytem, znajdujemy najbliższy szczyt położony na dalszym odcinku trasy. W tym celu możemy najpierw oznaczyć wszystkie szczyty, a następnie przeglądać trasę w odwróconej kolejności, pamiętając pozycję ostatnio spotkanego szczytu. W ten sposób wypełnimy tablicę nast, gdzie |nast[i] będzie najbliższym szczytem od miejsca numer |i na prawo (lub wartość ∞ , jeżeli dalej nie występuje już żaden szczyt). Dla powyższego rysunku mamy nast = [1,1,3,3,5,5,10,10,10,10,10,∞ ].

Zauważmy, że możemy rozmieścić co najwyżej  √ -- ⌊ n +1⌋ flag. Ta obserwacja doprowadzi nas do rozwiązania optymalnego. Jeśli ustawiamy jakąś flagę na pozycji p, to wiemy, że następna flaga powinna być ustawiona na pozycji dalszej lub równej |p+ k. Takie miejsce możemy znaleźć w czasie stałym, korzystając z tablicy nast. Pseudokod takiego rozwiązania może wyglądać następująco:

obrazek

Całkowita liczba operacji nie przekroczy √2 (n)=O(n) O , gdyż zarówno zewnętrzna jak i wewnętrzna pętla zostaną wykonane co najwyżej - (√n)O razy.