267 TreiD

[•bogdan2412]

Aici puteţi discuta despre problema TreiD.

[•devilkind]

nu inteleg fac brut pe linii, si dinamica pe coloane si totusi iau 0 puncte, toate testele mele merg.

ce ar putea fi gresit??

iata cum fac: fixez 2 linii, si apoi retin in v[ i ] - suma elementelor de pe coloana i, care se incadreaza intre cele 2 linii, v[ i ] il calculez in o(1) folosind sume partiale, iar apoi aplic algoritmu de suma maxima in o(n). dupa ce am aflat primu dreptunghi, initializez toate elementele acestuia cu -40000000 ptr a fi sigur ca nici un element de-al acestuia nu va fi gasit in urmatoarea suma maxima pe care o calculez.

[•Coty]

aici mi-a dat o eroare ciudata:

Cod:

 long i, j, rez=-INF, ;

pe compilatoarele de acasa (si in windows si in linux) nu  a zis nimica... stiu ca e cam incorect, dar aici l-a acceptat, de ce pe serverul infoa nu a vrut?

[•bogdan2412]

devilkind: ce-ai facut tu e greedy... iei tot timpu dreptunghiul de suma maxima.. asta nu-ti garanteaza faptul ca la final vei avea suma maxima a celor 3... gandeste-te mai mult la rezolvare

[•devilkind]

pai sa vedem eu trei dreptunghiuri de suma X,Y,Z dak as alege alte 3 numere X1, Y1, Z1,  atunci x1<=x; y1<=y; z1<=z si deci x1+y1+z1<=x+y+z;

akum ca ti-am demonstrat greedyu meu (cel putin am incercat) v-as ruga sa imi ziceti de nu ar merge.

[•wefgef]

4 4
50 50 50 50
-1 -1 -1 -1
50 50 50 50
-1 -1 -1 -1
50 50 50 50

[•devilkind]

aha akuma am reusit sa inteleg. mersi

[•pauldb]

In exemplu ar trebui N=6.

[•DITzoneC]

Am sters o linie, ca sa se potriveasa cu explicatia.

[•devilkind]

testele 3,12 si 17 au ceva particular in comun? iau WA pe ele

[•Cosmin]

Poate ai scapat o configuratie relativa a celor trei dreptunghiuri.

[•peanutz]

Tiberiu, cum se comporta algoritmul tau cand trebuie sa determini submatricea maxima a unui dreptunghi cu o singura coloana? Eu luam wa pe timus la o problema in genu asta. Am pus max = s[1], si a mers.

[•visanr]

Limita de timp cred ca e cam mica. Am O(N ^ 3), ce-i drept, cu o constanta maricica, dar ia TLE pe multe teste. Am vazut ca in afara de 2 surse, celelalte care au 100 au in jur de 400-500 ms pe ultimele teste. Cu o solutie incompleta iau 75, iar pe ultimele teste intra la limita, cu o solutie completa iau TLE la greu.

[•wefgef]

Am marit limita la 0.3 secunde.

[•visanr]

Mersi mult!

Are ceva special testul 8 de iau incorect doar pe el?  

LE: 100

[•repp4radu]

Salut!

Mi-ati putea da niste teste cu cazuri mai speciale?
Toate testele care mi le-am dat(si au fost destul de multe) le-am luat, dar iau 80 cu WA.

Mersi anticipat!