•domino
|
|
« : Iunie 05, 2005, 19:57:54 » |
|
Aici puteţi discuta despre problema Concurs.
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #1 : Iunie 09, 2005, 12:01:09 » |
|
Sal.. Am si eu o intrebare care pur si simplu ma scoate din sarite. La problema asta imi tot da pe ultimele 7 teste ceva de genul "MEMORY LIMIT EXCEED!" ( cred ca ultimele teste au toate N = 32000 si difera doar prin numarul de query-uri ). In programul meu am declarat urmatoarele ( avand NMax = 32000) - arborele propriu-zis l-am retinut ca referinte de tip "primul fiu-urmatorul frate" ( 2 * NMax ) - vectorul ( de lungime NMax ) pt. costurile pe fiecare nod ------ pt LCA am folosit: - un vector (cu NMax ) pt adancimea fiecarui nod - parcurgerea euler a nodurilor ( cu 2*NMax-1 pozitii ) - un arbore de intrevale care retine pozitia minimului pe intervalul din fiecare nod ( in total [2*(2*NMax - 1)-1] = 4*NMax-3 pozitii ). Cam asta am folosit... SI IMI DA "MEMORY EXCEED!". Se poate micsora cumva memoria cu pastrarea efectuarii unui query in timp logN? PLS... ASTEPT UN RASPUNS... bubbleSORT
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #2 : Iunie 09, 2005, 12:35:20 » |
|
Sal.. Am si eu o intrebare care pur si simplu ma scoate din sarite. La problema asta imi tot da pe ultimele 7 teste ceva de genul "MEMORY LIMIT EXCEED!" ( cred ca ultimele teste au toate N = 32000 si difera doar prin numarul de query-uri ). In programul meu am declarat urmatoarele ( avand NMax = 32000) - arborele propriu-zis l-am retinut ca referinte de tip "primul fiu-urmatorul frate" ( 2 * NMax ) - vectorul ( de lungime NMax ) pt. costurile pe fiecare nod ------ pt LCA am folosit: - un vector (cu NMax ) pt adancimea fiecarui nod - parcurgerea euler a nodurilor ( cu 2*NMax-1 pozitii ) - un arbore de intrevale care retine pozitia minimului pe intervalul din fiecare nod ( in total [2*(2*NMax - 1)-1] = 4*NMax-3 pozitii ). Cam asta am folosit... SI IMI DA "MEMORY EXCEED!". Se poate micsora cumva memoria cu pastrarea efectuarii unui query in timp logN? PLS... ASTEPT UN RASPUNS... bubbleSORT "Invalid memory reference" nu inseamna memorie depasita neaparat! Intra aici http://info.devnet.ro/forum/viewtopic.php?t=364 si poate te lamuresti despre ce ar mai putea fi vorba.
|
|
|
Memorat
|
|
|
|
•DeadStar
Client obisnuit
Karma: 2
Deconectat
Mesaje: 59
|
|
« Răspunde #3 : Iunie 09, 2005, 13:26:04 » |
|
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #4 : Iunie 22, 2005, 15:20:02 » |
|
Da... m-am prins ce avea... Eu declaram arborele de intervale un vector de lungime 4*NMax - 1, cand de fapt trebuia declarat de lungime 2^K, a.i. 2^K >= 4*NMax-1. De fapt scria si in referatu' de la lot, dar nici nu mi-am dat seama k e f. importanta linia aia si am trecut peste ea fara sa o judec... Avem impresia ca pt un arbore cu X noduri trebuiesc alocate exact X zone de memorie... ca la heap... mi-a luat 3/2 ore sa ma prind...
|
|
|
Memorat
|
|
|
|
•silviug
|
|
« Răspunde #5 : Iunie 22, 2005, 15:59:47 » |
|
Si ajungem la vorba de aur: "mai bine gandesti 5 minute in plus cand scrii codu decat sa debughezi 45" [later edit: sau chiar 90]
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•bogdan2412
|
|
« Răspunde #6 : Iulie 02, 2005, 14:14:50 » |
|
Ce e "Referatu' de la lot" ?
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #7 : Iulie 02, 2005, 14:38:36 » |
|
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #8 : Iulie 06, 2005, 12:41:10 » |
|
Cu ce e diferit testul 8 fata de celelalte, ca nu-mi iese deloc? Am folosit exact acelasi cod pentru LCA pe care l-am folosit si la problema Atac la care am maxim.
|
|
|
Memorat
|
|
|
|
•silviug
|
|
« Răspunde #9 : Iulie 06, 2005, 20:47:34 » |
|
concluzia: nu mai refolosi cod!
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•bogdan2412
|
|
« Răspunde #10 : Iulie 07, 2005, 11:45:54 » |
|
Pai intai am facut Concurs si n-a iesit decat de 90 puncte si dupa aia am facut Atac pe baza sursei de la Concurs, fara sa modific nimic legat de LCA. Nu pot sa inteleg de ce nu merge problema asta...
|
|
|
Memorat
|
|
|
|
•DeadStar
Client obisnuit
Karma: 2
Deconectat
Mesaje: 59
|
|
« Răspunde #11 : Iulie 07, 2005, 20:22:15 » |
|
M-am uitat si nu este special. De asemenea nu este cel mai mare.
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #12 : August 02, 2005, 20:11:50 » |
|
La problema asta parcurgerea euler trebuie facuta cumva iterativ? Eu am facut recursiv si nu merg decat primele 2 teste, in rest WA. Am trimis rezolvare cu arbore de intervale si rezolvare dailalta pe intervale de puteri ale lui 2 si acelasi rezultat.
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•vladcyb1
|
|
« Răspunde #13 : August 05, 2005, 10:57:54 » |
|
Problema asta imi mananca zilele!!! Am trimis brute-force si nu iau nici un TLE. Primele 2 teste OK, in rest "Incorect sau fisier de iesire lipsa". Am facut parcurgerea iterativ, recursiv nici o varianta nu ia mai mult de 20 de puncte. Poate cineva macar sa vada daca functioneaza corect evaluarea la problema asta. (cei care au luat 100 sa mai trimita inca o data si sa-mi zica si mie daca functioneaza).
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•Dorin
Client obisnuit
Karma: 7
Deconectat
Mesaje: 73
|
|
« Răspunde #14 : August 05, 2005, 13:41:57 » |
|
la problema aceasta nu am inteles cand 1 sefule lui 2 shi 3 ii seful lui 4 seful comun la echipa 2 cu 4 care este !!!ei nu mai au alti sefi 1 sau 3
|
|
|
Memorat
|
Smile ! ... tomorow will be worse
|
|
|
cristi8
Vizitator
|
|
« Răspunde #15 : August 05, 2005, 18:41:46 » |
|
citeste mai atent enuntul.. in primul rand, zice la inceput ca e arbore.. si in al doilea rand, la date de intrare zice asa: Urmatoarele N-1 linii contin cate doua numere X,Y care descriu ierarhia firmei(X este seful lui Y). ..adica N-1 angajati AU sef.. => e doar o radacina
|
|
|
Memorat
|
|
|
|
•Dorin
Client obisnuit
Karma: 7
Deconectat
Mesaje: 73
|
|
« Răspunde #16 : August 05, 2005, 19:23:31 » |
|
no bine atunci ms ser pare ca ar trebui sa fiu mai atent cand citesc un enunt
|
|
|
Memorat
|
Smile ! ... tomorow will be worse
|
|
|
u-92
Vizitator
|
|
« Răspunde #17 : Decembrie 21, 2005, 20:06:46 » |
|
M*log(N) este de ajuns pt problema asta? eu iau TLE pe ultimele 5 teste (mai iau si doua WA`uri nustiu de ce.. )
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #18 : Martie 08, 2006, 22:14:09 » |
|
am si eu o nelamuririe...
un angajat poate sa aiba mai multi sefi?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
u-92
Vizitator
|
|
« Răspunde #19 : Martie 08, 2006, 22:40:59 » |
|
nu, contrazice enuntul care zice ca firma are o structura ierarhica in forma de arbore
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #20 : Martie 08, 2006, 23:13:14 » |
|
adica fisierul asta nu e corect?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•DeadStar
Client obisnuit
Karma: 2
Deconectat
Mesaje: 59
|
|
« Răspunde #21 : Martie 08, 2006, 23:22:59 » |
|
Nu este bun. 2 are doi sefi, iar 3 apare si ca sef si ca subaltern al nodului 2.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #22 : Martie 08, 2006, 23:28:28 » |
|
2 nu este seful lui 3. ultima pereche e interogare . eu am in prog meu asa ceva: for i:=1 to n-1 do begin readln(f,a,b); viz[b]:=true; ...... end;
for i:=1 to n do if not viz[i] then radacina:=i;
daca faceam ultimul for de la n la 1 obtineam mai putine pct... deasemenea schimband modalitatea de aflare a radacinii luam testele pe care le acum le pic... algoritmul eu zic ca e bun.. fac LCA in O(1).
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•DeadStar
Client obisnuit
Karma: 2
Deconectat
Mesaje: 59
|
|
« Răspunde #23 : Martie 08, 2006, 23:36:28 » |
|
da am uitat de interogari.. oricum nu este bun testul. O chestie de genul for i:=1 to n sau for i:= n downto 1 influenteaza mult. Mie mi se pare clar ca gresesti ceva minor la rezolvare. Am impresia ca testele cate nu-ti merg sunt mai mari. Eventual verifica limitele, iar daca tot nu vezi nimic implementeaza din nou.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #24 : Martie 09, 2006, 16:32:40 » |
|
mersi pentru lamuriri.
intre timp mi-am dat seama ce busea. nu era vina programului meu, era compilatorul de pascal.
SFAT pt cei care lucreaza in pascal: renuntati la instructiunea readln. in mom in care am schimbat toti readln in read, a mers de 100.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|