036 Parantezare optima de matrici

[•Marius]

Aici puteţi discuta despre problema Parantezare optima de matrici.

[•Florian]

E stransa limita de timp sau e busita sursa asta ?

[•pauldb]

Limita de timp nu este stransa. Sunt destule surse care iau 100 de puncte si intra in sub o secunda.

[•Florian]

Am o nelamurire. Am trimis doua surse: una si a doua. 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? 

[•pauldb]

Uite, 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 2^x, 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.

[•Florian]

Deci cel mai sigur e sa declari fix cat ai nevoie, nu?

[•wefgef]

Nu cred ca e cea mai buna idee sa declari exact cat ai nevoie, recomand sa pui cu 5-10 mai mult.

[•Bogdan_tmm]

Cod:

	for(int i=1;i<=30;i++)
	{
		a.push_back(i);
		printf("%d %d\n",a.size(),a.capacity());
	}

Cod:

1 1
2 2
3 3
4 4
5 6
6 6
7 9
8 9
9 9
10 13
11 13
12 13
13 13
14 19
15 19
16 19
17 19
18 19
19 19
20 28
21 28
22 28
23 28
24 28
25 28
26 28
27 28
28 28
29 42
30 42

asta e in visual c++. S-ar putea ca in gcc sa se dubleze de fiecare data memoria alocata.
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...

[•philip]

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?

[•mathboy]

Incearca smenul lui Cosmin Negruseri cu SetTextBuf de aici :http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942. S-ar putea sa mearga .

[•philip]

Incearca smenul lui Cosmin Negruseri cu SetTextBuf de aici :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(n³)? Sau se poate optimiza altcumva?

[•alexandru92]

Exista o solutie NlogN din cate stiu, citeste prin Cormen

[•philip]

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.

[•alexandru92]

http://zhuzeyuan.hp.infoseek.co.jp/ita/chap16.htm
Citeste mai jos, pe la Optimal polygon triangulation

[•philip]

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...

the optimal triangulation procedure runs in time O(n³)

[•Marius]

Exista o solutie NlogN din cate stiu, citeste prin Cormen

Nu există aşa ceva. Oriunde vei găsi O(n³).

[•blasterz]

Incearca smenul lui Cosmin Negruseri cu SetTextBuf de aici :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(n³)? 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 ?

[•philip]

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.

[•SpiderMan]

Am vazut de multe ori aceasta "greseala". Corect este o matrice, doua matrice nu matrici, puteti vedea si in DEX  .

[•dushmi]

Aveti cumva vreo idee de ce sursa http://infoarena.ro/job_detail/520020?action=view-source iese din timp, pe cand sursa 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.

[•feelshift]

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) 

[•cont_teste]

de ce link-ul catre cartea lui Cormen..este un link catre un site in chineza?

[•claudiumihail]

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

[•S7012MY]

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

[•claudiumihail]

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 , 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 .