Această problemă este inspirită din o problemă de la $CEOI 2002$ şi este evident că ne cere să determinăm o atribuire satisfiabilă pentru o formulă logică formată ca conjuncţie între cerinţele care se transformă astfel:

* cerinţa de tip $0$ corespunde propoziţiei <tex> x \vee y </tex>;
* cerinţa de tip $1$ corespunde propoziţiei <tex> x \vee \sim y </tex>;
* cerinţa de tip $2$ corespunde propoziţiei <tex> \sim x \vee y </tex>;
* cerinţa de tip $3$ corespunde propoziţiei <tex> \sim x \vee \sim y </tex>.

* cerinţa de tip 0 corespunde propoziţiei <tex> x \vee y </tex>;
* cerinţa de tip 1 corespunde propoziţiei <tex> x \vee \sim y </tex>;
* cerinţa de tip 2 corespunde propoziţiei <tex> \sim x \vee y </tex>;
* cerinţa de tip 3 corespunde propoziţiei <tex> \sim x \vee \sim y </tex>.

Una din primele două rezolvări ar fi putut soluţiona această problemă, dar problema de la $CEOI$ avea limite mai mari şi pentru rezolvarea ei ar fi trebuit un algoritm de complexitate $O(N + M)$.

h3. Soluţie
Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>.

Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.

Transformăm această problemă într-o instanţă de $2-SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.

