[STADION]

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

eu am luat 90 la aliniere pentru ca nu respecta restrictiile ( n<300.000 - strict mai mic de 300.000 deci poate fi maxim 299.999). Nici problema cavaleri nu respecta restrictiile. (dar oricum nu imi merge pe teste cu n mai mare de 9973 )

Cod:

	f=fopen("cavaleri.in", "r");
	g=fopen("cavaleri.out","w");
	fscanf(f, "%lld", &n);
	a[1]=0;  a[2]=0; a[3]=4; a[4]=9; a[5]=13;
	if(n<6)
	{
		fprintf(g, "%lld", a[n]);
		return 0;
	}
	else
	{
		for(i=6; i<=n; i++)
		{
			a[i]=(a[i-1]%9973+(a[i-2]-2)%9973)%9973;
		}
		fprintf(g, "%lld", a[n]);
		return 0;
	}

Ce ar trebui modificat ca sa iau 100? http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1189

Idee pentru problema Aliniere ,grupa S:
Daca ai fi luat pe foaie ai fi observat asta :
n=1   1
n=2   2
n=3   3
n=4   5
n=5   8
n=6   13
n=7   21   etc.   deci Fibonacci
Si ideea e ca nu trebuie sa generezi termenii fibonacci,ca doar al 300000-lea termen e imens  
Folosind (A+B)%C = ((A%C)+(B%C))%C
ar rezulta urmatorul cod :

Cod:

nr=2;
while(nr<n)
{
	aux=r2;
	r2=(r1+r2)%9973;
	r1=aux;
	nr++;
}
fout<<r2<<"\n";

cu initializarile nr=0,r1=1,r2=2 si luat separat cazurile n==1 si n==2

P.S. : precizez ca am luat 100 pct cu asta  
P.S2. : la problema Cavaleri nu mai este fibonacci dar probabil tot gasesti o regula pentru sir ca sa aplici analog (A+B)%C = ((A%C)+(B%C))%C  

Arata mai bine asa 
Felicitari pentru initiativa 

P.S. : observ eu gresit,sau nu se poate pune semnatura pe forumul infoarena? 

Mda,aveti dreptate,mate a fost motivul(sau oarecum eu am fost motivul)
Cand am vazut runda 6 programata peste locala de mate am vorbit prin mail cu doamna Emanuela Cerchez si a fost de acord sa schimbe pe duminica.Si se pare ca a facut la fel pentru runda 8(cand pe 12 martie ar fi fost judeteana de mate),dar pentru runda 8 a fost programata din prima duminica fara sa mai am vreo implicatie  .

Pentru cei care doresc mai multe detalii despre sortarea cu functia sort pe mai multe criterii cititi aici un post despre acest subiect al profesorului meu   Ce e important e sa stii forma standard sort(v,v+n,Ordonare()) sau sort(v+1,v+n+1,Ordonare()) daca tii vectorul de la 1 la n,iar in functia Ordonare() bagi toate criteriile de care ai nevoie in if-uri si else-uri    Cam la fel cred ca s-ar proceda si pe qsort,dar prefer sort.

http://www.dponline.ro/articol.php?idarticol=77

Si deci ar fi mai avantajos ca la fiecare program sa declar variabilele global?

De fapt explicatia lui Filip Stefan nu o prea inteleg asa de bine,oricum nu e cea mai potrivita ca argument.
Treaba sta in felul urmator:
1.tu la o problema la un concurs ai data o limita de memorie de tipul memorie totala/memorie stiva,de exemplu 2mb/1mb sau 16mb/1mb (ce vreau sa spun e ca in general stiva e 1mb)
2.in acea memorie de stiva intra practic ce ai declarat tu in functia main
3.deci declararea vectorilor in main are 2 dezavantaje,anume ca in primul rand depasesti acea memorie pentru stiva in majoritatea problemelor(vei primi kill by signed 11 de regula),deoarece ai nevoie de vectori mari,iar in al doilea rand daca declari vectorul local in main,atunci va trebui sa-l initializezi tu dupa cu 0 peste tot(daca era declarat global era deja initializat peste tot cu 0)  
4.totusi nu este bine sa declari orice variabila globala,adica vectorii da,dar variabilele,ar trebui declarate astfel : cele importante pe care le citesti tu din fisierul de intrare,le declari globale(pentru a le folosi eventual mai usor la subprograme),iar restul intermediare si cele pentru fisierul de iesire local ; asta deoarece tot ce este declarat local se afla pe stiva si este cu mult mai rapid decat ce este global,asa ca este foarte prost sa lucrezi cu toate variabilele globale  

