095 Color

[•domino]

Aici puteţi discuta despre problema Color.

[•realboss]

Merge rezolvarea cu cautare binara?
Sau ar trebui sa-mi dau seama de cate triunghiuri negre sunt dupa ce aflu numarul celor rosii?

[•wefgef]

sau ar trebui sa iti dai seama cat e suma celor negre+cele rosii .

[•marius135]

limita de timp?

am O(n) depasit:)
mariti limita la 0,5 sa poata citi lumea linistita

[•MarcvsHdr]

Ceva e tare tare naspa la problema asta. Am o solutie care tot ia 50 p astfel:
- primele 4 teste, TLE.
- testul 5, TLE/WA (depinde de optimizari)
- ultimele 5 teste, corecte

Algoritmul meu se compune din:
1. citire  - O(m) <- nu se poate scapa de asta
2. un DF <- ca sa determin cate cicluri rosii sunt.
3. niste calcule care duc la solutie. O(2*n) (am pus si constanta).

Am incercat mai multe variante. Simulez listele de adiacenta cu vectori (adica sunt alocate static) ca sa evit sa bag pointeri (nu se prea cunoaste diferenta, 0,01 secunde la testul 5). DF-ul n-ar trebui sa ia mai mult de O(n), avand in vedere ca sunt n noduri. Eu mai fac niste operatii si pentru cazul in care nodul in care incerc sa merg e deja vizitat (totusi, doar 3 adunari !!)... 

Ce pot sa ii mai fac? Tot iau TLE. Evident, solutia este liniara. In cazul asta, constanta conteaza mult. 

[•Tabara]

Eu am parsat citirea...desi nu a fost nevoie decat pentru ultimul test 
 

[•MarcvsHdr]

Ok. Tocmai am realizat ceva. Calculam tot felul de tampenii aiurea, ca se reduceau in formula finala. Acum dupa simplificare algoritmul meu e:
1. citirea O(m)
2. calculul O(n)

Din moment ce n<=4000, nu prea conteaza ala.

Iau 80p. - TLE pe primele doua teste.

Cum ai parsat citirea? Numerele sunt cate doua pe linie. Nu stiu daca e foarte mare diferenta sa citesti M linii sau sa citesti 2*M numere.

Deci, problema asta chiar are limita de timp pus aiurea. Imi pare rau ca m-am chinuit doua ore sa ii reduc timpul de executie cu 12 milisecunde, in conditiile in care se ia TLE cu citire :|.

[•Tabara]

Nu stiu ce sa zic... Eu luam 90 fara parsare.
( Am parsat cu fread ).

Tie cred ca O(m) din citire iti face probleme mai degraba decat O(n) din rezolvare.
Incearca sa parsezi citirea si vezi ce iese.  , desi sincer sa fiu e destul de ciudata faza, atata timp cat iti intra ultimul test in timp si nu iti intra primele doua 

Oricum, incearca si parsare ca nu ai nimic de pierdut 
 

[•bogdan2412]

Ultimul test e mic, primele 2 sunt alea mari... Nu prea aveai cum sa iei TLE pe ultimu si sa-ti intre primele 2

Nu intra problema fara sa parsezi citirea

[•Tabara]

Ultimul test e mic, primele 2 sunt alea mari... Nu prea aveai cum sa iei TLE pe ultimu si sa-ti intre primele 2

Nu intra problema fara sa parsezi citirea

Mda.. ..ai avut dreptate. 
M-am uitat acuma si eu in monitor la sursa aceea de 90, fara parsare a mea.

Cod:

Test	Timp executie	Memorie folosita	Mesaj	Punctaj
1	320ms	224kb	Time limit exceeded.	0
2	288ms	248kb	OK	10
...........................................................

Primul test e ala nasol.