Problemă - Programare dinamică

[•TheNechiz]

Fie B o matrice binară (elemente numai 0 și 1) cu L linii și C coloane. Vrem
să gasim valoarea m cea mai mare astfel încât există o sub-matrice pătratică M
de dimensiuni m x m din B care are toate elementele = 1. Dacă este permisă
permutarea coloanelor lui B scrieți un program care calculează m.

Iau o matrice m[i..L][j..C] cu proprietatea că m[ i ][ j ] = suma elementelor matricei pătratice cu colțul din stânga sus în i și colțul din dreapta jos în j. Verific dacă această sumă e egală cu "latură la pătrat", apoi păstrez cea mai mare astfel de sumă.

Nu reușesc să-mi dau seama cum ar trebui să îl aflu pe m, dacă se pot permuta coloanele.

PS: Nu e o obligatoriu să se folosească programarea dinamică.

[•klamathix]

Îți precalculezi pentru fiecare celulă cea mai lungă secvență de 1 care începe în celula respectivă și merge în sus, fie ea lengthUp[i ][j]. Apoi îți fixezi linia (i-ul), acum îl poți privi pe lengthUp ca fiind unidimensional. Fiindcă poți permuta coloanele, le vei permuta astfel încât lengthUP să fie sortat crescător/descrescător. Apoi te descurci tu

[•TheNechiz]

Mersi pentru răspuns. 
Nu pot să cred că rezolvarea era așa de simplă și nu am văzut-o.

[•klamathix]

Cu plăcere. Avem versiunea cu dreptunghi și pe site http://www.infoarena.ro/problema/logs. Cere O(n * m) din câte țin minte.

[•TheNechiz]

În loc de sortare am construit un vector V cu proprietatea că V[ i ] reține numărul secvențelor de cel puțin i de 1.

Puțin off-topic:
Am încercat să implementez asta și pentru logs, dar am luat 60p. Am citit câteva comentarii și după am încercat să fac citirea cu parsare, dar nu m-am ridicat mai sus de 60p.

După, am zis să încerc ideea cu sortarea, dar am luat 30p...( folosind qsort din stdlib )

[•klamathix]

E posibil reinit()-urile alea să te tragă în jos, teoretic sunt O(n ^ 2) și îți domină complexitatea.

[•TheNechiz]

Am scos reinit()-urile și am folosit un vector pentru a determina cea mai mare secvență de unu. Cum aș mai putea să reduc complexitatea ?

[•klamathix]

Sursele tale au fie N * M * log N, fie N * N.

Soluția bună are N * M curat. Ideea e că atunci când mai înaintezi cu o linie înălțimile de 1 se schimbă într-un mod destul de particular, care îți permite să le ții sortate în timp liniar, nu să faci sort() sau qsort() la fiecare pas. Vezi care e particularitatea asta la care mă refer .

[•TheNechiz]

Poți să-mi dai un hint ?

[•klamathix]

Când mai cobori o linie, o înălțime fie crește cu 1 fie devine 0. Cele care cresc își păstrează ordinea relativă, cele care devin 0 se duc în capătul șirului.

[•TheNechiz]

Acest indiciu mi-a zis că sunt pe drumul cel bun. Nu aveam în minte o metodă clară de a implementa această idee. Într-un final, am găsit o cale. Dar presupun că trebuie să-i fac o îmbunătățire. Am luat 80p. Mai am o idee, dar are aceeași complexitate ca ultima sursă trimisă.