Deci tine minte asa :
1. VECTORII MEREU GLOBAL (bineinteles la fel si matricele sau orice alt tablou)
2. VARIABILELE IMPORTANTE GLOBAL SI RESTUL LOCAL

Sper ca ai inteles ce vreau sa zic  

a[] sau v[] ? Hotaraste-te  

Vectorul v[],ca am scris mai in graba si am mai si dat copy-paste din codul meu,oricum iti dadeai si singur seama de asta   Am modificat acum postul cu v[]

[singura parcurgere]

Care este cea mai eficienta metoda de stergere a unei valori dintr-un vector ?
Exemplu: Pentru vectorul cu valori v[5] = {1,2,3,4,5}, sa se stearga valoarea lui v[3], aceasta fiind in schimb inlocuita de cea a lui v[4] (analog pentru v[4] si v[5] daca vectorul ar fi fost mai mare)

Daca doresti sa ai elementele in vector inca in ordine si doar sa elimini din vector toate valorile x ,intr-o singura parcurgere a vectorului,atunci faci urmatorul algoritm:
1.ai initial k=0
2.parcurgi vectorul
3.daca v[ i ]==x atunci k++
4.daca v[ i ]!=x atunci v[ i - k ]=v[ i ]
5.la final dupa parcurgere,inainte de a face afisarea sau altceva,faci n=n-k

adica in cod ar fi asa:

Cod:

k=0;
for(i=1;i<=n;i++)
{
	if(v[i]==x)
		k++;
	else
		v[i-k]=v[i];
}
n=n-k;

[volumul III]

