1089 TractoMarm

[•pauldb]

Aici puteţi discuta despre problema TractoMarm.

[•marius21]

Genial numele... 

[•mrares]

Care este complexitatea care intra in timp ?
Eu faceam dfs initial si aflam distantele din 1 la restul si pentru fiecare muchie noua cautam sa vad daca pot "minimza" prin x, sau y... tot un fel de dfs cat timp vecinul nu e blocat si distanta de la 1 la el e mai mare decat distanta de la 1 la x sau y la el.

[•octav]

O optimizare este sa observi ca numarul de noduri care trebuie vizitate pentru un query poate fi mai mic.

Presupunem ca dist(x) < dist(y) (altfel se inverseaza x si y).

In primul rand, y si fiecare din copii lui y vor micsora suma distantelor cu dist(y) - dist(x) fiecare. Niciunul din copiii lui y nu trebuie vizitati (trebuie doar sa se calculeze cati copii are fiecare nod din arbore, lucru care se poate face in DFS-ul initial).

Apoi, daca se calculeaza z = LCA(x, y), se observa ca este de ajuns sa se viziteze numai nodurile dintre y si z, mergand pe parinti (care se calculeaza tot in DFS-ul initial). Contributia copiilor nodurilor de pe calea dintre y si z (exceptand copiii care fac parte din cale) se calculeaza ca mai sus.

Cu un LCA banal, se scot 40p. Nu stiu daca un LCA in O(1) ajunge pentru 100p, poate mai trebuie si alte smecherii

Later edit: rationamentul de mai sus e valid, dar LCA-ul e complet inutil (de fapt, nici nu foloseam rezultatul LCA-ului). Trebuie sa fie alta smecherie pt 100p.

[•Bit_Master]

Muchiile create de intrebari raman si la intrebarile urmatoare?

[•Florian]

Nu.

[•Bit_Master]

Eu iau 0 puncte si nu inteleg greseala rationamentului.(WA peste tot)
Calculez pt fiecare elem suma partiala a arborelui sau (egala cu adancimea sa + adancimile tuturor fiilor sai), numarul total de fii ai fiecarui nod prin dfs.
Apoi pt fiecare intrebare pur si simplu:
-notez TATA nodul mai putin adanc si FIUL nodul mai adanc al perechii care formeaza noua muchie
Acum ii scade adancimea FIULUI cu
h_vechi - h_nou
unde h_nou = h_TATA + 1 (FIUL se leaga de tata)

tot la fel de mult va scadea adancimea la toti fii sai

=> raspuns s[1] (suma adancimilor tuturor) - (nr_fii[FIU] + 1)*(h[FIU] - h[TATA] - 1)

Am testat mai multe exemple si-mi da corect pe toate testele mele si totusi iau 0. F ciudat.

[•Florian]

Vezi ca se modifica mai multe noduri, nu doar cele din subarborele lui FIU.

[•Bit_Master]

Vezi ca se modifica mai multe noduri, nu doar cele din subarborele lui FIU.

De fapt eu nici nu folosesc s-ul. Folosesc doar suma adancimilor intregului arbore (s[1]). Ideea e ca doar la nodul FIU si la fii sai se modifica adancimea... la care alte noduri sa se mai modifice adancimea (stiu ca s[punctul unde era legat] si s[TATA] se schimba, dar eu de fapt nici nu le folosesc.)

[•skull]

Se mai modifica si unii dintre stramosi, chiar si fii de stramosi, ci nu doar fiii nodului pentru care se imbunatateste distanta.

[•Bit_Master]

Se mai modifica si unii dintre stramosi, chiar si fii de stramosi, ci nu doar fiii nodului pentru care se imbunatateste distanta.

adancimea lor se modifica?
Cred ca un contraexemplu ar fi cel mai bun.

[•andrei.12]

Nicaieri in enunt nu este prezent cuvantul adancime, ci distanta de la nodul 1 la celelalte (oricum cand adaugi o muchie, graful nu mai e arbore, deci nu mai exista notiunea de adancime).
Un contraexemplu bun ar fi chiar exemplul problemei, daca nu ma insel.

