Deque și aplicații

[•stef2n]

Comentarii la articolul Deque și aplicații scris de Marius Stroe.

Marius și-a propus să prezinte în acest articol o structură de date tot mai des întâlnită în concursurile de informatică: deque. Veți remarca numărul mare de probleme explicate, tocmai pentru a vă ajuta să descoperiți mai ușor problemele în care se pretează această structură.

[•Marius]

Ca întotdeauna, îi mulţumesc lui Ştefan pentru revizuirea şi îmbunătăţirea calităţii articolului. Dacă nu s-ar fi uitat peste el, cu siguranţă nu ar fi plăcut nimănui.

[•wefgef]

Bravo, Marius! Văd că munceşti constant la îmbunătaţirea saitului! Keep up the good work!

[•elfus]

Bun articol. Felicitari autorilor!

[•claudiumihail]

Salut,

Ar fi util de mentionat si problema Avioane[0] in lista de aplicatii rezolvabile cu ajutorul unui deque.

Claudiu

• http://www.infoarena.ro/problema/avioane

[•Impaler_009]

De fapt, la problema Otilia, algoritmul pentru 100 se infaptuieste chiar cu o stiva. MinY(i) este dat de cel mai mic j pentru care MinY[i-j] > j*P. Dar asta este si ordinea in care le avem in lista: de la varf catre coada: MinY[i-1], MinY[i-2] s.a.m.d, deci toate operatiile se pot la un singur capat => stiva.  Deque-ul (cel putin din cate am inteles eu) ar aparea in cazul in care adaugarea/excluderea elementelor din lista ar depinde de un parametru iar calitatea de "cea mai buna solutie" de un altul (de ex., vrem sa calculam v(i) minim cu i pe intervale [j..k]; adaugarea/excluderea depinde de j si k, pe cand solutia optima depinde de v(i)), ceea ce nu e cazul aici. Deci nu stiu in ce masura se justifica tag-ul de deque la problema asta  

[•pauldb]

Am schimbat.

[•claudiumihail]

Ca fapt divers, si problema Ksecv se poate face doar cu stiva. Nu e nevoie de deque pentru 100p.

Claudiu