Omówienie zadania Schody (II etap XXXII OI)
Wprowadzenie
Celem zadania jest obliczenie, jak szybko można przemieścić pracowników w budynku z jednego rozmieszczenia do drugiego. W rozmieszczeniu liczy się tylko liczba pracowników na każdym piętrze (pracownicy są nierozróżnialni). Każda klatka schodowa, łącząca dwa piętra, może być używana jednocześnie przez maksymalnie jedną osobę w każdej jednostce czasu. Chcemy zoptymalizować ten proces tak, aby zminimalizować całkowity czas potrzebny na przemieszczenie wszystkich pracowników.
Uproszczenie problemu
Zacznijmy od obserwacji, że w optymalnym rozwiązaniu pracownicy nie będą się wzajemnie "mijać". Oznacza to, że między każdą parą sąsiednich pięter ruch będzie odbywał się wyłącznie w jedną stronę – w górę lub w dół. Dlaczego? Jeśli mielibyśmy przypadek, w którym jeden pracownik schodzi na piętro \(i\), a inny potem wchodzi na piętro \(i+1\), to można ich docelowe piętra zamienić. To nie pogorszyłoby wyniku, a mogłoby nawet go poprawić. Oznacza to, że piętra możemy podzielić na przedziały, na których pracownicy będą przemieszczać się w tym samym kierunku i możemy takie przedziały pięter rozważyć niezależnie.
Kierunek ruchu pracowników
Aby określić, w którą stronę mają się przemieszczać pracownicy, możemy policzyć ile jest oraz ile powinno być osób na niższych piętrach (suma liczb osób na piętrach od 1 do \(i\)). Porównujemy te sumy dla konfiguracji początkowej i końcowej:
- Jeśli na piętrach od 1 do \(i\) w konfiguracji początkowej jest więcej pracowników niż potrzeba, nadmiar osób musi przejść wyżej.
- Jeśli w konfiguracji końcowej na tych piętrach brakuje osób, musimy przysłać je z wyższych pięter.
Brutalne rozwiązanie
Najprostsze podejście polega na iteracyjnym przesuwaniu pracowników w odpowiednim kierunku. Dla każdej pary pięter liczymy, ilu pracowników musi przejść przez klatkę schodową w danym kierunku. Następnie przesuwamy pracowników w jednostkach czasu (o ile to możliwe), aż osiągniemy stan docelowy. To rozwiązanie jest poprawne, ale nieefektywne - wymaga sprawdzania każdego piętra i przesuwania osób pojedynczo, co jest czasochłonne. W zależności od implementacji, możemy za nie otrzymać od 7 do 17 punktów.
Rozwiązanie prawie optymalne
Zanim przejdziemy do szczegółów, warto zauważyć, że myślimy o tym, kiedy korzystamy z klatek schodowych w kontekście przedziałów czasowych. Są one ograniczonym zasobem – w każdej jednostce czasu może korzystać z nich tylko jedna osoba, a kiedy klatka schodowa jest nieużywana, to tracimy cenny czas. Chcemy maksymalnie wykorzystać jej dostępność, przesuwając ludzi kiedy tylko można. Oznacza to, że klatki schodowe będą zajęte przez dłuższe (ciągłe) przedziały czasu, choć dla danej klatki może istnieć więcej niż jeden taki przedział.
Skoro wiemy, w jakim kierunku i ile osób będzie się przemieszczać między piętrami, możemy skupić się na efektywnym wyznaczaniu przedziałów czasu, w których klatki schodowe będą zajęte. Załóżmy, że analizujemy przedział, na którym wszyscy pracownicy przemieszczają się w górę (dla kierunku w dół proces jest symetryczny). Zauważmy, że:
- Pracownicy zaczynający na danym piętrze powinni być wysyłani w pierwszej kolejności - pozwala to uniknąć początkowego marnowania czasu, gdy klatka schodowa nie jest używana.
- Jeśli pracowników zaczynających na danym piętrze nie wystarczy, pozostałe zapotrzebowanie uzupełniamy pracownikami przychodzącymi z niższych pięter.
Zauważmy, że wiedząc, ilu pracowników z niższych pięter będzie korzystać z danej klatki schodowej, możemy łatwo określić przedziały czasu, w których będzie ona zajęta. Wystarczy przesunąć wszystkie przedziały czasu z piętra \(i-1\) o jednostkę czasu później (pamiętając o tym, aby usunąć lub skrócić te, z których pracownicy zostaną na piętrze \(i\)). Pozostałe "luki" w przedziałach czasu możemy wypełnić pracownikami z piętra \(i\) (aby nasze rozwiązanie działało szybko, należy dwa styczne przedziały zawsze łączyć w jeden). Wynik możemy łatwo odtworzyć, szukając najpóźniejszego momentu, w którym klatka schodowa była zajęta.
Aby efektywnie zarządzać tym procesem, utrzymujemy informację o zajętości klatek schodowych w strukturze, która pozwala łatwo dodawać i przesuwać przedziały czasu (możemy to zrobić np. za pomocą kolejki par mówiących o tym, kiedy dany przedział czasu się zaczyna i kończy).
Za takie rozwiązanie otrzymujemy już 48 punktów.
Rozwiązanie optymalne
Przeanalizujmy, co jest najbardziej czasochłonne w naszym rozwiązaniu. W każdej iteracji musimy przesunąć wszystkie przedziały czasu o jednostkę czasu później. W przypadku, gdy przedziałów jest dużo, zajmie to sporo czasu. Jak możemy tego uniknąć?
Zauważmy, że zawsze wszystkie przedziały przesuwamy o tę samą wartość. Możemy zatem wprowadzić pojęcie globalnego przesunięcia. Oznacza to, że zamiast faktycznie przesuwać przedziały, zapamiętujemy, o ile zostały one przesunięte w sumie. Kiedy dodajemy nowy przedział lub chcemy poznać wynik, uwzględniamy to globalne przesunięcie w obliczeniach (dodając przedział odpowiednio wcześniej lub zwiększając wynik dodatkowo o to przesunięcie). Dzięki temu nasze rozwiązanie działa w czasie \(O(n)\), gdzie \(n\) to liczba pięter, co pozwala na uzyskanie pełnej liczby punktów.
Rozwiązanie alternatywne
Jeszcze przedstawimy rozwiązanie o innej, prostej idei, ale trochę trudniejsze do udowodnienia i zaimplementowania. Pomijamy szczegóły, ponieważ rozwiązanie opisane powyżej jest już optymalne. Można udowodnić, że wynik na kawałku długości \(m\), w którym pracownicy idą w jedną stronę, jest równy
- \(max\{u(i,j) + (j - i) : 1 ≤ i ≤ j ≤ m,u(i,j) > 0\}\), gdzie:
- \(u(i,j) := d(i) - (b(i) + \ldots + b(j - 1))\),
- zaś \(d(i) = a(1)+\ldots+a(i - 1) - (b(1)+\ldots+b(i - 1))\)