055 Cerere

[•costeapaul]

Aici puteţi discuta despre problema Cerere.

[•Cosmin]

De ce postezi la Traseu? Nu ai vazut regulile?

[•domino]

are cineva evaluatorul de la cerere? Sau macar un test mai adevarat...
ca am fost extrem de cu vaca la concurs .
10x....

Am mutat topic-ul. Dupa cum a zis si Cosmin, citeste regulile inainte sa postezi in sectiunea aceasta.  

[•Motanul_Danila]

Cum pot afla cel de-al k-lea strămoş al unui nod ?

[•ParrAzitU]

Cum pot afla cel de-al k-lea strămoş a unui nod ?

 
E simplu. tii cu vector de tati : t = tata lui i
si faci de k ori i = t, si tadaa ai ajuns pe stramosul k al nodului i.. Asta dc el are k stramosi.. :lol:

[•Motanul_Danila]

Cum pot afla cel de-al k-lea strămoş a unui nod ?

 
E simplu. tii cu vector de tati : t = tata lui i
si faci de k ori i = t, si tadaa ai ajuns pe stramosul k al nodului i.. Asta dc el are k stramosi.. :lol:

Genial!

[•ParrAzitU]

ms.
La ce te asteptai de la intrebarea ta ?

[•Motanul_Danila]

La ceva mai eficient.
Când apar soluţiile la preONI runda # 2 ?

[•druid]

Poti sa faci o parcurgere in adancime si ai o stiva si cand ajungi pe un nivel nou, pui in stiva nodul curent... si de asemenea retii al K-lea parintele pt nodul curent (ai daca esti in nodul I si pe nivelul L, ai stiva ST, si vectorul K - citit din fisier, raspunsul pt nodul I este ST[L-K])

[•masterthor]

am facut o implementare divide et impera la problema asta, dar imi ies numai 4 teste, iar restul 3 timed out, toate celelalte raspuns greshit. ratzionamentul shi modul de implementare nu mi se *par* greshite mie, shi ma intrebam daca pot sa postez codul aici, shi daca cineva vede buba, sa ma lumineze shi pe mine. ashtept raspuns

[•silviug]

Poate nu v-a spus nimeni.. dar chiar am scris solutii la aceste probleme..

http://info.devnet.ro/articole.php?page=art&art=49

PS: terminati cu recursivitatea pe citate.. se vede clar la ce ati raspuns din moment ce postul e exact cel de sus

[•masterthor]

silviug: asta nu inseamna ca alte variatii la solutia ta (cele facute de restul populatiei) nu sunt bune, sau aproape bune. tot nu m-am lamurit daca pot sa postez codul, tare mult ash vrea sa intzeleg cu ce am greshit

[•silviug]

1. Solutia la cerere nu am facut eu, deci nu e "solutia mea"
2. Nu am pretins niciodata ca numai eu fac solutii bune iar "restul lumii" nu. Te rog fii mai atent cu afirmatiile de genul asta

Multumesc pentru intelegere

[•masterthor]

imi pare rau, n-am avut intentzia sa atac pe cineva anume. ideea era pur si simplu ca exista unele variatii asupra tuturor solutiilor, si daca iau ca perfecta solutia oficiala, nu prea ma simt bine (mult mai bine ma simt cand incerc "varianta mea" si vad care sunt punctele slabe shi cele bune) shi programarea e un fel de arta, chiar daca uneori nu e privita asha poate delirez acum, dar sunt sigur ca nu totul trebuie facut "ca la carte".

din nou, imi cer scuze pentru cele spuse in post-ul anterior.

[cristi8]

sunt sigur ca nu totul trebuie facut "ca la carte".

ba da, totul trebuie "ca la carte".

[•masterthor]

discutzia asta nu ishi are locul aici. ideea e ca potzi sa implementezi anumite modificari, nu neaparat dupa cum gandesc cei care fac solutiile, shi tot sa obtii toate punctele.

[•bogdan2412]

Imi poate spune cineva cum poti determina radacina arborelui in mod eficient? Nu cred ca pot sa fac DF pt fiecare nod care are 0 in Ki pana cand gasesc unu de unde parcurg tot arboru ca ar tine ceva...

[•domino]

Imi poate spune cineva cum poti determina radacina arborelui in mod eficient? Nu cred ca pot sa fac DF pt fiecare nod care are 0 in Ki pana cand gasesc unu de unde parcurg tot arboru ca ar tine ceva...

Tii gradul interior al fiecarui nod si radacina va fi nodul in care nu intra nimic.

[•bogdan2412]

Sunt destept rau... Mersi mult oricum

[•Deliverance]

Cu DF am luat 100 de puncte la stramosi si 0 la cerere(WA la toate).
Are cineva un test "mai serios" sa vad si eu unde am gresit?

[•stifmeister]

Mi-e nu imi plac grafurile de nici o culoare si nu prea am lucrat astfel de probleme pana acum.
Cum fac sa memorez grafuri de dimensiuni foarte mari? (ex. 100 000 de noduri, ca in problema "cerere").

Si nu am inteles solutia comisiei. Dupa cate am inteles eu din grafuri, parcurgerea in adancime pentru exemplul din problema este : 1 2 3 4 5 6 7 9 10 8. Stramosul lui 6 este p[6-1] = p[5] = 5 ( FALS).

[•Cosmin]

Cristian Cadar a scris un tutorial de teoria grafurilor in gazeta de info, el incepe din numarul  din Decembrie 1999, Vol. 9/8, si poti vedea articolele la adresa http://www.ginfo.ro/revista/arhiva.shtml . Cat despre reprezentarea grafului pentru problema cerere poti folosi cu incredere liste de vecini.

[•mirceacnu]

Vreau si yo un test k nu shtiu d c nu-mi merge problema asta!    

[•vladcyb1]

Problema asta are o chickitza ceva? Am implementat cu df-ul manual dar nu iau decat 45 de puncte restul WA.  Imi da cineva un sfat?

[•filipb]

Construieste un ex de arbore cu vreo 20 noduri si verifica stiva DFS la fiecare pas sa vezi daca DFS-ul manual merge bine. Altceva nu are ce sa fie...Fara cod in fata nu pot sa imi dau seama..
  HINT: Vezi sa initializezi cu 0 toate nodurile in care se pot rezolva cererile ( sa nu le consideri la distanta 1 fata de ele insele ). Mai rescrie o data sursa daca tot nu-ti iese... Mai mult de atat n-am ce sa fac sa te ajut...