Omówienie zadania Drwale (II etap XXX OI)

Podstawowe obserwacje

W zadaniu mamy dane \(n\) kawałków drewna o długościach \(a_1, a_2, \dots, a_n\), które mają zostać porąbane przez dwóch drwali: Bitka i Bajtka. Rąbanie kawałka o długości \(a_i\) zajmuje \(a_i\) minut. Kiedy jeden z drwali skończy rąbać kawałek, bierze następny ze stosu. Jeśli obaj skończą jednocześnie, to pierwszeństwo ma Bitek. Naszym celem jest obliczenie ile najdłużej może trwać proces, jeśli kolejność kawałków na stosie jest wyjątkowo niefortunna.

Na początek spojrzymy na to, jak przebiega proces rąbania. Za każdym razem, kiedy któryś z drwali skończy rąbać kawałek drewna, bierze on następny kawałek ze stosu. Pierwszą ważną obserwacją jest to, że w momencie, kiedy jeden z drwali skończy pracę i nie będzie miał nic do roboty, to drugi także skończy, lub będzie rąbał jeden ostatni kawałek drewna (gdyby były to przynajmniej dwa kawałki, to mógłby wziąć jeden z nich zamiast czekać).

Można zauważyć, że wynik dla ustalonej kolejności tych samych kawałków drewna zależy tylko i wyłącznie od czasu, jaki jeden z drwali spędza na koniec czekając. Jeśli oznaczymy ten czas jako \(x\), to czas pracy \(t\) będzie \(t = \frac{1}{2}(A - x) + x\), gdzie literą \(A\) oznaczamy sumę czasów rąbania wszystkich kawałków. Widać, że im większy \(x\), tym dłużej zajmuje w sumie cała praca.

Można także pójść o krok dalej i zauważyć, że \(x\) zależy od tego, który kawałek jest na stosie ostatni - będzie on zawsze mniejszy lub równy czasowi rąbania ostatniego kawałka, więc wydaje się logiczne, aby ostatni kawałek był jak najdłuższy. Okazuje się, że będzie to najdłuższy z kawałków drewna, jednakże należałoby to udowodnić.

Najpierw jednak warto zauważyć, że możemy podzielić kawałki drewna pomiędzy dwóch drwali w praktycznie dowolny sposób, w jaki chcemy (z pewnymi ograniczeniami). To znaczy, jeśli da się podzielić drewno pomiędzy dwóch drwali w taki sposób, że na koniec pracy jednego drwala drugi nie posiada już żadnych kawałków drewna, których jeszcze nie zaczął ciąć, to wtedy da się ułożyć kawałki w takiej kolejności, która po symulacji procesu da nam taki podział. Jedyna sytuacja, w której nie do końca to działa następuje, kiedy obaj drwale kończą jednocześnie, a ostatni kawałek, który został, ma przypadać Bitkowi. Jednakże treść zadania mówi, że jeśli obaj drwale kończą jednocześnie, to następny kawałek przypada Bajtkowi. Możemy łatwo pozbyć się tego problemu zakładając, że Bajtek zawsze dostaje ten większy stos, co nie zmienia rozwiązania zadania. Załóżmy, że mamy dwa uporządkowane stosy kawałków drewna - jeden, który chcemy aby porąbał Bitek oraz drugi, który ma porąbać Bajtek. Będziemy łączyć te stosy w jeden, który po symulacji procesu da nam właśnie taki podział.

Na początku, obaj drwale czekają na robotę, czyli według treści powinniśmy dać kawałek Bajtkowi. Następnie musimy dać kawałek drewna Bitkowi, ponieważ teraz już tylko on czeka. Następnie czekamy, aż któryś z drwali skończy rąbać i wtedy dajemy mu nowy kawałek ze stosu przeznaczonego dla niego. Za każdym razem, kiedy "dajemy" kawałek, to tak naprawdę po prostu umieszczamy go na głównym stosie. Kolejność w jakiej dajemy kawałki, będzie tą permutacją stosu, która da nam taki podział jak chcemy. Będziemy kontynuować proces aż do momentu kiedy na stosie, z którego chcemy dać kawałek drewna, żadne takowe nie pozostały. Okazuje się, że w takiej sytuacji stos przeznaczony dla drugiego z drwali także będzie pusty. Dzieje się tak, ponieważ na początku założyliśmy, że gdy jeden drwal skończy robotę, to drugi nie może już mieć żadnych kawałków na swoim stosie. Skoro oba stosy są puste, to ustaliliśmy kolejność wszystkich kawałków drewna.

