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

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

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

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

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

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ţă

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

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

h2. Date de intrare

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.

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.

h2. Date de ieşire

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

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

h2. Restricţii

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

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

h2. Exemplu

| 1 0 0 1
|

h3. Indicatii pentru rezolvare

h2. Explicaţie

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.

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

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

h3. Indicaţii pentru rezolvare

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

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

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

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

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

h3. Aplicatii