|
Titlul: 002 TreiD Scris de: ditzone din August 11, 2006, 11:02:39 Aici puteti pune intrebari despre problema TreiD.
Titlul: Raspuns: 002 TreiD Scris de: Savin Tiberiu din August 11, 2006, 11:15:12 o submatrice trebuie sa contina cel putin un element nu??
Titlul: Raspuns: 002 TreiD Scris de: Cosmin Negruseri din August 11, 2006, 11:16:53 Da.
Titlul: Raspuns: 002 TreiD Scris de: Oltean Dorin din August 11, 2006, 11:33:26 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 :thumbup:
Titlul: Raspuns: 002 TreiD Scris de: ditzone din August 11, 2006, 11:38:56 S-a corectat exemplul.
Titlul: Raspuns: 002 TreiD Scris de: VladS din August 11, 2006, 16:30:50 Cam stransa limita de timp. Cred ca cine a scos N^3 merita 100 :P
Titlul: Raspuns: 002 TreiD Scris de: Cosmin Negruseri din August 11, 2006, 16:35:23 Am modificat limita de timp.
Titlul: Raspuns: 002 TreiD Scris de: nivan din August 11, 2006, 18:11:41 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). :oops: Nici n-am rabdare pan se afiseaza rezolvarile.
Titlul: Raspuns: 002 TreiD Scris de: Savin Tiberiu din August 11, 2006, 20:07:47 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
Titlul: Raspuns: 002 TreiD Scris de: Cosmin Negruseri din August 11, 2006, 21:04:51 Pt ca nu e buna ideea :).
Titlul: Re: 002 TreiD Scris de: Bogdan-Cristian Tataroiu din August 11, 2006, 21:18:36 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 :) Titlul: Raspuns: 002 TreiD Scris de: Cosmin Negruseri din August 11, 2006, 21:44:40 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. |