013 Petrica

[•fluffy]

Aici puteţi discuta despre problema Petrica.

[•filipb]

Problema cere: "Dandu-se un arbore cu N noduri, sa se elimine 3 muchii astfel incat diferenta dintre cea mai mare si cea mai mica suma a costurilor nodurilor din fiecare arbore ramas sa fie minima?" NU? Am testat o gramada... pur si simplu nu vrea sa ia mai mult de 10 pct....

[•greco]

Hm... daca rezolvarea ta implica la un moment dat sa faci niste diferente, te-ai uitat si tu sa nu scazi aceeasi porcarie de doua ori ?  

[•filipb]

Da... Eu ciclam trei noduri i1, i2, i3, diferite intre ele si diferite de radacina si eliminam muchiile i1-parinte[i1], i2-parinte[i2], i3-parinte[i3]. Fiecare arbore care ramanea in padurea formata era considerat un nod comprimat si facem un nou arbore cu 4 noduri in care prelucram separat fiecare nod... obtineam O(N^3). sper sa imi dau seama ce e...

[•silviug]

Pai in primul rand.. solutia ta nu cred ca este O(N^3) din moment ce tai 3 noduri si apoi prelucrezi padurea de arbori rezultata.

Hint: Taie doar doua noduri si incearca sa-l tai pe al treilea inteligent (ai sa iasa O(N^3))

[•filipb]

Iesea O(N^3) pentru k eu retineam S = suma costurilor nodurilor din subarborele cu radacina in nodul i. Si nu aveam decat de prelucrat (scazut, adunat, etc. ) niste valori S[i1], S[i2], S[i3], S[radacina].
   Oricum, o sa ma gandesc si la chestia cu alegerea doar a doua noduri... (nu prea m-am gandit la asta). ms de sfat.

    O sa postez dupa 27... dak acum evaluatorul e oprit...

[•silviug]

Hmm.. cred ca e buna si ideea ta. O fi de la implementare.

[•bogdan2412]

Si eu ma gandisem la aceeasi solutie. Am implementat-o acum si am luat 100 puncte. Probabil ai gresit undeva la implementare.

[•filipb]

Sigur e de la implementare... O sa o rescriu de la inceput, alta varianta nu am...  

[•filipb]

La problema asta m-am prins partial ce avea (acum iau 40, nu 10.. se vede diferenta... ) )... Era de la faptul ca unele muchii se puteau repeta... Eu citeam doar primele n-1 muchii (credeam ca nu se repeta...), si nu pana la sfarsitul fisierului.... Daca mai vad inca o greseala, iau 100

[•domino]

La problema asta m-am prins partial ce avea (acum iau 40, nu 10.. se vede diferenta... ) )... Era de la faptul ca unele muchii se puteau repeta... Eu citeam doar primele n-1 muchii (credeam ca nu se repeta...), si nu pana la sfarsitul fisierului.... Daca mai vad inca o greseala, iau 100

Nu are cum sa fie de la asta , fiindca eu am luat 100 cu aceasta citire:

Cod:

    f = fopen("petrica.in", "r");
    fscanf(f, "%d\n", &N);
    for (i = 0; i < N; i++)
        fscanf(f, "%d", A + i);
    for (i = 0; i < N - 1; i++)
        fscanf(f, "%d %d", &j, &k), j--, k--,
        G[j][Deg[j]++] = k, G[k][Deg[k]++] = j;
    fclose(f);

[•horax]

Eu cred ca am o singura problema la rezolvare. Din problema nu-mi dau exact seama cum sa determin radacina.

Are cineva vreo idee.

[•filipb]

Agata pur si simplu arborele in nodul 1 ( considera radacina = 1 ) si porneste algoritmul tau ( nu conteaza ce radacina alegi, rezultatul e acelasi... ).

[u-92]

are ceva special testul 3? iau WA pe el
am obtinut un algoritm O(n^2*log(n)+n^3).. intai fac lca iar apoi iau 3 noduri si elimin muchiile [i-tata] si calculez cele 4 sume in functie de cazurile care apar

[•cristy]

testul 10 e smecher?

l-am facut...intre timp

[•alex_prg]

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

[ditzone]

Da.. O(n^3) intra in timp...

[•tm_radu]

Cat va da pe:

Cod:

13
2 1 1 2 1 1 1 2 1 2 2 2 1
1 2
2 6
3 4
4 5
4 6
6 8
6 13
7 8
8 9
9 10
11 13
12 13

?  multumesc anticipat

[•bogdan2412]

2

[•tm_radu]

da....mersi....am luat 100 intre timp 

[•devilkind]

ce au in comun testele 2 4 5 7 8 de iau WA pe ele  , nu inteleg, pur si simplu citesc muchiile, imi creez vectoru de tati cu ajutoru unui DF, apoi parcurg toate nodurile de la 2 la n (agat arborele in nodul 1), si elemin muchia i - arb ( arb - vectoru de tati), si apoi calculez suma ptr fiecare subarbore creeat (cel cu radacina in 1, i,j,k respectiv), si vad diferenta dintre maxim si minim.

[Later edit] am incercat sa citesc si pana la eof dar tot aia

[•k_ounu_eddy]

La problema asta sunteti siguri ca structura e un arbore?Eu as crede ca e un graf.

[•gabitzish1]

La problema asta sunteti siguri ca structura e un arbore?Eu as crede ca e un graf.

N orase conectate prin strazi bidirectionale astfel incat exista un drum unic intre oricare doua dintre ele.

Din asta eu inteleg ca e graf neorientat, conex si fara cicluri => arbore.

[•k_ounu_eddy]

Da ,ai dreptate,nu am fost atent la precizarea cum ca ar exista un drum unic intre 2 orase.
[EDIT]:Am facut problema si nu am luat decat 10p.Vrand sa observ unde cade programul meu,am zis sa introduc testul lui Toma Radu,dar din cate observ ala nu ii un arbore,deoarece nodul 6 are doi tati.Gresesc eu cu ceva?

[•gabitzish1]

Da, gresesti undeva Testul respectiv e corect, si muchiile alea formeaza un arbore.
In fisierul de intrare poti sa gasesti muchia 1 - 2 sau 2 - 1 avand aceeasi semnificatie. Daca observi, sunt 4 muchii legate de nodul 6:(2,6) (4,6) (6,8) si (6,13), dar asta nu inseamna ca 6 are 2 tati si 2 fii ci doar faptul ca 6 e legat prin muchie de nodurile 2, 4, 8, 13.
Arbore = graf neorientat conex si aciclic. (Nu trebuie neaparat sa aiba o radacina si o ierarhie "X este tatal lui Y").