477 Alee

[•devilkind]

programul tau pare ca ia TLE din cauza ca are complexitate prea mare. Daca am inteles bine toata matricea la fiecare pas. Cum pot fi aproximativ N^2 pasi * N^2 pe fiecare pas => N^4 care cred ca e cam mare ptr problema asta.

[•gabor_oliviu1991]

probabil ca din cauza asta. oricum, a mai facut cineva prob cu dinamica de 100?

[•Pepelea_Flaviu]

De ce nu faci cu Lee ?

[•vlad_oltean]

tu faci minimul daca nu e -1... si ce faci daca in N, E, V, si S e pom si tu nu poti ajunge in punctul respectiv? ...

ceva de genul:

Cod:

0 0 -1 0 0
0 -1 0 -1 0
0 0 -1 0 0
0 0 0 0 0
0 0 0 0 0

daca fisierul .in ar arata cam asa

Cod:

5 4
1 3
2 2
2 4
3 3
2 3 5 5

cat ar fi raspunsul pt exemplul asta?

[•gabor_oliviu1991]

0. pt ca nu poti iesi din [2,3]

[•Addy.]

pai si de ce ar trebui sa treaca prin [2,3]?
scopul este sa ajunga in [5,5]. eu am incorrect pe testul 8, nu-mi dau seama de ce. sunt cazuri particulare?

[•marcelcodrea]

Scopul este sa pleci de la o poarta si sa ajungi la alta.

Scrieti un program care sa determine numarul minim de dale necesare pentru construirea unei alei continue de la o poarta la cealalta.

[•Addy.]

pe exemplul ala era scopul sa ajunga in [5,5].
L.E.: deci e posibil ca cele 2 porti sa nu fie in zone de margine? adica sa poata fi in interior?   
even later edit: nvm, am gasit.

[•udrescu_cristi]

nu iau decat 80 pct cu un lee clasic..nu inteleg care e problema..in mod normal ar trebui sa mearga..

[•Roswen]

ce e special pe testul 4?   
am facut un lee clasic si iau numai 90 de pcte, imi pica pe testul 4 cu incorect.
Este ceva caz exceptie?

[•andunhill]

Am si eu o intrebare. Daca imi cicleaza de ce imi apare la borderou memory limit exceeded in loc de tle.
http://infoarena.ro/job_detail/466551 asta ia memory limit exceedet in loc de tle, iar sursa asta ia 100 de puncte cu aceeasi memorie declarata http://infoarena.ro/job_detail/466555 .

[•R.A.R]

Rezolvai in mod recursiv ?

[•andunhill]

nu. Pur si simplu la sursa de care lua memory limit exceeded am modificat ceva la vecini si am luat 100.

[•Oancea.Catalin]

eu iau 80 (cu "incorect" pe testul 6 si testul 8 )
matricea are la inceput toate elementele 0
si cele cu pomi le pun -1;
in punctul din care plec pun 1.
daca

Cod:

a[i][j]==x si a[i+1][j]==0 atunci in a[i+1][j] pun x+1

si pun in coada i si j
si pentru fiecare element din coada marchez vecinii
cand a ajuns la finish afiseaza

Cod:

 a[x_finish][y_finish] 

ce e gresit?

[•eudanip]

Poate ai gresit ceva la implementare sau ai uitat un caz particular. Nu trebuie neaparat algoritmul sa fie gresit. Din moment ce ai luat 80 pct presupun ca ai o gandire corecta doar ca ai uitat un caz sau doua.

[•Oancea.Catalin]

pai folosesc algoritmul Lee ... deci ar trebui sa mearga... nu stiu ce cazuri speciale ar putea sa apara.
E obligatoriu sa ajunga la tinta?  Sau exista cazuri in care nu se poate ( adica toti vecinii sa fie pomi )?

[•SpiderMan]

Eu la prima sursa am avut MLE pe testele 6 si 8. Vezi daca limitele sunt puse bine, daca ai ceva gen short si trebuie int .... Sunt teste mari.

[•Oancea.Catalin]

