Pagini: [1] 2 3   În jos
  Imprimă  
Ajutor Subiect: 013 Parcurgere in latime  (Citit de 38757 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Decembrie 06, 2008, 19:43:55 »

Aici puteti discuta despre problema Parcurgere in latime.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #1 : Decembrie 07, 2008, 22:14:20 »

Iau 80 la pb asta. E destul de fustrant ca nu fac o parcurgere in latime de 100 de puncte. Faza e ca iau memory limit exceeded... Intr-adevar, nu sterg elementele din coada.. Dar totusi... nici in sursa asta http://infoarena.ro/job_detail/223158?action=view-source nu vad nicaieri vreo instructiune care sa stearga elementul extras, din coada. Care e diferenta? [ sursa mea: http://infoarena.ro/job_detail/228490?action=view-source ] Eu am lucrat cu liste simplu inlantuite...

ps: nu stiu stl, si desi nu mi-ar fi greu sa invat 2-3 instructiuni ca sa-mi iasa problema asta, is curios de ce nu-mi intra si programul meu, in memorie...  Think
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #2 : Decembrie 07, 2008, 22:20:32 »

Sursa ta iese din memorie pentru ca aloci mai mult de 16 Mb. Pentru fiecare vecin tii 2 informatii (tipul vecinului si pointerul spre vecinul urmator) => 2 * 4 bytes. Cum fiecare muchie apare de doua ori (pentru fiecare sens), in total pentru fiecare muchie ai 2 * 2 * 4  = 16 bytes.
Memorat

Am zis Mr. Green
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #3 : Decembrie 08, 2008, 14:41:44 »

Sursa ta iese din memorie pentru ca aloci mai mult de 16 Mb. Pentru fiecare vecin tii 2 informatii (tipul vecinului si pointerul spre vecinul urmator) => 2 * 4 bytes. Cum fiecare muchie apare de doua ori (pentru fiecare sens), in total pentru fiecare muchie ai 2 * 2 * 4  = 16 bytes.

De fapt, folosesc pt fiecare muchie 2*4 = 8 bytes [ ca e graf orientat ]. In fine... O sa implementez in stl. Ms pentru explicatii!  Thumb up
Memorat
k_ounu_eddy
Vorbaret
****

Karma: -104
Deconectat Deconectat

Mesaje: 161



Vezi Profilul
« Răspunde #4 : Decembrie 09, 2008, 00:16:44 »

Fara sa invat STL,nu pot sa iau 100p ?
Memorat
gcosmin
Nu mai tace
*****

Karma: 205
Deconectat Deconectat

Mesaje: 307



Vezi Profilul
« Răspunde #5 : Decembrie 09, 2008, 07:26:12 »

daca inteleg eu bine problema, si nu ai memorie suficienta pentru o lista inlantuita, trebuie sa tii listele de adiacenta prin vectori alocati dinamic. vezi articolul cu multe smenuri; acolo este un smen cu malloc si citirea fisierului de doua ori, la grafuri cu liste de adiacenta
Memorat
k_ounu_eddy
Vorbaret
****

Karma: -104
Deconectat Deconectat

Mesaje: 161



Vezi Profilul
« Răspunde #6 : Decembrie 09, 2008, 09:09:55 »

Am incercat si asa,dar imi iese din timp .  Very Happy
Faza e ca la urma am asa:
-for(int i=1;i<=n;i++)
    scrie cost(i);
si imi ia cam mult timp.Nu este vreo functie care sa imi scrie in fisierul de iesire direct tot vectorul?
Memorat
anna_bozianu
De-al casei
***

Karma: 5
Deconectat Deconectat

Mesaje: 111



Vezi Profilul
« Răspunde #7 : Decembrie 09, 2008, 14:06:09 »

Confirm si eu aceeasi problema la ultimele doua teste.
Cu listele de vecini cu pointeri MLE, cu smenul cu recitirea fisierului de intrare TLE.
Concluzie: rusine sa-mi fie ca nu am invatat macar vectorii din STL.
Intrebare nevinovata: parsarea citirii ar putea imbunatati timpul?


L.E. Cu modificarea limitei de memorie merge folosind pointeri. 10x paul. Smile
« Ultima modificare: Decembrie 09, 2008, 19:45:51 de către Bozianu Ana » Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #8 : Decembrie 09, 2008, 17:38:59 »

Limita de memorie a fost modificata la 32768 kbytes si problema a fost reevaluata. Imi cer scuze pentru eventualele neplaceri.
Memorat

Am zis Mr. Green
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #9 : Decembrie 09, 2008, 22:25:33 »

Ar trebui sa aveti grija la problemele astea cand fixati limitele de timp si memorie. Scopul lor este sa invete lumea algoritmii, nu jmenuri de implementare. Ati putea cere cuiva sa va ajute si cu o sursa in pascal, sa fiti siguri ca intra Smile
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #10 : Decembrie 10, 2008, 01:46:26 »

Mda, si eu as zice sa mariti limitele. Atata timp cat algoritmul e corect si nu e implementat foarte prost ar trebui sa ia 100 pe problema. Nu tre sa ne aratam muschii Smile mai ales la arhiva educationala.
Memorat
c_e_manu
Nu mai tace
*****

Karma: 56
Deconectat Deconectat

Mesaje: 243



Vezi Profilul
« Răspunde #11 : Februarie 17, 2009, 19:51:05 »

am si eu o intrebare... la problema asta, pe PC-ul meu, folosind vector din STL iau Segmentation Fault, chiar si pe sursa de la linkul cu 100 de pcte... trebuie sa caut un compilator mai nou?? am incercat cu compilatoarele de la mingw si rhide downloadate de la linkurile date de voi... Huh

mai exact, in partea asta de cod:
Cod:
for (j = 0; j < G[S[i]]; j++)
if (Cost[A[S[i]][j]] == -1)//aici
dupa ce a-ul a fost declarat:
Cod:
vector<int> a[MaxN]

daca nu e voie sa incerc sa accesez a[var1][var2], cum de sursa aceea a  luat 100? Huh
Memorat
florinlupan
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #12 : Martie 11, 2009, 09:37:46 »

Ii misto eu folosesc info arena pentru pregatire la olimpiada judeteana Banana
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #13 : Martie 11, 2009, 19:33:14 »

Citat
 am si eu o intrebare... la problema asta, pe PC-ul meu, folosind vector din STL iau Segmentation Fault, chiar si pe sursa de la linkul cu 100 de pcte... trebuie sa caut un compilator mai nou?? am incercat cu compilatoarele de la mingw si rhide downloadate de la linkurile date de voi...
 
posibil sa fie compilatorul devina ..........mie imi merge perfect Very Happy  .  Incearca fara vectori STL, folosind Lista de adiacenta alocata dinamica Very Happy
ps :incercat  cu Borland C++ 5.01 ,dar daca merge pe el merge pe orice garantez Tongue
Memorat
c_e_manu
Nu mai tace
*****

Karma: 56
Deconectat Deconectat

Mesaje: 243



Vezi Profilul
« Răspunde #14 : Martie 11, 2009, 22:08:26 »

daca te uitai, ai fii observat ca problema am rezolvat-o de ceva vreme... nelamurirea cu vectorii STL ramane... si da, am incercat cu liste de adiacenta, dar mi se pare mai simpla varianta ce foloseste STL... daca cineva are timp si chef sa ma lamureasca, astept PM... mersi! Ok
Memorat
mlazari
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 28



Vezi Profilul
« Răspunde #15 : Aprilie 07, 2009, 15:52:44 »

Mi-a luat cam mult timp ca sa obtin 100 de puncte la problema asta(in Free Pascal)  Very Happy. Luam TLE la ultimele 2 teste. Am modificat de o multime de ori sursa pina am ajuns la o sursa fara nici o procedura si... acelasi lucru: 80p. Mai apoi mi-a venit o ideie: sa nu eliberez memoria folosita(cu dispose) si am acumulat 100p. cu sursa initiala  Shocked Yahoo!
Memorat
florin_marius90
Strain


Karma: -15
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #16 : Septembrie 13, 2009, 12:22:12 »

salut , am si eu o problema ... pe aceeasi sursa am primit 90 de pct, am trimis-0 iar si am primit 80 de puncte.... toata treaba tine de timp , ca depasheste timpu. Daca o trimit pe seara poate obtin 100 ?
 help plss

   poate e site ul incarcat si compilatoru numai ruleaza la parametri optimi si deaia face asa .   ms
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #17 : Septembrie 13, 2009, 14:01:51 »

Am modificat limita de timp la 2.2 secunde si am reevaluat.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
florin_marius90
Strain


Karma: -15
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #18 : Septembrie 13, 2009, 14:49:54 »

gata ms Very Happy
Memorat
zalman
Strain
*

Karma: -11
Deconectat Deconectat

Mesaje: 31



Vezi Profilul
« Răspunde #19 : Februarie 12, 2010, 10:52:14 »

Se poate uita cineva sa vada de ce iau SIGSEGV pe toate testele? http://infoarena.ro/job_detail/395124
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #20 : Februarie 12, 2010, 11:22:05 »

Trebuie sa aloci coada mult mai mare. Nu iti ajunge doar de 100000, pentru ca ai 1 mil de muchii maxim, si de aia iei KBS .

Mai bine aloc-o cu STL.

Cod:
queue<int> Q;
Q.push(a); //adaugi in coada
Q.front(); //interoghezi sa vezi care este primul element
Q.pop(); //scoti primul element din coada
Memorat
zalman
Strain
*

Karma: -11
Deconectat Deconectat

Mesaje: 31



Vezi Profilul
« Răspunde #21 : Februarie 12, 2010, 12:29:43 »

Acelasi lucru da si cu STL`u  Brick wall
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #22 : Februarie 12, 2010, 17:47:02 »

Tu faci o confuzie :trebuie sa faci BFS (Breadth First Search) , dar crezi ca se numeste  DFS ( Depth First Search , care nu te ajuta aici) . Foarte mult nu te-ar fi afectat daca n-ai fi numit si fisierele dfs.in , dfs.out Smile De-aici signalul.

@George
Pai , de ce ? Doar nu baga muchii in coada.

L.E. Si btw , parcurgerea in latime iti asigura faptul ca daca nod1 a fost procesat inainte de nod2 , d[nod1] < d[nod2]. Deci , cu alte cuvinte d[nod1] , odata calculat ,  nu va mai fi schimbat in viitor. E destul sa verifici doar daca d[nod] == -1 inainte sa-l bagi in coada. Ce faci tu acolo e defapt Bellman - Ford .
« Ultima modificare: Februarie 12, 2010, 18:19:49 de către Mihai Calancea » Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #23 : Februarie 12, 2010, 18:33:54 »

Nu inteleg ce vrei sa spui. Daca bagi maxim N (in total) noduri intr-o coada , back nu va trece de N. Si front nu va trece de back.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #24 : Februarie 12, 2010, 18:40:23 »

Asa e, scuze  Confused
Memorat
Pagini: [1] 2 3   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines