346 Padure

[•bogdan2412]

Aici puteţi discuta despre problema Padure.

[•Tabara]

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 
Si totusi are cineva idee ce as putea gresi..
  

[•Dastas]

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? :/

[•Tabara]

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.
 

P.S. Daca iei 100, sa ma dumiresti si pe mine ca nu inteleg ce am gresit 
 

[•astronomy]

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.

[•Tabara]

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

[•Dastas]

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.

[•astronomy]

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.

[•Dastas]

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?

[•astronomy]

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.

[•devilkind]

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

[•mocke]

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

[•Florian]

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? 

[•peanutz]

Daca tii 2 cozi cum s-a zis mai sus, iti intra sigur, si in memorie si in timp.

[•astronomy]

Spui ca ai o coada de dimensiune 100.000, dar esti sigur ca e suficient? Coada ar putea ajunge la dimensiuni mai mari

[•Florian]

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?

[•Dastas]

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.

[•Florian]

Functia aia recursiva o apelai de fiecare data cand introduceai un element in coada? Si il pastrai doar pe cel optim?

[•Dastas]

Apelul initial se face de fiecare data cand scoti un element din coada si vrei sa-l expandezi.

[•Robytzza]

care e dimensiunea maxima la care poate sa ajunga coada   ca eu am dat 400.000 si am un tesct cu incorect unu cu KBS si restul sunt bune

 P.S am scos 100 10x 

[•peanutz]

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.

[•razyelx]

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

[•Mishu91]

Descrie putin algoritmu' pe care il folosesti

[•razyelx]

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.

[•Mishu91]

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