Nu aveti permisiuni pentru a descarca fisierul grader_test22.in
Diferente pentru problema/2sat intre reviziile #35 si #36
Nu exista diferente intre titluri.
Diferente intre continut:
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.
O alta solutie 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 obtine70 de puncte.
O alta solutie 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 50 de puncte.
O alta solutie neoptima, 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 aproximativ70 de puncte.
O alta solutie neoptima, 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 50 de puncte.
