Stadion

[•scipianus]

am o intrebare la urmatoarea problema   :
Am o matrice binara in care trebuie sa aflu patratul de arie maxima care are in cele 4 colturi 0 (se cere sa afisez latura patratului si coordonatele coltului stanga-sus).
Am facut aceasta problema in O(n^3) si as dori sa stiu daca este posibila in complexitate mai mica , deoarece problema cand a fost data(pe vremea Borland) era 170x170 matricea,dar nemaifiind problemele cu memoria de la Borland,acum s-ar putea da si 1000x1000 cred.
Solutia mea este urmatoarea:

Cod:

void RezolvareA()
{
	int i,j,L,gasit=0,solx,soly;
	for(L=min(n,m);L>=1 && !gasit;L--)
	{
		for(i=1;i<n-L+2 && !gasit;i++)
		{
			for(j=1;j<m-L+2 && !gasit;j++)
			{
				if(!a[i][j] && !a[i][j+L-1] && !a[i+L-1][j] && !a[i+L-1][j+L-1])
				{
					solx=i;
					soly=j;
					gasit=L;
				}
			}
		}
	}
	fout<<gasit<<' '<<solx<<' '<<soly<<"\n";
}

Ceva idei de O(n^2) sau exista macar? 


Enunt complet :

STADION
Grigorel si Ionica sunt acum doi mari arhitecti si se gandesc sa construiasca un stadion de forma patratica pe harta orasului.Ei au la dispozitie harta orasului care este de forma dreptunghiulara NxM. Locurile ocupate cu alte cladiri sunt codificate prin 1,iar locurile libere prin 0.
Cerinta:
a) Ajutati-i pe cei doi mari arhitecti care nu stiu programare sa iasa din aceasta dificila problema,gasind patratul de arie maxima din oras care sa aiba in colturi numai locuri libere.
b) De asemenea gasiti patratul de arie maxima care contine pe margini si in interior numai locuri libere.
Date de intrare:
Datele se citesc din fisierul stadion.in astfel:
-pe prima linie doua numere naturale n,m reprezentand numarul de linii,respectiv coloane
-pe urmatoarele n linii,cate m numere din {0,1} despartite prin cate un spatiu
Date de iesire:
Rezultatul se va tipari in fisierul stadion.out astfel:
-pe prima linie 3 numere naturale,separate prin cate un spatiu,reprezentand latura unui patrat de arie maxima,care are in colturi locuri libere,urmat de coordonatele coltului stanga sus ale acestei zone
-pe a doua linie 3 numere naturale,separate prin cate un spatiu,reprezentand latura unui patrat de arie maxima,care este complet gol,urmat de coordonatele coltului stanga sus ale acestei zone
Restrictii si precizari:
- 0<n,m<=170
- pentru 30% din teste se garanteaza (0<n,m<=30)
- daca exista mai multe solutii se va afisa doar una dintre ele
- se acorda 40% din punctaj pentru cerinta a) ,respectiv 60% din punctaj pentru cerinta b)
Exemplu:
stadion.in
4 4
0 0 1 0
0 0 0 0
0 0 0 1
0 0 0 0

stadion.out
4 1 1
3 2 1

Timp maxim de executie : 1 secunda

[•PlayLikeNeverB4]

Cred ca se face cu Divide et Impera. Seamana cu problema taieturilor.

Faci o functie care gaseste “zona” goala cea mai mare.

drept(Xa,Xb,Ya,Yb) -Xa,Xb coordonatele coltului stanga sus, Ya,Yb - coordonatele dreapta jos (sau poti sa le alegi cum vrei, dar asa e in problema); Xa -linia, Xb-coloana

a) Daca vreunul dintre colturi are valoarea 1, atunci gasesti un dreptunghi mai mic cat mai mare care nu contine acel colt.
Sa zicem ca coltul (Xa,Xb) e 1. Noile dreptunghiuri vor fi:
drept(Xa+1,Xb,Ya,Yb)
drept(Xa,Xb+1,Ya,Yb)
Pentru celelalte colturi e la fel.
Cand gasesti un dreptunghi care are toate colturile libere, cauti sa aiba latura mica cat mai mare (latura mica a dreptunghiului e defapt viitoarea latura a patratului) si memorezi coltul stanga-sus.
Afisezi latura maxima gasita si apoi coordonatele memorate care ii corespund.

