** {'Peace Commission (Polish Olympiad in Informatics, 2001)':2-sat#peace-commission}
** {'Excursion (Baltic Olympiad in Informatics, 2001)':2-sat#excursion}
** {'Orpath (Olimpiadă Rusia)':2-sat#orpath}

** {'Aladdin (Bursele Agora 2005/2006, Runda 1)':2-sat#aladdin}

h2(#introducere). Introducere

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

Într-o ţară pacifistă, există $N$ oraşe şi $K$ autobuze $(1 <= N, K <= 100)$. La orele aglomerate ale zilei, nu trebuie să existe două autobuze care merg în acelaşi timp în sensuri opuse. Traseul fiecărui autobuz este un ciclu. Spunem că el merge în sens pozitiv dacă va parcurge oraşele în ordinea $1 2 3 4 1 2 3 4 1 2$ ... sau în sens negativ dacă le parcurge în ordinea $1 4 3 2 1 4 3 2 1 4$ ... Găsiţi o posibilitate de atribuire a sensului fiecărui autobuz astfel ca accidentele de trafic să fie evitate (nu vor exista două autobuze care să se întâlnească şi să aibă sensuri de mers opuse). Pentru fiecare autobuz se vor şti oraşele de pe ruta lui, şi pentru fiecare două oraşe vecine pe rută se va şti timpul necesar autobuzului pentru a ajunge dintr-un oraş în altul. De exemplu, pentru $4$ oraşe unde oricare două sunt la timp de mers egal cu $10$, şi pentru două autobuze cu rutele $1 2 4$ şi $3 4 2$, o soluţie ar fi ca primul autobuz să meargă în sens pozitiv iar celălalt în sens negativ.

bq. Într-o ţară pacifistă, există $N$ oraşe şi $K$ autobuze $(1 <= N, K <= 100)$. La orele aglomerate ale zilei, nu trebuie să existe două autobuze care merg în acelaşi timp în sensuri opuse. Traseul fiecărui autobuz este un ciclu. Spunem că el merge în sens pozitiv dacă va parcurge oraşele în ordinea $1 2 3 4 1 2 3 4 1 2$ ... sau în sens negativ dacă le parcurge în ordinea $1 4 3 2 1 4 3 2 1 4$ ... Găsiţi o posibilitate de atribuire a sensului fiecărui autobuz astfel ca accidentele de trafic să fie evitate (nu vor exista două autobuze care să se întâlnească şi să aibă sensuri de mers opuse). Pentru fiecare autobuz se vor şti oraşele de pe ruta lui, şi pentru fiecare două oraşe vecine pe rută se va şti timpul necesar autobuzului pentru a ajunge dintr-un oraş în altul. De exemplu, pentru $4$ oraşe unde oricare două sunt la timp de mers egal cu $10$, şi pentru două autobuze cu rutele $1 2 4$ şi $3 4 2$, o soluţie ar fi ca primul autobuz să meargă în sens pozitiv iar celălalt în sens negativ.

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.

h2(#aladdin). 'Aladdin':problema/aladdin (Bursele Agora 2005/2006, Runda 1)
 
bq. Aladdin, aşa cum ştiaţi, este un mare magnat în afacerea de comercializare a covoarelor magice. Acesta doreşte să o cucerească pe prinţesa Iasmina, iar aceasta, pentru a-i testa inteligenţa îl roagă să îi facă un covor dreptunghiular împărţit în pătrăţele, asemănator unei table de şah cu $N$ linii şi $M$ coloane $(1 <= N, M <= 1000)$. Fiecare pătrăţel de pe covor trebuie colorat cu alb sau cu negru. Pentru fiecare pătrat care conţine $4$ pătrăţele Iasmina pune condiţia să aibă un număr fixat de pătrăţele colorate cu negru. Ajutaţi-l pe Aladdin să realizeze un covor care satisface condiţiile impuse de prinţesa Iasmina!
 
h3. Soluţie
 
Întâi, să considerăm un exemplu. Pentru o cerinţă de forma:
<tex> 3 \ 2 \ 3 </tex>
<tex> 2 \ 3 \ 3 </tex>
<tex> 1 \ 2 \ 1 </tex>
 
una din soluţii este:
<tex> 1 \ 1 \ 0 \ 1 </tex>
<tex> 1 \ 0 \ 1 \ 1 </tex>
<tex> 0 \ 1 \ 1 \ 0 </tex>
<tex> 0 \ 0 \ 0 \ 0 </tex>
 
Fie <tex> A </tex> o matrice soluţie a problemei noastre. Vom numerota rândurile matricii de la $0$ la $N - 1$ şi coloanele de la $0$ la $M - 1$. Matricea de intrare <tex> S </tex> reprezintă de fapt sumele din fiecare pătrat de câte $2 x 2$ elemente. Facem observaţia că dacă ştim într-un pătrat de $2 x 2$ valorile pentru trei dintre celule, atunci valoarea din a patra celulă este unic determinată pentru că ştim suma elementelor din pătrat. Vedem astfel, că dacă ştim valorile elementelor din prima linie a matricii <tex> A </tex> şi din prima coloană, restul valorilor sunt unic determinate.
Pentru a rezolva problema vom presupune <tex> A[0][0] </tex> cunoscut (de fapt, mai întâi vom rezolva problema presupunând că <tex> A[0][0] = 1 </tex>, iar dacă nu obţinem nicio soluţie vom încerca cu <tex> A[0][0] = 0 </tex>). Vom nota celulele <tex> A[0][1] </tex>, <tex> A[0][2]</tex>, … <tex> A[0][M - 1] </tex> cu <tex> x_{1} </tex>, <tex> x_{2} </tex>, … <tex> x_{M-1} </tex> iar celulele <tex> A[1][0] </tex>, <tex> A[2][0] </tex>, … <tex> A[N - 1][0] </tex> cu <tex> y_{1} </tex>, <tex> y_{2} </tex>, … <tex> y_{N-1} </tex>.
 
table{width: 90px; text-align: center}. | <tex> A[0][0] </tex> | <tex> x_{1} </tex> | <tex> x_{2} </tex> | <tex> ... </tex> | <tex> x_{M-1} </tex>|
| <tex> y_{1} </tex> | <tex> 1 </tex> | <tex> 1 </tex> | ... | <tex> 1 </tex> |
| <tex> y_{2} </tex> | <tex> 0 </tex> | <tex> 1 </tex> | ... | <tex> 0 </tex> |
| ... | ... | ... | ... | ... |
| <tex> y_{N-1} </tex> | <tex> 0 </tex> | <tex> 1 </tex> | ... | <tex> 1 </tex> |