[•AndrewTheGreat]

Eu nu inteleg de nici o culoare unde am gresit in rationamentu meu...

Pornesc de la premiza ca pentru fiecare nod exista un drum minim din radacina la el, rezulta ca fiecare nod e influentat de distanta pana la tatal lui, si anume dist[tata] + 1.

Bun, atunci introducand o muchie intre x si y ( unde dist[ x ] < dist[y] ) verific daca se inbunatateste distanta pana la y, daca da atunci fiecare din fii lui si el o sa isi inbunatateasca distanta cu = dist veche [y] - dist noua [y]. La urmatoru pas ma duc la tata(y) unde verific daca pot aduce noi inbunatatiri ca distanta pana la el, daca da repet algoritmu, avand grija sa nu actualizez ramura de pe care am venit.


Daca vedeti greseli in rationament as fi recunoscator daca imi spuneti si mie  .

[•DraStiK]

Pai idea e buna. Da nu optima. Obtii 40p cu ideea ta.

[•Bit_Master]

Nicaieri in enunt nu este prezent cuvantul adancime, ci distanta de la nodul 1 la celelalte (oricum cand adaugi o muchie, graful nu mai e arbore, deci nu mai exista notiunea de adancime).
Un contraexemplu bun ar fi chiar exemplul problemei, daca nu ma insel.

Da, m-am prins pe urma. Exemplul mergea si asa. Ms.

[•AndrewTheGreat]

Pai cu idea de mai sus obtin 0 pct, si iau numa "Incorect"...  

LE: Merci Marcule, am avut o revelatie citind inca o data sursa si enunutu  .

Apropo 1 nu este radacina intotdeauna, nu ? 

[•Florian]

Pai nu trebuie sa ai o revelatie ca sa iti dai seama ca gresesti la implementare.

[•BalcauIonut]

Nu inteleg ce gresesc..
Am precalculat numarul de fii si pt fiecare intrebare apelez:

Cod:

querry(y,cost[x]+1);

Si functia:

Cod:

void querry(int x,int cnou){      //x este nodul pe care lucrez, cnou este noul cost minim pe care il are daca se foloseste muchia adaugata
    if(cnou<cost[x]){                //daca este imbunatatit
    rez+=(fii[x]+1-upd)*(cost[x]-cnou);  //scad din costul total costul sau - costul nou, adica imbunatatirea, pentru fiecare fiu al sau care nu a fost deja calculat si pentru el insusi
    upd=fii[x]+1;  //updatez numarul de noduri luate in calcul
    querry(tata[x],cnou+1);  //calculez pentru stramosul sau, costul fiind incrementat cu o unitate
    }
 }

mi se pare o rezolvare logica. probabil ca nui cea mai eficienta da in fine..
ma poate ajuta cineva?

[•crushack]

Intrebare:  la problema asta exista o solutie mai buna ca O(NlgN + MlgN) ? Ca mie nu-mi intra in timp 

[•andrei.12]

Da, solutia noastra are O(m + n)

[•dutzul]

am o intrebare , sunt adaugate mai multe muchii sau doar 1 ,ca nu ma prind (adica de fiecare data se adauga o muchie la arborele initial si dupa se sterge?)

[•klamathix]

Muchiile adaugate la fiecare query sunt ipotetice, nu raman in graf. Se vede asta din cerinta, din exemplu si de pe forum unde s-a mai raspuns o data la intrbarea asta .

[•dutzul]

mda ai dreptate dar totusi nu reiese din exemplu asta,m-am uitat pe foaie ,chiar daca lasi muchiile raspunsul e tot acelasi.Am citit comenturile in fuga si n-am observat intrebarea.Oricum mersi de raspuns.

[•mihaipopa12]

Cred ca ar trebui marita limita de timp la aceasta problema.
Am scris o sursa O(n+m) si ia 70 de puncte cu citirea parsata.

[•wefgef]

Done!