Omówienie zadania Waga (III etap XXIX OI)

Mamy 7 odważników o masach od 1 do 7 kilogramów, ale nie wiemy, który jest który. Należy to ustalić przy pomocy minimalnej liczby ważeń na wadze szalkowej (kładziemy na szalkach dwa podzbiory odważników i dostajemy informację, który jest cięższy).

Sortowanie

Na ten problem można spojrzeć jak na problem sortowania permutacji siedmioelementowej. Można wykonać dowolny algorytm sortowania i zastąpić każde porównanie, które chce on wykonać, przez ważenie dwóch odważników na wadze.

Algorytmy o złożoności kwadratowej (np. sortowanie bąbelkowe) wykonają co najwyżej \({7 \choose 2} = 21\) porównań, co daje już punkty za takie rozwiązanie.

Algorytm sortowania przez scalanie (zaimplementowany jako stable_sort w bibliotece standardowej C++) zrobi co najwyżej 15 porównań.

Uwaga: algorytm sort z biblioteki standardowej C++ może wymagać 21 porównań (dla krótkich ciągów wywołuje on procedurę działającą kwadratowo).

Lepsze sortowanie

Można próbować rozwiązać ten problem nieco ,,na palcach”. Dzielimy tablicę na część lewą (zawierającą trzy odważniki) i prawą (zawierającą cztery odważniki). Sortujemy je optymalnie z użyciem odpowiednio 3 i 5 porównań (implementując optymalne algorytmy sortowania stałej liczby liczb), a następnie robimy złączenie tych dwóch części, tak jak w algorytmie sortowania przez scalanie, używając dodatkowych 6 porównań.

Łącznie takie rozwiązanie wykonuje zaledwie \(14\) ważeń w pesymistycznym przypadku.

Niestety tego typu pomysłami nie da się zdobyć maksymalnej punktacji, gdyż dowolny algorytm sortowania oparty o porównania dwóch elementów będzie wykonywał co najmniej \(\lceil \log_2 7! \rceil = 13\) ważeń.

Ograniczenie dolne na liczbę ważeń

Każdy deterministyczny algorytm znajdowania kolejności odważników można przedstawić w postaci drzewa. W każdym jego węźle znajduje się podzbiór zbioru \(7! = 5040\) możliwych wynikowych permutacji. Z każdego węzła możemy wykonać jedno z \(3^7 = 2187\) możliwych zapytań (dla każdego odważnika ustalamy niezależnie czy ma być na lewej szalce, na prawej szalce, czy na stole), przy czym niektóre z tych zapytań są sobie równoważne (np. są swoimi odbiciami lustrzanymi).

W każdym węźle drzewa wybieramy zapytanie, jakie będziemy chcieli zadać i to dzieli zbiór permutacji z tego węzła na trzy zbiory: zgodne z odpowiedzią ,,lewa szalka cięższa”, ,,prawa szalka cięższa” lub ,,waga w równowadze”. W liściach drzewa znajdują się podzbiory złożone z pojedynczych permutacji (zatem mamy co najmniej \(7!\) liści).

Celem zadania jest dokonać w węzłach takich wyborów zapytań, aby wysokość tego drzewa była jak najmniejsza (wysokość odpowiada pesymistycznej liczbie zapytań).

Ponieważ mamy co najmniej \(7!\) liści i w każdym węźle dzielimy zbiór permutacji na 3 podzbiory, to drzewo będzie miało wysokość co najmniej \(\lceil \log_3 7! \rceil = 8\). Więc każdy deterministyczny algorytm będzie musiał zrobić co najmniej 8 ważeń.

Możemy napisać program komputerowy, który sprawdzi dla każdego możliwego pierwszego zapytania, na jakie zbiory permutacji dzieli ono zbiór wszystkich permutacji. Okaże się wtedy, że zawsze jeden z tych zbiorów będzie miał rozmiar co najmniej 2208. Z tego możemy wywnioskować, że po pierwszym zapytaniu konieczne jest jeszcze zadanie \(\lceil \log_3 2208 \rceil = 8\) zapytań, a więc wysokość drzewa musi być równa co najmniej \(9\).

Całkiem dobre rozwiązanie zachłanne

Intuicyjnie widać, że warto wykonywać takie zapytania, które dzielą aktualny podzbiór permutacji w węźle na mniej więcej trzy równe części. Nie jest to do końca możliwe (zwykle mało permutacji trafia do zbioru ,,waga w równowadze”), ale możemy próbować minimalizować rozmiar największej części.

Nie jest zupełnie oczywiste, że takie rozwiązanie jest dostatecznie dobre (równie dobrze dzieląc równomiernie możemy zostać z takimi podzbiorami, których nie będzie się dało dalej równomiernie dzielić), ale przetestowanie go w praktyce pozwala stwierdzić, że będzie ono potrzebować jedynie 10 ważeń.

Rozwiązanie wzorcowe

Aby znaleźć drzewo o wysokości 9, użyjemy przeszukiwania z nawrotami. Na początek algorytmowi dajemy zbiór \(7!\) permutacji i mówimy, że szukamy drzewa o wysokości 9. W korzeniu iterujemy się po wszystkich możliwych ruchach i dla każdego z synów rekurencyjnie szukamy drzewa o wysokości co najwyżej 8.

A ogólnie: jeśli jesteśmy w węźle, mamy podzbiór \(p\) permutacji i chcemy znaleźć drzewo o wysokości co najwyżej \(h\), to iterujemy się po możliwych ważeniach, dzielimy podzbiór permutacji na trzy części i dla każdej z nich szukamy drzewa o wysokości co najwyżej \(h-1\). Warto na początku sprawdzić, czy \(\lceil \log_3 p \rceil \leq h\), bo w przeciwnym wypadku od razu możemy stwierdzić, że drzewa nie da się zrobić.

Takiego baktraka optymalizujemy, implementując spamiętywanie oraz trzymając zbiory permutacji jako bitset<5040>.

Można również w ramach preprocessingu zapamiętać dla każdego ważenia, jaki podzbiór wszystkich permutacji trafia do każdej z trzech części (czyli wygenerować trzy bitsety). Podczas generowania ważeń w dowolnym węźle, wystarczy wykonać bitową operację and z bitsetem z węzła a bitsetami dla trzech części.

Można zatem wygenerować całe drzewo, a następnie wkleić je do programu. Mając takie wygenerowane drzewo, zadawanie pytań i reagowanie na odpowiedzi jest już bardzo proste.