Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 1089 TractoMarm  (Citit de 3816 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« : Decembrie 05, 2010, 13:51:24 »

Aici puteţi discuta despre problema TractoMarm.
Memorat

Am zis Mr. Green
marius21
Strain
*

Karma: -20
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #1 : Decembrie 05, 2010, 14:55:47 »

Genial numele...  Rolling on the Floor Laughing
Memorat
mrares
Strain


Karma: -5
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #2 : Decembrie 05, 2010, 15:12:04 »

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.
« Ultima modificare: Decembrie 05, 2010, 15:17:19 de către Mardare Rares » Memorat
octav
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #3 : Decembrie 05, 2010, 15:41:57 »

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 Smile

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.
« Ultima modificare: Decembrie 05, 2010, 15:55:27 de către Octavian Voicu » Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #4 : Decembrie 05, 2010, 20:41:12 »

Muchiile create de intrebari raman si la intrebarile urmatoare?
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #5 : Decembrie 05, 2010, 20:44:51 »

Nu.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #6 : Decembrie 05, 2010, 20:46:01 »

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.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #7 : Decembrie 05, 2010, 20:47:18 »

Vezi ca se modifica mai multe noduri, nu doar cele din subarborele lui FIU. Smile
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #8 : Decembrie 05, 2010, 20:58:34 »

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

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.) Think
Memorat
skull
Client obisnuit
**

Karma: 17
Deconectat Deconectat

Mesaje: 75



Vezi Profilul
« Răspunde #9 : Decembrie 05, 2010, 21:11:31 »

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

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #10 : Decembrie 05, 2010, 21:35:26 »

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.
Memorat
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« Răspunde #11 : Decembrie 05, 2010, 22:22:35 »

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.
Memorat
AndrewTheGreat
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 15



Vezi Profilul
« Răspunde #12 : Decembrie 07, 2010, 18:45:44 »

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  Smile.
« Ultima modificare: Decembrie 07, 2010, 19:12:24 de către Andrei Alexandrescu » Memorat
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #13 : Decembrie 08, 2010, 17:22:42 »

Pai idea e buna. Da nu optima. Obtii 40p cu ideea ta.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #14 : Decembrie 08, 2010, 17:35:05 »

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.
Memorat
AndrewTheGreat
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 15



Vezi Profilul
« Răspunde #15 : Decembrie 08, 2010, 18:17:40 »

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

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

Apropo 1 nu este radacina intotdeauna, nu ?  Rolling Eyes
« Ultima modificare: Decembrie 10, 2010, 23:12:07 de către Andrei Alexandrescu » Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #16 : Decembrie 09, 2010, 09:17:47 »

Pai nu trebuie sa ai o revelatie ca sa iti dai seama ca gresesti la implementare. Smile
Memorat
BalcauIonut
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #17 : Aprilie 05, 2011, 11:27:04 »

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?
« Ultima modificare: Aprilie 05, 2011, 11:49:23 de către Balcau Ionut » Memorat
crushack
De-al casei
***

Karma: 23
Deconectat Deconectat

Mesaje: 108



Vezi Profilul
« Răspunde #18 : Mai 29, 2011, 00:19:40 »

Intrebare:  la problema asta exista o solutie mai buna ca O(NlgN + MlgN) ? Ca mie nu-mi intra in timp  Brick wall
Memorat
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« Răspunde #19 : Mai 29, 2011, 08:39:00 »

Da, solutia noastra are O(m + n)
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #20 : August 30, 2012, 00:12:01 »

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?)
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #21 : August 30, 2012, 00:27:49 »

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 Rolling Eyes.
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #22 : August 30, 2012, 02:35:21 »

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. Very Happy
« Ultima modificare: August 30, 2012, 02:40:50 de către Bodnariuc Dan-Alexandru » Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #23 : Noiembrie 03, 2012, 18:35:07 »

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.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #24 : Noiembrie 03, 2012, 19:15:58 »

Done!
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines