•Marius
|
|
« : Ianuarie 14, 2010, 07:37:44 » |
|
Aici puteţi discuta despre problema 2SAT.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•wefgef
|
|
« Răspunde #1 : Ianuarie 14, 2010, 10:39:18 » |
|
Cred ca ar trebui detaliata mai mult solutia optima.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Marius
|
|
« Răspunde #2 : Ianuarie 15, 2010, 20:44:07 » |
|
Cred ca ar trebui detaliata mai mult solutia optima. S-a rezolvat.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•Marius
|
|
« Răspunde #3 : 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.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•anna_bozianu
|
|
« Răspunde #4 : 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.
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #5 : Iulie 05, 2010, 09:41:22 » |
|
Evalul la problema asta este busit. Daca afisezi un sir de zerouri iei 100 de puncte: int rez = 1; for (i = 1; i <= m; i++) rez = rez | eval_term(expr[i]);
Ar trebui sa fie "&" in loc de "|".
|
|
|
Memorat
|
|
|
|
•ciprianf
|
|
« Răspunde #6 : 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 ). 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
|
|
|
Memorat
|
|
|
|
•claudiumihail
Strain
Karma: 5
Deconectat
Mesaje: 33
|
|
« Răspunde #7 : 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, 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
|
|
|
Memorat
|
|
|
|
•darren
Client obisnuit
Karma: 106
Deconectat
Mesaje: 76
|
|
« Răspunde #8 : 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"
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #9 : Martie 02, 2012, 15:33:40 » |
|
Am corectat, multumim!
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Cosmin1490
Strain
Karma: 1
Deconectat
Mesaje: 17
|
|
« Răspunde #10 : August 15, 2013, 01:28:03 » |
|
Nici in cazul in care se opteaza pentru algorimul lui Tarjan nu e necesara sortarea topologica.
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #11 : 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.
|
|
|
Memorat
|
|
|
|
|