|
Titlul: 346 Padure Scris de: Bogdan-Cristian Tataroiu din Martie 13, 2007, 20:07:20 Aici puteţi discuta despre problema Padure (http://infoarena.ro/problema/padure).
Titlul: Răspuns: 346 Padure Scris de: Tabara Mihai din Martie 13, 2007, 21:37:39 Iau 'Incorect' pe 50% din teste.Dar nu imi dau seama de ce.. :'(.Problema nu pare iesita din comun si din moment ce am luat 50 de puncte, as tinde sa cred ca algoritmul este bun, insa am alta greseala.
Sa fie de la faptul ca am facut Lee pe matrice de 1000*1000 ? :? [Later Edit] .E de la algoritm sigur.Am facut mici modificari si iau 60 :-k Si totusi are cineva idee ce as putea gresi.. ](*,) ](*,) :oops: :'( Titlul: Răspuns: 346 Padure Scris de: Ionescu Vlad din Martie 13, 2007, 23:54:46 Eu nu reusesc nici cum sa trec de 50 de puncte...
Cu matrice de 1000x1000 si coada de 1000x1000 iau sigsegv pe toate testele, cu coada de 1000x1000 si matrice de 700x700 iau 50... un memory limit exceeded, 3 sigsegv si un incorect... Ceva indicii pentru reducerea memoriei? :/ Titlul: Răspuns: 346 Padure Scris de: Tabara Mihai din Martie 14, 2007, 14:26:37 Eu nu reusesc nici cum sa trec de 50 de puncte... Cu matrice de 1000x1000 si coada de 1000x1000 iau sigsegv pe toate testele, cu coada de 1000x1000 si matrice de 700x700 iau 50... un memory limit exceeded, 3 sigsegv si un incorect... Ceva indicii pentru reducerea memoriei? :/ Ma mir... ???..mie imi intra doua matrici de 1000*1000 plus o coada de c[2501][2]. Oricum, daca crezi ca de la memorie ti se trage ai putea face cu alocare dinamica cand calculezi a doua matrice ( cea dinamica ) si retii doar rezultatul final care te intereseaza. :thumbup: P.S. Daca iei 100, sa ma dumiresti si pe mine ca nu inteleg ce am gresit :'( :peacefingers: Titlul: Răspuns: 346 Padure Scris de: Airinei Adrian din Martie 14, 2007, 14:57:01 Daca nu descrii ceea ce faci, nu prea te poate ajuta nimeni.
Poti sa reduci memoria de exemplu retinand o pozitie (x,y) intr-un singur int: Cod: int poz = (x<<10)+y; Cod: x = poz>>10, y = poz&1023 Titlul: Răspuns: 346 Padure Scris de: Tabara Mihai din Martie 14, 2007, 15:10:50 Am incercat eu si cu char si tot 60 iau.Dar faza este ca daca ar fi de la memorie nu ar trebui sa ma astept la ceva de genul : Memory Limit Excedeed sau KILLES BY SIGNAl ....
In schimb eu iau WA :? :? Eu cred ca gresesc algoritmul. Am facut o matrice b[i,j] - numarul minim de diamante cu care am putut ajunge pe pozitia (i,j), iar in Lee am facut asa Cod: if ( b[iv][jv] > b[i][j] && a[iv][jv] == a[i][j] ) a[i,j] - matricea initiala, iar c e coada. Titlul: Răspuns: 346 Padure Scris de: Ionescu Vlad din Martie 14, 2007, 15:39:31 Cred ca am rezolvat cu memory limit exceeded folosind char, dar sigsegv-urile tot au ramas...
Cred ca-i din cauza cozii, ca am reusit sa iau 60 punand coada pe 1500x1500 de la 1000x1000... cam de cat ar trebui sa fie coada? :/ algoritmul meu ar fi: am o structura cu doua componente, x si y, si un vector lee de aceasta structura declarat 1500x1500; o matrice de tip char b de 1000x1000 in care imi calculez valorile, initializata cu 127; o matrice de tip short a in care citesc valorile. lee[0].x = startx-1, lee[0].y = starty-1; b[startx-1][starty-1] = 0; pentru fiecare element din coada, daca este posibil sa merg intr-o noua directie (nu depaseste granitele matricei, si valoarea b[inou][jnou] este mai mare decat valoarea b[ i ][j], atunci adaug noul element in coada. daca a[inou][jnou] != a[ i ][j] atunci b[inou][jnou] = b[ i ][j] + 1; cam asta ar fi ideea... totusi iau 4 sigsegv pe ultimele 4 teste... postez si cod daca am voie. Titlul: Răspuns: 346 Padure Scris de: Airinei Adrian din Martie 14, 2007, 15:42:21 Asta nu prea e lee (parcurgere bf). E un bellman-ford, adica tu introduci un element de mai multe ori in coada, spre deosebire de o parcurgere unde introduci fiecare element doar o singura data si stii sigur care ar fi numarul maxim de elemente din coada.
Titlul: Răspuns: 346 Padure Scris de: Ionescu Vlad din Martie 14, 2007, 16:05:16 Da, intr-adevar e posibil sa se introduca de mai multe ori unele elemente... cum as putea face sa introduc o singura data? asa nu as risca sa nu obtin intotdeauna solutia corecta?
Titlul: Răspuns: 346 Padure Scris de: Airinei Adrian din Martie 14, 2007, 16:07:18 Poti rezolva problema printr-o parcurgere bf (eu am facut ceva cu 2 cozi). Adica calculezi intai toate nodurile pentru care distanta este 0, apoi 1 si tot asa pana cand ai vizitat pozitia finala.
Titlul: Răspuns: 346 Padure Scris de: Savin Tiberiu din Martie 14, 2007, 16:23:36 am si eu probleme cu memoria dar am impresia ca felul in care am abordat eu problema nu merge cu memorie mai putine. Fac intai un FILL si imi creez niste zone in matrice in care ma pot misca fara sa platesc nimik, apoi ptr creez un graf in care fiecare zona reprezinta un nod si am muchii intre oricare 2 zone vecine, si fac un bf de la nodul sursa la nodul destinatie (nodul sursa si nodul destinatie corespund zonelor in care se afla printul algorel respectiv castelul). Totusi insa acel graf poate avea n^2 noduri si de aceea banuiesc ca iesa din memorie. se poate reduce memoria folosind aceasta idee sau tre sa incerc alta abordare??
PS: asa iau 70 de pct Titlul: Răspuns: 346 Padure Scris de: Barca Cristian Mihai din Martie 14, 2007, 17:50:49 Poate nu-ti mai iese din memorie daca folosesti o coada circulara... :-k
Titlul: Răspuns: 346 Padure Scris de: Florian Marcu din Iulie 02, 2007, 16:20:46 La problema asta iau 60 de puncte, cu KBS pe ultimile 4. Am doua matrici de tip int 1000*1000, o coada de 100.000, formata dintr-un vector de tip int [ am folosit kestia aia pe biti prezentata mai sus, care retine intr`o variabila doua pozitii], si inca cateva variabile tot de tip int. Care este problema? Vrea cineva care a facut problema sa-mi spuna cam cata memorie a folosit? :?
Titlul: Răspuns: 346 Padure Scris de: Andrei Homorodean din Iulie 02, 2007, 17:58:39 Daca tii 2 cozi cum s-a zis mai sus, iti intra sigur, si in memorie si in timp.
Titlul: Răspuns: 346 Padure Scris de: Airinei Adrian din Iulie 02, 2007, 18:03:20 Spui ca ai o coada de dimensiune 100.000, dar esti sigur ca e suficient? Coada ar putea ajunge la dimensiuni mai mari
Titlul: Răspuns: 346 Padure Scris de: Florian Marcu din Iulie 02, 2007, 19:34:33 Daca tii 2 cozi cum s-a zis mai sus, iti intra sigur, si in memorie si in timp. Nu prea inteleg solutia asta...si orikum....kred k dak intra in memorie, ar trebui sa mearga si programul meu... Spui ca ai o coada de dimensiune 100.000, dar esti sigur ca e suficient? Coada ar putea ajunge la dimensiuni mai mari Am o coada de 100.000, insa la pozitiile de start si de sf am pus asa: poz=(poz+1)%100.000. Nu e deajuns k sa o transform in coada circulara? Titlul: Răspuns: 346 Padure Scris de: Ionescu Vlad din Iulie 02, 2007, 19:42:02 Eu parca am folosit ~14 mega pe ultimul test. Ideea a fost sa am o functie recursiva care sa ma "scoata" din zonele cu acelasi numar pe ele, fara a le mai baga din nou in coada. Poate te ajuta asta.
Alta ideea ar fi sa faci coada dinamica, sub forma de lista inlantuita. Daca p e inceputul, cand mergi in p->next, il stergi pe p. Nu stiu daca te ajuta la problema asta... mie mi-a mers cu coada facuta pe vector si functie recursiva asa ca nu am mai implementat si asa. Titlul: Răspuns: 346 Padure Scris de: Florian Marcu din Iulie 02, 2007, 19:52:21 Functia aia recursiva o apelai de fiecare data cand introduceai un element in coada? Si il pastrai doar pe cel optim?
Titlul: Răspuns: 346 Padure Scris de: Ionescu Vlad din Iulie 02, 2007, 20:40:01 Apelul initial se face de fiecare data cand scoti un element din coada si vrei sa-l expandezi.
Titlul: Răspuns: 346 Padure Scris de: Ionescu Robert Marius din Ianuarie 10, 2008, 15:01:26 care e dimensiunea maxima la care poate sa ajunga coada :peacefingers: ca eu am dat 400.000 si am un tesct cu incorect unu cu KBS si restul sunt bune
P.S am scos 100 :D 10x Titlul: Răspuns: 346 Padure Scris de: Andrei Homorodean din Ianuarie 10, 2008, 23:50:16 Poti sa verifici tu asta.. Bagi o linie in program in care daca sfarsitul cozii depaseste o anumita valoare, dai sa ruleze instructiunea a[-1] si iei segmentation fault... Mai e o varianta sa faci for( ; ; ) si de la care ai lua tle, dar banuiesc ca ai tle-uri aici. :)
Titlul: Răspuns: 346 Padure Scris de: razyelx din Martie 06, 2009, 20:50:06 Iau incorect pe ultimele 4 teste. Rezolvarea e cea cu coada circulara, in care adauga un element de fiecare data cand se indeplineste o conditie. totusi mi-e nu imi iese din timp, imi da incorect pe ultimele 4. Ajutati-ma!!!
Titlul: Răspuns: 346 Padure Scris de: Andrei Misarca din Martie 06, 2009, 21:44:19 Descrie putin algoritmu' pe care il folosesti
Titlul: Răspuns: 346 Padure Scris de: razyelx din Martie 06, 2009, 23:20:33 Am doua matrici de 1000 * 1000(b[][] o initializez cu -1) si o coada de 4000 de elemente. Fac o parcugere din (pl, pc)(pozitia de start din b[][] are valoarea 0 in loc de -1) in toate cele 4 directii. Prima conditie ca un element sa fie introdus in coada este ca sa fie in matrice. Apoi dupa ce trece de aceasta vin doua ramuri mari:
1.daca a[x2][y2] == a[x1][y1] daca b[x2][y2] > b[x1][y1] || b[x2][y2] , b[x2][y2] = b[x1][y1] si adaug elementul in coada 2.daca a[x2][y2] != a[x1][y1] daca b[x2][y2] > b[x1][y1]+1 || b[x2][y2]==-1 , b[x2][y2] = b[x1][y1]+1 si adaug elementul in coada Coada este circulara. Parcurgerea se opreste cand prim == ultim. Nu inteleg unde e greseala. Titlul: Răspuns: 346 Padure Scris de: Andrei Misarca din Martie 08, 2009, 10:00:29 Cam asa ceva am facut si eu, numa' ca am folosit 2 cozi, una pentru elementele egale cu elementul curent, una pentru elementele diferite.
Evident, cand scot un element din coada, prioritate vor avea cele din coada elemntelor egale cu elementul anterior, iar in caz ca aceasta este vida voi scoate un element din coada elementelor diferite. :) Sper ca si inteles ceva din ce am scris mai sus :D Titlul: Răspuns: 346 Padure Scris de: razyelx din Martie 08, 2009, 12:48:06 Interesanta ideea, dar poti sa imi dai un exemplu pentru care algoritmul meu cade?
Titlul: Răspuns: 346 Padure Scris de: Andrei Misarca din Martie 08, 2009, 13:47:27 Ai grija la coada circulara... oricum interesant ca iei WA, pt ca ar trebui sa iei TLE (tu adaugi un element in coada de mai multe ori)
Titlul: Răspuns: 346 Padure Scris de: razyelx din Martie 08, 2009, 15:15:41 Pai adaug un element dupa conditiile care le-am pus mai sus. Eu zic ca e ok. Cum altfel as putea restrictiona adaugarea?Nu prea ar trebui sa iau TLE. Dar ar fi mai bine decat WA pe 4 teste. Am incercat cum ai zis si tu: cu doua cozi. Algoritmul e ceva de genu:
cat timp coada 1 nu este vida{ verifica vecinii lui a[x1][y1]{ daca a[x2][y2] == a[x1][y1] daca b[x2][y2] > b[x1][y1] || b[x2][y2] , b[x2][y2] = b[x1][y1] si adaug elementul in coada 1 daca a[x2][y2] != a[x1][y1] daca b[x2][y2] > b[x1][y1]+1 || b[x2][y2]==-1 , b[x2][y2] = b[x1][y1]+1 si adaug elementul in coada 2 } daca coada 1 este vida daca coada 2 nu este vida preia in coada 1 primul element din coada 2 } Dar iau doar 40 de puncte pe el. Deci era mai bun celalalt. Titlul: Răspuns: 346 Padure Scris de: Andrei Misarca din Martie 08, 2009, 20:57:45 Ceva de genu am facut si eu :D Ai grija sa nu-ti crape cand faci coada circulara.
Daca vrei iti trimit sursa, poate te lamuresti mai bine :) Titlul: Răspuns: 346 Padure Scris de: Cosmin-Mihai Tutunaru din Martie 09, 2009, 23:59:28 Ma cam supara problema asta :D
Am facut prima data o rezolvare cu Bellman Ford, si obtin 60 pct (restul TLE) Acum...m-am gandit sa fac cu Dirjkstra....si obtine 90 pct (TLE pe testul 9) Ce rezolvare ar trebui sa aplic? p.s. rezolvare pt 100 pct :readthis: Titlul: Răspuns: 346 Padure Scris de: Andrei Misarca din Martie 10, 2009, 18:07:51 Cred ca te-ai complicat putin cu Dijkstra... merge un bf putin mai smecher (vezi ideea cu 2 cozi) :)
Titlul: Răspuns: 346 Padure Scris de: Cosmin-Mihai Tutunaru din Martie 10, 2009, 18:24:38 Cred ca te-ai complicat putin cu Dijkstra... merge un bf putin mai smecher (vezi ideea cu 2 cozi) :) De ce sa am doua cozi? Nu e mai bine daca am o singura coada circulara? LE: Am luat 100 pct cu Dijkstra cu citirea parsata :yahoo: Titlul: Răspuns: 346 Padure Scris de: Andrei Grigorean din Martie 10, 2009, 18:28:35 Daca citesti posturile anterioare cu multa atentie, vei vedea ca problema nu este un BF simplu, e putin mai complicat - de aceea ai nevoie de 2 cozi.
Titlul: Răspuns: 346 Padure Scris de: Vlad Eugen Dornescu din Aprilie 03, 2010, 22:12:24 Eu iau 5 WA pe ultimele 5 teste cu 2 cozi de 520000 elemente. Un hint ? Se poate sa gresesc ceva ?
Eu fac un lee asa: Cod: while(first<last)//cat timp mai am elemente in coada Titlul: Răspuns: 346 Padure Scris de: Vlad Tarniceru din Noiembrie 27, 2010, 11:39:38 am nevoie de putin ajutor, eu iau 70 de puncte cu TLE si nu stiu ce as mai putea optimiza
eu fac asa lee-ul Cod: for (; !Q.empty (); ){Titlul: Răspuns: 346 Padure Scris de: Pripoae Teodor Anton din Noiembrie 27, 2010, 13:59:00 Verifica daca e in coada atunci cand updatezi, daca e, nu il mai baga inca o data.
Titlul: Răspuns: 346 Padure Scris de: Vlad Tarniceru din Noiembrie 27, 2010, 16:16:18 mersi de hint, dar e mai incet ca inainte (60 pct de data asta)... ca sa fac asta am luat o matrice c[ i ][ j ] in care verific daca apare sau nu :?
Titlul: Răspuns: 346 Padure Scris de: FMI Ciprian Olariu din Iunie 11, 2011, 19:09:42 (stiu ca nu s-a mai postat de ceva vreme,dar am nevoie de ajutor)
Poate sa-mi explice cineva sau macar sa-mi dea un indiciu despre rezolvarea corecta(cu 2 cozi din cate inteleg) ? Eu iau 60 cu memory exceeded folosind o coada alocata dinamic care bineinteles baga de prea multe ori acelasi element si depaseste memoria ??? Am folosit si acea codificare a coordonatelor sugerata de Adrian Airinei,dar nu rezolva asta problema cu memoria Cod: inc=0; LE : s-a rezolvat,am luat 100pct :peacefingers: Mersi Magnus (http://infoarena.ro/utilizator/magnus) pentru indicatii :D Titlul: Răspuns: 346 Padure Scris de: cont cu nume gresit sau fals din Iunie 11, 2011, 19:40:08 faci un bfs din start, apoi sa zicem ca tu ai ajuns la un nod
pt vecinii lui faci un bfs/dfs pentru copacii de aceeasi specie sper ca am dat doar un hint :) l.e.: si bineinteles tii o matrice care sa tina minte daca elementul este sau nu in coada deja Titlul: Răspuns: 346 Padure Scris de: Mihai Visuian din Ianuarie 03, 2012, 15:07:13 0 inseamna copac sau spatiu liber?
Titlul: Răspuns: 346 Padure Scris de: Paul-Dan Baltescu din Ianuarie 03, 2012, 15:24:46 0 simbolizeaza un tip de copac, la fel ca celalalte numere naturale.
Titlul: Răspuns: 346 Padure Scris de: Mihai Visuian din Februarie 28, 2012, 09:49:37 Nu stiu de ce iau KBS pe ultimele teste... Am declarat 2 matrici de 1001*1001 si o coada de 1002001;
Nu am nicio idee pe unde iese programul din limite. P.S: Am facut un BFS Modificat. Titlul: Răspuns: 346 Padure Scris de: Salajan Razvan din Aprilie 17, 2012, 21:09:15 Am nevoie de niste sfaturi de la cei care au luat 100.
Am trimis mai multe surse printre care : bellman ford(70), dijkstra(70); Ultima sursa trimisa de la care ma asteptam sa i`au 100 m`a dezamagit(doar 80 cu tle pe ultime 2 teste).Am o parcurgere in latime si una in adancime. Pentru fiecare nod nou adaugat in coada fac un fill si bag in coada toti vecinii care sunt la fel. Complexitatea ar fi O (n + m) pentru ca un nod e introdus in coada doar o singura data. Titlul: Răspuns: 346 Padure Scris de: andreycurent din Aprilie 17, 2012, 21:22:09 Si eu am problema asta de multa vreme la incercate... Cred ca solutia e :
,,Poti rezolva problema printr-o parcurgere bf (eu am facut ceva cu 2 cozi). Adica calculezi intai toate nodurile pentru care distanta este 0, apoi 1 si tot asa pana cand ai vizitat pozitia finala." . E comentariu pe prima pagina. Pare interesanta solutia asta, dar mereu mi-a fost lene sa o implementez. Mi-am zis si eu of-ul.. :indifferent: Titlul: Răspuns: 346 Padure Scris de: Simoiu Robert din Aprilie 17, 2012, 21:33:03 Cam trebuie marita limita, eu cu sursa veche iau 70 pct ....
Titlul: Răspuns: 346 Padure Scris de: UAIC.VlasCatalin din August 14, 2012, 21:10:58 Mda limita chiar este destul de strinsa si la memorie si la timp, daca rezolv problema cu memoria am TLE pe un test, iar daca rezolv problema cu timpul am MLE pe acelasi test, cred ca ar trebui marit timpul la 0,2 ms ](*,)
Titlul: Răspuns: 346 Padure Scris de: Tudor Tiplea din August 14, 2012, 21:20:58 @Catalin: Se poate lua inca 100, daca parsezi citirea si folosesti 2 cozi, una in care pui elemente daca e egal cu elementul curent, si una normala (la limita, da, dar intra). Bafta! :)
Titlul: Răspuns: 346 Padure Scris de: UAIC.VlasCatalin din August 14, 2012, 22:01:49 Nu prea inteleg cum sa fac cu doua cozi insa am luat 100 pina la urma cu timpul maxim ~100 ms, si memorie ~4,5 MB, adica destul de departe de limite, la fel am facut parsare apoi mi-am creat o lista circulara de 20 000 de elemente pe care am folosit-o ca coada :D
Titlul: Răspuns: 346 Padure Scris de: Mihai Calancea din August 14, 2012, 23:37:15 Incearca sa intelegi cum se face cu 2 cozi. Sfatul meu e sa incercati sa invatati lucruri din probleme, nu sa le invingeti, i.e sa luati 100 :) Nu parsati si faceti incantatii ca sa mearga codul mai repede, noi vom mari limitele suficient incat sa nu fie niciodata nevoie sa faceti asta daca algoritmul e corect (cu mici exceptii gen cele ale lui Ciucu, ca acolo ala-i farmecul):D
Ideea principala la solutia cu 2 cozi e ca in momentul in care expandezi un nod sa oferi prioritate vecinilor de aceeasi culoare cu el. Ceea ce inseamna ca mai tii o coada cu toti vecinii de expandat de culoarea curenta si de fiecare data cand alegi un nod pentru expandat verifici intai prima coada si treci la a doua doar daca nu mai ai nimic de aceeasi culoare. Ca sa intelegi de ce merge asta mult mai repede, gandeste-te cand merge incet Bellman-Fordul: cand are de reactualizat costul pentru acelasi nod de multe ori. Cod: 111 Uita-te putin pe exemplul asta. Daca vrei sa ajungi din dreapta sus in dreapta jos si pornesti un BF, exista sansa ca el sa sa gaseasca prima oara costul 5. Apoi sa gaseasca unul de 4, etc. Daca dai prioritate 1-urilor in expandare mergi la fix din prima si nu mai reiterezi nimic. For further reference, problema asta este un caz particular de Dijkstra cu costuri mici (aici costurile sunt doar 0 si 1). Ideea se poate adapta, e explicat destul de bine in topicul din arhiva educationala: http://infoarena.ro/forum/index.php?topic=2778.0 Titlul: Răspuns: 346 Padure Scris de: Radu-Andrei Szasz din August 15, 2012, 10:58:48 Eu am incercat sa implementez varianta cu 2 cozi(prima pentru elementele pentru care nu se plateste in plus, a doua pentru cele pentru care e necesara plata unui cristal) si am luat 50p, cu 2 WA si 3 TLE. WA il iau din cauza ca daca am in prima coada sa zicem o pozitie pe care se afla un copac de tip 7 si acesta e vecin cu un copac de tip 1, pe cel de tip 1 il bag in a doua coada. Daca copacul de tip 1 are si un alt copac de tip 1 ca vecin, care se afla deja in prima coada, eu actualizam valoarea, dar nu il bagam pe 1 si in prima coada. Astfel incat nu mai era corect sa opresc algoritmul imediat dupa ce ajungeam in nodul de final(puteam avea costuri mai mici in aceeasi coada). Dar asta m-ar scapa de WA. Eu nu stiu cum pot scapa de TLE.
PS nu bag un nod in coada decat daca i se imbunatateste costul(ceea ce se intampla maxim de doua ori <initial el fiind infinit, iar mai apoi poate avea loc cazul de mai sus in care il bag in ambele cozi>) Titlul: Răspuns: 346 Padure Scris de: UAIC.VlasCatalin din August 15, 2012, 13:17:00 Nu cred ca pentru algoritmul implimentat de mine exista cazuri cind poate fi imbunatatit de doua ori costul unui nod, teoretic la mine fiecare celula poate fi introdusa in coada cel mult odata, eu tin un tablou auxiliar b, unde b[ i ] [ j ]=costul minim pentru a ajunge din pozitia finala in pozitia i,j plus 1; respectiv raspunsul este b[ x1 ][ y1 ] - 1; mai intii introduc in coada toate celulele care au acelasi cost ca si pozitia finala si marcez in b, apoi pentru fiecare celula din coada controlez daca are vecin de culoare diferita care inca nu a fost expadat si daca are introduc vecinul respectiv in coada apoi toate celulele de aceeasi culoare cu vecinul si respectiv marchez in b si astfel pina cind pozitia de start are valoarea 0, repectiv pentru testul:
111 122 133 144 155 111 daca vreau sa ajung din 1,1 in 6,3 atunci voi introduce in coada toate pozitiile cu costul 1, si deodata afisez solutia adica destul de repede, iar daca vreau alta pozitie e deajuns inca un pas ca se aflu solutia adica de ex cind expadez 1,2 voi nota ambele pozitii cu costul 2 si le voi pune in coada, apoi pentru 1,3 nu fac nimic, apoi voi marca pe pozitiile cu costul 3, apoi cu 4 si in final cu 5, avind toate pozitiile incluse in coada o singura data si cred ca chiar daca scot parsarea oricum acest algoritm nu v-a merge mai incet decit cel cu 2 cozi :? Titlul: Răspuns: 346 Padure Scris de: Bodnariuc Dan Alexandru din August 25, 2012, 16:44:29 eu m-am gandit la solutia lui devilkind, fac un fill si dupa aia fac un graf. Ca sa nu pun muchiile de mai multe ori la un nod m-am gandit sa folosesc un set (sau map) numai ca cum zicea el pot fi pana la n^2 noduri in graf si imi pun urmatoarea intrebare:
daca declar un set <char> A[1000.000] ocupa ceva? adica per total nu bag mai mult de n^2 muchii numai ma gandesc sa nu ocupe pointerii memorie. Declararea unui set nu ocupa memorie daca e doar declarat(nu pun nimic in el)? Titlul: Răspuns: 346 Padure Scris de: Adrian Budau din August 25, 2012, 16:52:43 Ba da. Fiecare set ocupa cativa bytes(Daca imi amintesc bine ocupa 12). Si fiecare element din set aduce cu el inca 8 bytes.
Titlul: Răspuns: 346 Padure Scris de: Bodnariuc Dan Alexandru din August 25, 2012, 19:33:28 si <vector>,<list> ocupa ceva?
Titlul: Răspuns: 346 Padure Scris de: Adrian Budau din August 25, 2012, 20:38:26 vector 12 bytes si list 8 bytes. List mai ocupa 8 bytes pe element iar vector ocupa(deobicei) mai mult decat e marimea lui. Daca ai x elemente in vector el ocupa cat 2^k elemente unde k e cel mai mic numar natural astfel incat 2^k >= x
Titlul: Răspuns: 346 Padure Scris de: Bodnariuc Dan Alexandru din August 25, 2012, 23:34:07 ok mersi :thumbup:
Titlul: Răspuns: 346 Padure Scris de: Oncescu Costin din Octombrie 16, 2012, 16:40:20 Ati putea sa imi dati si mie niste teste ca iau 20 cu tle dar sunt sigur ca imi cicleaza.Pe testele pe care mi le-am dat mi-a mers.
Multumesc anticipat :) Titlul: Răspuns: 346 Padure Scris de: Pirtoaca George Sebastian din Octombrie 16, 2012, 16:53:30 Uite aici :
Cod: 30 15 7 10 25 8 Cod: 10 17 5 10 8 17 Sper sa te ajute. Titlul: Răspuns: 346 Padure Scris de: Oncescu Costin din Octombrie 18, 2012, 15:36:35 Mutumesc mult!Chiar m-a ajutat
Titlul: Răspuns: 346 Padure Scris de: Marian Iacob din Decembrie 05, 2012, 16:59:00 Imi explica si mie cineva dc iau tle pe testul 9 ca nu-mi dau seama! ](*,)
multumesc! Titlul: Răspuns: 346 Padure Scris de: Pirtoaca George Sebastian din Decembrie 05, 2012, 20:38:46 Trebuie sa parsezi citirea pentru 100. Si eu aveam complexitatea optima O(n*m) si luam TLE. Bafta! :ok:
Titlul: Răspuns: 346 Padure Scris de: Marian Iacob din Decembrie 06, 2012, 10:11:42 ms fain!! am luat 100 :yahoo: ...aia era problema!!
Titlul: Răspuns: 346 Padure Scris de: Alexandru Valeanu din Ianuarie 25, 2013, 21:10:27 Poate sa-mi spune si mie cineva cum mai poate fi modificata sursa mea pentru a intra in timp?
Titlul: Răspuns: 346 Padure Scris de: Pirtoaca George Sebastian din Ianuarie 26, 2013, 09:19:53 Problema se rezolva folosind 2 cozi (nu cu o parcurgere in latime simpla). Calculezi mai intai nodurile cu distanta 0 , apoi cele cu distanta 1 , s.a. Merge mai repede asa deoarece rezultatul va fi un numar mic. Succes! :ok:
Titlul: Răspuns: 346 Padure Scris de: Alexandru Valeanu din Martie 06, 2013, 00:19:07 Poate cineva sa posteze niste teste mai mari/dificile...iau la 5 teste WA si chiar nu imi explic de ce.
Titlul: Răspuns: 346 Padure Scris de: Constantin Mihai din Ianuarie 20, 2016, 15:51:49 Poate cineva sa puna testul 2, va rog? Iau 90 de puncte si nu inteleg unde am gresit...
Multumesc. Titlul: Răspuns: 346 Padure Scris de: Constantin Mihai din Ianuarie 20, 2016, 16:24:00 Am reusit. 100p :yahoo:
|