nu ... le-am avut long long  si luam MLE iar acum le am int si imi da WA... dar mai mult ma deranjeaza ca o sursa cu "forta bruta" cu o complexitate de O(n^4) . ia 90 de puncte... si la mine coada e de 70000( oricum cred ca daca as incerca sa accesez coada la elementul 70001 ar da killed by signal ... in nici un caz WA

[•SpiderMan]

Pentru ca long long e mai costisitor, luai TLE si acum int poate nu e suficient. Incearca sa iei testele ( daca ai de unde ) si sa vezi daca merge cu long long , sau cu int.

[•pauldb]

nu ... le-am avut long long  si luam MLE iar acum le am int si imi da WA... dar mai mult ma deranjeaza ca o sursa cu "forta bruta" cu o complexitate de O(n^4) . ia 90 de puncte... si la mine coada e de 70000( oricum cred ca daca as incerca sa accesez coada la elementul 70001 ar da killed by signal ... in nici un caz WA

M-am uitat pe sursa ta si am vazut o greseala. Atunci cand verifici sa nu depasesti limitele matricii, verifici de ambele dati relativ la n si niciodata relativ la m.

In plus, am observat ca tu in sursa ai 4 if-uri, cate unul corespunzator fiecarei directii. Acest lucru se poate simplifica (din punct de vedere al implementarii) folosind un for, astfel:

Cod:

int dirx[4] = {-1, 0, 1, 0};
int diry[4] = {0, -1, 0, 1};

...

for (int i = 1; i <= lungime_coada; ++i) {
  ...
  for (int j = 0; j < 4; ++j) {
     int x = coada_x[i] + dirx[j];
     int y = coada_y[i] + diry[j];
     // verificari pentru x si y si eventual adaugarea pozitiei in coada 
  }
  ...
}

Ideea poate fi aplicata si la alte probleme: cu 8 directii, cu cai pe tabla de sah, etc.

[•Oancea.Catalin]

pai verific la N pentru ca matricea are dimensiuni NxN si in sursa nu am decat un for    (defapt 2 .. cu cel de la citirea obstacolelor)
sigur te-ai uitat pe sursa mea?

[•pauldb]

Da, dar nu citisem atent problema. M-am uitat din nou si gresesti la ultima conditie, la care iesi din matrice (intri pe linia 0). Daca folosesti metoda de care iti povesteam, ai sanse mult mai mici sa gresesti la astfel de conditii.

[•Oancea.Catalin]

da ... asa e  multumes 

[•flaviusc11]

Eu de ce iau doar 70 de puncte pe urm sursa?

Cod:

#include<cstdio>
using namespace std;
int lb[175][175],n;
void drum(int k, int l, int c)
{
 if(l+1<n)
if(lb[l+1][c]>k+1)
  { lb[l+1][c]=k+1;
    drum(k+1,l+1,c); }
if(l>0)
if(lb[l-1][c]>k+1)
  { lb[l-1][c]=k+1;
    drum(k+1,l-1,c); }
if(c+1<n)
if(lb[l][c+1]>k+1)
  { lb[l][c+1]=k+1;
    drum(k+1,l,c+1); }
if(c>0)
if(lb[l][c-1]>k+1)
  { lb[l][c-1]=k+1;
    drum(k+1,l,c-1); }
}
int main()
{ freopen("alee.in","r", stdin);
  freopen("alee.out","w",stdout);
    int aux,m,i,j,x,y,x2,y2;
    scanf("%d %d",&n,&m);
   aux=n*n;
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    lb[i][j]=aux;
for(i=1;i<=m;i++)
  { scanf("%d %d",&x,&y);
    lb[x-1][y-1]=-1;}
    scanf("%d %d %d %d",&x,&y,&x2,&y2);
lb[x-1][y-1]=1;
drum(1,x-1,y-1);
printf("%d\n", lb[x2-1][y2-1]);
return 0;
}

[•jupanubv92]

Din cate am vazut tu ai TLE si MLE. Memorie prea multa nu ţi-ai alocat, deci cel mai probabil depăşeşti limita de memorie a stivei, din cauză că faci recursiv. Îţi recomand să încerci să faci lee-ul cu o coadă, pentru a evita situaţia asta.