241 BMatrix

[•Cosmin]

Aici puteţi discuta despre problema BMatrix.

[•Marius]

Ce idei aveti ? (legate de problema )

 

[u-92]

problema e de idee.. vezi cum poti pune cele 2 dreptunghiuri.. daca vrei ceva mai consistent cauta in "task and solutions" de la ioi2005

[•Cosmin]

Cele doua dreptunghiuri care nu se suprapun vor putea fi separate printr-o linie orizontala sau printr-o linie verticala. Si acum pt fiecare pozitionare posibila a liniei de separare ai ajuns la problema mai simpla de determinare a unui dreptunghi maxim gol. Problema asta este clasica si se poate rezolva in mai multe moduril, cele mai des folosite fiind cel in O(n^3) si O(n^2). Daca esti atent poti face o rezolvare in O(n^3) sau O(n^2) in total.

[•pauldb]

Este ceva deosebit la testul 19?  [iau WA]. [Peste tot in problema folosesc longint si matricile le-am indexat de la 0..300].
Cred ca trebuie sa fie altceva. 

[•devilkind]

stie vreo cineva care e faza cu testu 9?? e vreun caz particular ceva?? iau 95 cu WA pe acest test si nu inteleg de ce  .
Am facut un algoritm care ruleaza in n^3.

[•fireatmyself]

in:

Cod:

5 12
111110011111
111100111111
111010111011
111110101111
111110111101

6 13
1111111111111
1100101101010
1101011111111
1101101111111
1101001110111
1111111110111

9 14
11111111100111
11111111100111
10101111111111
11011111111111
11111111111111
11111100111111
11101110111111
11010011111111
11111111111011

20 20
11001111011111111011
11001111110111110111
11001101111011101111
11001111111101011111
10001111111110111111
11001111111111111111
11111111111111111101
11111110000111111111
11111111111111111111
11111111111111001111
11111111111111001111
11000000011111111111
11111111111111110111
11000000011111111111
11111111111111111111
11111111111011111111
11110001001000111111
11111111111111110111
11111110001111111111
11111111111111110111

out:

Cod:

6 6 6 
19

sper ca n-am busit ceva 

[•devilkind]

Am luat 100 dar totusi nu prea inteleg ce era gresit. adik pe testele puse de tine obtineam aceleasi rezultate doar ca am facut o modifiacare care nu afecta codul (dupa parerea mea deloc) si am luat 100. Adica eu pana acum nu am luat in considerare si acoperirea cu un singur dreptunghi.

[•fireatmyself]

pai nu e bine, pentru ca tu trebuia sa determini aria maxima pe care o acopera exact doua dreptunghiuri, nu cel mult doua dreptunghiuri

[•devilkind]

tocmai de aia nu inteleg nici eu de ce luam doar 95 pana akuma. Sunteti siguri ca testu 9 e corect??

[•fireatmyself]

da, suntem siguri. ideea este ca daca exista un singur dreptunghi de 0 (vezi exemplul de mai jos) acesta se poate imparti in doua dreptunghiuri (exista mai multe moduri pentru a o face, dar aria ramane tot cea a dreptunghiului initial). poate nu tratai cum trebuie acest caz.

Cod:

3 5
11111
10001
10001

explicatie: o solutie posibila ar fi sa consideri primul dreptunghi format din casutele (2, 2) si (3, 2), iar al doilea dreptunghi format din casutele (2, 3), (2, 4), (3, 3), respectiv (3, 4). o alta solutie ar fi sa consideri dreptunghiul format din casutele (2, 2), (2, 3), respectiv (2, 4) si dreptunghiul format din casutele (3, 2), (3, 3), respectiv (3, 4). in ambele cazuri raspunsul este 6.

[•savim]

Problema merge O ( N ^ 3)? Am incercat o astfel de dinamica si iau 90p (TLE pe ultimile doua). Si daca nu merge, puteti sa-mi dati un hint pentru O( N ^ 2) ?

[•pauldb]

Incearca sa folosesti doar O(N^2) memorie.

[•wefgef]

Problema se poate face si in O(N^2). Stii sa faci submatricea de suma maxima in O(N^2)?

