055 Cerere

[•vladcyb1]

10x Programul meu gresea la aflarea radacinii.

[•devilkind]

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

[•cos_min]

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

->vezi la df,sigur acolo gresesti ceva

[•Aymd]

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

[•devilkind]

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

[•k_ounu_eddy]

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

[•savim]

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

[•k_ounu_eddy]

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

[•gabor_oliviu1991]

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

Pe prima linie a fiserului de iesire se vor gasi N numere G1 G2 ... Gn, Gi reprezentand numarul de maimute pe la care trece cererea maimutei numarul i (excluzand-o pe aceasta)

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           

[•Florian]

Cod:

ea trebuie sa prezinte o cerere in scris celui de-al Ki-lea stramos al ei si numai acestuia .

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

[•Robytzza]

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

[•Alexa_ioana_14]

Cum pot sa aflu radacina arborelui?

[•pauldb]

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

[•Pepelea_Flaviu]

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.

[•Alexa_ioana_14]

Multumesc  !

[•deneo]

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

[•Schumi]

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.

[•mihai.constantin]

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.

[•AlexandruValeanu]

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