Mai este vreun caz particular in afara de cel in care graful nu este conex, sau de cel in care mai mult de 2 noduri au grad impar?

 ....de aici stiu mersi mult de idee

Imi da si mie cineva o idee la problema asta? singura care imi vine in minte e sa fac o dinamica pentru fiecare piesa de domino aleasa ca punct de inceput....insa nu cred ca O(n^2) incape in limita de timp....

cat va da pe:
9
6 -8 -2 -4 -6 -10 -3 12 -12

mie mi-a dat:

Cod:

-33 2 7
-12 9 9
6 1 1
12 8 8

Mie mi-au venit 2 idei pe masura ce o citeam:
1) cautare binara + verificare lee
2) o dinamica d[j] dimensiunea maxima pe care o poate avea bila pentru a putea ajunge in patratul ce are coltul stanga sus in coord de i si j...

n-am apucat sa le implementez 

Citeste articolul cu solutia problemei :
http://info.devnet.ro/articole.php?page=art&art=40&artpage=1

spor la implementat

Ce raspuns ai gasit?

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.

Cod:

        1                           1(3)                      1(3)                         1(3)               
       / \            ->           / \            ->         / \             ->           / \                     
     /     \                     /     \                   /     \                      /     \              
    2      3                     2      3                  2(2)   3                    2(2)   3(2)             

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?

Pe testul :

Cod:

5 4
1 2
3 4 
4 5
3 5

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

daca nu exista solutie ce se va afisa?

Ok, mersi de sfat.... o sa caut mai mult despre asta

Ce-i memoizarea? 

Si cum pot sa o fac fara sortare? 

Imi zice si mie cineva cat da pe:

Cod:

5
5 30
2 120
3 630
5 4410
1 9699690

? va rog...

Eu n-am folosit radisort, ci numsort, care foloseste un pic mai multa memorie....probabil de acolo ii TLE-ul. O sa incerc si cu radix sort sa vad daca reusesc. mersi de sfaturi

Banuiesc ca O(n^2+HMAX) se scoate folosind alt tip de sortare....am scos O(N^2) acum insa tot iau TLE pe ultimul test...sa fie oare de la faptul ca declar siruri de 1000000 de int-uri?

Care ii complexitatea oficiala? ca iau tle pe 2 teste....

Care este complexitatea la aceasta problema? am un O(n^2), dijkstra pe liste....

de 1,2 ,3 ...8 cifre sau formate din cifrele astea?

Nu se mai tin concursuri pe infoarena?  ar fi binevenit unul acuma in vacanta...

Pentru n = 1, trebuie afisat 0, nu?

Ce naspa ca nu este decat un singur test  imi da bine pe toate testele facute de mana, dar totusi primesc WA...

Pentru:

Cod:

3
12
12543 7
2345 2
60 3
3467 5
7347 4 
57629 5
100 3
24560 9
3232 6
1231 10
45325 8
4
100 2
101 4
102 6
5
10000 1
10000 2
10001 5
10001 3

va da:

Cod:

Consumul minim = 83446.
Consumul minim = 219.
Consumul minim = 11297.

? 

mi-ati putea spune unde pot gasi mai multe despre formule logice in forma 2CNF? am incercat si pe google da n-am gasit mare lucru...

A da ...am inteles  ...sorry....