071 Concurs

[•domino]

Aici puteţi discuta despre problema Concurs.

[•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...  

 
                                                                      bubbleSORT

[•domino]

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.

[•DeadStar]

hmm..testul 4 nu-i chiar asa de mare. Ai citit http://info.devnet.ro/articole.php?page=art&art=19 ?

[•filipb]

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...  

[•silviug]

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]

[•bogdan2412]

Ce e "Referatu' de la lot" ?

[•domino]

Ce e "Referatu' de la lot" ?

http://info.devnet.ro/download.php?page=cat&cat=24

[•bogdan2412]

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.

[•silviug]

concluzia: nu mai refolosi cod!

[•bogdan2412]

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...

[•DeadStar]

M-am uitat si nu este special. De asemenea nu este cel mai mare.

[•vladcyb1]

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.  

[•vladcyb1]

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).

[•Dorin]

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  

[cristi8]

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

[•Dorin]

no bine atunci ms ser pare ca ar trebui sa fiu mai atent cand citesc un enunt

[u-92]

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.. )

[•wefgef]

am si eu o nelamuririe...

un angajat poate sa aiba mai multi sefi?

[u-92]

nu, contrazice enuntul care zice ca firma are o structura ierarhica in forma de arbore

[•wefgef]

Cod:

3 1
1 1 1
1 2
3 2
2 3

adica fisierul asta nu e corect?

[•DeadStar]

Nu este bun. 2 are doi sefi, iar 3 apare si ca sef si ca subaltern al nodului 2.

[•wefgef]

2 nu este seful lui 3. ultima pereche e interogare .

eu am in prog meu asa ceva:

Cod:

 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).

[•DeadStar]

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.

[•wefgef]

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.