Bogatas

Htio bih se ovom prilikom osvrnuti na neobične test podatke za ovaj zadatak. Dugo sam rješavao ovaj zadatak i optimizirao misleći da nešto krivo radim.

Pogledajte kod i zamjetite što sam izkomentirao jer u suprotnom ne prolazi time limit na zadnjem test primjeru.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
using namespace std;

#define pb(x) push_back(x)

int N, T;
int polje[200][200] = { 0 };
vector < pair < int, int > > stabla, sstabla;

inline int minimum( int a, int b ) { return ( a > b ) ? b : a; }

int nadji_najveci_kv( int x1, int y1 ) {
int ret = 1, minn = minimum( x1, y1 );
for( int i = 0; i < N - minn; ++i ) {
int x2 = x1 + i;
int y2 = y1 + i;
bool valid = true;

if( ( x2 > N ) || ( y2 > N ) ) break;
for( int j = 0; j < stabla.size(); ++j ) {

/*if( stabla[j].first >= x1 && stabla[j].first <= x2 &&
stabla[j].second >= y1 && stabla[j].second <= y2 ) { valid = false; break; }*/

if( sstabla[j].first >= y1 && sstabla[j].first <= y2 &&
sstabla[j].second >= x1 && sstabla[j].second <= x2 ) { valid = false; break; }
}

if( valid ){ ret = i+1; }
}
return ret;
}

bool cmp( pair < int, int > a, pair < int, int > b ) {
return a.first > b.second;
}

int main() {
scanf( "%d %d", &N, &T );
stabla.resize( T );
for( int i = 0; i < T; ++i ) {
int a, b; scanf( "%d %d", &a, &b );
polje[--a][--b] = 1;
//stabla.pb( make_pair( a, b ) );
sstabla.pb( make_pair( b, a ) );
}

//sort( stabla.begin(), stabla.end());
sort( sstabla.begin(), sstabla.end());

int sol = 0;
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j )
if( !polje[i][j] ) {
int tmp = nadji_najveci_kv( i, j );
sol >?= tmp;
j += tmp;
}
cout << sol << endl;

/*sort( stablax.begin(), stablax.end());
for( int i = 0; i < stablax.size(); ++i )
cout << stablax[i].first << " " << stablax[i].second << endl;*/

return 0;
}

šta si ga ti zakomplicirao!!!
zašto jednostavno ne probas svaki moguci kvadrat da bude lijevi gornji vrh i vidiš kolko ga mozes prosiriti?
Za zadnji test-primjer mu treba 0.06 sekundi.

PITANJE ADMINU....
Zašto nema jasno navedenih test-primjera? Zašto nisu sva ograni&#269;enja jasno zadana? Zašto ne piše koliko je ispisao naš program, a koliko je to&#269;no rješenje (kad je rješenje krivo)?

I BTW mislim da imate pogrešna rješenja!!! Dajte još neke test primjere i rezultate koje ste vi dobili!

Evo 2 rjesenja sa slozenosti O(N*N*lg N):
Ako je u matrici na mjestu [x][y] stablo stavi 1 a ako nije stavi 0.
1) Onda kreni od pocetka matrice do kraja i sumiraj sve od pocetnog ugla pomocu DP-a: m[x][y] = m[x-1][y] + m[x][y-1] - m[x-1][y-1] za svaki x[1..max] i y[1..max] -> O(N*N). Sada mozes efikasno odgovorit na pitanje kolko ima stabla od pocetnog ugla do [x][y]u O(1), a isto tako i koliko ima stabla u podrucju od [x1][y1] do [x2][y2] na slijedeci nacin:
koliko_stabla = m[x2][y2] - m[x2][y1] - m[x1][y2] + m[x1][y1] opet pomocu DP-a u O(1). Znaci kvadrat je prazan ako je taj broj 0. Kada trebas provjeriti da li postoji "prazan" kvadrat strane A pokusaj smjestiti kvadrat na sve moguce pozicije i na gore naveden nacin provjeri da li je prazan. To mozes u O(N*N) * O(1). Sada sa binarnim pretrazivanjem ustanovi najveci "prazan" kvadrat strane A . To ti je onda O(N*N*lg N)
2)Idi kroz matricu od "dole" prema "gore". Kad si u y-toj vrsti i prolazis kroz kolone i ako je na nekom mjestu x (x-ta kolona) stablo, updateaj niz[x] sa y. Na taj nacin znas gdje je do sada "najvise stablo" u svakoj koloni. Sada trazis najveci kvadrat koji pocinje u y-toj vrsti i ide "dolje" dok ne naidje na stablo bilo dole ili lijevo ili desno. To radis na slijedeci nacin rekurzivno: nadjes "najvisu" kolonu (tj. onu kolonu koja ima "najvise stablo" je kvadrat ili od y do y(najviseg stabla) i zoves rekurziju za desno od tog najviseg stabla i lijevo i ovo rekurzivno ponavljas dok je interval (lijevo - desno) > 0. Na prvi pogled je slzenost za ovo jedno provjeravanje N*N (rekurzija N puta i N zbog trazenja minimuma na intervalu [lijevo, desno]) ali ako ovo implementiras pomocu tzv. tournament tree-a onda minimum na intervalu [lijevo, desno] mozes naci u O(lg N) pa slijedi slozenost O(N*lg N). Ovaj postupak radis za y tj. za svaku vrstu i onda je ukupna slozenost O(N * N * lg N).

Na istu foru mozes rijesit i z-dijamant samo malo teze zbog rotacije.

postoji algoritam slozenosti O(n^2)...radi se dinamickim..pa razmisli malo..
Na istu ideju mozes da odradis dijamant...