493 Cezar

[•otilia_s]

       Multumesc mult pentru pont! 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. 

[•ucc_5]

Eu nu inteleg de ce in raspuns este valoarea 11, nu trebuia sa fie 10 ?

[•gabitzish1]

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

[•ucc_5]

Da asa e l-am uitat pe 2  . Stiam ca eu am gresit dar chiar nu inteleg cum de am putut rata nodul ala.
Multumesc mult pentru raspuns

[•dornescuvlad]

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. 

[•pauldb]

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
{
	bool operator() (const int x, const int y) const
	{
		return cost[x] > cost[y];
	}
};

set <int, semn> s;

[•dornescuvlad]

Cod:

int n, k, dp[nmax], x, y, mx, i, howmany, elem, cost;
set<int> Senat[nmax];
int father[nmax], viz[nmax];

Am incercat si asa si primesc niste erori :

Cod:

Compiling...
cezar.cpp
cezar.cpp:27: error: no type named `value_type' in `struct semn'
cezar.cpp:27: error: template argument 3 is invalid
cezar.cpp:27: error: invalid type in declaration before ';' token
cezar.cpp: In function `int main()':
cezar.cpp:61: error: `push' has not been declared
cezar.cpp:61: error: request for member of non-aggregate type before '(' token
cezar.cpp:76: error: `top' has not been declared
cezar.cpp:76: error: request for member of non-aggregate type before '(' token
cezar.cpp:78: error: `pop' has not been declared
cezar.cpp:78: error: request for member of non-aggregate type before '(' token
cezar.cpp:84: error: `push' has not been declared
cezar.cpp:84: error: request for member of non-aggregate type before '(' token
cezar.cpp:90:2: warning: no newline at end of file

cezar.o - 11 error(s), 1 warning(s)

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?

[•ucc_5]

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 ).
Pana si sursele oficiale iau MLE pe 2 teste. E ceva ciudat ...

[•mathboy]

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

[•ucc_5]

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.

[•APOCALYPTO]

Si eu iau 95 cu MLE pe ultimul test declarand vectorii asa:

Cod:

#define nmax 10001

vector<short> G[nmax];
short N,K,nh;
short c[nmax];
short H[nmax];

Imi poate spune si mie cineva cum sa mai reduc din memorie?

Multumesc anticipat!
Cu H[]-heapul si c[] vectorul folosit pentru dinamica.

[•pauldb]

Incearca sa nu folosesti vectori din STL pentru listele de adiacenta.

[•thesilverhand13]

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?

[•maritim]

Matrice de adiacenta? Numarul de noduri ajunge pana la 10.000, ar fi bine sa folosesti liste de adiacenta pentru a pastra nodurile grafului.

[•soriyn]

Cum pot sa reduc memoria ?

Cod:

bitset<maxn> uz;
struct graf
{
	short int nod;
	graf *next;
};
graf *a[maxn];
short int cost[maxn],h[maxn];

[•MciprianM]

Cod:

bitset<maxn> uz;
struct graf
{
	short int nod [2];
	graf *next;
};
graf *a[maxn];
short int cost[maxn],h[maxn];

[•Dddarius95]

    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 ] ;
descendenti [ Tata ] += 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

[•Impaler_009]

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.

[•sicsic]

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?

[•tudormaxim]

Declara (in afara de NR-ul pe care il afisezi) toate variabilile short. Altceva nu stiu ce ar putea fi..

[•FlorinHaja]

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

[•mouse_wireless]

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

[•klamathix]

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