Titlul: Problemă - Programare dinamică Scris de: FMI Razvan Birisan din Noiembrie 05, 2015, 20:00:15 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ă. Titlul: Răspuns: Problemă - Programare dinamică Scris de: Mihai Calancea din Noiembrie 05, 2015, 22:00:00 Îț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 :)
Titlul: Răspuns: Problemă - Programare dinamică Scris de: FMI Razvan Birisan din Noiembrie 05, 2015, 22:21:32 Mersi pentru răspuns. :thumbup:
Nu pot să cred că rezolvarea era așa de simplă și nu am văzut-o. ](*,) Titlul: Răspuns: Problemă - Programare dinamică Scris de: Mihai Calancea din Noiembrie 06, 2015, 13:09:10 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.
Titlul: Răspuns: Problemă - Programare dinamică Scris de: FMI Razvan Birisan din Noiembrie 06, 2015, 17:16:25 Î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 ) Titlul: Răspuns: Problemă - Programare dinamică Scris de: Mihai Calancea din Noiembrie 06, 2015, 20:48:05 E posibil reinit()-urile alea să te tragă în jos, teoretic sunt O(n ^ 2) și îți domină complexitatea.
Titlul: Răspuns: Problemă - Programare dinamică Scris de: FMI Razvan Birisan din Noiembrie 07, 2015, 18:25:44 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 ? Titlul: Răspuns: Problemă - Programare dinamică Scris de: Mihai Calancea din Noiembrie 08, 2015, 14:10:45 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 :). Titlul: Răspuns: Problemă - Programare dinamică Scris de: FMI Razvan Birisan din Noiembrie 11, 2015, 18:34:08 Poți să-mi dai un hint ?
Titlul: Răspuns: Problemă - Programare dinamică Scris de: Mihai Calancea din Noiembrie 12, 2015, 14:32:45 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.
Titlul: Răspuns: Problemă - Programare dinamică Scris de: FMI Razvan Birisan din Noiembrie 15, 2015, 20:43:01 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ă.
|