Această soluţie este liniară ca şi complexitate în numărul de elemente citite la intrare.
h2(#peace-commission). Peace Commission (Polish Olympiad in Informatics, 2001)

bq. Comisia Publică a Păcii trebuie să fie compusă în parlamentul Republicii Democrate a ţării Byteland după regulile impuse de Legea Foarte Importantă. Din păcate unul dintre obstacole este acela că unii deputaţi nu se înţeleg cu ceilalţi. Comisia trebuie realizată astfel ca următoarele condiţii să fie îndeplinite: fiecare partid trebuie să aibă exact un reprezentant în comisie; dacă doi deputaţi nu se înţeleg, ei nu pot fi ambii membrii ai comisiei. Fiecare partid are exact doi deputaţi în parlament. Toţi număraţi de la $1$ până la $2n (1 <= n <= 8000)$. Deputaţii cu numerele $2i-1$ şi $2i$ aparţin celui de al $i$-lea partid. Se vor da $m (0 <= m <= 20 000)$ perechi de deputaţi <tex> (a, b) </tex> care nu se înţeleg. Se cere realizarea unei comisii dacă acest lucru este posibil. Un exemplu ar fi pentru trei partide şi perechile <tex> (1, 3) </tex> şi <tex> (2, 4) </tex> care nu se înţeleg comisia alcătuită din membrii <tex> \{1, 4, 5\} </tex>.

bq. Comisia Publică a Păcii trebuie să fie compusă în parlamentul Republicii Democrate a ţării Byteland după regulile impuse de Legea Foarte Importantă. Din păcate, unul dintre obstacole este acela că unii deputaţi nu se înţeleg cu ceilalţi. Comisia trebuie realizată astfel ca următoarele condiţii să fie îndeplinite: fiecare partid trebuie să aibă exact un reprezentant în comisie; dacă doi deputaţi nu se înţeleg, ei nu pot fi ambii membrii ai comisiei. Fiecare partid are exact doi deputaţi în parlament. Toţi număraţi de la $1$ până la $2n (1 <= n <= 8000)$. Deputaţii cu numerele $2i-1$ şi $2i$ aparţin celui de al $i$-lea partid. Se vor da $m (0 <= m <= 20 000)$ perechi de deputaţi <tex> (a, b) </tex> care nu se înţeleg. Se cere realizarea unei comisii dacă acest lucru este posibil. Un exemplu ar fi pentru trei partide şi perechile <tex> (1, 3) </tex> şi <tex> (2, 4) </tex> care nu se înţeleg comisia alcătuită din membrii <tex> \{1, 4, 5\} </tex>.

h3. Soluţie
Fiecărui partid îi vom asocia o variabilă; variabila va lua valoarea <tex> 1 </tex> dacă membrul $2i - 1$ al partidului va aparţine comisiei şi valoarea <tex> 0 </tex> dacă membrul $2i$ va aparţine comisiei. Pentru ca din partidul $x$ să existe exact un membru în expresie introducem  <tex> A_{x} \wedge \sim A_{x} </tex>.
Putem exprima că doi membrii ai parlamentului $(2i, 2j)$ nu se înţeleg prin expresia logică <tex> \sim A_{i} \vee \sim A_{j} </tex>. Astfel nu pot ambele variabile <tex> A_{i} </tex> şi <tex> A_{j} </tex> să aibă în acelaşi timp valoarea <tex> 1 </tex> adică $2i$ şi $2j$ nu pot face parte în acelaşi timp din comisie. Dacă cei doi membrii sunt $(2i - 1, 2j - 1)$ atunci îi putem codifica prin expresia <tex> A_{i} \vee A_{j} </tex> astfel <tex> A_{i} </tex> şi <tex> A_{j} </tex> nu pot avea în acelaşi timp valoarea <tex> 0 </tex>, iar dacă membrii sunt $(2i , 2j - 1)$ se poate scrie ca <tex> \sim A_{i} \vee A_{j} </tex> astfel <tex> A_{i} </tex> nu poate avea valoarea <tex> 1 </tex> când <tex> A_{j} </tex> are valoarea <tex> 0 </tex>.

Exemplu din problemă poate fi scris ca expresia logică în modul următor: <tex> A_{1} \wedge \sim A_{1} \wedge A_{2} \wedge \sim A_{2} \wedge A_{3} \wedge \sim A_{3} \wedge (A_{1} \vee A_{2}) \wedge (\sim A_{1} \vee \sim A_{2}) </tex>.
Din nou vom putea folosi cel de al treilea algoritm explicat pentru a obţine o rezolvare de complexitate $O(N + M)$.

Exemplul din problemă poate fi scris ca expresia logică în modul următor: <tex> A_{1} \wedge \sim A_{1} \wedge A_{2} \wedge \sim A_{2} \wedge A_{3} \wedge \sim A_{3} \wedge (A_{1} \vee A_{2}) \wedge (\sim A_{1} \vee \sim A_{2}) </tex>.
Din nou vom putea folosi cel de al 'patrulea algoritm':#solutie4 explicat pentru a obţine o rezolvare de complexitate $O(N + M)$.

h2(#excursion). Excursion (Baltic Olympiad in Informatics, 2001)

h3. Soluţie

Este evident că şi această problemă se poate uşor transforma într-o instanţă de $2SAT$. Fiecare turist ne dă prin dorinţele sale o expresie literală cu doi literali. Vizitarea sau nevizitarea oraşului de index $i$ va fi reprezentată prin variabila booleană <tex> A_{i} </tex>.  Exemplul din problemă poate fi transformat astfel: <tex> (A_{1} \vee \sim A_{2}) \wedge (A_{2} \vee A_{4}) \wedge (A_{3} \vee A_{1}) </tex>.

Este evident că şi această problemă se poate uşor transforma într-o instanţă de $2-SAT$. Fiecare turist ne dă prin dorinţele sale o expresie literală cu doi literali. Vizitarea sau nevizitarea oraşului de index $i$ va fi reprezentată prin variabila booleană <tex> A_{i} </tex>.  Exemplul din problemă poate fi transformat astfel: <tex> (A_{1} \vee \sim A_{2}) \wedge (A_{2} \vee A_{4}) \wedge (A_{3} \vee A_{1}) </tex>.

h2(#orpath). Orpath (Olimpiadă Rusia)

h3. Soluţie

Pentru orice două autobuze vom găsi care sunt sensurile de mers pentru ele astfel ca cele două autobuze să nu se întâlnească şi să provoace un accident. Pentru un sens fixat putem afla pentru un autobuz pe ce interval de timp va fi pe o anumită stradă. El va fi în general pe o stradă $(i, j)$ pe un interval de tipul $[t1 + k*T … t2 + k*T]$ unde $t1$ este timpul din prima rută parcursă pentru a ajunge la $i$, $t2$ timpul pentru a ajunge la $j$ iar $T$ este durata totală a unei rute. Acum, pentru a determina dacă două autobuze se vor întâlni pe o rută $(i, j)$ trebuie ca ele să se deplaseze în sensuri opuse pe această rută, iar intervalele lot $[t1 + k*T1 .. t2 + k*T1]$ se intersectează cu intervalele $[tt1 + p*T2 … tt2 + p*T2]$. Este clar acum că putem transforma problema într-o instanţă de $2-SAT$ prin maparea autobuzelor în variabile logice, a sensurilor de mers în valorile $adevărat$ şi $fals$, iar pentru orice pereche de autobuze să fie o propoziţie logică ce ia valoarea adevărat doar dacă sensurile de mers determinate de variabilele logice asociate autobuzelor sunt compatibile. Mai trebuie determinat într-un mod eficient dacă două clase de intervale de timp se intersectează. Aceasta rămâne ca temă cititorului.

Pentru orice două autobuze vom găsi care sunt sensurile de mers pentru ele astfel ca cele două autobuze să nu se întâlnească şi să provoace un accident. Pentru un sens fixat putem afla pentru un autobuz pe ce interval de timp va fi pe o anumită stradă. El va fi în general pe o stradă $(i, j)$ pe un interval de tipul $[t1 + k*T … t2 + k*T]$ unde $t1$ este timpul din prima rută parcursă pentru a ajunge la $i$, $t2$ timpul pentru a ajunge la $j$ iar $T$ este durata totală a unei rute. Acum, pentru a determina dacă două autobuze se vor întâlni pe o rută $(i, j)$ trebuie ca ele să se deplaseze în sensuri opuse pe această rută, iar intervalele lor $[t1 + k*T1 .. t2 + k*T1]$ se intersectează cu intervalele $[tt1 + p*T2 … tt2 + p*T2]$. Este clar acum că putem transforma problema într-o instanţă de $2-SAT$ prin maparea autobuzelor în variabile logice, a sensurilor de mers în valorile $adevărat$ şi $fals$, iar pentru orice pereche de autobuze să fie o propoziţie logică ce ia valoarea $adevărat$ doar dacă sensurile de mers determinate de variabilele logice asociate autobuzelor sunt compatibile. Mai trebuie determinat într-un mod eficient dacă două clase de intervale de timp se intersectează. Aceasta rămâne ca temă cititorului.

h2(#aladdin). 'Aladdin':problema/aladdin (Bursele Agora 2005/2006, Runda 1)

<tex> A[i-1][j] = (-1)^{(i-1)} x_{j} + (-1)^j y_{i-1} + b[i-1][j] </tex>,
<tex> A[i-1][j-1] = (-1)^{(i-1)} x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i-1][j-1] </tex>,
<tex> A[i][j-1] = (-1)^i x_{j-1} + (-1)^{(j-1)} y_{i} + b[i][j-1] </tex>,

atunci:

<tex> A[i][j] = S[i-1][j-1] - A[i-1][j] - A[i][j-1] - A[i-1][j-1] = </tex>
<tex> = S[i-1][j-1] - ((-1)^{(i-1)} x_{j} + (-1)^j y_{i-1} + b[i-1][j]) - </tex> <tex> ((-1)^{(i-1)} x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i-1][j-1]) - ((-1)^i x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i][j-1]) = </tex>
<tex> = (-1)^i x_{j} - (-1)^j y_{i-1} + (-1)^i x_{j-1} + (-1)^j y_{i-1} - </tex> <tex> (-1)^i x_{j-1} + (-1)^j y_{i} + S[i-1][j-1] - b[i-1][j] - b[i][j-1] - b[i-1][j-1] = </tex>
<tex> = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>.

De aici concluzionăm că <tex> b[i][j] = S[i-1][j-1] - b[i-1][j] - b[i][j-1] - b[i-1][j-1] \ (*)</tex>.
Avem un sistem format din inecuaţiile:
<tex> 0 \le x_{j} \le 1 </tex>
<tex> 0 \le y_{i} \le 1 </tex>

<tex> -b[i][j] \le (-1)^i xj + (-1)^j yi \le 1 - b[i][j] </tex>

<tex> -b[i][j] \le (-1)^i x_{j} + (-1)^j y_{i} \le 1 - b[i][j] </tex>

Este uşor acum să transformăm acest sistem într-o formulă booleană în {'formă normal conjunctivă':2-sat#forme-normale} în care fiecare expresie are cel mult $2$ literali. Fiecare relaţie o putem înmulţi sau nu cu $-1$ astfel ca părţile constante ale relaţiei să fie pozitive. Observăm că <tex> | b[i][j] | \le 2 </tex> altfel nu avem soluţie. Dacă <tex> | b[i][j] | = 2 </tex> atunci ambele variabile au valori fixe, iar dacă <tex> | b[i][j] | = 1 </tex> sau <tex> | b[i][j] | = 0 </tex> atunci relaţia o putem scrie ca o disjuncţie logică cu doi literali.

Este uşor acum să transformăm acest sistem într-o formulă booleană în {'formă normal conjunctivă':2-sat#forme-normale} în care fiecare expresie are cel mult $2$ literali. Fiecare relaţie o putem înmulţi sau nu cu $-1$ astfel ca părţile constante ale relaţiei să fie pozitive. Observăm că <tex> | b[i][j] | \le 2 </tex>, altfel nu avem soluţie. Dacă <tex> | b[i][j] | = 2 </tex> atunci ambele variabile au valori fixe, iar dacă <tex> | b[i][j] | = 1 </tex> sau <tex> | b[i][j] | = 0 </tex> atunci relaţia o putem scrie ca o disjuncţie logică cu doi literali.

O relaţie precum <tex> 0 \le x + y \le 1 </tex> poate fi tansformată logic în <tex> \sim x \vee \sim y </tex>, astfel <tex> x </tex> şi <tex> y </tex> nu vor fi în acelaşi timp <tex> 1 </tex>, una de genul <tex> 1 \le x + y \le 2 </tex> va fi transformată în <tex> (x \vee y) </tex>, astfel cel puţin <tex> x </tex> sau <tex> y </tex> va fi egal cu <tex> 1 </tex>, alta de tipul <tex> 0 \le x - y \le 1 </tex> poate fi scrisă ca <tex> x \vee \sim y </tex>, una de tipul <tex> 2 \le x + y \le 3 </tex> în <tex> x \wedge y </tex>, iar una de tipul <tex> 0 \le -x -y \le 1 </tex> în <tex> \sim x \wedge \sim y </tex>, una de tipul <tex> 1 \le x - y  \le 2 </tex> în <tex> x \wedge \sim y </tex>.