002 TreiD

[ditzone]

Aici puteti pune intrebari despre problema TreiD.

[•devilkind]

o submatrice trebuie sa contina cel putin un element nu??

[•Cosmin]

Da.

[•Dorin]

Matricea din exemplu are 6 lini nu 5 ... puteti corecta ?? si explicatile  matricea a treia are elementele 6 3 si 6 cu 4 iar cea de a doua are elementele 4 cu 1 si 5 cu 1 

[ditzone]

S-a corectat exemplul.

[VladS]

Cam stransa limita de timp. Cred ca cine a scos N^3 merita 100 

[•Cosmin]

Am modificat limita de timp.

[nivan]

 Da in mod normal cam cum s-ar face. Ca eu nu ma pot gandi decat la sume partiale... cu care scot O(N^4). Nici n-am rabdare pan se afiseaza rezolvarile.

[•devilkind]

poti face N^3 folosind brut pe linii si dinamica pe coloane. totusi cu o astfel de rezolvare eu am luat 0 si nu inteleg de ce

[•Cosmin]

Pt ca nu e buna ideea .

[•bogdan2412]

Rezolvarea mea in N^3 trata mai multe cazuri... Imparteam matricea in 3 parti diferite si cautam fiecare din cele trei matrici in fiecare din acele parti... In total sunt 6 cazuri... 3 cazuri care le cautam in matricea initiala si 3 cazuri in matricea rotita cu 90 grade

Cod:

+-----+     +-----+     +-----+
|     |     |     |     |  |  |
|-----|     |-----|     |  |  |
|     |     |  |  |     |  |  |
|-----|     |  |  |     |-----|
|     |     |  |  |     |     |
+-----+     +-----+     +-----+

Calculez in N^3 max[ i ][ j ] = submatricea de suma maxima aflata intre liniile i si j inclusiv pentru primul caz si inca o matrice asemanatoare pentru celelalte 2 cazuri...
Apoi variez cele doua linii si calculez in O(1) suma celor 3 submatrici din cele 3 zone formate.

Sper ca v-am dat o idee vaga macar Probabil ca exista si rezolvari mult mai simple

[•Cosmin]

Asta era si ideea mea .
Chestia e ca trei dreptunghiuri pot fi impartite de o linie verticala sau orizontala, si astfel imparti problema in doua subprobleme care cauta submatricea optima dintr-un dreptunghi, sau doua submatrici ce nu se suprapun de suma maxima din un dreptunghi. Rezolvand probleme de tipul asta pe toate dreptunghiurile care au trei cel putin doua laturi ce se sprijina pe laturile dreptunghiului mare, poti rezolva problema mai generala cu trei dreptunghiuri.