Przeskocz do treści

Delta mi!

Loading

Informatyczny kącik olimpijski

Przeciąganie liny

Tomasz Kazana

o artykule ...

  • Publikacja w Delcie: marzec 2017
  • Publikacja elektroniczna: 1 marca 2017
  • Autor: Tomasz Kazana
    Afiliacja: Instytut Informatyki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (77 KB)

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.

obrazek

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.

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.

obrazek

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.