infoarena

Aici puteti discuta despre problema Parcurgere in latime (http://infoarena.ro/problema/bfs).

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

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!  :thumbup:

Fara sa invat STL,nu pot sa iau 100p ?

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

Am incercat si asa,dar imi iese din timp .  :D
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?

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

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

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

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 :) mai ales la arhiva educationala.

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

mai exact, in partea asta de cod:
dupa ce a-ul a fost declarat:
daca nu e voie sa incerc sa accesez a[var1][var2], cum de sursa aceea a  luat 100? ???

posibil sa fie compilatorul devina ..........mie imi merge perfect :D  .  Incearca fara vectori STL, folosind Lista de adiacenta alocata dinamica :D
ps :incercat  cu Borland C++ 5.01 ,dar daca merge pe el merge pe orice garantez :P

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:

Mi-a luat cam mult timp ca sa obtin 100 de puncte la problema asta(in Free Pascal)  :D. 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  :shock: :yahoo:

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

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

gata ms :D

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

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.

Acelasi lucru da si cu STL`u  ](*,)

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

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.

Asa e, scuze  :?

La BFS tu adaugi in coada fiecare nod cel mult o data! Atunci coada are nevoie de N elemente!
Probabil se confunda BFS cu Bellman-Ford cu coada, cand un nod e introdus in coada de mai multe ori!!!

ms @klamathix

ceva idee de rezolvare in pascal? in c am vazut ceva ciudat...un fel de record..vector..semimatrice habar nam cu stl(sau std ziceati voi pe aici...) dar in pascal nu stiu daca exista asa ceva? ceva poate alocare dinamica sau nu inteleg...

Se cheama STL :-'
Am facut o filtrare dupa sursele din pascal care au luat 100pct poate te ajuta http://infoarena.ro/monitor?task=bfs&compiler=fpc&score_begin=100 :)

Buna,

mi-ati putea spune cum vad testele de la problema parcurgere in latime?

Pe fondul galben ai : De asemenea, poti vedea si testele accesand atasamentele. Dai click pe el si ai acolo testele . ( uite aici un link, http://infoarena.ro/problema/bfs?action=attach-list ) . Test.in inseamna input, iar Test.ok inseamna ce trebuie sa afiseze programul.

Mie-mi scrie la "scorul tau in arhiva" N/A desi am ultima sursa trimisa are 100 de puncte.

In arhiva educationala, nu iti arata scorul obtinut, aceasta facilitate va fi adaugata doar la IA 3.

Si ce e de preferat cand lucrezi cu cozi?
deque sau queue?

Depinde de ce ai nevoie. Daca la un capat doar adaugi si la celalalt doar stergi atunci foloseste queue :D

Cum se citesc numerele din fisierul de iesire la evaluare?
Ca am vazut ca daca afisezi cu format " %i" in loc de "%i ", iei 0 in loc de 100.
Adica daca erau string-uri era clar ca conta. Dar vad ca si la numere conteaza daca afisezi un spatiu in fata.

Care credeti ca ar fi cauza de iau time limit exceeded?Implementare cu STL.http://infoarena.ro/job_detail/633394?action=view-source

Nu ai complexitatea buna. Tu faci cate un bfs pt fiecare nod. Ideea e sa il faci doar odata pt toate nodurile si retii intr-un vector rezultatele. Datele de intrare fiind mari s-ar putea sa ajute si citirea cu streamuri. Si apropo, sper sa nu gresesc, dar nu are niciun efect acel long  :-'

Am si eu o nelamurire. Am de exemplu N=4(nr noduri) si M=3(nr drumuri), iar drumurile sunt asa:
1 2
1 3
4 1
Inteleg ca daca adaug fiecarui nod toti vecinii, adica v[ x ].push_back(y) si v[ y ].push_back(x), irosesc multa memorie, dar daca dau doar v[ x ].push_back(y) si fac BFS din nodul 1, nu risc sa nu treaca prin nodul 4??? :-s

Nu irosesti memorie. E necesar sa le tii pe ambele directii.

Imi poate explica cineva de ce iau Killed by signal pe toate testele..dupa calculele mele nu am depasit memoria disponibila...sursa:http://www.infoarena.ro/job_detail/1019769?action=view-source (http://www.infoarena.ro/job_detail/1019769?action=view-source)

http://www.infoarena.ro/job_detail/1019765?action=view-source (http://www.infoarena.ro/job_detail/1019765?action=view-source)-aici am pus 5000..si tot aceiasi chestie e.Nu ar trebui sa prind cateva teste?

Poate nu exista astfel de teste. De ce nu vrei sa pui cat trebuie? :)

Daca puneam cat trebuie depaseam memoria disponibila...oricum acum am implementat in algoritm un deque si am optinut 50 de puncte  :) Am vazut la o sursa de 100 p ca nu a implementat tablouri bidimensionale..astfel ca i-a ajuns memoria.. nu am nici cea mai mica idee cum se face cu tablouri unidimensionale.

Poti implementa graful cu liste de adiacenta.

Si daca implementez liste de adiacenta,fara sa le aloc dinamic (tot un tablou bidimensional),pierd cumva timp de executie?sau doar memorie?

E mai rau din toate punctele de vedere.

Buna seara ,am facut problema aceasta si cea cu sortarea topologica in java si la ambele am runtime error nu inteleg de ce

Buna seara!
Primesc aceasta eroare:
Eroare de compilare:
Main.java:8: error: class Bfs is public, should be declared in a file named Bfs.java
public class Bfs {
^
1 error

si nu inteleg pentru ca m-am asigurat ca numele sursei coincide cu numele clasei.

Problema apare de la faptul ca sursa ta este automat redenumita in Main.java. Clasa ta ar trebui sa se numeasca Main nu BFS.

Imi puteti raspunde si mie ? din ce cauza primesc runtime error ?

Se poate sa se uite cineva la sursa mea? Am verificat testele si am raspunsurile bune. Cu toate astea, primesc la toate testele incorect pe site. Cu siguranta e o greseala penibila dar nu pot sa o vad...

Pt. ultimul care a intrebat: http://www.infoarena.ro/job_detail/1836210
Declararea : ifstream .. nu fstream...

Ah... Ce greseala de incepatori. Nu inteleg totusi de ce nu am primit vreo eroare. In orice caz, multumesc mult de raspuns

 :rotfl: ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,)

Sursele trimise in java pe Infoarena trebuie sa se numeasca Main.java (si implicit numele clasei trebuie sa se numeasca Main)