Najdłuższy kawałek drewna

Na początek przypuśćmy, że najdłuższy kawałek nie jest najdłuższym kawałkiem u tego z drwali, który go rąbie. W takiej sytuacji możemy po prostu przełożyć go na koniec i wciąż będzie to dobry podział. Jest tak dlatego, że podział nie jest dobry wtedy i tylko wtedy, kiedy jeden z drwali miałby kawałek, który zaczyna rąbać ściśle po tym, jak drugi skończy całą pracę (wtedy zgodnie z treścią drugi z drwali wziąłby już ten kawałek). Łatwo zauważyć, że taka sytuacja nie może się wytworzyć poprzez przesunięcie najdłuższego kawałka na koniec. Dodatkowym wnioskiem z tego jest fakt, że w każdym możliwym rozwiązaniu, można kawałki rąbane przez każdego z drwali posortować od najkrótszego do najdłuższego.

Teraz pokażemy, że zawsze istnieje rozwiązanie optymalne takie, że najdłuższy kawałek jest rąbany przez drwala, który kończy później. Wykonamy dowód nie wprost, zakładając, że jedyne istniejące rozwiązania optymalne nie spełniają warunku (czyli najdłuższy kawałek zawsze jest u tego, kto kończy wcześniej). Przez \((a_1, a_2, \dots, a_n; b_1, b_2, \dots, b_m)\) będziemy oznaczać rozwiązanie, gdzie \(a_1, a_2, \dots, a_n\) oznacza (w kolejności) kawałki drewna rąbane przez jednego z drwali, a \(b_1, b_2, \dots, b_m\) oznacza te rąbane przez drugiego. Nie ma znaczenia, który drwal to Bitek, a który to Bajtek, ponieważ problem jest praktycznie symetryczny. Jest tak, ponieważ warunek, że Bajtek ma pierwszeństwo brania kawałka drewna, kiedy obaj drwale skończą jednocześnie, nie wpływa w żadnym istotnym stopniu na rozwiązanie zadania.

Niech \((a_1, a_2, \dots, a_n; b_1, b_2, \dots, b_m)\) będzie optymalnym rozwiązaniem. Niech kawałki będą posortowane niemalejąco, czyli \(a_1 \leq a_2 \leq \ldots \leq a_n\) oraz \(b_1 \leq b_2 \leq \ldots \leq b_m\). Dodatkowo załóżmy, że \(b_m\) jest najdłuższym kawałkiem (czyli \(b_m > a_n\) ), a suma \(b_1 + b_2 + \ldots + b_m\) jest mniejsza od sumy \(a_1 + a_2 + \ldots + a_n\). W uproszczeniu zakładamy istnienie optymalnego rozwiązania takiego, że najdłuższy kawałek jest u tego z drwali, który kończy pracę wcześniej. Naszym celem teraz jest pokazanie, że będzie istniało rozwiązanie nie gorsze niż \((a_1, a_2, \dots, a_n; b_1, b_2, \dots, b_m)\), które spełnia warunek, że najdłuższy kawałek jest u tego, kto kończy ostatni.

Łatwo zauważyć, że gdy \((a_1, a_2, \dots, a_n; b_1, b_2, \dots, b_m)\) jest rozwiązaniem, to zachodzi \[ \sum_{i = 1}^{n-1}a_i \leq \sum_{i=1}^{m}b_i \] ponieważ usunięcie ostatniego kawałka z wierzchu stosu \(a\) nie może spowodować, że stos \(a\) wciąż będzie dłuższy od stosu \(b\). Gdyby tak było, to oryginalny podział nie mógłby być dobrym podziałem, ponieważ ostatni kawałek stosu \(a\) powinien wtedy przypadać drwalowi rąbiącemu stos \(b\). Rozważymy teraz dwa przypadki:

1. Gdy \( \sum_{i = 1}^{n-1}a_i = \sum_{i=1}^{m}b_i\).
   Wtedy możemy po prostu przenieść kawałek \(a_n\) na stos \(b\), uzyskując rozwiązanie \((a_1, a_2, \dots, a_{n-1}; b_1, b_2, \dots, b_m, a_n)\). Nietrudno zauważyć, że jest to dobry podział. Jest to także optymalne rozwiązanie, ponieważ różnica długości stosów się nie zmienia. Dodatkowo, stos \(b\) jest teraz dłuższy od stosu \(a\), ale zawiera najdłuższy kawałek, czyli \(b_m\). Sprzeczność.
2. Gdy \( \sum_{i = 1}^{n-1}a_i < \sum_{i=1}^{m}b_i\).
   Wtedy rozpatrzymy dwa podprzypadki:
   • Gdy zachodzi \(\sum_{i=1}^{n-1}a_i > a_n + \sum_{i=1}^{m-1}b_i\).
     W tym przypadku możemy przenieść kawałek \(a_n\) ze stosu \(a\) na stos \(b\), otrzymując w ten sposób podział \((a_1, a_2, \dots, a_{n-1}; b_1, b_2, \dots, b_m, a_n)\). Jest to dobry podział i nie gorsze rozwiązanie, które spełnia warunek, ponieważ \(a_n+\sum_{i=1}^{m}b_i > a_n + \sum_{i=1}^{n-1}a_i = \sum_{i=1}^{n}a_i\). Sprzeczność.
   • Gdy zachodzi \(\sum_{i=1}^{n-1}a_i \leq a_n + \sum_{i=1}^{m-1}b_i\).
     W tym przypadku możemy zamienić ostatnie kawałki obu stosów, uzyskując podział \((a_1, a_2, \dots, a_{n-1}, b_m; b_1, b_2, \dots, b_{m-1}, a_n)\). Jest to rozwiązanie nie gorsze, które spełnia obserwację. Sprzeczność.

Skoro wszystkie przypadki prowadzą do sprzeczności, możemy stwierdzić, że zawsze istnieje optymalne rozwiązania takie, że najdłuższy kawałek jest rąbany przez tego z drwali, który kończy ostatni.

Problem plecakowy

Skoro wiemy, że najdłuższy kawałek drewna zawsze można bezpiecznie przesunąć do tego, kto kończy ostatni, to możemy po prostu odłożyć go na bok i dodać go dopiero na koniec. W momencie, kiedy odłożymy ten ostatni kawałek, nasz problem staje się o wiele prostszy - teraz wystarczy już tylko podzielić stos na części w taki sposób, aby różnica pomiędzy nimi była jak najmniejsza, a następnie dołożyć najdłuższy kawałek temu który ma mniejszy stos. W celu uzyskania takiego podziału zastosujemy programowanie dynamiczne, konkretnie jest to problem plecakowy. Będziemy próbować dać jednemu drwalowi kawałki w taki sposób, aby suma ich długości była jak najbliższa połowy sumy długości, z wyłączeniem najdłuższego kawałka. Wtedy na koniec po prostu dodamy najdłuższy kawałek do tej długości i otrzymamy wynik.

Algorytm taki ma niestety złożoność \(O(n \cdot A)\), co nie uzyska zbyt wielu punktów.

Usprawnienia

