273 Secventa 4

[•filipb]

Aici puteţi discuta despre problema Secventa 4.

[koala]

Imi poate spune cineva mai exact,cum folosesc deque-ul pentru a afla minimul din secventa i-y,i-x ? 

Va multumesc !

[•pauldb]

La pasul i, introduci elementul de pe pozitia i-x (a[i-x]) in deque. Atat timp cat a[i-x] este mai mare ca ultimul element din deque, scoti ultimul element din deque. Apoi adaugi a[i-x] in deque. Minimul il vei avea intotdeauna in prima pozitie a deque-ului. Daca primul element din deque este egal cu a[i-y] atunci, il scoti din deque.

[koala]

Multumesc de informatie ! 

[•sima_cotizo]

La pasul i, introduci elementul de pe pozitia i-x (a[i-x]) in deque. Atat timp cat a[i-x] este mai mare ca ultimul element din deque, scoti ultimul element din deque. Apoi adaugi a[i-x] in deque. Minimul il vei avea intotdeauna in prima pozitie a deque-ului. Daca primul element din deque este egal cu a[i-y] atunci, il scoti din deque.

Nu am inteles eu prea bine unde il bagi pe A[i-x], atata timp cat il poti baga in ambele capete. In prima pozitie nu il poti baga fiindca nu ar mai fi minimul acolo, deci il bagi la sfarsit. Dar nu inteleg de ce scoti elemente mai mici ca A[i-x] din coada, atat timp cat ele pot reprezenta minime viitoare...

Ma iertati daca am intrebat chestii evidente, dar nu prea inteleg cum functioneaza tipul asta de coada.

PS: nu poate fi rezolvata problema aflarii minimului si cu un minheap, din care scufunzi radacina daca e "indepartata" de pozitia actuala cu mai mult de y pozitii?..

[•Bluedrop_demon]

La pasul i, introduci elementul de pe pozitia i-x (a[i-x]) in deque : Atat timp cat a[i-x] este mai mare ca ultimul element din deque, scoti ultimul element din deque. Apoi adaugi a[i-x] in deque. Minimul il vei avea intotdeauna in prima pozitie a deque-ului. Daca primul element din deque este egal cu a[i-y] atunci, il scoti din deque.

Dupa prima fraza urmeaza ":" si astfel ce urmeaza explica cum introduci elementul a[i-x]. Cat timp ultimul e mai mic decat el, il scoti din deque, dupa care pui elementul a[i-x] pe ultima pozitie pana cand ai pus a[i-y] pe prima pozitie.

P.S. Asa am inteles eu cel putin...

[•rares192]

La problema aceasta ati logaritmat in baza 10 ? ma gandesc ca pt valoarea 0 sau negative nici macar nu e definit logaritmul. Cum ati procedat ?

[•rares192]

Eu am logaritmat fiecare nr citit si am tinut niste sume partiale si apoi am facut in o(n) cu un deque dar tot 70 de puncte iau..ma gandesc ca e din cauza lg(0) care nu e definit si nu imi dau seama cum se procedeaza.

[•DraStiK]

Eu am logaritmat fiecare nr citit si am tinut niste sume partiale si apoi am facut in o(n) cu un deque dar tot 70 de puncte iau..ma gandesc ca e din cauza lg(0) care nu e definit si nu imi dau seama cum se procedeaza.

Cand le logaritmezi, logaritmeaza valoarea in modul a numerelor, si ca sa stii cand ai logaritmat un numar negativ, poti vine un vector semn[ i ] in care iti tii semnul numarului.
Poti citi mai multe in articolul cu solutiile oficiale. http://infoarena.ro/warm-up-2006/solutii

[•rares192]

Multumesc ! Acum iau 95  ca iau WA la testul 16 si nu imi dau seama de ce . Are cineva testul 16 ?

[•patrutoiuandrei]

vad ca multa lume a luat 95 pct cu incorect pe testul 9. este caz particular?