Pagini: [1] 2 3 4   În jos
  Imprimă  
Ajutor Subiect: 010 Stramosi  (Citit de 27465 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
fluffy
Echipa infoarena
De-al casei
*****

Karma: 71
Deconectat Deconectat

Mesaje: 146



Vezi Profilul
« : Martie 08, 2004, 20:01:13 »

Aici puteţi discuta despre problema Stramosi.
Memorat
Chris
Vizitator
« Răspunde #1 : August 05, 2004, 17:46:25 »

Buna Very Happy !!

Care este complexitatea "oficiala" la problema stramosi ?

Eu am trimis o sursa cu complexitate (N+M)*log(N) si imi merg 9 teste (nu mi se incadreaza in timp al 9 - lea test!!!). Am incercat sa optimizez programul si tot 90 de puncte ia (in for-ul de la 1 la m am operatii rapide - incrementari, atribuiri, "&" pe biti, si shiftari)... Exista cumva o complexitate mai buna Huh?? (sau singura metoda de a lua 100 de puncte e sa rescriu codul in limbaj de asamblare).
Memorat
andreit1
Vizitator
« Răspunde #2 : August 07, 2004, 22:37:05 »

Exista o solutie de complexitate n+m*log(n) care e suficienta pentru 100 de puncte. Deci probabil ar fi bine sa lasi deoparte rezolvarea gasita de tine si sa cauti alta.
Memorat
wickedman
Echipa infoarena
Nu mai tace
*****

Karma: 227
Deconectat Deconectat

Mesaje: 670



Vezi Profilul WWW
« Răspunde #3 : August 12, 2004, 01:33:32 »

multi au luat 80-90 de puncte la aceasta problema pentru ca au spart linia de cache de prea multe ori (eg. in loc sa mearga in principal pe linii si dupa aceea pe coloane - asa cum ai citi dintr-o carte sau, mai bine zis, din RAM  :lol: ) au mers cu indicii rasturnati.
Memorat
Chris
Vizitator
« Răspunde #4 : August 28, 2004, 14:21:48 »

:cry: Sincer sa fiu, nu prea am idei pentru complexitate N+M*log(N). Putin ajutor, va rog !!! Pentru fiecare nod retin stramosii cu ordinul putere a lui 2, si pentru a afla al k lea stramos folosesc reprezentarea binara a lui k pt descompunere!! (poate chestia asta imi cam da peste cap cache-ul!!) (desi folosesc numai shiftari, atribuiri si & pe biti (care iau in jur de 1 ciclu de procesor!))
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #5 : August 28, 2004, 17:32:29 »

Citat din mesajul lui: Chris
:cry: Sincer sa fiu, nu prea am idei pentru complexitate N+M*log(N). Putin ajutor, va rog !!! Pentru fiecare nod retin stramosii cu ordinul putere a lui 2, si pentru a afla al k lea stramos folosesc reprezentarea binara a lui k pt descompunere!! (poate chestia asta imi cam da peste cap cache-ul!!) (desi folosesc numai shiftari, atribuiri si & pe biti (care iau in jur de 1 ciclu de procesor!))


Probabil ca tu ai acolo acolo o matrice A[j] care zice al 2^j-lea stramos al nodului i... incearca sa tii in schimb in A[j] = al 2^i-lea stramos al nodului j (inverseaza dimensiunile).. vezi daca merge
Memorat
Chris
Vizitator
« Răspunde #6 : Septembrie 01, 2004, 17:33:14 »

Very Happy Mersi pentru sfat!!!! Am luat 100 de puncte daca am inversat indicii si am optimizat citirea/scrierea in fisier!!!
Memorat
cristi8
Vizitator
« Răspunde #7 : Februarie 25, 2005, 11:49:29 »

mmm... eu am facut O(N+M) si am luat 100... seamana f mult cu problema "cerere", dar mai trebuiau niste kestii in plus..
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #8 : Martie 16, 2005, 18:59:02 »

La problema aceasta e a treia oara cand mi se imtampla urmatorul lucru: fac problema recursiv si... doua teste ratate din cauza ca stiva e prea mica. Am stat mult pana sa-mi dau seama de ce imi da RUN ERROR - Invalid memory reference
E vreo metoda de a mari stiva cu 100-200 kilo astfel incat sa mearga o rezolvare recursiva? Nu pot sa fac si eu cautare in adancime recursiva... Sad

Scuzati repetitia excesiva a cuvantului recursiv...
Memorat
VladS
Vizitator
« Răspunde #9 : Martie 16, 2005, 19:01:18 »

Poti sa simulezi stiva prin folosirea unui vector. Astfel algoritmul devine iterativ.
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #10 : Martie 16, 2005, 19:21:12 »

Citat din mesajul lui: bogdan2412
La problema aceasta e a treia oara cand mi se imtampla urmatorul lucru: fac problema recursiv si... doua teste ratate din cauza ca stiva e prea mica. Am stat mult pana sa-mi dau seama de ce imi da RUN ERROR - Invalid memory reference
E vreo metoda de a mari stiva cu 100-200 kilo astfel incat sa mearga o rezolvare recursiva? Nu pot sa fac si io cautare in adancime recursiva... Sad

Scuzati repetitia excesiva a cuvantului recursiv...


Eu am implementat DF-ul recursiv si mi-a mers de 100  Eh?
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #11 : Martie 16, 2005, 19:58:03 »

Vezi daca poti sa mai elimini din variabilele care le transferi functii!
Memorat
calinux
Strain
*

Karma: 5
Deconectat Deconectat

Mesaje: 42



Vezi Profilul
« Răspunde #12 : Mai 04, 2005, 21:09:36 »

La problema asta, prima mea idee a fost pur si simplu sa scriu o functie recursiva care sa il intoarca pe a[a[a[a[a[a[a[a[....[q]]]]]]..]], unde a este vectorul. O astfel de abordare mi-a adus 80 de puncte. Luam TLE la ultimele 2. Am incercat sa retin stramosii 2^K, si am facut asta folosind o functie similara, dar asa, chiar si cu putine optimizari am luat 70 de puncte (3 TLE-uri).  :cry:  Cum as putea sa memorez mai repede stramosii de ordin 2^K decat parcurgand vectorul de tati pt. fiecare si cand ajung la o putere de a lui 2 sa o retin? Poate cineva sa ma ajute?
Memorat

"And all that is now,
And all that is gone,
And all that's to come,
And everything under the sun is in tune
But the sun is eclipsed by the moon"
The Dark Side of The Moon - Pink Floyd
DeadStar
Client obisnuit
**

Karma: 2
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #13 : Mai 04, 2005, 21:34:48 »

Ai facut si cu operatii pe biti? Mai este o alta metoda de rezolvare asemanatoare cu cea de la problema Cerere, este si ceva hint la articole.
 Cool
Memorat

Chris
Vizitator
« Răspunde #14 : Mai 05, 2005, 14:18:26 »

Poti sa calculezi matricea a[logN][N] , unde a[k] = cel de-al 2^k-lea stramos al lui i. O poti calcula in O(N*log(N)) prin relatia de recurenta :
a[k] = a[k-1][ a[k-1] ] (te folsesti de ce ai calculat deja).
Eu am obtinut 100 de puncte cu chestia asta (se raspunde la fiecare intrebare in O(log(N))) dar poti face ceva asemanator rezolvarii la problema "cerere" si sa raspunzi in O(1).
Memorat
calinux
Strain
*

Karma: 5
Deconectat Deconectat

Mesaje: 42



Vezi Profilul
« Răspunde #15 : Mai 05, 2005, 19:46:52 »

Am reusit.  Dancing  Mersi Chris. Aici greseam. imediat ce am facut ca tine am luat 100. Trebuia sa imi fii dat seama k avand im matrice precedentul pot determina curentul. d'oh!  d'oh!  d'oh!  Embarassed  Embarassed  Embarassed

Mersi mult si bafta in continuare!  wink
Memorat

"And all that is now,
And all that is gone,
And all that's to come,
And everything under the sun is in tune
But the sun is eclipsed by the moon"
The Dark Side of The Moon - Pink Floyd
vladut.forum
Vizitator
??
« Răspunde #16 : Iulie 29, 2005, 18:58:48 »

Eu iau numai 40 pct si nustiu de ce... matricea A o calculez corect
Cod:

fin>>p>>q;
stramos=p;

while (q>0) {
rr=1; count=0; varza=q;
while (varza>0) {count++; varza/=2;rr*=2;} rr/=2; count--;
      q-=rr;
      stramos=v[count][stramos];
      rr/=2;
      count--;
   }
  fout<<stramos<<'\n';
          }

ce  am gresit in aflarea al q-lea stramos a lui p... la ultimele doua teste iau TLE iar la restu WA si Correct (in total 40 puncte)
Memorat
vladut.forum
Vizitator
« Răspunde #17 : Iulie 30, 2005, 12:17:54 »

Acum am facut alfel, fac reprezentarea binara a lui Q... si aflu exact ce si cum.. acu astept sa reina evaluatorul ca vad ca e oprit pentru un timp...
Memorat
fireatmyself
Nu mai tace
*****

Karma: 35
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #18 : Decembrie 06, 2005, 11:53:19 »

io fac 4*N+M*log(N) (nu fac liste, fac cu alocare dinamica) si iau TLE la ultimele 2 teste...  Brick wall
1.2 e "la limita" dupa parerea mea. ar trebui sa fie un pic mai mult timp
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #19 : Decembrie 06, 2005, 13:33:25 »

Poti s-o faci oricand in O(N + M)  Whistle
Memorat
fireatmyself
Nu mai tace
*****

Karma: 35
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #20 : Decembrie 06, 2005, 20:27:25 »

pai am facut o(N+M), dar vreau sa iau max si cu solutia N+M*log(N)  Whistle
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #21 : Decembrie 28, 2005, 21:29:02 »

daca a e tatal lui i, avem neaparat a<i (ca valoare) Huh
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #22 : Decembrie 28, 2005, 21:44:39 »

Nu cred ca e neaparat, dar, totusi, la ce-ti trebuie sa stii asta? Anxious
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #23 : Decembrie 28, 2005, 21:46:38 »

pei daca era, atunci ... cum sa zic, pentru tatal lui i (pe care deja il procesasem) puteam sa retin intr-un fel lista de stramosi, asa ca al k-lea stramos al lui i era al (k-1)-lea stramos al lui a... da daca nu e... Sad ramane de vazut
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #24 : Decembrie 28, 2005, 21:54:43 »

nu stiu daca am inteles exact ce zici, dar daca da, incearca sa faci o sortare topologica si o sa se aplice conditia intrebata de tine (tatal lui i e in stanga lui i in sirul sortat topologic)

sau.. poti sa aplici aceeasi gandire, dar nu parcurgi nodurile de la 1 la N, ci de la radacina la frunza printr-o parcurgere in adancime ceva..
Memorat
Pagini: [1] 2 3 4   În sus
  Imprimă  
 
Schimbă forumul:  

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