1.Pai o carte buna,care stiu ca contine grafuri printre altele este volumul III de la "Programarea in limbajul C/C++ pentru liceu" de Emanuela Cerchez si Marinel Serban (http://www.polirom.ro/catalog/carte/programarea-in-limbajul-c-c++-pentru-liceu-volumul-al-iii-le-2408/),seria aceasta de 3 volume reprezantand cam ce e mai bun in materie de informatica in limba romana.Nu te impacienta daca vezi pe site-ul polirom ca nu mai e in stoc,ca iti spun sigur ca o gasesti in librarii sau pe alte site-uri   (sper sa nu patesti ca mine,ca eu am cautat primul volum ca disperatul in 2 orase,pe toate site-urile,la autori,la editura,si pana la urma mi-a gasit ultimul exemplar din depozitul editurii si mi l-a trimis   oricum dupa cca. 1 luna s-a facut retiparire,aflasem si eu asta de la autori cand inca cautam cartea)

2.Am mai vazut ceva interesant gen Ael,pe site-ul campion la arhiva exista acolo o sectiunea software in care este inclus ceva numit "Teoria grafurilor",care de altfel apare cu o scurtatura si la categoria ultimele adaugate,la software.Doar ca asta mai mult explica si mai pune asa niste intrebari in joaca la fel ca la Ael,adica nu e ceva serios de pregatire,e mai mult sa ai habar despre grafuri ,chestiile de baza.Sper ca e bun linkul asta,fiindca merge foarte prost site-ul campion   Teoria Grafurilor

Eu iti recomand prima optiune deci,si chiar ti-as recomanda toata seria de 3 volume daca consideri ca mai ai ce invata si ca doresti sa inveti ceea peste ce ai sarit  

Se tot chinuia un coleg sa faca problema si i-a iesit numai de 20-30pct si de asta am stat aseara sa ma uit pe forum(gandindu-ma ca oricum n-as scoate mai mult de atat) si dupa ce am citit tot(foarte multe replici comice,contre intre greedy si backtracking,etc.) am zis aseara sa incerc si eu o idee sa vad daca imi iese 
Ideea mea era sa fac toate posibilitatile pentru linii,simuland adunarea in baza 2 pentru maxim 16 linii,adica 2^16,apoi la fiecare posibilitate,dupa ce faceam flip la liniile marcate cu 1,parcurgeam toata matricea noua(pe cea initiala o pastram altundeva) si calculam suma de pe fiecare coloana in modul si o adaugam la suma si comparam cu maximul si actualizam,apoi copiam din nou matricea initiala in cea de "lucru",mai goleam vectorul cu sumele de pe coloane si generam urmatoarea posibilitate,avand o singura functie in program,anume cea pentru FlipLinie 
Deci va spun sincer ca mai mult de 10 puncte nu credeam sa iau,mai ales gandindu-ma si la timp,desi acum imi dau seama ca la 16*16 nu e asa mult,iar daca stau sa ma gandesc mai bine ce am facut eu acopera totusi toate variantele de matrice intr-un mod mai rapid 
Oricum am ramas cu gura cascata dupa ce dintr-o singura trimitere pe infoarena(si mi-a luat 10 minute sa fac problema,fiind clasa a IX-a) am luat 100 

Multumesc pentru sfaturile de pe acest topic  Cei care inca nu v-ati prins cum se face chiar ar trebui sa cititi mai atent forumul

PS : sper ca n-am facut ceva rau postand ideea destul de completa aici 

In libraria standard a limbajului C este implementata o varianta naiva de Quicksort (poate fi apelata prin qsort(...) - o sursa demonstrativa gasiti aici), iar STL-ul ofera programatorilor C++ atat functia sort, o implementare a algoritmului Introsort (o sursa demonstrativa aici), cat si functiile make_heap si sort_heap, pentru a putea implementa usor Heapsort (sursa demonstrativa aici). De asemenea, o varianta scurta de implementare a algoritmului Merge Sort (inspirata din acest articol) puteti gasi aici.

Eu pana acum foloseam ca metoda de sortare functia sort din STL pentru orice tip de sortare de genul sort(a,a+n,Ordonare()),unde la functia Ordonare fac ordonare dupa ce criterii doresc.
Din ce scrie sus aflu deci ca mai exista qsort si cele 2 functii pentru heapsort.Pana la urma care dintre sort,qsort si heapsort prin STL,este mai rapida ?  

Dacă mai treci prin topic, să-mi spui și mie ce diferă de ediția a2a (scrie printre primele pagini) dacă poți, te rog.

uite aici o portiune din carte care are si detaliile despre ce contine editia 3 in plus 
http://mitpress.mit.edu/books/chapters/0262033844pref1.pdf

[pow]

Functia pow este mare consumatoare de timp.
O functie ce calculeaza pe x la puterea n,in timp logaritmic este urmatoarea :

Cod:

double RidicareLaPutere(double x,int n)
{
	double p=1;
	while(n>0)
	{
		if (n & 1) // n este impar
		{
			p=p*x;
			n--;
		}
	x=x*x;
	n=n>>1; // sau n = n / 2
	}	
	return p ;
}

Gata,am reusit sa inteleg metoda si sa fac problema.Am avut o dilema la postul urmator in care credeam ca "-" dintre pozitia curenta si pozitia in care a fost.... era o explicatie,nu semnul minus si ma intrebam de ce e varful stivei * pozitia curenta 

Initial calculezi A[i,j] = numarul de 0 consecutivi deasupra pozitiei i, j. Apoi parcurgi linie cu linie matricea si iti propui sa afli cel mai mare dreptunghi plin cu 0 deasupra liniei i (linia curenta). Parcurgi linia de la stanga la dreapta si adaugi valorile A[i,j] intr-o stiva. Cat timp elementul din stiva este mai mare decat elementul curent acesta este scos. Vezi daca varful stivei * (pozitia curenta - pozitia in care a fost varful adaugat in stiva) este mai bun ca solutia si actualizezi. Reiei apoi acelasi algoritm pe linie de la dreapta la stanga si in final vei obtine cel mai bun dreptunghi deasupra liniei i. De mentionat ca cu acest algoritm, nu poti (cel putin nu stiu eu cum) afla cel mai mare dreptunghi cu 0 cu coltul in (i, j).

Ma gandesc dreptunghiul si patratul maxim de 0 sunt dinamici care ar trebui adaugate in arhiva educationala pe viitor. Buru, modifici tu pagina?

Abia dupa m-am gandit ca ala e minus,am luat pas cu pas pe exemplu si am inteles  Mersi de ajutor

S-a mai discutat pe aceasta tema la problema Bmatrix. Ar trebui sa te ajute indicatiile de acolo.

Ok.Am citit acum din acel post,insa nu prea am inteles asa de bine ideea propusa de tine si m-am chinuit sa vad pas cu pas solutia urmatoare(ultima postata) insa nu prea inteleg :

Fac exact asa cum ai explicat tu. Uite o sursa: http://infoarena.ro/job_detail/312811?action=view-source

Mentin o stiva de perechi (inaltime, pozitie), sortate strict crescator dupa inaltime, care reprezinta candidatii pentru capatul din stanga al dreptunghiului de arie maxima. Pentru pasul i sa spunem ca ai inaltimea h. Vrei sa introduci in stiva. Daca h este mai mare decat varful stivei adaugi perechea (h, i). Altfel, scoti din stiva cat timp inaltimea din varf este mai mare strict decat h. Daca ramai in varf cu o inaltime egala cu h, nu faci nimic. Altfel adaugi perechea (h, j), unde j reprezinta ultima pozitie pe care ai sters-o din varful stivei. Stiva ar functiona astfel pe exemplul dat de tine:

Pasul 1: (4, 1).
Pasul 2: Scoti (4, 1), adaugi (3, 1). Stiva arata astfel: (3, 1).
Pasul 3: Scoti (3, 1), adaugi (2, 1). Stiva arata astfel: (2, 1).
Pasul 4: Adaugi (3, 4). Stiva arata astfel: (2, 1), (3, 4).
Pasul 5: Adaugi (4, 5). Stiva arata astfel: (2, 1), (3, 4), (4, 5).

Verficarile le fac atunci cand scot din stiva. La sfarsit am grija sa golesc de tot stiva, facand verificarile necesare.

As dori daca se poate sa-mi explici mai clar decat a spus-o aici wefgef,eventual sa-mi arati stiva pas cu pas pentru exemplul meu din desen si verificarile necesare cand se fac(fiindca nu vad cand s-ar verifica dreptunghiul de inaltime 2 dintre pozitiile 1-3 sau dreptunghiul de inaltime 1 de pe toata linia,adica bine,nu sunt astea solutia si nu analizez orice dreptunghi,insa nu vad logica cu care ajung la candidatul pentru solutie).  

[Problema auxiliara:]

Am de facut o problema cu o matrice de 0 si 1,in care trebuie sa aflu submatricea de arie maximala compusa numai din elemente 0.Practic problema se reduce la o alta astfel : intr-o alta matrice pe pozitia (i,j) voi avea numarul de elemente 0 consecutive de deasupra sa inclusiv el insusi(asta in cazul in care pe pozitia (i,j) am un element 0) si apoi se face o parcurgere pe fiecare linie a matricei noi rezolvand la fiecare linie urmatoarea problema auxiliara (cea la care vreau sa primesc niste indicatii despre cum s-ar rezolva LINIAR) :

Problema auxiliara:
Se considera un sir de n numere naturale ce reprezinta inaltimea unor turnuri pozitionate unul dupa altul,lipite,in aceasta ordine.Sa se determine care este dreptunghiul de arie maxima(sau mai bine spus care este acea arie maxima ; la fel si la problema cu submatricea trebuie sa aflu doar aria maxima, nu neaparat si locatia sa).

Explicatie(problema principala-crearea celei de-a 2-a matrici):
Daca am matricea:                       Atunci a 2-a matrice va arata astfel:

1 0 1 0 1                                0 1 0 1 0
0 0 1 0 0                                1 2 0 2 1
1 1 0 1 1                                0 0 1 0 0
1 0 0 1 0                                0 1 2 0 1
0 0 0 0 1                                1 2 3 1 0

Explicatie(problema auxiliara):
Daca avem sirul 2 4 2 1 5 4 1  atunci reprezentarea ar fi urmatoarea :


Asa cum am precizat,doresc doar indicatii spre a gasi solutia liniara la problema auxiliara  

din cate stiu eu poti declara o functie inline numai daca nu are in ea instructiuni repetitive(for,while,do-while) 

La restrictii apare a si b mai mici ca 2 miliarde. Asta inseamna ca in teste o sa fie un numar care o sa contina un factor prim mai mare de 45000, de unde si impartirea cu 0 si eroarea sigfpe.

mda,s-ar parea ca ai dreptate,dar acum ca am mai marit vectorii pt ciur,imi zice signal 11 pana sa fi verificat daca nu depasesc si marimea pt stiva
signal 11 stiu ca era depasirea limitelor unui vector,dar de ce dracu da asta?
http://infoarena.ro/job_detail/493879

nu e asta,uita-te si tu ca in tot programul am o imparitire si n-are nici o treaba cu 0

va rog uitati-va careva pe cod si ziceti de ce e signal 8,ca problema da bine daca o verificati cu exemple 

Cod:

#include<fstream>
using namespace std;
int a[45001],prime[5000],n,e[5000],v[20001];
int main()
{
	long int i,j;
	for (i=4;i<=45000;i=i+2)
		a[i]=1;
	for (i=3;i<=45000;i=i+2)
		if (a[i]==0)
			for (j=i*i;j<=45000;j=j+2*i)
				a[j]=1;
	n=0;
	for (i=2;i<=45000;i++)
		if (a[i]==0)
			prime[n++]=i;
	
	
	long int a,b,nrdiv=0,aux,nr=0,contor=0,k,w,x=0,e1=0,f1;
	ifstream fin("maxd.in");
	ofstream fout("maxd.out");
	fin>>a>>b;
	long int min=a;
	for(i=a;i<=b;i++)
	                 {e1=0;
		             w=0;
		             k=0;
		             aux=i;
		             nr=1;
                     while(aux!=1)
		                          {f1=prime[k];
			                      e1=0;
			                      while (aux%f1==0 && aux!=1)
			                            {aux=aux/f1;
				                        e1++;
			                            }
                                  if (e1 != 0)
			                         {e[w]=e1;
                                     w++;
			                         }
                                  k++;
		                          }
                     for(j=0;j<w;j++)
                                     if(e[j]!=0) nr=nr*(1+e[j]);
                     if(nr>nrdiv) nrdiv=nr;
		             v[x]=nr;
		             x++;
		             for(j=0;j<5000;j++)
		                                e[j]=0;
	                 }
	for(i=0;i<=x;i++)
		if(v[i]==nrdiv)
		               {contor++;
			           if(v[i]==nrdiv && contor==1) min=a+i;
		               }
	fout<<min<<' '<<nrdiv<<' '<<contor;
	fin.close();
	fout.close();
	return 0 ;
}

La problema aceasta de ce apare "Killed by signal 8"?  
http://infoarena.ro/job_detail/493067