[•Cosmin]

Andrei daca stii sa faci submatricea de suma maxima in O(n^2) atunci poti sa scrii un research paper. Cel mai bun algoritm cunoscut are complexitate putin mai mica decat O(n^3).

Probabil tu te refereai la submatricea maxima plina de 0.

[•wefgef]

), Da la submatricea maxima plina de 0 ma refeream .

[•savim]

Nu, stiu doar O ( N ^ 3). O sa incerc sa optimizez memoria cum a zis Paul, sa vad cat iau. Daca nu merge asa, o sa ma gandesc la O (N ^ 2).

L.E.: Am reusit sa iau suta  , modificand ordinea unor foruri, si micsorand tipul variabilelor. Pana la urma nu a trebuit sa tin ultimele doua linii din dinamica, oricum multumesc de sfaturi!

[•Dastas]

Eu sunt foarte curios cum se face submatrice maxima plina de zerouri in O(n²)... as fi recunoscator daca ar explica cineva ideea .

[•pauldb]

Initial calculezi A[i,j] = numarul de 0 consecutivi deasupra pozitiei i, j. Apoi parcurgi linie cu linie matricea si iti propui sa afli cel mai mare dreptunghi plin cu 0 deasupra liniei i (linia curenta). Parcurgi linia de la stanga la dreapta si adaugi valorile A[i,j] intr-o stiva. Cat timp elementul din stiva este mai mare decat elementul curent acesta este scos. Vezi daca varful stivei * (pozitia curenta - pozitia in care a fost varful adaugat in stiva) este mai bun ca solutia si actualizezi. Reiei apoi acelasi algoritm pe linie de la dreapta la stanga si in final vei obtine cel mai bun dreptunghi deasupra liniei i. De mentionat ca cu acest algoritm, nu poti (cel putin nu stiu eu cum) afla cel mai mare dreptunghi cu 0 cu coltul in (i, j).

Ma gandesc dreptunghiul si patratul maxim de 0 sunt dinamici care ar trebui adaugate in arhiva educationala pe viitor. Buru, modifici tu pagina?

[•bogdan2412]

S-au schimbat o parte din teste de la aceasta problema pentru a pica solutiile incorecte care luau 100 de puncte si s-au reevaluat toate sursele trimise pana acum.

[•APOCALYPTO]

Initial calculezi A[i,j] = numarul de 0 consecutivi deasupra pozitiei i, j. Apoi parcurgi linie cu linie matricea si iti propui sa afli cel mai mare dreptunghi plin cu 0 deasupra liniei i (linia curenta). Parcurgi linia de la stanga la dreapta si adaugi valorile A[i,j] intr-o stiva. Cat timp elementul din stiva este mai mare decat elementul curent acesta este scos. Vezi daca varful stivei * (pozitia curenta - pozitia in care a fost varful adaugat in stiva) este mai bun ca solutia si actualizezi. Reiei apoi acelasi algoritm pe linie de la dreapta la stanga si in final vei obtine cel mai bun dreptunghi deasupra liniei i. De mentionat ca cu acest algoritm, nu poti (cel putin nu stiu eu cum) afla cel mai mare dreptunghi cu 0 cu coltul in (i, j).

Ma gandesc dreptunghiul si patratul maxim de 0 sunt dinamici care ar trebui adaugate in arhiva educationala pe viitor. Buru, modifici tu pagina?

Cine e acesta acesta?
Elementul din varful stivei?
Cum se introduc valori in stiva? Pe parcursul parcurgerii liniei i sau imediat ce trecem la linie noua introducem toate elementele liniei respective in stiva?
Cand  incepem sa parcurgem de la dreapta la stanga linia i se va intampla ceva cu stiva? Elementel vor ramane la fel ca atunci cand am terminat de parcurs de la stanga la dreapta?
Din ce vom obtine cel mai bun dreptunghi de deasupra liniei i? In stiva?

Multumesc anticipat pentru raspunsuri!

[•pauldb]

Voi detalia mai mult solutia de mai sus pentru ca nu e completa si nici in totalitate corecta.


