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 lor $[t1 + k*T1 ... t2 + k*T1]$ să se intersecteze 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 $[t1 + k*T1 ... t2 + k*T1]$ ale primului să se intersecteze cu intervalele $[tt1 + p*T2 ... tt2 + p*T2]$ ale celui de-al doilea. 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> 0 </tex> | <tex> 1 </tex> | <tex> 1 </tex> | <tex> 0 </tex> |
| <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> | <tex> 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>.

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>...</tex>, <tex> A[0][M - 1] </tex> cu <tex> x_{1} </tex>, <tex> x_{2} </tex>, <tex>...</tex>, <tex> x_{M-1} </tex>, iar celulele <tex> A[1][0] </tex>, <tex> A[2][0] </tex>, <tex>...</tex>, <tex> A[N - 1][0] </tex> cu <tex> y_{1} </tex>, <tex> y_{2} </tex>, <tex>...</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_{N-1} </tex> | <tex> 0 </tex> | <tex> 1 </tex> | ... | <tex> 1 </tex> |

Acum, pentru fiecare celulă putem demonstra prin inducţie că <tex> A[i][j] = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>. Unde <tex> b[i][j] </tex> sunt nişte constante ce sunt calculate în funcţie de matricea primită la intrare.
Este uşor de observat că dacă:
<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>,

Acum, pentru fiecare celulă putem demonstra prin inducţie că <tex> A[i][j] = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>. Unde <tex> b[i][j] </tex> sunt nişte constante ce sunt calculate în funcţie de matricea primită la intrare. Este uşor de observat că dacă:
 
<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>.

<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>.