repet si io ... faina ideea de rezolvare. Asta e solutia oficiala a problemei ?

sigur e bun exemplu 2 ? eu primesc 3 ... cred ca acolo calculeaza p(p^1)

un O(n^3) intra in timp aici ? daca da problama e simpla nu ?

mersi  ma uit peste el

am gasit ceva pe net ... da nam rabdare sa incerc si asa ...
mam mai uitat peste program si aleg pe primele k componente o fac in O(k*numaru de componente) ... poate ca daca numaru de componente este f mare si k tot f mare tinde catre un O(n*n) si iese din timp nu ?

nu-mi spune nimic  ... poti sami dai un link calumea ? ce complexitate ar trebui sa scot ?

la problema asta consider bananierii varfuri intrun graf. Determin muchiile dupa ce sortez pozitiile lor si dupaia fac o parcurgere in latime sa determin componentele conexe, in final le iau pe cele mai mari k.  Complexitatea e O(n*log n). Primesc pe doua teste TLE ... cum sal mai imbunatatesc ?

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 

nu stiti unde gasesc solutiile la "stelele informaticii" 2005 ?

ok . mersi ... citesc 

da ok ... nici nu ma gandeam sa retin arborele cu matrice de adiacenta ... nus batut in cap. Da pentru a construi lista de fii trebuie sa folosesc atuncia O(n^2) care nu intra in timp. nu ? in sensu ca reiau muchiile si caut un varf anume intre printre ele. nu ?

am matrice de 16000 pe 16000.   ii prea mult ?

Programul imi trece de compilare si totusi iau 0 puncte cu mesajul RUN ERROR - SIGKILL la toate testele. Am declarat oare o matricea prea mare ?

[long]

  ok cred cas batut in cap. Primesc pentru doua teste "RUN ERROR - Invalid memory reference", desi am declarat toti indicii si chiar toate variabilele long.  NU ma prind ... poate exista teste si cu siruri mai lungi de  1.000.000 

Am dat acuma de curiozitate lmax = 10.000.000 si merge ... ciudat 

suffix array nu stiu exact ce inseamna ... da vroiam sa folosesc functia prefix din kmp. LA asta se refere suffix array ?

aicia ii ceva kmp nu ?   

Primesc TLE la jumate din teste si cred ca pentru ca am construit arborele initial ( cu radacina in 1 ) parcurgand muchiile de n ori .. deci in O(n^2) . Nu vad totusi cum as putea sal construiesc altfel ... nam cum sa tin o matrice de vecini de 16000 pe 16000. Am incercat sa merg la noroc , adica ca poate nu exista varfuri cu peste 200 de vecini si sa declar matricea de 16000 pe 200 da nu prea . Nu stiu ... imi da o idee cineva ?

nu ma prind de problema .... ma gandesc ca trebuie construit un graf dar nam cum sa iau R*C noduri nu ? ... ma ajuta cineva ?

nu stie cineva cum pot calcula restu impartirii la 9901 a unui produs de mai multe progresii geometrice? ... presupun ca un algoritm liniar nu intra in timp ... deci in timp logaritmic  ....  la ce ma ajuta faptul ca 9901 ii prim ?

tot textul este scris in fisier pe o singura linie sau pot aparea mai multe caractere de sfarsit de linie ?

nu pricep o kestie ... calculez costul mediu al unui cilcu .... adica indiferent care ? sau caut ciclul cu costul mediu minim ?