Informatyczny kącik olimpijski

Przeciąganie liny

W tym miesiącu proponujemy zadanie Przeciąganie liny, które pojawiło się w podwarszawskim Józefowie, podczas zeszłorocznej Bałtyckiej Olimpiady Informatycznej. Zadanie opisuje problem optymalizacji znanej wakacyjno-urlopowej zabawy. Co ciekawe, warstwa fabularna proponowanego rozwiązania - choć pozostaje w podobnych klimatach - to jednak odchodzi od liny na rzecz plecaka.

|1a,2b,3d,6e,5c,8h,9i,7 f,4g,10 j — Wierzchołki oznaczono liczbami, krawędzie - literami. Jedyne możliwe przyporządkowania to:
$| 1a,2b,3d,6e,5c,8h,9i,7 f,4g,10 j$ albo
$|1a,3b,2c,5e,6d,8h,9i,7 f,4g,10 j.$

Ale po kolei:

W zadaniu rozważamy $|2n$ osób chcących zabawić się w tytułową grę. Lina do zabawy ma przygotowane $2n$ uchwytów, po $n$ z każdej strony. Każda z osób deklaruje zawczasu dwa uchwyty, przy których chciałaby się znaleźć. Znamy również siłę każdej z osób, wyrażoną przez liczbę naturalną od $|1$ do $|s.$ Naszym celem jest ustalić, czy jest możliwe takie ustawienie uczestników zabawy, aby każdy dostał jeden z dwóch wybranych przez siebie uchwytów oraz aby różnica sił między dwiema drużynami nie przekraczała pewnej danej liczby $k.$

Ograniczenia opisane w zadaniu wydają się dość dziwaczne. Najlepiej jest na nie spojrzeć w następujący sposób. Rozważmy graf $|G,$ w którym wierzchołki reprezentują uchwyty, a krawędzie - ludzi. Krawędź $e$ łączy wierzchołki $|u$ i $v$ wtedy i tylko wtedy, gdy osoba $e$ zadeklarowała jako ulubione właśnie uchwyty $|u$ i $v.$ W tym języku przyporządkowanie osobom uchwytów sprowadza się do (wzajemnie jednoznacznego) przyporządkowania krawędziom jednego z ich wierzchołków.

Nawet jeśli zapomnimy o warunku dotyczącym zrównoważenia sił obu stron, nie zawsze jest możliwe jakiekolwiek przyporządkowanie spełniające wszystkie preferencje dotyczące uchwytów. Przede wszystkim, w $G$ każda spójna składowa o $|m$ wierzchołkach musi mieć dokładnie $|m$ krawędzi. Takie grafy to tak zwane pseudolasy, a więc zbiory rozłącznych pseudodrzew. Każde pseudodrzewo zawiera dokładnie jeden cykl (dlaczego?). W takim grafie istnieją tylko dwa różne przyporządkowania wierzchołków do sąsiednich krawędzi. Dla wierzchołków nie leżących na cyklu możliwy jest tylko jeden wybór. Na cyklu wybory są dwa: przyporządkujemy krawędzie kolejnym wierzchołkom albo zgodnie albo przeciwnie do ruchu wskazówek zegara.

Wobec powyższego, nasze rozwiązanie w pierwszej fazie sprawdza, czy dane wejściowe rzeczywiście tworzą pseudolas. Jeśli nie, to oczywiście odpowiedź na zadanie brzmi również "nie". Dalej zakładamy więc, że mamy do czynienia już tylko z pewnym zbiorem pseudodrzew. Jak zauważyliśmy wcześniej, dla każdego takiego pseudodrzewa mamy tylko dwie możliwości. Dla każdej z nich obliczmy jaką siłę do lewej strony liny wnosi. Te wartości oznaczmy jako $ai$ oraz $|bi$ dla $|i$ -tego pseudodrzewa. Bez straty ogólności załóżmy, że zawsze $|a ⩽ b . i i$ Widzimy, że łączna siła lewej drużyny będzie równa co najmniej $|Piai$ i co najwyżej $|Pi bi = Pi ai + Pi(bi− ai),$ przy czym każdy ze składników $|(bi− ai)$ możemy dodać bądź nie, według naszego uznania. Pamiętajmy oczywiście, że chcemy, aby ta siła mieściła się między $|(S/2− k/2)$ a $|(S/2+ k/2),$ gdzie $S$ oznacza łączną siłę wszystkich osób.

To ostatnie spojrzenie na problem z zadania opiszemy w języku tak zwanego problemu plecakowego (ang. knapsack problem). Rozważmy plecak o pojemności maksymalnej $(S/2 +k/2 − Pi ai)kg$ . Mamy dostępny zbiór przedmiotów (indeksowany $i$ ) o wagach $(bi− ai)kg$ . Pytamy, czy uda się nam zabrać przedmioty o łącznej wadze co najmniej $|(S/2− k/2 −Pi ai)kg$ i jednocześnie nieprzekraczającej pojemności plecaka.

Problem plecakowy to klasyczny problem, który da się standardowo rozwiązać w czasie $O(nS).$ W naszym zadaniu możemy jednak znaleźć rozwiązania lepsze (o ile $s ≪ n$ ), bo działające w czasie $√ -- |O( S)⋅O(S) = O(S3~2).$

Skorzystamy z założenia, że siła każdej osoby (a więc i wagi przedmiotów w problemie plecakowym) jest wyrażona liczbą naturalną. Wnioskujemy z tego, że istnieje co najwyżej $|O(√ S)$ różnych wartości wag przedmiotów (suma $|m$ różnych liczb naturalnych jest równa co najmniej $m ---2-- = O(m2)$ ). Pozostaje ostatni krok, zrealizowany za pomocą programowania dynamicznego:

Tworzymy (początkowo wypełnioną zerami) binarną tablicę $t$ rozmiaru $|S,$ w której będziemy zaznaczać, czy da się przygotować plecak o ustalonej wadze. Działamy w pętli o $√ -- O( S)$ obrotach, w każdym obrocie dając dostęp do kolejnej unikatowej wagi przedmiotu.

Oto pseudokod jednego obrotu, dla nowej wagi $w$ występującej $|q$ razy:

W każdym kroku pętli albo uzyskujemy nową objętość plecaka albo kończymy dodawania dla ustalonej objętości. Oba zdarzenia mogą wystąpić $|S$ razy, stąd czas działania jednego obrotu pętli to faktycznie $O(S)$ tak, jak zapowiedzieliśmy.