|
Titlul: 041 2SAT Scris de: Marius Stroe din Ianuarie 14, 2010, 07:37:44 Aici puteţi discuta despre problema 2SAT (http://infoarena.ro/problema/2sat).
Titlul: Răspuns: 041 2SAT Scris de: Andrei Grigorean din Ianuarie 14, 2010, 10:39:18 Cred ca ar trebui detaliata mai mult solutia optima. :thumbup:
Titlul: Răspuns: 041 2SAT Scris de: Marius Stroe din Ianuarie 15, 2010, 20:44:07 Cred ca ar trebui detaliata mai mult solutia optima. :thumbup: S-a rezolvat. :yahoo: Titlul: Răspuns: 041 2SAT Scris de: Marius Stroe din Ianuarie 17, 2010, 15:52:55 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. :) Titlul: Răspuns: 041 2SAT Scris de: Bozianu Ana din Ianuarie 17, 2010, 15:57:16 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.
Titlul: Răspuns: 041 2SAT Scris de: Pripoae Teodor Anton din Iulie 05, 2010, 09:41:22 Evalul la problema asta este busit. Daca afisezi un sir de zerouri iei 100 de puncte:
Cod:
Ar trebui sa fie "&" in loc de "|". [-X Titlul: Răspuns: 041 2SAT Scris de: Farcasanu Alexandru Ciprian din Ianuarie 10, 2011, 17:11:16 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 :-k). 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! :D http://infoarena.ro/job_detail/520843 Titlul: Răspuns: 041 2SAT Scris de: Claudiu Mihail din Ianuarie 16, 2012, 05:07:25 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 (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 Titlul: Răspuns: 041 2SAT Scris de: Rares Buhai din Martie 02, 2012, 15:17:50 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" Titlul: Răspuns: 041 2SAT Scris de: Andrei Grigorean din Martie 02, 2012, 15:33:40 Am corectat, multumim!
Titlul: Răspuns: 041 2SAT Scris de: Balan Radu Cosmin din August 15, 2013, 01:28:03 Nici in cazul in care se opteaza pentru algorimul lui Tarjan nu e necesara sortarea topologica.
Titlul: Răspuns: 041 2SAT Scris de: Adrian Budau din August 15, 2013, 05:18:56 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.
|