837 Pari

[•astronomy]

Aici puteti discuta despre problema Pari.

[•Florian]

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?

[•Marius]

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.

[•Florian]

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...

[•Marius]

Daca numarul de noduri negre este par, atunci exista solutie?

Din câte îmi aduc aminte, cred că sunt şi ceva componente conexe.

[•wefgef]

Exista solutie <=> in fiecare componenta conexa ai numar par de noduri negre.

[•Florian]

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 ]. In cazul in care nu este solutie se afiseaza "0 0 0" (fara ghilimele), nu?