W celu przyspieszenia działania naszego algorytmu, należy jeszcze raz spojrzeć na ograniczenia dotyczące danych z zadania - liczba \(n\) może być równa nawet \(1\, 000\, 000\), ale zauważmy, że istnieje także górne ograniczenie na \(A\), czyli sumę długości kawałków. Gdyby kawałków było równo \(1\,000\,000\) i chcielibyśmy aby każdy był inny, to byłoby to niemożliwe, ponieważ ich suma byłaby zdecydowanie zbyt duża. Wybierając po kolei różne kawałki o najmniejszej możliwej długości uzyskamy dla \(n\) kawałków sumę liczb naturalnych od \(1\) do \(n\), która jest rzędu \(n^2\). W takim razie, gdybyśmy chcieli mieć wszystkie liczby różne, to może być ich maksymalnie \(O(\sqrt{A})\). W takim razie możemy pogrupować kawałki o tych samych długościach i rozwiązać problem plecakowy z pogrupowanymi elementami. Można to zrealizować na różne sposoby, jednym z nich jest dodatkowo trzymanie tablicy informującej nas ile razy dla danego indeksu został już "wykorzystany" dany kawałek w celu uniknięcia wykorzystania tego samego kawałka więcej razy niż go mamy.

Takie rozwiązanie ma złożoność \(O(n\log n + A\cdot \sqrt{A})\).

Operacje bitowe

Problem plecakowy można rozwiązać bardzo szybko za pomocą operacji bitowych. Kiedy interesuje nas jedynie osiągalność danej sumy, wystarczy trzymać tablicę osiągalności jako bitset. W tym celu musimy jednak odrobinę się cofnąć i na chwilę zapomnieć o poprzednich usprawnieniach, zamiast tego rozwiązując zwyczajny problem plecakowy. Zauważmy, że kiedy dodajemy kawałek o długości \(x\), to obliczamy stany programowania dynamicznego w następujący sposób: jeśli \(dp[k] = 1\), czyli mamy podzbiór kawałków o łącznej sumie \(k\), to możemy dołożyć nasz kawałek i uzyskać \(dp[x + k] = 1\). Robimy to jednak w sposób niezależny - dla danego kawałka nasze stany powinny zależeć jedynie od długości kawałka i od stanów sprzed dołożenia tego kawałka. Mamy w takim razie sytuację, kiedy chcemy obliczyć wiele niezależnych od siebie nawzajem stanów mających zawsze wartość \(0\) albo \(1\). Jeśli będziemy trzymać tablicę naszych stanów jako bitset to można zrobić to w bardzo prosty sposób. Wystarczy skopiować tablicę, wykonać na niej bitshift w prawo o \(x\), a następnie wykonać operacją "or" na tych dwóch bitsetach.

Złożoność takiego rozwiązania to \(O(n\cdot A)\).

Rozwiązanie wzorcowe

Dwóch metody, których użyliśmy aby przyspieszyć rozwiązanie nie da się połączyć w prosty sposób. Przynajmniej nie jest to możliwe przy oryginalnych założeniach problemu. Możemy jednak dokonać pewnych przekształceń równoważnych, aby sprowadzić nasz problem do prostszego. W tym celu niezbędna jest jedna obserwacja dotycząca problemu plecakowego. W tym przypadku warto pomyśleć o problemie plecakowym konkretnie jako o wydawaniu reszty. Wyobraźmy sobie, że mamy trzy identyczne kawałki drewna o długości \(X\). Możemy za ich pomocą naturalnie "wydać" wartości \(0, X, 2X, 3X\). Zauważmy jednak, że nasze trzy kawałki o długości \(X\) możemy zastąpić tylko dwoma kawałkami: jednym o długości \(X\) oraz jednym o długości \(2X\). Wtedy wartości osiągalne przez sumy podzbiorów są takie same, ale mamy o jeden kawałek mniej. Możemy powtarzać tę czynność do czasu, aż nie będziemy mieć żadnych trójek. Zostanie nam wtedy \(O(\sqrt{A})\) kawałków, ponieważ będą powtarzać się maksymalnie dwa razy, a ich suma się nie zmieni.

Po takim przekształceniu można już rozwiązać problem plecakowy za pomocą operacji bitowych i uzyskać maksymalną liczbę punktów za zadanie.