infoarena

Aici puteţi discuta despre problema Cerere (http://infoarena.ro/problema/cerere).

De ce postezi la Traseu? Nu ai vazut regulile?

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

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

 :P
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!

ms.
La ce te asteptai de la intrebarea ta ? :P

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

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])

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 :)

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

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 :)

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

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.

ba da, totul trebuie "ca la carte".

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.

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.

](*,) Sunt destept rau... Mersi mult oricum :mrgreen:

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?

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).

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.

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

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? :-k

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...

10x Programul meu gresea la aflarea radacinii.

nu inteleg, am implementat DF-u recursiv si dak nu determin radacina iau 0 (WA peste tot) iar dak o determin iau 20 de pct cu TLE peste tot.

PS: radacina o determin vazand care nod nu are tata  ](*,)

[LATER EDIT] sorry prima data am scris gresit, iau TLE nu WA dak determin radacina

->nu cred ca ii de la aflarea radacinii, cel putin asa am aflat si eu

->vezi la df,sigur acolo gresesti ceva

La o prima rezolvare am luat 20 puncte ... restul TLE
M-am bazat pe o proprietate pe care credeam ca o are citirea muchiilor si am luat 50 puncte ... restul TLE
Nu cumva ar trebui sa fie specificat in enunt (daca e adevarat) ca fiecare muchie citita nu este decat o adaugare de frunza in arborele format pana la pasul respectiv ?

Pentru o mai buna intelegere a intrebarii:
pentru vectorul de tati: 0 1 2 3 presupun ca citirea muchiilor va fi de genul:
1 2                            3 4    1 2
2 3       si niciodata      2 3  , 3 4 sau alte permutari ale sirului de muchii.
3 4                            1 2    2 3

nu stiu testele dar sunt destul de sigur ca acea propietate de care zici tu nu exista :P

Dati-mi va rog un sfat,ca nu stiu care e treaba :)).Iau doar 20 de puncte,si restul SIGSEGV.Pe testele facute de mine,programul imi da mereu rezultatul corect.Puteti sa postati un mic test,sau poate a mai patit cineva asa ceva,si ma lumineaza si pe mine?
Va multumesc

SIGSEGV iei de obicei daca te duci "aiurea" in memorie. Vezi daca nu ai pus dimensiunile vectorilor prea mici, sau daca apelezi ceva ce nu exista... :wink:

Am verificat tot,dimensiunile vectorilor nu sunt prea mici,iar de accesat ceva ce nu exista tot nu am gasit... ](*,)

hmmmm... din cate am inteles eu problema, pt testul problemei arborele imi arata cam asa:

                  1
                /    \
              2       6
             / \     /  \
            3   4  7   8
                /   /  \
               5   9   10

nodurile ingrosate fiind maimutele la care poti rezolva cererile. bun... sa zicem ca daca maimuta 4 vrea sa rezolve o cerere, aceasta trimite cererea la numarul 2, care la randul ei o trimite la 1 sau 3 (ambii fiind la aceasi distanta).


deci avem distanta 2 adica cererea porneste de la 4 -> 2 -> 1 (sau 3). si in fisierul de intrare G[4] = 1. aici n-am inteles. multumesc anticipat  :)       

LE: am pus si 5-ul :p           

Dupa cum vezi in .in, K[4] = 2. Ceea ce inseamna ca maimuta 4 va trimite cererea celui de-al 2-lea stramos al ei. Al doilea stramos al ei este 1 (atentie! nu poate fi 3!), care rezolva cererea. Deci cererea a trecut doar pe la o singura maimuta (maimuta 1), si de asta G[4]=1. Si apropo, ai sarit nodul 5, in arborele tau. [desi nu conteaza].

Sunt singurul cu 85  :'( ..si nu vad de ce  :? ...Va uitati un pic peste sursa poate vedeti voi .. :peacefingers:
http://infoarena.ro/job_detail/277260?action=view-source

Cum pot sa aflu radacina arborelui?

Radacina arborelui este maimuta care nu are tata. Deci este acea maimuta care nu apare ca "B".

Tu citesti din fisierul de intrare muchiile arborelui (cate doua valori A si B cu semnificatia ca A este tatal nodului B). Pentru a determina care este radacina arborelui trebuie sa vezi ce nod nu are nici un parinte. Pentru a afla acest lucru poti folosi de ex. un vector T[], unde pe pozitia i retii parintele nodului i. Astfel radacina arborelui va fi nodul care are valoarea 0.

Multumesc  :) !

solutia cu parcurgerea bfs care lua pana acum 100p acum ia 30p ... nu ar trebui sa ia 100 ? :-k

Cred ca ar trebui marita putin limita de timp. Am luat 80 de puncte cu citirea standard si 100 cu streamuri fara sa modific in nici un fel solutia.

Cred ca limita de timp ar trebui marita. Am facut o rezolvare asemanatoare cu cea de la problema Stramosi (la care obtin 100p), dar iau la 3 teste TLE. Am si parsat, dar degeaba.

Borderou: http://www.infoarena.ro/job_detail/1675829
Sursa: http://www.infoarena.ro/job_detail/1675829?action=view-source

Multumesc anticipat.

Solutia optima este O(n). O solutie de complexitate O(n log n) nu ar trebui sa ia 100p.