|
Titlul: 1013 Guess Scris de: Cezar Mocan din Mai 03, 2010, 15:26:37 Aceasta problema se poate reduce usor la 2SAT si am observat ca solutia oficiala este un greedy. Are cineva o demonstratie ca acel greedy merge?
Titlul: Răspuns: 1013 Guess Scris de: Andrei Grigorean din Mai 03, 2010, 15:33:10 Echivalenta intre problema asta si 2SAT este clara. Am citit si eu solutia oficiala si mi se pare gresita. In functie de modul in care este implementata sursa cred ca se pot gasi usor contraexemple.
|