== include(page="template/taskheader" task_id="2sat") ==

Problema satisfiabilităţii, notată prescurtat cu '$SAT$':http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Basic_definitions.2C_terminology_and_applications cere determinarea existenţei unei atribuiri satisfiabile pentru o formulă booleană. O atribuire de valori booleene pentru variabilele acestei expresii se numeşte $atribuire satisfiabilă$ dacă evaluarea expresiei după atribuirea valorilor are ca rezultat valoarea de adevăr $adevărat$.

Problema satisfiabilităţii, notată prescurtat cu '$SAT$':http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT cere determinarea existenţei unei atribuiri satisfiabile pentru o formulă booleană. O atribuire de valori booleene pentru variabilele acestei expresii se numeşte $atribuire satisfiabilă$ dacă evaluarea expresiei după atribuirea valorilor are ca rezultat valoarea de adevăr $adevărat$.

Următoarea formulă: <tex> \phi = ((x_{1} \rightarrow x_{2}) \vee \sim((\sim x_{1} \leftrightarrow x_{3}) \vee x_{4})) \wedge \sim x_{2} </tex>, are o atribuire satisfiabilă dată de: <tex> \langle x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1 \rangle </tex>.

Un exemplu de formulă ar fi: <tex> \phi = ((x_{1} \rightarrow x_{2}) \vee \sim((\sim x_{1} \leftrightarrow x_{3}) \vee x_{4})) \wedge \sim x_{2} </tex>, aceasta având o atribuire satisfiabilă <tex> \langle x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1 \rangle </tex>.

Orice formulă booleană poate fi transformată în două forme:

* în '$forma normal conjunctivă$':http://en.wikipedia.org/wiki/Conjunctive_normal_form expresia este scrisă ca o _conjuncţie_ de propoziţii, iar fiecare propoziţie este o _disjuncţie_ de literali;

* în '$forma normal conjunctivă$':http://en.wikipedia.org/wiki/Conjunctive_normal_form expresia este scrisă ca o conjuncţie de propoziţii, iar fiecare propoziţie este o disjuncţie de literali;

* în '$forma normal disjunctivă$':http://en.wikipedia.org/wiki/Disjunctive_normal_form expresia este scrisă ca o _disjuncţie_ de propoziţii în interiorul cărora există doar _conjuncţii_ de literali;

* în '$forma normal disjunctivă$':http://en.wikipedia.org/wiki/Disjunctive_normal_form expresia este scrisă ca o disjuncţie de propoziţii în interiorul cărora există doar conjuncţii de literali;

În rezolvarea acestei probleme ne interesează doar forma normal conjunctivă. Problema $SAT$ pe cazul general este '$NP-completă$':http://en.wikipedia.org/wiki/NP-complete, chiar şi dacă restricţionăm expresiile la unele care în forma normal conjunctivă au doar _trei_ literali în fiecare dintre propoziţii. Problema satisfiabilităţii pentru asemenea expresii se numeşte '$3SAT$':http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability.

h2. Cerinţă

Dându-se o expresie $2SAT$ să se determine o atribuire satisfiabilă a acesteia.

Dandu-se o expresie $2SAT$ sa se determine o atribuire satisfiabila a acesteia.

h2. Date de intrare

Fişierul de intrare $2sat.in$ va conţine pe prima linie două numere naturale, $N$, numărul de termeni care apar în expresie, şi $M$, numărul de propoziţii disjunctive din care este formată expresia. Pe fiecare dintre urmatoarele $M$ linii se vor afla câte două numere întregi, numerele de ordine ale termenilor prezenţi în fiecare dintre propoziţii. Semnul $-$ în faţa unui număr reprezintă negarea termenului în expresie.

Fişierul de intrare $2sat.in$ va contine pe prima linie 2 numere naturale, $N$ - numarul de termeni care apar in expresie si $M$ - numarul de propozitii disjunctive din care este formata expresia. Pe fiecare dintre urmatoarele $M$ linii se vor afla cate 2 numere intregi, numerele de ordine ale termenilor prezenti in fiecare dintre propozitii. Semnul $-$ in fata unui numar reprezinta ca termenul respectiv apare negat in expresie.

h2. Date de ieşire

În fişierul de ieşire $2sat.out$ se vor afişa $N$ numere naturale, $0$ sau $1$, reprezentând o atribuire satisfiabilă pentru expresia dată în fişierul de intrare, sau valoarea $-1$ în caz că expresia nu admite soluţie.

