1020 Submatrix

[•pauldb]

Aici puteți discuta despre problema Submatrix.

Problema a fost adăugată de Andrei Antonescu.

[•alexandru92]

Elementele matricii  intre ce interval oscileaza ?
Cu aceeasi sursa cu care am luat 100pct la Oni by Net obtin aici 50pct...

[•wefgef]

Testele de la ONI erau proaste. Nici cele de pe infoarena nu sunt cele mai bune.

[•alexandru92]

Testele de la ONI erau proaste. Nici cele de pe infoarena nu sunt cele mai bune.

Ok, dar elementele din matrice sunt <= 100 sau  is < ( 2^31 )-1 ?

[•andrei-alpha]

Am completat in enunt.

[•Robytzza]

Stiti cumva cum pot face rost de sursele mele de la Nationala?
Am uitat sa mi le i-au pe stik. pe cele de la ONI. 

[•Robytzza]

sursa de 0 la ONI
http://infoarena.ro/job_detail/442165 
prea penal , mi sa spus ca a iesit din memorie pe toate testele

[•stocarul]

Asta pentru că declari prea multă memorie.
InfoArena îți permite să declari mai multă memorie, și primești MLE doar dacă accesezi mai multă decât ai voie. La ONI nu îți este permis să declari mai multă memorie decât ai voie.

[•Robytzza]

e bine de stiut ) 

[•cr1st18]

la problema aceasta care este complexitatea dorita ?

[•SpiderMan]

Complexitatea oficiala este O(N³)

[•flaviusc11]

Pe testele oficiale programul meu ia 30 de puncte. De ce aici iau 0 puncte?

[•toni2007]

Pt ca testele oficiale erau busite. Aici sunt alte teste.

[•andrei-alpha]

Tu iei kbs pe toate testele pentru ca iesi din memoria alocata.

[•flaviusc11]

Ok...dar totusi cum sa ies din memoria alocata, care este de 16 MB, daca am declarat 2 matrici [301][301] si 2 vectori de 9000 componente? astea nu ocupa mai mult de 1,5 MB.... apropo pe testele oficiale valorile matricei erau mici, aici sunt mai mari de 9000?

[•stocarul]

Ok...dar totusi cum sa ies din memoria alocata, care este de 16 MB, daca am declarat 2 matrici [301][301] si 2 vectori de 9000 componente? astea nu ocupa mai mult de 1,5 MB.... apropo pe testele oficiale valorile matricei erau mici, aici sunt mai mari de 9000?

Dacă ai citi cu atenție enunțul, ai putea observa următoarea restricție:

Numerele din fişierul de intrare se vor incadra pe 32 de biţi cu semn.

[•flaviusc11]

Dacă ai citi cu atenție enunțul, ai putea observa următoarea restricție:

Numerele din fişierul de intrare se vor incadra pe 32 de biţi cu semn.

      Am citit enuntul cu atentie, dar nu stiam ce inseamna ca datele se vor incadra pe 32 de biti cu semn. Intre timp m-am documentat. Cred ca din cauza asta luam 0 puncte(pe testele oficiale valorile matricei nu erau mai mari de 100, in schimb aici datele sunt de tip int, adica pana la 2147483647).
      Oricum, multumesc tuturor pentru raspunsuri. M-am luminat putin.

[•flaviusc11]

Astazi am revenit asupra acestei probleme si am incercat sa folosesc clasa set. Dar nu inteleg de ce nu da rezultatul corect.

Cod:

#include<cstdio>
#include<set>
using namespace std;
int n,m,k,lmax;
int a[310][310];
void citire()
{
	freopen("submatrix.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	int i,j;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
}
void calculez()
{
	set<int>det;
	int i,j,l,q,r,dif=0,x;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		  {
		      l=0;
		      do
		      {
		          for(q=i;q<=i+l&&q<=n;++q)
		             x=a[j+l][q], det.insert(x);
		          for(r=j;r<=j+l&&r<=m;++r)
                             x=a[i+l][r],det.insert(x);
                          dif=det.size();
                          if(dif<=k && l>lmax)
                               lmax=l;
                          ++l;
		      }
		      while((l<n&&l<m) &&(dif<=k));
		      det.clear();
		  }
    freopen("submatrix.out","w",stdout);
    printf("%d\n",lmax+1);
}
int main()
{
	citire();
	calculez();
	return 0;
}

E bun rationamentul?

[•tudorgalatan]

De ce am KBS 11 pe toate testele? Nu observ.

Cod:

int matrix[310][310];
int ve[1000002];

int main ()
{
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
        {
            k = i;
            l = j;
            while (k<=N && l<=M)
            {
                sol2 = 0;
                for (u=1; u<=1000000; u++)
                    ve[u] = 0;
                for (u=i; u<=k; u++)
                    for (v=j; v<=l; v++)
                    {
                        ve[matrix[u][v]]++;
                        w++;
                    }
                for (u=1; u<=1000000; u++)
                    if (ve[u] > 0)
                        sol2++;
                sol1 = k-i+1;
                if (sol2 <= K && sol1 > sol)
                    sol = sol1;
                k++;
                l++;
            }
        }
}

[•klamathix]

Citește topicul înainte să postezi, poate au avut și alții aceeași nelămurire  .