|
Titlul: 036 Parantezare optima de matrici Scris de: Marius Stroe din Noiembrie 28, 2009, 21:56:20 Aici puteţi discuta despre problema Parantezare optima de matrici (http://infoarena.ro/problema/podm).
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Florian Marcu din Decembrie 04, 2009, 11:59:11 E stransa limita de timp sau e busita sursa asta (http://infoarena.ro/job_detail/371205?action=view-source) ?
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Paul-Dan Baltescu din Decembrie 04, 2009, 13:33:49 Limita de timp nu este stransa. Sunt destule surse (http://infoarena.ro/monitor?task=podm&score_begin=100) care iau 100 de puncte si intra in sub o secunda.
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Florian Marcu din Decembrie 10, 2009, 20:31:06 Am o nelamurire. Am trimis doua surse: una (http://infoarena.ro/job_detail/371232?action=view-source) si a doua (http://infoarena.ro/job_detail/371233?action=view-source). In prima, am declarat bst[512][512] si d[512]. In cea de-a doua am bst[502][502] si d[502]. Timpii de executie sunt cu mult in favoarea celei de-a doua variante ( au scazut de la 1700+ ms la 912 ms pe testul maxim). Nu mai exista nicio deosebire in cele doua surse. Care e faza? :o
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Paul-Dan Baltescu din Decembrie 10, 2009, 23:20:25 Uite (http://infoarena.ro/job_detail/372626?action=view-source), am trimis si eu o data sursa ta, declarand matricea de 511 pe 511 si a intrat in timp. Tind sa cred ca pe ultimele versiuni la compilatorului, cand declari un vector/matrice de dimensiune 2x, aloca mai multa memorie decat ar trebui. Cred ca nu e o intamplare izolata, am mai intalnit si eu recent de situatie de acelasi tip.
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Florian Marcu din Decembrie 11, 2009, 09:06:30 Deci cel mai sigur e sa declari fix cat ai nevoie, nu?
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Andrei Grigorean din Decembrie 11, 2009, 16:20:27 Nu cred ca e cea mai buna idee sa declari exact cat ai nevoie, recomand sa pui cu 5-10 mai mult.
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Tirca Bogdan din Decembrie 12, 2009, 03:00:21 Cod: for(int i=1;i<=30;i++) Cod: 1 1 alte cateva exemple mai mari 95 141 142 211 212 316 712 1066 92171 138255 L.E. Asta in cazul in care vectoru e declarat in stl... Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Philip din Februarie 09, 2010, 20:08:15 Presupun ca pentru pascal nu s-a verificat daca intra in timp.
http://infoarena.ro/monitor?task=podm&compiler=fpc Sau as mai putea optimiza sursa mea cu ceva? Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Dragos-Alin Rotaru din Februarie 09, 2010, 21:38:32 Incearca smenul lui Cosmin Negruseri cu SetTextBuf de aici :http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942 (http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942). S-ar putea sa mearga .:)
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Philip din Februarie 15, 2010, 20:55:38 Incearca smenul lui Cosmin Negruseri cu SetTextBuf de aici :http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942 (http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942). S-ar putea sa mearga .:) Nu cred ca ar ajuta mult, avand in vedere ca am de citit maxim 500 de numere. O sa incerc totusi. LE: Nu merge. Exista o solutie mai buna decat O(n3)? Sau se poate optimiza altcumva? Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: alexandru din Februarie 15, 2010, 21:14:45 Exista o solutie NlogN din cate stiu, citeste prin Cormen :)
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Philip din Februarie 15, 2010, 21:22:53 Exista o solutie NlogN din cate stiu, citeste prin Cormen :) Nu este, poate confunzi problema cu alta. In Cormen e aceeasi solutie ca cea oficiala de aici. Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: alexandru din Februarie 15, 2010, 21:30:45 http://zhuzeyuan.hp.infoseek.co.jp/ita/chap16.htm
Citeste mai jos, pe la Optimal polygon triangulation Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Philip din Februarie 15, 2010, 21:44:32 http://zhuzeyuan.hp.infoseek.co.jp/ita/chap16.htm Citeste mai jos, pe la Optimal polygon triangulation Intr-adevar, nu am vazut asta, dar totusi... Citat the optimal triangulation procedure runs in time O(n3) Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Marius Stroe din Februarie 15, 2010, 23:01:26 Exista o solutie NlogN din cate stiu, citeste prin Cormen :) Nu există aşa ceva. :) Oriunde vei găsi O(n3). Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Mircea Dima din Februarie 15, 2010, 23:43:11 Incearca smenul lui Cosmin Negruseri cu SetTextBuf de aici :http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942 (http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942). S-ar putea sa mearga .:) Nu cred ca ar ajuta mult, avand in vedere ca am de citit maxim 500 de numere. O sa incerc totusi. LE: Nu merge. Exista o solutie mai buna decat O(n3)? Sau se poate optimiza altcumva? M-am uitat peste sursa ta si am o întrebare : De ce declari matricea s de 10000 pe 10000 ? Nu trebuia de 501 pe 501 ? Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Philip din Februarie 15, 2010, 23:54:15 M-am uitat peste sursa ta si am o întrebare : De ce declari matricea s de 10000 pe 10000 ? Nu trebuia de 501 pe 501 ? Ba da, ai dreptate. Nu stiu de ce am declarat-o asa. Ramane insa problema incadrarii in timp la ultimul test. Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Simoiu Robert din Octombrie 25, 2010, 14:37:51 Am vazut de multe ori aceasta "greseala". Corect este o matrice, doua matrice nu
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Mihai-Alexandru Dusmanu din Ianuarie 07, 2011, 12:13:58 Aveti cumva vreo idee de ce sursa http://infoarena.ro/job_detail/520020?action=view-source (http://infoarena.ro/job_detail/520020?action=view-source) iese din timp, pe cand sursa http://infoarena.ro/job_detail/520021?action=view-source (http://infoarena.ro/job_detail/520021?action=view-source) nu?
Singura diferenta este ca intr-una matricea este de 1<<9 si in cealalta de 502. Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Feelshift din Februarie 16, 2011, 21:49:25 In atentia celor ce folosesc pentru valoarea infinit 0x3f3f3f3f: aceasta nu este suficient de mare si primeste WA pe ultimele doua teste (cel putin in cazul meu) :P
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Cont Teste din Martie 05, 2013, 23:29:25 de ce link-ul catre cartea lui Cormen..este un link catre un site in chineza?:)
Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Claudiu Mihail din Septembrie 01, 2013, 06:12:54 Salut,
Problema asta cica ar avea o rezolvare in n log n (sau n^2), conform mai multor surse. Cea mai relevanta e asta(0). Am incercat sa urmaresc algoritmul din articol si sa-l aplic manual pe niste exemple (exemplul din articol, precum si exemplul de la problema actuala si testul 2 din atasamente; le-am ales pe astea ca sunt simple si pot fi parcurse manual). Nu am putut sa duc pana la capat algoritmul, in sensul ca explicatiile date de autoare sunt pe alocuri insufieciente, cel putin pentru mine. Poate cineva are mai multa sclipire decat mine. E destul de greu de gasit pe net orice informatie despre metoda asta. Sunt curios daca articolul e gresit (s-a dovedit a fi incorect) sau daca exista alt motiv pentru care sunt informatii numai despre metoda clasica in n^3. Oricum interesant de dezbatut asta. Si ca tot veni vorba, poate si asta(1) e interesant/de folos cuiva. Numai bine, Claudiu (0) http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/0603055.pdf (1) http://codeforces.com/blog/entry/8219 Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Petru Trimbitas din Septembrie 01, 2013, 23:33:18 wow, super tare
LE: Aici nu merge deoarece costul e v[ i ]*v[k]*v[j] si atunci nu se mai pastreaza inegaliteatea indicilor link-ul de pe uva nu mai merge Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Claudiu Mihail din Septembrie 02, 2013, 06:27:59 Articolul din link-ul cu PDF-ul postat contine in a doua parte (pagina 4 din PDF) un algoritm dedicat pentru matrix chain multiplication. Autoarea pretinde ca ar fi n^2, dupa cum am zis in post-ul precedent. Ideea se bazeaza pe echivalenta problemelor matrix chain multiplication si minimum weight polygon triangulation. Echivalenta dintre aceste doua probleme, ca fapt divers, este prezentata ca un excercitiu si in cartea de probleme a lui Ioan Tomescu (aia din care tot se dadeau mai demult probleme la ONI).
Dupa cum am zis, am incercat sa urmaresc algortimul dedicat dar m-am impotmolit pe exemple. PS: Algoritmul state-of-the-art pentru matrix chain multiplication cica ar fi asta: ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf (ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf) , care e in n log n. Din cate am observat e citat intr-o sumedenie de alte articole si ma mira ca nu e explicat nicaieri mai in detaliu (chiar si intr-un curs avansat). N-am stat sa-l diger insa, din moment ce sunt prea varza sa-l pricep macar pe cel in O(n^2) PPS: Petru, am presupus ca macar prima parte din post-ul tau a fost legat de ce am scris eu mai sus :). Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Rapeanu George din Noiembrie 05, 2016, 11:29:37 exemplul este gresit ](*,) ](*,) ](*,) ](*,)
rezultatul e 2466 Titlul: Răspuns: 036 Parantezare optima de matrici Scris de: Mihai Calancea din Noiembrie 08, 2016, 22:42:08 Cred că ar mai fi semnalat cineva că este greșit, după atâția ani și atâtea surse de 100 :). E mai probabil să greșești tu.
|