•fluffy
|
|
« : 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 !! 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 ?? (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
|
|
« 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
|
|
« Răspunde #5 : August 28, 2004, 17:32:29 » |
|
: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 » |
|
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
|
|
« 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... 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
|
|
« Răspunde #10 : Martie 16, 2005, 19:21:12 » |
|
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... Scuzati repetitia excesiva a cuvantului recursiv... Eu am implementat DF-ul recursiv si mi-a mers de 100
|
|
|
Memorat
|
|
|
|
•svalentin
|
|
« 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
Mesaje: 42
|
|
« 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
Mesaje: 59
|
|
« 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.
|
|
|
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
Mesaje: 42
|
|
« Răspunde #15 : Mai 05, 2005, 19:46:52 » |
|
|
|
|
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 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
|
|
« 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... 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
|
|
« Răspunde #19 : Decembrie 06, 2005, 13:33:25 » |
|
Poti s-o faci oricand in O(N + M)
|
|
|
Memorat
|
|
|
|
•fireatmyself
|
|
« 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)
|
|
|
Memorat
|
Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
|
|
|
•Coty
|
|
« Răspunde #21 : Decembrie 28, 2005, 21:29:02 » |
|
daca a e tatal lui i, avem neaparat a<i (ca valoare)
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #22 : Decembrie 28, 2005, 21:44:39 » |
|
Nu cred ca e neaparat, dar, totusi, la ce-ti trebuie sa stii asta?
|
|
|
Memorat
|
|
|
|
•Coty
|
|
« 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... ramane de vazut
|
|
|
Memorat
|
|
|
|
•svalentin
|
|
« 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
|
|
|
|
|