Jastrzębie

Ciężko uznać za fajne zadanie, którego rozwiązanie zaczyna się od parsowania wyrażenia boolowskiego. Proponuję na chwilę o tym jednak zapomnieć i dać szansę zadaniu Fox Hawks z tegorocznego finału Facebook Hacker Cup. Mimo smutnego kawałka na samym początku można w nim znaleźć całkiem elegancki i chyba niekoniecznie standardowy pomysł.

Na wejściu dostajemy wyrażenie boolowskie na n zmiennych (nazywanych po prostu 1,2,\ldots,n) oraz liczbę k. Istotne jest to, że każda zmienna pojawia się dokładnie raz w całym wyrażeniu! Celem jest wyznaczenie k-tego leksykograficznie rozwiązania, czyli przyporządkowania \text{\bf{false}} lub \text{\bf{true}} do każdej zmiennej tak, aby wyrażenie wyliczało się do \text{\bf{true}}. Dwa rozwiązania porównujemy leksykograficznie w standardowy sposób, czyli najpierw patrzymy na to, co przyporządkowują zmiennej n, potem zmiennej n-1, i tak dalej. Oryginalną treść, w której zamiast zmiennych pojawiają się jastrzębie i w związku z tym jest całkiem śmiesznie, można zobaczyć tutaj.

Wspomnijmy jeszcze o limitach: wiemy, że całe wyrażenie składa się z co najwyżej 2500000 znaków, n\leq 200 000 oraz k \leq 10^{18}. Czyli pewnie należy celować w rozwiązanie o złożoności \mathcal{O}(n\log n), być może jeszcze z jakimś dodatkowym logarytmem. Lub dużą stałą.

Zacznijmy od rozwiązania prawie-że-naiwnego. Na całkiem naiwne raczej nas nie stać, bo wszystkich przyporządkowań może być nawet 2^n. Jeśli jednak oznaczymy rozmiar wyrażenia przez m, dość łatwo jednak skonstruować algorytm, który działa w czasie \mathcal{O}(nm). Wyobraźmy sobie bowiem, że próbujemy ustalić co należy przyporządkować kolejnym zmiennym n,n-1,n-2,\ldots,1. Zaczynamy od przyporządkowania zmiennej n wartości \text{\bf{false}}. Teraz chcielibyśmy policzyć, na ile sposobów można przyporządkować wartości pozostałym zmiennym tak, aby wyrażenie wyliczyło się do \text{\bf{true}}. Nietrudno policzyć te sposoby przechodząc rekurencyjnie drzewo rozbioru wyrażenia (kluczowe jest tutaj, że każda zmienna pojawia się tam co najwyżej raz). Jeśli wynik to co najmniej k, przechodzimy do kolejnej zmiennej. Jeśli nie, zmniejszamy k o wynik, przypisujemy zmiennej n wartość true, no i też przechodzimy do kolejnej zmiennej. O całym algorytmie można myśleć jako o wyszukiwaniu binarnym wśród wszystkich 2^n ciągów binarnych opisujących możliwe rozwiązania. No i fajnie, ale trochę wolno.

Zanim zabierzemy się za skonstruowanie szybszego rozwiązania, wyjaśnijmy może to „drzewo rozbioru”. Chodzi o dość prostą rzecz: jeśli nasze wyrażenie to !((1 \& 2) \,\hat{}\, (3 | 4)) \& 5, chcemy skonstruować coś takiego:

jastrzebie1

Darujmy sobie może rozważania nad tym, jak takie drzewo skonstruować i załóżmy, że już je mamy. Od tego momentu będziemy utożsamiać wierzchołki drzewa rozbioru z reprezentowanymi przez nie wyrażeniami. W szczególności, będziemy mówić, że wierzchołek wylicza się do \text{\bf{true}} lub \text{\bf{false}}.

Spróbujmy dołożyć do powyższego rozwiązania dość prostą optymalizację. Po ustaleniu co należy przyporządkować kolejnej zmiennej, można spróbować usunąć ją z drzewa rozbioru odpowiednio propagując przypisaną wartość w górę. To znaczy, jeśli ustalamy wartość zmiennej x, to x | A można zastapić \text{\bf{true}} gdy x=\text{\bf{true}} lub A gdy x=\text{\bf{false}}. Podobne proste reguły można napisać dla x \& A, x \,\hat{}\, A oraz !x. Pomijając na razie kwestię tego, jak długo może zająć nam propagowanie zmian w górę drzewa, dostajemy gwarancję, że rozmiar aktualnego drzewa zależy od liczby zmiennych, którym nie przypisaliśmy jeszcze żadnej wartości…

Prawie. Faktycznie tak jest, o ile nasze drzewo to drzewo binarne, czyli każdy z jego wierzchołków wewnętrznych ma dokładnie dwoje dzieci. Wtedy wierzchołków wewnętrznych jest mniej niż liści, a liście do dokładnie jeszcze nieustalone zmienne. W drzewie mogą się jednak także pojawiać wierzchołki unarne (odpowiadające negacji), i co gorsze może się ich pojawiać dowolnie wiele. Wystarczy jednak zadbać o to, żeby !!A było zawsze zastępowane przez równoważne wyrażenie A, co gwarantuje, że tych unarnych wierzchołków jest nie więcej niż binarnych, a co za tym idzie całkowity rozmiar aktualnego drzewa jest mniejszy niż trzykrotność liczby jeszcze niezdeterminowanych wierzchołków.

No to sobie trochę zoptymalizowaliśmy, ale do rozwiązania jeszcze daleko. Pójdźmy więc krok dalej i zauważmy, że powyższą optymalizację można zastosować także patrząc na naiwne rozwiązanie od drugiej strony. Zmienna 1 aż do przedostatniej iteracji może być dowolnie ustalona, więc może dałoby się ją w podobny sposób wyeliminować z drzewa rozbioru?

Może, ale nie tak całkiem trywialnie jak wcześniej. Oprócz liści reprezentujących zmienne wprowadźmy sobie liście reprezentujące być może większe poddrzewa oryginalnego poddrzewa. Taki skompresowany liść przechowuje informację o liczbach różnych wartościowań zmiennych występujących w odpowiadającym mu poddrzewie, które sprawiają, że jego korzeń wylicza się do \text{\bf{true}} lub \text{\bf{false}}. Obydwie liczby mogą być dość spore, ale ponieważ finalnie i tak interesuje nas k-te wartościowanie, można „przyciąć” je do co najwyżej k. Intuicyjnie, skompresowane liście pozwalają nam powiedzieć, że dokładna wartość danej zmiennej x nie jest jeszcze istotna, bo najpierw i tak trzeba wybrać wartościowania zmiennych n,n-1,\ldots,x+1. Możemy więc zastąpić x przez skompresowany liść przechowujący (1,1). Podobnie jak wcześniej, możemy próbować propagować taką informację w górę. Na przykład !(t,f) można przepisać do (f,t). Podobnie, (t_1,f_1) \& (t_2,f_2) można przepisać do (t_1\cdot t_2,t_1\cdot f_2+f_1\cdot t_2+f_1\cdot f_2) (analogiczne proste formułki można napisać dla pozostałych operacji). Czyli możemy uprościć drzewo, gdy tylko wszystkie dzieci jakiegoś wierzchołka wewnętrznego są skompresowanymi liśćmi. Ale czy gwarantuje to, że rozmiar aktualnego drzewa jest proporcjonalny do liczby „prawdziwych” liści?

No nie, bo niby dlaczego. Możemy przecież mieć długą ścieżkę, która wygląda jakoś tak:

jastrzebie2

Cały pomysł ze skompresowanymi liścmi wydaje się w tym momencie raczej bezużyteczny. Spróbujmy go więc trochę podkręcić. Niech (t,f) oznacza liczbę wartościowań wyliczoną dla ostatniego wierzchołka na ścieżce z powyższego przykładu. Nietrudno uwierzyć (lub udowodnić przez indukcję), że jeśli (t',f') oznacza liczbę wartościowań wyliczoną dla pierwszego wierzchołka na ścieżce, to t'=\alpha\cdot t+\beta\cdot f oraz f'=\gamma\cdot t+\delta\cdot f, gdzie współczynniki \alpha,\beta,\gamma,\delta zależą tylko od operacji na ścieżce i liczb przechowywanych w skompresowanych liściach zwisających ze ścieżki. Czyli tak naprawdę zamiast przechowywać całą długą ścieżkę wystarczy zapamiętać współczynniki \alpha,\beta,\gamma,\delta!