În fişierul de ieşire $2sat.out$ se vor afisa $N$ numere naturale, $0$ sau $1$, reprezentand o atribuire satisfiabila pentru expresia data in fisierul de intrare, sau valoarea -1 in caz ca expresia nu admite solutie.

h2. Restricţii

* $1 ≤ N ≤ 100 000$.
* $1 ≤ M ≤ 200 000$.

* $1 ≤ N ≤ 100000$
* $1 ≤ M ≤ 200000$

h2. Exemplu

| 1 0 0 1
|

h2. Explicaţie

h3. Indicatii pentru rezolvare

_(Cum s-a ajuns la soluţie, cum au fost mapaţi termenii cu numerele întregi [să zicem că reprezintă indexul variabilei $x$?])_.

O solutie evidenta este incercarea celor $2^N^$ configuratii posibile pentru termenii expresiei si apoi verificarea lor, aceasta abordare ducand la o complexitate de $O(2^N^ * M)$. Cu aceasta complexitate se obtin 20 de puncte, iar o sursa demonstrativa se gaseste 'aici':/job_detail/372167?action=view-source.

h3. Indicaţii pentru rezolvare

'O alta solutie':/job_detail/372174?action=view-source se poate realiza daca fixam o variabila $p$ dintr-o propozitie. In cazul acesta suntem obligati sa ii dam o anumita valoare celeilalte variabile din acea propozitie, $q$, ceea ce ne obliga sa atribuim valori si variabilelor care se gasesc in alte propozitii care il contin pe $q$. Astfel "propagam" schimbarile si, daca problema admite solutie vom ajunge la ea, complexitatea finala fiind $O(N * M)$. Acest algoritm obtine 70 de puncte.

Pentru detalii în legatură cu soluţiile consultaţi 'Problema 2-satisfiabilităţii':/2-sat.

'O alta solutie neoptima':/job_detail/372176?action=view-source, in complexitatea $O(N^2^ * M)$ se bazeaza pe un algoritm randomizat. Initial se atribuie valori arbitrare variabilelor, iar apoi cat timp expresia nu este satisfacuta se gaseste o propozitie cu valoarea de adevar $0$ si se schimba valoarea unuia dintre cei 2 termeni componenti ai propozitiei. Precizam ca aceasta abordare se comporta foarte bine in practica, asa ca ar trebui sa obtina aproximativ 70 de puncte.

O soluţie evidentă este încercarea celor $2^N^$ configuraţii posibile pentru termenii expresiei şi verificarea lor. Această abordare duce însă la o complexitate de $O(2^N^ * M)$. Cu această complexitate se obţin $20$ de puncte, iar o sursă demonstrativă se găseşte 'aici':/job_detail/372167?action=view-source.

'Solutia optima':/job_detail/372206?action=view-source, in complexitatea $O(M + N)$ se foloseste de 'relatia de implicatie':http://en.wikipedia.org/wiki/Logical_implication, transformand astfel problema intr-una de grafuri, care se poate rezolva determinand 'componentele tare-conexe':/problema/ctc.

'O altă soluţie':/job_detail/372174?action=view-source se conturează dacă fixăm o variabilă $p$ dintr-o propoziţie. În cazul acesta suntem obligaţi să îi dăm o anumită valoare celeilalte variabile din acea propoziţie, $q$, ceea ce ne obligă să propagăm atribuiri de valori şi variabilelor care se găsesc în alte propoziţii care îl conţin pe $q$, şi aşa mai departe. Astfel, dacă problema admite soluţie vom ajunge la ea. Complexitatea finală fiind $O(N * M)$. Acest algoritm obţine $70$ de puncte.
 
'O alta soluţie neliniară':/job_detail/372176?action=view-source, în complexitatea $O(N^2^ * M)$, se bazează pe un algoritm randomizat. Iniţial, se atribuie valori arbitrare variabilelor, după care, cât timp expresia nu este satisfăcută, se găseşte o propoziţie cu valoarea de adevăr $0$ şi se schimbă valoarea unuia dintre cei doi termeni componenţi ai propoziţiei. Precizăm că această abordare se comportă foarte bine în practică, aşa că ar trebui să obţină aproximativ $70$ de puncte.
 
'Soluţia optimă':/job_detail/372206?action=view-source, în complexitatea $O(M + N)$, se foloseşte de 'relaţia de implicaţie':http://en.wikipedia.org/wiki/Logical_implication ce transformă expresia într-un graf, care se poate rezolva determinând 'componentele tare-conexe':/problema/ctc.

Pentru mai multe detalii in legatura cu solutiile consultati 'articolul':/2-sat.

h3. Aplicatii