|
Titlul: 837 Pari Scris de: Airinei Adrian din Aprilie 05, 2009, 11:25:57 Aici puteti discuta despre problema Pari (http://infoarena.ro/problema/pari).
Titlul: Răspuns: 837 Pari Scris de: Florian Marcu din Aprilie 06, 2009, 07:39:34 Citat Ideea ce se conturează este ca din fiecare nod alb să parcurgem graful în lăţime sau adâncime adunând alternativ +1 şi -1 pe muchii ... Ar trebui sa fie "negru" acolo, nu?Titlul: Răspuns: 837 Pari Scris de: Marius Stroe din Aprilie 06, 2009, 08:24:34 Citat Ideea ce se conturează este ca din fiecare nod alb să parcurgem graful în lăţime sau adâncime adunând alternativ +1 şi -1 pe muchii ... Ar trebui sa fie "negru" acolo, nu?Corect, am modificat. Titlul: Răspuns: 837 Pari Scris de: Florian Marcu din Aprilie 06, 2009, 13:19:54 Daca numarul de noduri negre este par, atunci exista solutie? [ <=> daca nr de noduri negre este impar, atunci nu exista solutie? ]
Eu cred ca nu e asa, insa, daca intr-adevar nu ar fi asa, atunci ar trebui ca operatiile sa fie retinute intr-un vector, care va fi afisat la sfarsit [ in cazul in care s-au colorat toate in alb ]. Dar asta imi cam iese din timp. :| Daca afisez din prima, si consider pozitiv raspunsul la intrebarea de mai sus, iau un tle pe testul 4. Complexitatea e O(N*M), deci nu ar trebui sa am probleme. Poate doar daca imi cicleaza... Titlul: Răspuns: 837 Pari Scris de: Marius Stroe din Aprilie 06, 2009, 13:29:53 Daca numarul de noduri negre este par, atunci exista solutie? Din câte îmi aduc aminte, cred că sunt şi ceva componente conexe. :) Titlul: Răspuns: 837 Pari Scris de: Andrei Grigorean din Aprilie 06, 2009, 16:42:15 Exista solutie <=> in fiecare componenta conexa ai numar par de noduri negre.
Titlul: Răspuns: 837 Pari Scris de: Florian Marcu din Aprilie 06, 2009, 18:21:40 Da. E clar. Faza e ca iau tle pe testul 4, si nu exista niciun caz in care sa nu fie solutie [ in testele problemei ] [ am verifcat :evil: ]. In cazul in care nu este solutie se afiseaza "0 0 0" (fara ghilimele), nu? :?
|