|
Titlul: 493 Cezar Scris de: Adrian Diaconu din August 13, 2007, 22:57:10 Aici puteţi discuta despre problema Cezar (http://infoarena.ro/problema/cezar).
Titlul: Răspuns: 493 Cezar Scris de: Savin Tiberiu din August 15, 2007, 11:59:11 la ultima restrictie, aia cu testele, am impresia ca la una din ele Paul a uitat sa puna $.$ la N.
Titlul: Răspuns: 493 Cezar Scris de: Adrian Diaconu din August 15, 2007, 12:03:30 S-a corectat.
Titlul: Răspuns: 493 Cezar Scris de: Chis Raoul din August 31, 2007, 14:06:42 atzi facut careva pb asta de 100 pe infoarena ? mie imi da mle p doua teste
Titlul: Răspuns: 493 Cezar Scris de: Paul-Dan Baltescu din August 31, 2007, 14:38:01 Au facut-o cativa: http://infoarena.ro/monitor?task=cezar. Limita este exact ca la OJI.
Titlul: Răspuns: 493 Cezar Scris de: Ionescu Vlad din August 31, 2007, 14:41:24 O modalitate de a reduce memoria folosita e sa folosesti short in loc de int unde se poate...
Titlul: Răspuns: 493 Cezar Scris de: Chis Raoul din August 31, 2007, 14:46:52 k, 10x ;)
Titlul: Răspuns: 493 Cezar Scris de: Barsan Paul din Decembrie 09, 2007, 15:31:29 ](*,) 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? Titlul: Răspuns: 493 Cezar Scris de: Paul-Dan Baltescu din Decembrie 09, 2007, 20:09:21 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. :) Titlul: Răspuns: 493 Cezar Scris de: Barsan Paul din Decembrie 10, 2007, 10:19:36 [-o< merci
pfu, numi vine sa cred ca nu mam gandit la asta :aha: Titlul: Răspuns: 493 Cezar Scris de: Bozianu Ana din Ianuarie 15, 2008, 00:08:49 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. Titlul: Răspuns: 493 Cezar Scris de: Andrei Grigorean din Ianuarie 15, 2008, 00:12:24 E cat se poate de simplu. Nu exista teste cu k == n-1, iar programul tau e chiar la limita cu memoria.
Titlul: Răspuns: 493 Cezar Scris de: Bozianu Ana din Ianuarie 15, 2008, 00:18:00 Si eu care crezusem ca exista spiridushi.
Titlul: Răspuns: 493 Cezar Scris de: Alexandru Pana din Februarie 13, 2008, 21:54:56 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 ?
Titlul: Răspuns: 493 Cezar Scris de: Bondane Cosmin din Februarie 13, 2008, 21:57:39 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.
Titlul: Răspuns: 493 Cezar Scris de: Alexandru Pana din Februarie 13, 2008, 21:59:37 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..
Titlul: Răspuns: 493 Cezar Scris de: Andrei Grigorean din Februarie 13, 2008, 22:55:55 Poate poti sa folosesti short int in loc de long int. Short int merge pana de la -32568 la 32567.
Titlul: Răspuns: 493 Cezar Scris de: Alexandru Pana din Februarie 13, 2008, 23:02:46 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 ) Titlul: Răspuns: 493 Cezar Scris de: Andrei Grigorean din Februarie 14, 2008, 11:53:43 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 (http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai). Titlul: Răspuns: 493 Cezar Scris de: constantin din Martie 10, 2008, 11:10:38 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. Titlul: Răspuns: 493 Cezar Scris de: Paul-Dan Baltescu din Martie 10, 2008, 12:30:45 S-a mai vorbit despre asta mai sus.
Titlul: Răspuns: 493 Cezar Scris de: Paul-Dan Baltescu din Martie 10, 2008, 12:43:41 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). :)
Titlul: Răspuns: 493 Cezar Scris de: constantin din Martie 10, 2008, 12:45:40 Ups...ai dreptate....acum am inteles :D
Titlul: Intrebare Scris de: Otilia Stretcu din Martie 03, 2010, 12:12:04 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? :? Titlul: Răspuns: 493 Cezar Scris de: Mircea Dima din Martie 03, 2010, 12:40:08 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 :) Titlul: Răspuns: 493 Cezar Scris de: Otilia Stretcu din Martie 03, 2010, 15:25:34 Multumesc mult pentru pont! :D Nu reusesc totusi sa aplic si pentru cazul meu, se poate si daca am un vector de vectori ? (cum ar fi lista de vecini)
Chiar si cu aceasta noua informatie, tot nu reusesc sa aflu de ce se depasesc cei 640kb. Pentru cele 20 000 nr pe care vreau sa le aloc, vor fi alocate 2^15=32768 de tip short, care tot nu ar trebui sa ocupe atat de mult. Ma tem sa nu fac vreo greseala asemanatoare la OJI. :sad: Titlul: Răspuns: 493 Cezar Scris de: Usurelu Catalin din Martie 03, 2010, 16:39:16 Eu nu inteleg de ce in raspuns este valoarea 11, nu trebuia sa fie 10 ?
Titlul: Răspuns: 493 Cezar Scris de: Gabriel Bitis din Martie 03, 2010, 16:58:23 Problema e la ramura (1->2; 3->2; 2->8 ), aici probabil tu numeri 4 in loc de 5. Senatorii din 1 si 3 platesc cate 2 banuti, iar senatorul din 2 plateste un banut (probabil l'ai uitat pe cel din 2).
Titlul: Răspuns: 493 Cezar Scris de: Usurelu Catalin din Martie 03, 2010, 17:04:49 Da asa e l-am uitat pe 2 #-o. Stiam ca eu am gresit dar chiar nu inteleg cum de am putut rata nodul ala.
Multumesc mult pentru raspuns :peacefingers: Titlul: Răspuns: 493 Cezar Scris de: Vlad Eugen Dornescu din Ianuarie 12, 2011, 15:22:46 Salut.Primesc MLE pe multe teste, din cauza ca folosesc priority_queue si am memorie O(N^2).
Cum pot face a.i sa reduc memoria la O(N) pentru priority_queue (cumva sa tin minte doar cost[ nod ] - costul de a ajunge in nodul i, si sa stiu cand extrag costul din varful heapului, ca acesta apartine nodului i).In felul asta as putea scapa de al doilea camp, si MLE. :) Titlul: Răspuns: 493 Cezar Scris de: Paul-Dan Baltescu din Ianuarie 12, 2011, 17:54:28 N+N = 2N. :)
Ai putea sa tii in priority queue nodul si sa implementezi operatorul de comparare astfel incat sa compari dupa cost. Mai multe informatii poti gasi pe net si un exemplu asemanator pentru set poti gasi mai jos: Cod: struct semn Titlul: Răspuns: 493 Cezar Scris de: Vlad Eugen Dornescu din Ianuarie 13, 2011, 00:06:19 Cod: int n, k, dp[nmax], x, y, mx, i, howmany, elem, cost; Am incercat si asa si primesc niste erori : Cod: Compiling... Cum as putea reduce memoria altfel? :) L.E : Am lasat pr.queue deoparte si am implementat min-heapul de mana.Din pacate primesc tot MLE, pe aceleeasi teste. Ar trebui sa tin arborii cu liste (si sa scriu eu functia de eliminare a nodurilor)? Consuma set<int>, vector<int> mai multa memorie? Titlul: Răspuns: 493 Cezar Scris de: Usurelu Catalin din Februarie 01, 2011, 12:58:01 Nu poate nimeni da un indiciu in legatura cu memoria? ca vad ca majoritatea celor cu 95 de puncte, au facut o modificare mica in sursa si au trimis-o la cateva minute distanta, deci cred ca e ceva simplu ...
Am incercat sa fac vectorii sa ocupe mai putina memorie prin citirea fisierului de 2 ori si culmea imi ocupa mai mult spatiu la evaluare, chiar daca vectorii mei sunt mai mici (i-am testat :D). Pana si sursele oficiale iau MLE pe 2 teste. E ceva ciudat ... Titlul: Răspuns: 493 Cezar Scris de: Dragos-Alin Rotaru din Februarie 01, 2011, 14:38:26 O modalitate de a reduce memoria folosita e sa folosesti short in loc de int unde se poate... Titlul: Răspuns: 493 Cezar Scris de: Usurelu Catalin din Februarie 01, 2011, 14:49:58 Am folosit peste tot short int, nu prea vad ce optimizari ar mai putea fi facute.
Culmea e ca am facut un vector unsigned char (m-am uitat peste valori sa fiu sigur ca nu e nevoie de mai mult) si desi ar fi trebuit ca vectorul sa ocupe jumatate din memoria initiala (vectorul avea intial 10000 de elemente, deci acu ar fi echivalentul a 5000 de elemente), la rezultate imi arata ca, consuma cu 10 kb mai mult, la penultimu test. Asta da paradox. Titlul: Răspuns: 493 Cezar Scris de: Dragos din Februarie 02, 2011, 21:32:13 Si eu iau 95 cu MLE pe ultimul test declarand vectorii asa:
Cod: #define nmax 10001 Imi poate spune si mie cineva cum sa mai reduc din memorie? Multumesc anticipat! Cu H[]-heapul si c[] vectorul folosit pentru dinamica. Titlul: Răspuns: 493 Cezar Scris de: Paul-Dan Baltescu din Februarie 03, 2011, 00:43:08 Incearca sa nu folosesti vectori din STL pentru listele de adiacenta.
Titlul: Răspuns: 493 Cezar Scris de: FII Florea Toma Eduard din Ianuarie 05, 2012, 01:44:27 Bun,iau 85 de puncte cu MLE pe ultimele teste.Din cate am vazut la sursele de 100 folosesc cam jumatate din memoria pe care o folosesc eu.Cum se explica asta?Mentionez caci utilizez aceleasi declaratii ca apocalipto.Sa fie din cauza matricei de adiacenta unde retin totul ca un graf neorientat? :'(
Multumesc anticipat! Later Edit: vreun smen de micsorare a memoriei? :shock: Titlul: Răspuns: 493 Cezar Scris de: Cristian Lambru din Ianuarie 06, 2012, 20:19:25 Matrice de adiacenta? Numarul de noduri ajunge pana la 10.000, ar fi bine sa folosesti liste de adiacenta pentru a pastra nodurile grafului.
Titlul: Răspuns: 493 Cezar Scris de: Sorin Rita din Ianuarie 07, 2012, 01:06:22 Cum pot sa reduc memoria ?
Cod: bitset<maxn> uz; Titlul: Răspuns: 493 Cezar Scris de: MciprianM din Ianuarie 07, 2012, 11:45:01 Cod: bitset<maxn> uz; Titlul: Răspuns: 493 Cezar Scris de: Darius-Florentin Neatu din Februarie 08, 2014, 15:49:55 Salut. Fac desfrunzirea. Am un heap in care bag initial toate frunzele. La fiecare pas extrag din heap frunza de cost minim , o marchez si actualizez tatal.
Cod: cost [ Tata ] += cost [ frunza ] + 1 + descendenti [ frunza ] ; Unde frunza este un nod care poate la inceput nu era terminal, si de aceea a avut descendenti ; iar cost [ nod ] este costul total pe care il platesc senatorii descendenti ai lui nod ca sa ajunga pana in nod. Initial toate costurile sunt 0. Radacina arborelui am considerat-o ca fiind unul din cele K+1 noduri finale ramase. Daca Tatal mai are un singur vecin nevizitat il introduc in heap . Solutia este suma costurilor din nodurile nevizitate. Poate sa-mi spuna cineva unde gresesc? Iau 65p si incorect pe 7 teste ](*,) http://www.infoarena.ro/job_detail/1100654?action=view-source (http://www.infoarena.ro/job_detail/1100654?action=view-source) Titlul: Răspuns: 493 Cezar Scris de: Mihai Nitu din Februarie 09, 2014, 11:16:27 De ce trebuie sa fie atat de stransa limita de memorie? Nu mi se pare normal sa trebuiasca sa tragi de o sursa corecta, care ar trebui sa ia 100, o gramada de timp, sa o optimizezi pana in panzele albe ca sa ia 100 de puncte. In fine, pentru cei care se mai infrunta cu asta, incercati sa nu aveti mai mult de 2 vectori + heapul + listele de adiacenta, puneti short pe unde se poate, faceti citirea si afisarea cu scanf/printf, fara streamuri ca si alea ocupa memorie si cel mai probabil o sa va intre.
Titlul: Răspuns: 493 Cezar Scris de: FMI-Coteanu Vlad din Ianuarie 25, 2016, 22:10:37 http://www.infoarena.ro/job_detail/1580546?action=view-source
Din pacate un vector, un heap si listele sunt prea mult pentru memoria impusa...vreo sugestie? Titlul: Răspuns: 493 Cezar Scris de: Tudor Maxim din Ianuarie 26, 2016, 21:55:13 Declara (in afara de NR-ul pe care il afisezi) toate variabilile short. Altceva nu stiu ce ar putea fi..
Titlul: Răspuns: 493 Cezar Scris de: Florin Gabriel Haja din Septembrie 26, 2016, 20:23:48 Intra in limita de memorie cu lista de adiacenta implementata manual (vezi smenurile de pe infoarena) si muchiile retinute o singura data, FARA HEAPURI.
Vedeti sursa #1765371: http://www.infoarena.ro/job_detail/1765371 Titlul: Răspuns: 493 Cezar Scris de: Mouse Wireless din Septembrie 15, 2017, 15:17:41 Salut.
Am o intrebare legat de problema asta. Am scris o rezolvare care a luat 100p dar nu sunt sigur daca e corecta (uitandu-ma la alte surse care au luat 100, vad ca nu sunt chiar la fel). Ce mi-am dat seama e ca e usor sa afli ranspunsul la problema daca centrul ("senatul") e fixat. Dar nu stiam cum sa imi aleg centrul respectiv. Dupa ceva timp, am incercat sa il aleg greedily dupa regula "cel cu suma distantelor catre alte noduri minima" pentru ca intuitiv vorbind daca am suma distantelor mica, am mai putin de "minimizat" prin "pavare" ca sa ajung la raspunsul optim. Solutia a fost acceptata dar nu reusesc sa demonstrez corectitudinea ei. Cum stiu ca nu exista un nod care, desi in prima faza nu are suma distantelor minima, pot sa il "pavez" in asa fel incat sa obtin o solutie mai buna decat a altor noduri? Exista vreun contraxemplu? Ma poate ajuta cineva? Ma tot bate intrebarea asta :) Titlul: Răspuns: 493 Cezar Scris de: Mihai Calancea din Septembrie 17, 2017, 18:22:18 N-am rezolvat problema asta si n-am stat mult sa verific acum, sper ca nu vorbesc prostii.
Cred ca e corect ce faci. Daca presupunem ca alegem intai muchiile gratuite, centrul poate fi orice nod care are o muchie gratuita incidenta cu el (deci ai K + 1 variante la fel de bune). Atunci vrei sa demonstrezi doar ca exista intotdeauna o alegere optima a muchiilor gratuite care atinge si centrul "greedy" (sa-l numim centroid) descris de tine. Iar asta pare adevarat. Presupunand prin absurd ca setul optim de muchii nu atinge centroidul, atunci stergand una dintre muchiile cele mai indepartate de centroid si adaugand una noua "in directia" centroidului, costul nu poate sa creasca, fiindca muchia nou aleasa este utilizata de mai multi senatori decat cea veche (altfel centroidul n-ar fi fost centroid). |