infoarena

Aici puteţi discuta despre problema Colorare (http://infoarena.ro/problema/colorare).

aici e clar back nu ? am incercat unul care verifica toate posibilitatile de colorare da imi iese din timp pentru multe teste ... nu stiu cum sal mai optimizez  :?

Poate te inspira un pic solutia de la Zebughil (solutia in 3^n)
http://info.devnet.ro/articole.php?page=art&art=74&artpage=5

Pe testul :


va da cumva 3 36?
inca ceva...trebuie colorat graful cu exact p culori sau cu maxim p culori?

Da, e bine 3 36...

"Se cere determinarea numarului minim de culori necesar pentru o colorare valida. Pentru acest numar minim de culori se cere numarul de colorari valide ale nodurilor grafului."
Graful trebuie colorat cu exact p culori, unde p este minim...

Se poate rezolva problema si cu back in 0.01 daca te gandesti bine :)

Eu am incercat alta metoda... numarul minim de culori l-am determinat ca fiind numarul maxim de muchii ce se intalnesc intr-un nod din cele n. Apoi pentru fiecare punct neselectat am pornit un DF din el, si am notat intr-un vector nr[] - numarul de culori in care poate fi colorat nodul i...iar numarul de culori este numarul minim de culori - numarul de vecini care i-am colorat deja.


in paranteza am notat numarul de moduri in care poate fi colorat nodul i
si la sfarsit inmultesc toate valorile dintre nr[];
ar trebui sa fie corect, insa iau WA.....de ce?

E in mod evident WA pentru ca este cunoscut ca orice problema de colorare este NP-completa ( adica nu exista algoritmi polinomiali de rezolvare... ). Algoritmul tau este unul Greedy si pana acum nu s-a gasit nici un algoritm de acest gen pentru o problema de colorare. Deci sigur pentru grafuri mai mari algoritmul tau nu da rezultatul bun.
Un algoritm O(N!) este usor de scos, dar merge si folosind metoda de la zebughil ( un fel de dinamica pe multimi de noduri - tot exponential e, pentru ca ai 2^N submultimi de noduri, exponential in N ).

cica back optimizat merge cel mai bine.

Tocmai am spus mai sus ca backu (in O(N!)) merge in 0.01... rezolvarea in 3^n merge si in 0.2 pe unele cazuri. :P

Da, dar asta nu inseamna ca rezolvarea in N! e cea mai buna sau cea mai inteligenta.. e pur si simplu o rezolvare care se poate optimiza si opri in multe cazuri. Cred ca e mai util pentru cei care rezolva problema sa o rezolve prin cealalta metoda.

Cat de mare e numarul maxim de posibilitati? Intra in long long?

Da, intra pe long long.

Cum se pot consulta sursele trimise la aceasta problema, avand in vedere ca nu este acces momentan.

Doar pentru unele probleme sunt accesibile sursele si acestea sunt marcate corespunzator. Colorare nu este una dintre aceste probleme.

Ok. Se poate posta aici parte din sursa? sau hint-uri.

Daca poate cineva as dori sa-mi dea  un test mai dificil ( nu ma refer la cele oficiale ) deoarece nu imi dau seama ce gresesc. Determin numarul minim de culori din prima colorare care mi-o da backtrackingul si apoi generez toate colorarile cu numarul de culori mergand doar pana la cel determinat prin metoda mentionata . Pe toate testele kre le-am dat .. imi merge.

Cum se combina 2 submultimi de noduri ale unei multimi la problema asta?  :-k
Nu imi dau seama cum sa combin solutiile pentru dinamica... ](*,)

L.E.
Se pare ca avea legatura cu submultimile independente ale grafului.

Metoda mea e:  pt fiecare componenta conexa retinem nr minim de culori in v[ ]. Pt fiecare c.c facem bfs si in functie de culorile vecine stabilim culoarea nodului curent. Parcurgem v[ ] - ul descrescator si facem inmultirile.