493 Cezar

[•DITzoneC]

Aici puteţi discuta despre problema Cezar.

[•devilkind]

la ultima restrictie, aia cu testele, am impresia ca la una din ele Paul a uitat sa puna $.$ la N.

[•DITzoneC]

S-a corectat.

[•raula_san]

atzi facut careva pb asta de 100 pe infoarena ? mie imi da mle p doua teste

[•pauldb]

Au facut-o cativa: http://infoarena.ro/monitor?task=cezar. Limita este exact ca la OJI.

[•Dastas]

O modalitate de a reduce memoria folosita e sa folosesti short in loc de int unde se poate...

[•raula_san]

k, 10x

[•megabyte]

  ma poate ajuta cineva si pe mine, nu stiu dc iau numai 65 pct
Prima data construiesc un arbore cu radacina in 1 si calculez 2 vectori: bnd(i)-numarul de noduri ale subarborelui cu rad in i si bdr(i)-suma lungimilor tuturor drumurilor care vin de la fii la nodul i.Apoi calculez dr(i)- suma lungimilor tuturor drumurilor care vin din tot arborele cu formula : dr(t(i))+n-2*bnd(i), unde t(i)-tatal nodului i.Stabilesc centrul in nodul care are dr(i) minim.Solutia partiala ii dr(centru)
  Construiesc alt arbore cu radacina in centru si incep sa bag in heap_max vecinii centrului, cate un vecin i cu bdr(i) (reactualizat) ,extrag din heap nodul i cu bdr maxim, scad din solutia partiala numarul de noduri ale subarborelui i, si inserez in heap noii vecini ai nodului i.Dupa ce am scos k noduri presupun ca ar trebui sa-mi ramana solutia finala.
Care ar fi problema?

[•pauldb]

Din ce am inteles eu ca faci in partea a doua, tu alegi mereu nodul pentru care suma drumurilor din subarborele corespunzator este maxima. Daca faci asa, gandeste-te la urmatorul caz: un subarbore poate avea N noduri dispuse in lant sau poate avea N*(N+1)/2-1 noduri legate de radacina. Tu ai alege primul caz, deoarece suma drumurilor este N*(N+1)/2 > N*(N-1)/2-1. Cu toate astea, daca ai alege cel de-al doilea subarbore costul total ar scadea cu N*(N+1)/2-1, in timp ce primul scade costul total doar cu N.

La OJI probabil ai fi luat 90-95 de puncte cu solutia asta.

[•megabyte]

   merci
 pfu, numi vine sa cred ca nu mam gandit la asta 

[•anna_bozianu]

Paradoxul lui for( ; ; ) ;
Am rezolvat problema Cezar si am obtinut 95p cu MLE pe ultimul test. Plecand de la banuiala ca exista un caz particular k==n-1 introduc imediat dupa citirea n si k o instructiune if(k==n-1) for( ; ; ) ; asteptand bineinteles sa obtin TLE pe unul sau mai multe teste. Surpriza. Dupa intoducerea acestei linii in cod evaluatorul imi scoate 100 p. Asa ceva e dincolo de puterea mea de intelegere. PLS ...luminati-ma.

[•wefgef]

E cat se poate de simplu. Nu exista teste cu k == n-1, iar programul tau e chiar la limita cu memoria.

[•anna_bozianu]

Si eu care crezusem ca exista spiridushi.

[•recviem]

Am incercat programul oficial, si da TLE pe penultimul test si MLE pe ultimul. Si programul meu da MLE pe ultimul test la diferenta random intre 4 si 20 kb. Am modificat variabilele timp de o ora, nu am reusit nimic. Diferenta de memorie random este pe acelasi program. In ideea ca primul test mananca 644kb si al doilea 660kb.. chiar trebuie sa fie restrictiile atat de mici ?

[•cos_min]

Din cate stiu eu, programul este oprit din rulat atunci cand depasesti memoria si deci iti afiseaza o valoare apropiata de maximul admis de memorie. Sper sa nu ma insel.

[•recviem]

Imi iese din memorie de la citire. si nu memorez decat un graf prin lista de muchii si inca 2 vectori. Ce sa scot de acolo nu am idee..

[•wefgef]

Poate poti sa folosesti short int in loc de long int. Short int merge pana de la -32568 la 32567.

[•recviem]

Am incercat short int pe combinari de variabile ... la nodurile din graf pica suspicios pe penultimul test cu TLE si tot nu scap de MLE ..

Inca o intrebare, cand dau delete (pointer), imi elibereaza memoria astfel incat sa o pot refolosi, sau tot ce aloc dupa se adauga in continuare fara sa ocupe spatiul eliberat ? ( cel putin la suma de memorie pe care o afiseaza evaluatorul )

[•wefgef]

Nu stiu exact cum se calculeaza memoria folosita. Ar trebui sa iti raspunda oameni mai competenti ca mine.

In schimb, te sfatuiesc sa nu mai folosesti pointeri. Retine graful sub forma de liste de adiacenta. Poti sa citesti mai multe aici.

[•constantin02]

Salut! am facut si eu problema, insa numa de 65 de puncte si nu imi dau seama ce gresesc. Am implementat cu heapuri si totdeauna bag frunzele in heap si apoi scot tot cea mai mica in functie de lungimea totala fata de toti fii sai. Practic fac desfunzire si cand dau de o frunza noua o bag in heap, iar apoi o scot tot pe cea mai mica. Iar in final raman cu k muchii. La sfarsit
fac suma intre nodurile legate de cele k muchii si ar trebui sa obtin solutia corecta.

[•pauldb]

S-a mai vorbit despre asta mai sus.

[•pauldb]

Nu e intereseaza sa scoti in functie de lungimea minima fata de fii, ci in functie de numarul fiilor (si am dat exemplul de mai sus, sper ca acuma e inteligibil).

[•constantin02]

Ups...ai dreptate....acum am inteles 

[•otilia_s]

      As avea si eu o nelamurire legata de memoria ocupata de un vector in STL.  Am obtinut 95 pct, cu MLE pe ultimul test, desi conform calculelor mele ar fi trebuit sa se incadreze. Programul meu contine urmatoarele declaratii :
const int NMAX=10002;
vector <short> A[NMAX];
short nf[NMAX],H[NMAX],nr[NMAX];
      Pentru vectorii de tip short ar trebui sa am 2 bytes*3 vectori*NMAX elemente=59 kb.
      In A, care este lista de adiacenta, voi aloca 2*(NMAX-1) valori de tip short (pt ca in ultimul test se dau 10000 noduri), care ocupa inca vreo 20 kb.
      Deci restul pana 640kb(si chiar mai mult) ar trebui sa fie ocupat de pointeri. Cum se calculeaza memoria utilizata de ei? Ma puteti ajuta, va rog?   

[•blasterz]

Daca ai un vector din stl, de exemplu vector<short> , si in el ai adaugat (cu push_back) n elemente, vectorul va contine defapt 2^k > n elemente. De ex daca  n = 1025 vectorul va aloca 2048 de elemente de tip short.

poti folosi un truc pentru a micsora capacitatea (adica memoria folosita) vectorului la cat ai tu nevoie:

vector<short> (a).swap (a);
(practic creez un vector temporar si il inlocuiesc inapoi..)

poti sa afisezi a.capacity() inainte si dupa swap si o sa vezi diferenta