b) Pentru fiecare valoare de 1 in interiorul (sau pe marginea) dreptunghiului (Xa,Xb,Ya,Yb) cu coordonatele (Va,Vb) verifici toate dreptunghiurile mai mici (4) in care este impartit dreptunghiul mare (care pana la urma nu vor contine valori de 1 inauntru)
drept(Xa,Xb,Ya,Vb-1) –dreptunghiul din stanga
drept(Xa,Vb+1,Ya,Yb) -dreptunghiul din dreapta
drept(Xa,Xb,Va-1,Yb) -dreptunghiul de sus
drept(Va+1,Xb ,Ya,Yb) -dreptunghiul de jos

Am adaugat si scazut 1 pentru ca noile dreptunghiuri sa nu contina acea valoare de 1.
Daca nu contine nicio valoare de 1, cauti ca si la a) un dreptunghi cu latura mica cat mai mare (pentru ca aria patratului sa fie cat mai mare).
Daca aria lui e mai mare decat aria maxima gasita, atunci aceasta devine noua arie maxima.

Iti sugerez sa desenezi toate astea sa intelegi mai bine.

Huh, mi-a luat ceva... Daca nu o rezolvi, ma supar!

[•nparfene2004]

Nu e bine cu divide et impera.
Sunt algoritmi care se rezolva ineficient cu divide et impera. Acesta este unul din ele. Nu se reduce complexitatea, pentru ca oricum cauti toate patratele (de la latura mare la din ce in ce mai mica).

[•PlayLikeNeverB4]

Nu stiu cat e de eficienta, dar e mai eficienta decat 3 for-uri. Plus ca eu nu caut patrate, ci dreptunghiuri.
Sau poate imi demonstrezi ca gresesc...

[•nparfene2004]

Algoritmul e tot O(n ^ 3), iar dovada e modul in care apelezi:
drept(Xa+1,Xb,Ya,Yb)
drept(Xa,Xb+1,Ya,Yb)
De obicei, pentru a scadea complexitatea cu Divide et Impera, trebuie ca problema sa se imparta in doua (sau mai multe) parti de dimensiuni aproximativ egale si astfel sa obtin o complexitate de forma O(n^2 * log n).

[•scipianus]

Algoritmul e tot O(n ^ 3), iar dovada e modul in care apelezi:
drept(Xa+1,Xb,Ya,Yb)
drept(Xa,Xb+1,Ya,Yb)
De obicei, pentru a scadea complexitatea cu Divide et Impera, trebuie ca problema sa se imparta in doua (sau mai multe) parti de dimensiuni aproximativ egale si astfel sa obtin o complexitate de forma O(n^2 * log n).

1.am re-editat postul initial,sa fie mai usor de citit enuntul la ce cer eu
2.pana la urma exista solutie mai eficienta decat O(n^3) ? 

[•PlayLikeNeverB4]

Da, la cerinta a) ai dreptate, dar la b) nu e mai eficienta?

[•scipianus]

Da, la cerinta a) ai dreptate, dar la b) nu e mai eficienta?

"mai eficienta" decat ce? eu am aratat doar implementarea mea pentru cerinta a)
Uite aici si implementarea mea in O(n^2) la cerinta b) :

Cod:

void RezolvareB()
{
	int i,j,min1,Lmax=0,solx,soly;
	for(i=1;i<=n;i++)
		b[i][1]=1-a[i][1];
	for(j=1;j<=m;j++)
		b[1][j]=1-a[1][j];
	for(i=2;i<=n;i++)
	{
		for(j=2;j<=m;j++)
		{
			if(a[i][j]==1) b[i][j]=0;
			else
			{
				min1=min(b[i-1][j],b[i][j-1]);
				b[i][j]=min(min1,b[i-1][j-1])+1;
				if(b[i][j]>Lmax)
				{
					Lmax=b[i][j];
					solx=i-Lmax+1;
					soly=j-Lmax+1;
				}
			}
		}
	}
	fout<<Lmax<<' '<<solx<<' '<<soly<<"\n";
	fout.close();
}

Ideea la b) este de a forma o alta matrice in care in b[ i ][ j ] memorez (in caz ca este a[ i ][ j ]=0) latura maxima pe care o poate avea un patrat care are coltul din dreapta jos in (i,j),retinand care este valoarea maxima din matrice

Deci alta idee mai eficienta pentru a) nu exista sa inteleg? Ca tot nu raspundeti vreunu

[•nparfene2004]

La cerinta a) nu am din pacate nici eu vreo idee mai buna de O(n^3).
Dar as fi curios si eu sa vad vreo solutie de complexitatea mai mica.