Bardziej ogólnie, każdy wierzchołek wewnętrzny v przechowuje cztery współczynniki \alpha,\beta,\gamma,\delta. Liczba wartościowań, dla których wierzchołek odpowiadający v w oryginalnym drzewie wylicza się do \text{\bf{true}} lub \text{\bf{false}} to odpowiednio \alpha\cdot t+\beta\cdot f oraz \gamma\cdot t+\delta\cdot f, gdzie t i f to liczba wartościowań, dla których v wylicza się do, odpowiednio, \text{\bf{true}} i \text{\bf{false}}. Wyznaczając t i f bierzemy pod uwagę typ v, czyli odpowiadającą mu operację, oraz (wyliczone rekurencyjnie) liczby wartościowań, dla których wierzchołki odpowiadające jego dzieciom w oryginalnym drzewie wyliczają się do \text{\bf{true}} i \text{\bf{false}}. OK, ale czy taka modyfikacja rzeczywiście pozwala nam zagwarantować, że rozmiar aktualnego drzewa nie jest istotnie większy niż liczba „prawdziwych” liści?

Tak! Zauważmy bowiem, że w tym momencie tak naprawdę możemy pozbyć się wszystkich skompresowanych liści (czyli pomysł faktycznie był bezużyteczny, ale skąd było wiedzieć). Jeśli bowiem mamy w drzewie wierzchołek v, którego jedno (sytacja jest symetryczna, powiedzmy, więc że lewe) dziecko jest skompresowanym liściem, a drugie wierzchołkiem wewnętrznym v', można zmodyfikować współczynniki przechowywane w v' i podpiąć je zamiast v (a skompresowany liść i wierzchołek v zutylizować). Aby się o tym przekonać, pomyślmy o sytuacji, w której v odpowiada operacji \&. Niech t i f będą liczba wartościowań, dla których lewe dziecko v wylicza się do \text{\bf{true}} i \text{\bf{false}}, \alpha,\beta,\gamma,\delta współczynnikami przechowywanymi w v, a \alpha',\beta',\gamma',\delta' współczynnikami przechowywanymi w v'. Dodatkowo niech x oraz y będą zmiennymi oznaczającymi liczbę wartościowań, dla których v' wylicza się do \text{\bf{true}} i \text{\bf{false}} (v', a nie odpowiadający mu wierzchołek w oryginalnym drzewie, czyli nie uwzględniając jeszcze współczynników \alpha',\beta',\gamma',\delta'!). Wtedy liczba wartościowań, dla których v wylicza się do \text{\bf{true}} i \text{\bf{false}} to t\cdot (\alpha'\cdot x+\beta'\cdot y) oraz t\cdot(\gamma'\cdot x+\delta'\cdot y)+f\cdot((\alpha'+\gamma')\cdot x+(\beta'+\delta')\cdot y). Teraz trzeba jeszcze uwględnić współczynniki \alpha,\beta,\gamma,\delta, co tak naprawdę oznacza przemnożenie dwóch macierzy 2\times 2. Darujemy sobie rozpisywanie wyniku.

Podobne przekształcenia można wykonać dla pozostałych operacji. Podsumujmy: jesteśmy ustalić na sztywno wartościowania niektórych zmiennych oraz stwierdzić, że niektóre zmienne mogą być dowolnie zwartościowane, a następnie przepisać drzewo rozbioru wyrażenia tak, aby otrzymać równoważne drzewo, w którym wszystkie liście odpowiadają pozostałym zmiennym (to jest tym nieustalonym i niedowolnym). Być może warto doprecyzować, co dokładnie oznacza tutaj równoważność: jeśli ustalimy wartościowania niektórych z pozostałych zmiennych w obydwu drzewach (tym oryginalnym i tym równoważnym) i policzymy wartościowania, dla których korzenie obydwu drzew wyliczają się do \text{\bf{true}} i \text{\bf{false}}, to otrzymamy takie same wyniki (musimy jednak pamiętać, aby podczas tego wyliczania uwzględniać współczynniki \alpha,\beta,\gamma,\delta, które mogą pojawiać się w obydwu drzewach). Ale właściwie co z tego?

To, że jesteśmy już o krok od skonstruowania docelowego rozwiązania. Podzielmy bowiem wszystkie zmienne na dwie grupy n,n-1,\ldots,\lfloor\frac{n}{2}\rfloor oraz \lfloor\frac{n}{2}\rfloor-1,\lfloor\frac{n}{2}\rfloor-2,\ldots,1. Dopóki nie ustalimy wartości wszystkich zmiennych w pierwszej grupie, nie interesuje nas dokładne wartościowanie zmiennych w tej drugiej. Podobnie, podczas ustalania wartości zmiennych w drugiej grupie wartości zmiennych w tej pierwszej są już wybrane. Możemy więc najpierw przepisać drzewo zakładając, że zmienne w drugiej grupie mogą być dowolnie zwartościowane i uruchomić się na nim rekurencyjnie. Następnie jeszcze raz przepisać drzewo wybierając na sztywno wartościowania zmiennych w pierwszej grupie i znów uruchomić się rekurencyjnie.

I niby fajnie, ale co to właściwie znaczy uruchomić się rekurencyjnie? Przecież mniejsze podproblemy są trochę innej postaci niż ten oryginalny. Trzeba więc trochę doprecyzować: każde wywołanie dostaje liczbę k oraz drzewo rozbioru, które jest równoważne pierwotnemu drzewu z ustalonymi wartościami zmiennych n,n-1,\ldots,i+1 oraz dowolnymi wartościami zmiennych j-1,j-2,\ldots,n a zwraca wartościowanie zmiennych i,i-1,i-2,\ldots,j oraz liczbę k'\leq k o takiej własności, że po dodaniu do k' liczby wartościowań drzewa przy wyliczonym wartościowaniu przekracza k. Mówiąc mniej formalnie, takie wywołanie symuluje fragment wykonania naiwnego algorytmu na spójnym zakresie zmiennych i mówi nam, jak bardzo zmniejszyło się k podczas tego wykonania.

To już właściwie całe rozwiązanie. Całkowity czas działania jest bowiem opisany rekurencją T(n)=\mathcal{O}(n)+2T(\frac{n}{2}): rozmiar aktualnego drzewa jest zawsze proporcjonalny do liczby „aktywnych” zmiennych, a ta spada dwukrotnie w kolejnych wywołaniach. Dodatkowo, przepisanie drzewa w zasadzie sprowadza się do jednego przejścia do z dołu do góry, czyli wymaga tylko czasu liniowego. Cały algorytm działa więc w czasie \mathcal{O}(n\log n).

Reklamy

4 myśli nt. „Jastrzębie

  1. Czytam zdanie „Liczba wartościowań, dla których wierzchołek odpowiadający v w oryginalnym drzewie wylicza się do \text{\bf{true}} lub \text{\bf{false}} to odpowiednio \alpha\cdot t+\beta\cdot f oraz \gamma\cdot t+\delta\cdot f, gdzie t i f to liczba wartościowań, dla których v wylicza się do, odpowiednio, \text{\bf{true}} i \text{\bf{false}}.” już 3 raz i nadal nie rozumiem. Może pomogłaby mi ilustracja z tą transformacją (przyznam się, że zgubiłem się tak naprawdę akapit wcześniej i liczyłem na to, że się odnajdę, ale nie …)

  2. ok, chyba zakumałem. Za to zgubiłem się w innym miejscu. Mianowicie w tym którym mówisz, że zmienne można podzielić na trzy grupki: ustalone, obojętne i te trzecie. Jak dla mnie tych trzecich nie ma – albo zmienna jest już ustalona, albo może być dowolna. Zdaje się, że ta trzecia grupa bieże się z jakiegoś „lenistwa” tj. niechęci do gorliwego przepisywania drzewa za każdym razem gdy ustalimy jakąś zmienną. Zgadłem? Tj. jest to tylko kwestia optymalizacji a nie natury problemu?

    • Tak. Być może „obojętne” jest trochę złą nazwą. Tak naprawdę są to „zmienne, których wartości w k-tym wartościowaniu aktualnego drzewa nie będziemy dokładnie ustalać” (bo ustalimy je w innym wywołaniu rekurencyjnym).

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s