041 2SAT

[•Marius]

Aici puteţi discuta despre problema 2SAT.

[•wefgef]

Cred ca ar trebui detaliata mai mult solutia optima.

[•Marius]

Cred ca ar trebui detaliata mai mult solutia optima.

S-a rezolvat.

[•Marius]

Testele sunt sigur corecte ? Eu am luat de exemplu testul 10 de la atasamente. In grader_test10.in avem n=1289 iar grader_test10.ok contine doar o valoare de 1. Pe sursa mea am afisare -1 . Nu ar fi normal ca in ok sa avem ori -1 ori 1289 valori de 0 sau 1 ? Sau am inteles eu ceva gresit?  

L.E. Observ ca nimeni nu a obtinut punctaj maxim la problema.

În cazul în care nu ai soluţie în fişierul .ok se găseşte un singur -1. Altfel, problema nu admite soluţie unică, aşa că Cezar a ales să scrie 1 în fişier ca să spună evaluatorului că există soluţie. Ce vei scrie în fişierul 2sat.out va fi verificat de evaluator să verifice expresia.

Nimeni nu a implementat (corect) soluţia optimă. E un semn că testele sunt bune.

[•anna_bozianu]

Imi cer scuze. Intre timp am observat si eu ce am inteles gresit si am sters cu totul mesajul. Nu am observat ca intre timp mi s-a raspuns. Multumesc pentru promptitudine.

[•toni2007]

Evalul la problema asta este busit. Daca afisezi un sir de zerouri iei 100 de puncte:

Cod:

	
int rez = 1;
for (i = 1; i <= m; i++)
	rez = rez | eval_term(expr[i]);

Ar trebui sa fie "&" in loc de "|".

[•ciprianf]

Am rezolvat problema folosind ideea de la varianta cu complexitate O(N*M), insa am implementat diferit fata de sursa oficiala(intr-un mod mai eficient zic eu, nu imi dau insa seama daca complexitatea teoretica ramane tot O(M*N) sau scade ). Oricum, ideea e ca sursa ia 100 de puncte, ba chiar merge mult mai repede decat cea in O(N+M) (pe testul maxim intra in sub 0.6 sec)

Check it out!  http://infoarena.ro/job_detail/520843

[•claudiumihail]

Salut,

E interesant ca daca problema se rezolva utilizand algoritmul lui Kosaraju pentru determinarea componentelor tare conexe nu mai este nevoie si de o sortare topologica. Asta deoarece algoritmul lui Kosaraju da lista componentelor tare conexe sortata topologic deja (se poate vedea aici http://infoarena.ro/job_detail/662214, ca solutia merge comparabil o solutie bazata pe algoritmul lui Tarjan + o sortare topologica). Avantajul mare al algoritmului lui Kosaraju este ca este simplu de implementat si afce rezolvarea mai usoara decat o abordare cu Tarjan+sortare topologica.

Anyway, again just my 2 cents. Poate foloseste cuiva alternativa.

Claudiu 

[•darren]

Este o problema la cateva linkuri de la explicatii (este pus doar ce este dupa "infoarena.ro/"):
  - linkul catre articolul cu 2-SAT
  - linkurile cu solutiile de 20 de puncte si de 70 de puncte
  - linkurile catre problemele "Party" si "Aladdin"

[•wefgef]

Am corectat, multumim!

[•Cosmin1490]

Nici in cazul in care se opteaza pentru algorimul lui Tarjan nu e necesara sortarea topologica.

[•freak93]

Am sa modific acuma pagina problemei sa spuna asta. Din pacate informatia asta e cam obscura, si e si foarte utila. Am gresit sortarea topologica uneori si am luat punctaj mare din simplul fapt ca nu trebuia sortare topologica.