|
Titlul: 071 Concurs Scris de: Mircea Pasoi din Iunie 05, 2005, 19:57:54 Aici puteţi discuta despre problema Concurs (http://infoarena.ro/problema/concurs).
Titlul: Algoritmul LCA Scris de: Filip Cristian Buruiana din 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... [-o< :) bubbleSORT Titlul: Re: Algoritmul LCA Scris de: Mircea Pasoi din Iunie 09, 2005, 12:35:20 Citat din mesajul lui: filipb 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... [-o< :) 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. Titlul: 071 Concurs Scris de: Ionel Corneliu Gog din Iunie 09, 2005, 13:26:04 hmm..testul 4 nu-i chiar asa de mare. Ai citit http://info.devnet.ro/articole.php?page=art&art=19 ?
Titlul: M-am prins... Scris de: Filip Cristian Buruiana din 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... =D>
Titlul: 071 Concurs Scris de: Silviu-Ionut Ganceanu din 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]
Titlul: 071 Concurs Scris de: Bogdan-Cristian Tataroiu din Iulie 02, 2005, 14:14:50 Ce e "Referatu' de la lot" ?
Titlul: 071 Concurs Scris de: Mircea Pasoi din Iulie 02, 2005, 14:38:36 Citat din mesajul lui: bogdan2412 Ce e "Referatu' de la lot" ? http://info.devnet.ro/download.php?page=cat&cat=24 Titlul: 071 Concurs Scris de: Bogdan-Cristian Tataroiu din 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.
Titlul: 071 Concurs Scris de: Silviu-Ionut Ganceanu din Iulie 06, 2005, 20:47:34 concluzia: nu mai refolosi cod! :P
Titlul: 071 Concurs Scris de: Bogdan-Cristian Tataroiu din 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... :(
Titlul: 071 Concurs Scris de: Ionel Corneliu Gog din Iulie 07, 2005, 20:22:15 M-am uitat si nu este special. De asemenea nu este cel mai mare.
Titlul: 071 Concurs Scris de: Vlad Berteanu din 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. :-k
Titlul: 071 Concurs Scris de: Vlad Berteanu din 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).
Titlul: 071 Concurs Scris de: Oltean Dorin din 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 :-k Titlul: 071 Concurs Scris de: cristi8 din 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: Citat 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 Titlul: 071 Concurs Scris de: Oltean Dorin din August 05, 2005, 19:23:31 no bine atunci ms ser pare ca ar trebui sa fiu mai atent cand citesc un enunt #-o
Titlul: 071 Concurs Scris de: u-92 din 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.. :mrgreen: ) Titlul: 071 Concurs Scris de: Andrei Grigorean din Martie 08, 2006, 22:14:09 am si eu o nelamuririe...
un angajat poate sa aiba mai multi sefi? Titlul: 071 Concurs Scris de: u-92 din Martie 08, 2006, 22:40:59 nu, contrazice enuntul care zice ca firma are o structura ierarhica in forma de arbore
Titlul: 071 Concurs Scris de: Andrei Grigorean din Martie 08, 2006, 23:13:14 Cod: 3 1 adica fisierul asta nu e corect? Titlul: 071 Concurs Scris de: Ionel Corneliu Gog din 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.
Titlul: 071 Concurs Scris de: Andrei Grigorean din Martie 08, 2006, 23:28:28 2 nu este seful lui 3. ultima pereche e interogare :P.
eu am in prog meu asa ceva: Cod: for i:=1 to n-1 do begin 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). Titlul: 071 Concurs Scris de: Ionel Corneliu Gog din 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. :guns:
Titlul: 071 Concurs Scris de: Andrei Grigorean din 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. Titlul: Raspuns: 071 Concurs Scris de: Savin Tiberiu din Iulie 09, 2006, 14:03:11 ati putea sa imi dati si mie un test mai mare sau mai complicat :eyebrow:. tot iau 30 de pct si nu inteleg de ce. Fac o parcurgere euler si apoi determin lca in o(n), si culmea ca nu iau TLE ci WA si nu inteleg de ce.
Retin maximu la fiecare query si dak lca(x,y)=sol[0] (sol[0]=maximu intalnit pana atunci, sol[1]=prima persoana care a lucrat la proiect si sol[2] - a doua persoana) atunci verific dak (sol[1]*10+sol[2]>x*10+y). chiar nu inteleg unde gresesc. PS: Parcurgerea o fac recursiv am vazut ca sunt cateva posturi referitoare la acest lucru, insa nu inteleg ce legatura are chestia asta. arborele il retin folosind o lista de muchii pe care le ordonez dupa tata respectiv fiu dak e acelasi tata. Titlul: Raspuns: 071 Concurs Scris de: Marius Stroe din Iulie 14, 2006, 15:46:16 Testul 8 nu merge nicicum! Este cineva amabil sa imi spuna cum as putea sa trec de el ?
Am rezolvat Atac cu acelasi LCA! ](*,) Titlul: Re: 071 Concurs Scris de: Bogdan-Cristian Tataroiu din Iulie 14, 2006, 19:00:46 Radacina nu e neaparat in nodul 1... Eu din cauza asta picam testu 8
Titlul: Raspuns: 071 Concurs Scris de: Marius Stroe din Iulie 14, 2006, 19:32:21 Foarte subtil... :)
Titlul: Raspuns: 071 Concurs Scris de: Savin Tiberiu din Iulie 14, 2006, 19:58:35 parca la lca puteam sa agatam arborele in orice radacina ?? nu vad ce importanta are radacina arborelui
[later edit] mda ca de obicei ziceam prostii, cu determinarea radacinii am luat 70 pct :D Titlul: Raspuns: 071 Concurs Scris de: Sima Cotizo din Februarie 08, 2007, 21:51:48 Are ceva testul 7 mai special ?!? ... ca e singurul pe care iau TLE.
Fac cam asa: un DF recursiv / BF cu o coada dinamica / BF cu coada = vector... si LCA in log2(n) mai altfel decat in articol... adica: 1) aduc nodurile pe acelasi nivel [pe care il scot din DF/BF] ... adica pe ala care e mai "adanc" il urc pana cand ajung la aceeasi adancime 2) cat timp sunt diferite, urc ambele noduri prin tati... La celelalte teste am maxim 0.5 secunde, si testul 7 mi se pare ca s-a zis ca nu ar fi unul maxim... deci inseamna ca cicleaza undeva acel LCA... sau ca am alta problema... Titlul: Raspuns: 071 Concurs Scris de: Savin Tiberiu din Februarie 08, 2007, 22:03:33 si daca ai un arbore de genu
1 2 2 3 3 4 5 6 ... N-1 N. In cat timp determini lca dintre 1 si n. Mie mi se pare cam o(n). Sper ca exemplu nu contrazice datele problemei, am facut-o mai demult Titlul: Raspuns: 071 Concurs Scris de: Sima Cotizo din Februarie 08, 2007, 22:08:36 Yep stiu asta. Pai ummm... daca e asa se poate trata caz separat in problema, dar ar fi urat din partea mea... totusi daca e ceva de genu radacina are 2 fii si pe urma sa zicem ca restu sunt toti atarnati la rand de unul dintre ei... [nu toti ceilalti n-3 de unul din fii radacinii, ci unul dupa altul... in jos]... sau cazuri d-astea... :(
Ar mai fi ca abordarea mea ia log2(n) in general daca e heap... sau daca majoritatea nodurilor au minim doi fii. Titlul: Raspuns: 071 Concurs Scris de: Mircea Pasoi din Februarie 08, 2007, 22:16:43 Exista pe site o groaza de documentatie despre LCA in O(sqrt(N)), O(lg^2 N), O(1), etc. .. pentru gusturile tuturor
Titlul: Raspuns: 071 Concurs Scris de: Savin Tiberiu din Februarie 08, 2007, 22:55:44 care e ala in o(1) ?? eu nu am gasit nici un articol cu lca in o(1)
Titlul: Raspuns: 071 Concurs Scris de: Mircea Pasoi din Februarie 08, 2007, 22:59:23 care e ala in o(1) ?? eu nu am gasit nici un articol cu lca in o(1) Se pare ca in articolul cu LCA cu turul Euler e O(lgN), dar reducerea e triviala la O(1). Daca faci query intr-un interval [i..j] si k e cea mai mare putere a lui 2 a.i. 2^k <= j-i+1 ai RMQ(i, j) = min(A[ i ][k], A[j-2^k+1][k]) unde A[ x ][y] e minimul pe intervalul [x...x+2^y-1] Titlul: Raspuns: 071 Concurs Scris de: Andrei Grigorean din Februarie 08, 2007, 23:07:37 uite aici un articol care ar putea sa iti fie de folos:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor Titlul: Răspuns: 071 Concurs Scris de: Cezar Mocan din Noiembrie 08, 2008, 14:34:38 Nu reusesc sa fac programul sa treaca testul 8. Am citit ce s'a scris mai sus si radacina o aflu dupa citire, nu o iau direct 1. Ar mai fi si altceva?
[L.E.] Solved. Titlul: Răspuns: 071 Concurs Scris de: Macarescu Sebastian din Februarie 04, 2012, 18:34:54 Testul 4 are ceva special? Orice as face iau WA pe el ](*,)
Titlul: Răspuns: 071 Concurs Scris de: Vasilut Lucian din August 18, 2014, 21:14:57 Ce are mai special testul 8 ? :-'
LE : Done :ok: Titlul: Răspuns: 071 Concurs Scris de: Stoian Mihail din Aprilie 07, 2016, 15:04:02 Ce se intelege prin "cel mai mic sef comun al celor doi componenti din echipa"? - valoarea nodului ce reprezinta LCA-ul nodurilor sau seful comun cu valoarea cea mai mica?
Multumesc! Titlul: Răspuns: 071 Concurs Scris de: Florin Gabriel Haja din Mai 14, 2017, 17:20:39 Vă rog să corectați cerința... :readthis:
Citat In cazul in care un component al unei echipe este seful celuilalt atunci proectul primeste puncte chiar de la acesta. |