infoarena

Comentarii la articolul Deque și aplicații (http://infoarena.ro/deque-si-aplicatii) 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ă.

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

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

Bun articol. Felicitari autorilor! :)

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

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  :-k

Am schimbat.

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

Claudiu