Calculezi A[i,j] = numarul de 0 consecutivi deasupra pozitiei (i,j). Apoi fixam o linie i si ne propunem sa calculam dreptunghiul de arie maxima plin cu 0 care are latura de jos pe linia i. Pentru a atinge acest scop, vom calcula pentru fiecare coloana j, care este latimea maxima a unui dreptunghi plin cu 0 care are inaltimea A[i,j]. Adica ne dorim mai exact sa calculam acel j' < j maxim astfel incat A[i,j'] < A[i,j] si acel j''>j minim astfel incat A[i,j'']<A[i,j]. Este evident ca daca stim pe j' si j'' baza dreptunghiului de inaltime A[i,j] se intinde intre j'+1 si j''-1, deci latimea dreptunghiului este j''-1-j'. Astfel avem un candidat pentru marirea solutiei curente, de arie A[i,j]*(j''-1-j').

Mai trebuie sa vedem cum putem calcula j' si j'' pentru fiecare j. Mentionez ca j'' se obtine analog cu j', singura diferenta este ca linia i se parcurge de la dreapta la stanga pentru obtinerea lui. Pentru a afla j', vom parcurge coloanele de la stanga la dreapta si vom insera treptat intr-o stiva valorile A[i,j]. Vom mai folosi un vector suplimentar pentru a memora coloana cand a intrat o valoare in stiva. La fiecare pas eliminam varful stivei cat timp acesta este strict mai mare decat A[i,j]-ul curent. In continuare, daca A[i,j] este strict mai mare decat varful stivei, se introduce in stiva. Daca la pasul curent a fost eliminat cel putin un element din stiva, nu se modifica coloana de introducere pentru varful stivei chiar daca il introducem pe A[i,j]. Motivul este ca elementele eliminate au fost cu siguranta mai mari decat A[i,j] si deci dreptunghiul se poate intinde in urma. Altfel (daca nu a fost eliminat nici un element), coloana in care a fost introdus varful stivei se considera a fi j (deoarece coloana anterioara este de o inaltime strict mai mica). Astfel, pentru fiecare pozitie j, j'+1 = coloana pentru care a fost introdus varful stivei.

[•wefgef]

Solutia prezentata de tine initial este diferita (si mai rapida) de cea cu un post mai sus . In schimb, este mai usor de inteles corectitudinea algoritmului cu doua parcurgeri.

[•pauldb]

Pai, acum cand ma gandesc, solutia de mai sus chiar nu mi se pare corecta (ma refer la fraza "Vezi daca varful stivei * (pozitia curenta - pozitia in care a fost varful adaugat in stiva) este mai bun ca solutia si actualizezi"). De exemplu, nu mi se pare ca acopera cazuri de genul:

01110
00100
00000
00000

Tu cum faci dintr-o singura parcurgere?

[•wefgef]

Fac exact asa cum ai explicat tu. Uite o sursa: http://infoarena.ro/job_detail/312811?action=view-source

Mentin o stiva de perechi (inaltime, pozitie), sortate strict crescator dupa inaltime, care reprezinta candidatii pentru capatul din stanga al dreptunghiului de arie maxima. Pentru pasul i sa spunem ca ai inaltimea h. Vrei sa introduci in stiva. Daca h este mai mare decat varful stivei adaugi perechea (h, i). Altfel, scoti din stiva cat timp inaltimea din varf este mai mare strict decat h. Daca ramai in varf cu o inaltime egala cu h, nu faci nimic. Altfel adaugi perechea (h, j), unde j reprezinta ultima pozitie pe care ai sters-o din varful stivei. Stiva ar functiona astfel pe exemplul dat de tine:

Pasul 1: (4, 1).
Pasul 2: Scoti (4, 1), adaugi (3, 1). Stiva arata astfel: (3, 1).
Pasul 3: Scoti (3, 1), adaugi (2, 1). Stiva arata astfel: (2, 1).
Pasul 4: Adaugi (3, 4). Stiva arata astfel: (2, 1), (3, 4).
Pasul 5: Adaugi (4, 5). Stiva arata astfel: (2, 1), (3, 4), (4, 5).

Verficarile le fac atunci cand scot din stiva. La sfarsit am grija sa golesc de tot stiva, facand verificarile necesare.