660 Submat

[•DITzoneC]

Aici puteţi discuta despre problema Submat.

[•Florian]

Cod:

matricei Ai,j pentru care L1 ≤ i ≤ L2 si C1 ≤ i ≤ C2.
 

cred ca acolo e de fapt, C1 ≤ i ≤ C2.

Si cred ca limita de timp ar trebui scazuta pana la vreo 0.2 secunde.. mie mi`a intrat cu 192 ms cel mai mare test ...

[•raduzer]

Gata, am modificat. In legatura cu limita de timp, eu am pus-o exact la fel ca la ONI.

[LE] Am modificat si limita de timp din 1 sec in 0.5. Toate rezultatele au ramas la fel.

[•CezarMocan]

Si vezi, poate ar fi bine sa reduci memoria sa fie ca la ONI... vreo 640 Kb sau cat e.

[•DITzoneC]

Am redus limita de memorie la 640k si am reevaluat.

[•mihai0110]

am luat 100 cu o sursa clar gresita care pentru testul

3 5
0 0 0 1 1
0 1 0 1 1
0 0 0 1 1

imi afisa 9

ulterior am modificat incat sa imi dea bine, dar e ciudat sa iau 100 cu o sursa care da raspuns gresit pe un test mic

[•gabitzish1]

Testul tau e gresit...

Se considera o matrice A cu urmatoarele proprietati:

    * contine n linii si m coloane;
    * contine doar valorile 0 si 1;
    * pe fiecare linie valorile sunt plasate in ordine crescatoare.

nu are a treia proprietate.

[•mihai0110]

am citit pe sarite        

[•jupanu92]

Da ce prost am fost miam declarat degeaba o matrice cand eu am nevoie doar de numarul de zerouri Deja incep sa ma invat de vreo 3 zile iau numai cate 100 de p pana acu luam numai cate 20

[•devilkind]

incearca sa rezolvi probleme mai grele

[•jupanu92]

Da stai ma asa cas abia pe la inceput abia reusesc sa rezolv si eu o pr de cls a 8 a si tu zici sa fac dalea mai grele o sa trec la dalea mai grele dupa ce le rezolv pe astea usoare

[•MciprianM]

Maxim 8ms,320kb.
Am un 8ms, 2*4ms restul 0ms;
E cel mai rapid rezultat obtinut pe infoarena.

[•toni2007]

neah...
te-am luat:)

Cod:

1	0ms	8kb	OK	10
2	0ms	8kb	OK	10
3	0ms	8kb	OK	10
4	0ms	8kb	OK	10
5	0ms	12kb	OK	10
6	0ms	12kb	OK	10
7	4ms	12kb	OK	10
8	4ms	12kb	OK	10
9	4ms	176kb	OK	10
10	8ms	172kb	OK	10
Punctaj total	100

am consumat de doua ori mai putina memorie:)

[•wefgef]

M-am uitat peste sursele voastre si nu ai mai putina memorie decat el. In plus, timpii tai sunt mai slabi:

http://infoarena.ro/job_detail/193525

Complexitatea ta este mai buna totusi

[•bogdan2412]

eu am 4 ms http://infoarena.ro/job_detail/193510 evident ca timpii variaza cu mai mult de 10ms la aceeasi sursa da' ma rog

[•wefgef]

Da mah, da suma cumulata e proasta, si ai si complexitatea neoptima )

Uite toni, sursa ta in C++: http://infoarena.ro/job_detail/193539

[•bogdan2412]

maximu conteaza
la complexitate: citirea e n^2, (n^2+n log n) sau (n^2+n) e acelasi lucru

[•wefgef]

Te inseli prietene, complexitatea ta e N(M + log N). Iar a lui este N*M. Daca matricea era patratica, alta treaba .

[•bogdan2412]

mda, mi-ai zis-o

[•toni2007]

Da mah, da suma cumulata e proasta, si ai si complexitatea neoptima )

Uite toni, sursa ta in C++: http://infoarena.ro/job_detail/193539

dar stiam ca c-ul merge mai repede 

oricum bucket sort rulz

[•wefgef]

Am testat si eu o sursa acum cateva zile si in C++ mergea semnificativ mai repede .

[•xblade]

care e problema la aceasta sursa?

imi da Killed by signal 11(SIGSEGV).

EDIT:

am inteles buba, problema e ca nu stiu cum o rezolv...

[•c_e_manu]

La limita de memorie pentru problema asta (640KB), nu poti declara o matrice de 1001*1001. Depasesti limita de memorie cu alte cuvinte.

[•gabor_oliviu1991]

Cu alte cuvinte trebuie sa citesti fiecare linie intr-un vector, decat sa citesti toata matricea. Algoritmul e bun, in mare parte. Poti sa il stergi din post ca dupa toata lumea o sa stie cum se face

[•brainwashed20]

deci eu verific pt fiecare linie nr de 0uri, bag acele numere intru vector, il ordonez descrescator si apoi verific determin maximul de a[ i ]*i..
unde gresesc? iau 0 puncte..