MOKIP 07.01.2013

W skrócie: potrafimy sprawdzić w czasie linowym, czy zdanie typu $(x_1 \vee x_2) \wedge (x_2 \vee \neg x_3) \wedge (x_4 \vee \neg x_5) \wedge (\neg x_1 \vee x_2)$
zachodzi dla pewnego wartościowania zmiennych logicznych $x_1, x_2, x_3, x_4, x_5$. Ważne: w każdej alternatywie występują dokładnie dwie zmienne.

  • Elegancki kod na liczenie 2-SAT Marka Cygana spisany z wykładu Algorytmiki praktycznej. Kod jest tutaj (zawiera też rozwiązanie spokojnej komisji).
  • Zadania:
  1. Spokojna komisja z VIII OI
  2. Kindergarten z NCPC 2012, kod (jednak treść była trochę inna, niż mówiłem).
  3. Colourful rectangles z Top Codera. Niestety tutaj też przedstawiłem inną treść:) Ale morał wciąż ten sam — 2-SAT często łączy się z wyszukiwaniem binarnym. (Kod)
  4. Zadanie z jakiegoś obozu (domowe, żeby było o czym pomyśleć na II etapie), poniżej

Dany jest ciąg $k$ informacji $s_{i_1, j_1} = x_1, s_{i_2, j_2} = x_2, ... , s_{i_k, j_k} = x_k, i_a \leq j_a, x_a \in \{0, 1\} \mbox{ dla każdego } a$,
który opisuje pewien ciąg $n$ bitów $b_1, \ldots, b_n$ (już nie dany), $n \leq 10^9, k \leq 10^5$.

(1)
\begin{align} s_{i,j} = x \mbox{ oznacza, że } b_i + b_{i+1} + \ldots + b_j \equiv x (\mbox{ mod } 2), x \in\{0, 1\}, i \leq j \end{align}

Być może niektóre informacje są sprzeczne. Chcemy wyznaczyć największe takie $t$, że istnieje ciąg $(b_n)$ spełniający wszystkie $t$ pierwszych warunków.

Przykład:
Dla $n = 4$, $s_{1,4} =0, s_{2,3} =1, s_{4,4} = 1, s_{1,1} = 1$ poprawnym wynikiem jest 3, bo ciąg $(0, 1, 0, 1)$ spełnia 3 pierwsze warunki, ale żaden ciąg nie spełnia wszystkich czterech.

Wskazówka do zadania domowego — jako zmienną logiczną $v_i$ przyjmijmy sumę bitów $b_1 + b_2 + \ldots + b_i \mbox{ mod } 2$.
Następnie dodajemy odpowiednie klauzule dla każdej informacji $s_{x,y}$.

  1. dla $s_{x,y} = 1$ dodajemy klauzulę $v_x \not= v_{y+1} \equiv \left( (v_x \vee v_{y+1}) \wedge (\neg v_x \vee \neg v_{y+1}) \right)$
  2. dla $s_{x,y} = 0$ dodajemy klauzulę $v_x = v_{y+1} \equiv \left( (v_x \vee \neg v_{y+1}) \wedge (\neg v_x \vee v_{y+1}) \right)$

Wprawdzie wszystkich możliwych $v_i$ może być bardzo dużo ($10^9$), ale nas interesują tylko sumy kończące się na krańcach przedziałów
$s_{x,y}$, tych jest najwyżej $2 \cdot 10^5$.