Pagini: [1] 2 3   În jos
  Imprimă  
Ajutor Subiect: 346 Padure  (Citit de 19022 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« : Martie 13, 2007, 20:07:20 »

Aici puteţi discuta despre problema Padure.
Memorat
Tabara
Nu mai tace
*****

Karma: 20
Deconectat Deconectat

Mesaje: 216



Vezi Profilul
« Răspunde #1 : Martie 13, 2007, 21:37:39 »

Iau 'Incorect' pe 50% din teste.Dar nu imi dau seama de ce.. Cry.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 ?
 Confused

[Later Edit] .E de la algoritm sigur.Am facut mici modificari si iau 60  Think
Si totusi are cineva idee ce as putea gresi.. Brick wall Brick wall
 Embarassed  Cry
« Ultima modificare: Martie 13, 2007, 23:20:19 de către Tabara Mihai » Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #2 : 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? :/
Memorat
Tabara
Nu mai tace
*****

Karma: 20
Deconectat Deconectat

Mesaje: 216



Vezi Profilul
« Răspunde #3 : 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... Huh..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.
 Thumb up

P.S. Daca iei 100, sa ma dumiresti si pe mine ca nu inteleg ce am gresit  Cry
 peacefingers
Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #4 : 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;
si pentru decodificare
Cod:
x = poz>>10, y = poz&1023
Asa e si foarte rapid, fiindca faci doar operatii pe biti. Apoi, matricea de costuri poate fi de tip char fiindca elementele <= 104.
Memorat
Tabara
Nu mai tace
*****

Karma: 20
Deconectat Deconectat

Mesaje: 216



Vezi Profilul
« Răspunde #5 : 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  Confused Confused

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] )
                    {
                         b[iv][jv] = b[i][j];
                         ultim++;
                         c[ultim][0] = iv;
                         c[ultim][1] = jv;
                    }
                    if ( b[iv][jv] - b[i][j] > 1 && a[iv][jv] != a[i][j] )
                    {
                         b[iv][jv] = b[i][j] + 1;
                         ultim++;
                         c[ultim][0] = iv;
                         c[ultim][1] = jv;
                    }
unde iv, jv sunt pozitiile actuale cu care merg, iar i,j pozitiile de pe care am venit.
a[i,j] - matricea initiala, iar c e coada.
« Ultima modificare: Martie 14, 2007, 15:13:09 de către Tabara Mihai » Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #6 : 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.

« Ultima modificare: Martie 14, 2007, 15:41:10 de către Ionescu Vlad » Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #7 : 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.
Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #8 : 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?
Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #9 : 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.
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #10 : 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
Memorat
mocke
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 19



Vezi Profilul WWW
« Răspunde #11 : Martie 14, 2007, 17:50:49 »

Poate nu-ti mai iese din memorie daca folosesti o coada circulara... Think

Memorat

oricine greseste...nu oricine invatza
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #12 : 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?  Confused
Memorat
peanutz
Nu mai tace
*****

Karma: 10
Deconectat Deconectat

Mesaje: 296



Vezi Profilul
« Răspunde #13 : 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.
Memorat

....staind....
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #14 : 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
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #15 : 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?
Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #16 : 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.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #17 : 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?
« Ultima modificare: Iulie 02, 2007, 20:06:37 de către Marcu Florian » Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #18 : Iulie 02, 2007, 20:40:01 »

Apelul initial se face de fiecare data cand scoti un element din coada si vrei sa-l expandezi.
Memorat
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #19 : 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 Very Happy 10x 
« Ultima modificare: Ianuarie 11, 2008, 16:16:19 de către Ionescu Robert Marius » Memorat
peanutz
Nu mai tace
*****

Karma: 10
Deconectat Deconectat

Mesaje: 296



Vezi Profilul
« Răspunde #20 : 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. Smile
Memorat

....staind....
razyelx
Client obisnuit
**

Karma: 0
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #21 : 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!!!
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #22 : Martie 06, 2009, 21:44:19 »

Descrie putin algoritmu' pe care il folosesti
Memorat
razyelx
Client obisnuit
**

Karma: 0
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #23 : 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.

Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #24 : 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. Smile
Sper ca si inteles ceva din ce am scris mai sus Very Happy
Memorat
Pagini: [1] 2 3   În sus
  Imprimă  
 
Schimbă forumul:  

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