394 Vila 2

[•DITzoneC]

Aici puteţi discuta despre problema Vila 2.

[•Dastas]

Imi spuneti va rog cum ar functiona un deque care retine minimul pe exemplu? Am citit tot ce am gasit despre structura asta pe forum si tot nu-mi dau seama exact cum functioneaza 

[•peanutz]

Probabil cel mai bine ar fi sa vezi un deque, pentru ca nu e mare scofala. Da-mi un msg cu adresa de mail.

[•pauldb]

Imi spuneti va rog cum ar functiona un deque care retine minimul pe exemplu? Am citit tot ce am gasit despre structura asta pe forum si tot nu-mi dau seama exact cum functioneaza 

In deque incerci sa obtii varsta minima a unui vecin, pentru a maximaliza diferenta. (Nu trebuie sa tii si maximul pentru ca daca i e vecin cu j, atunci si j e vecin cu i.) La pasul i, cat timp ultimul element din deque este mai mare ca elementul de pe pozitia i+k, il scoti. Apoi adaugi in deque elementul de pe pozitia i+k. Verifici daca diferenta dintre elementul i si minimul din deque (varful deque-ului) este mai mare ca solutia ta si eventual actualizezi. Ultimul pas este sa verifici daca varful deque-ului este elementul de pe pozitia i-k si in acest caz il scoti, deoarece paraseste zona vecinilor care intereseaza. 

[•Dastas]

Va multumesc la amandoi, mi-a iesit pana la urma

[•alex_mircescu]

Ma ajutati si pe mine cu un test care sa aiba legatura cu #1??
Chiar nu stiu ce are... am incercat o tona de posibilitati...
Iau WA pe el... nu am probleme cu timpu' 

...

LE: Nu m-am prins inca... nu gasesc nimic... 

LLE: Am uitat sa spun ca mi-o iesit 

[•stocarul]

Am icnercat si eu o rezolvare la problema asta.
Si din pacate iau doar 60 pct 

Fac cu un deque pentru varsta maxima din interval, si apoi o compar cu varsta curenta...daca e mai mare decat maximul de pana acum, actualizez maximul

Pun functia de calculare:

Cod:

void rezolvare()
	{
	int i,j,p,q;
	p=1; q=0; //initial coada este goala
	for(i=1;i<=n;i++)
		{
		while(p<=q&&v[d[q]]<=v[i]) q--; //cat timp am varsta mai mare de adaugat
		d[++q]=i; //il punem in deque
		if(i-d[p]>k) p++; //dispare primul element
		j=v[d[p]]-v[i]; //diferenta dintre cel mai batran solarian din interval, si solarianul curent
		if(j>vmax) vmax=j; //am gasit o diferenta mai mare
		}
	}

LE: Am descoperit ce greseam....am facut cu doua deque-uri (unul pt minim, si altul pentru maxim) si am luat 100 

[•mihaionly]

A făcut cineva problema asta folosind un singur deque? Eu a trebuit să implementez două (maxim și minim) pentru că algoritmul descris în soluție nu a fost bun pe toate cazurile.
Dacă de exemplu, avem 1 2 3 4 7 și k=3, deque-ul îl va exclude pe 3 când dă de 4 iar când ajung la 7 nu pot decât să-l compar cu 4, maximul ieșind 3 când defapt este 4   

[•dornescuvlad]

Ce ar putea fi gresit in abordarea aceasta ?

Cod:

	FirstMax = 1, LastMax = 0; // DequeMax e goala
	FirstMin = 1, LastMin = 0; // DequeMin e goala
	
	for(i = 1; i <= N; i ++)
	{
		while(Values[i] >= Values[DequeMax[LastMax]] && LastMax >= FirstMax) LastMax --;
		DequeMax[++ LastMax] = i;
		if(abs(i - DequeMax[FirstMax]) > K) // conditia de vecini
			FirstMax ++;
		
		while(Values[i] <= Values[DequeMin[LastMin]] && LastMin >= FirstMin) LastMin --;
		DequeMin[++ LastMin] = i;
		if(abs(i - DequeMin[FirstMin]) > K) // conditia de vecini
			FirstMin ++;
		
		if(Values[DequeMax[FirstMax]] - Values[DequeMin[FirstMin]] > maxim)
				maxim = Values[DequeMax[FirstMax]] - Values[DequeMin[FirstMin]]; //cel mai mare element din secventa - cel mai mic element din secventa
	}

DequeMax - deque pentru maximul dintr-o secventa
DequeMin - deque pentru minimul dintr-o secventa

[•best4him]

Cod:

#include <fstream>
#include <cstdlib>
using namespace std;
 
ifstream fin("vila2.in");
ofstream fout("vila2.out");

int n,k,front,back,i,maxim,front1,back1;
int a[100010],d[100010],d1[100010];
 
int main()
{
maxim=-30001;
    
    fin>>n>>k;
    for(i=1;i<=n;i++){
        fin>>a[i];	
    }
     
    front=1,back=0;
	front1=1,back1=0;
     
    for(i=1;i<=n;i++){
         
        while(front<=back && a[i]>=a[d[back]])
            back--;
		d[++back]=i;
		while(front1<=back1 && a[i]<=a[d1[back1]] )
            back1--;
		d1[++back1]=i;

       if(i>=k &&  a[d[front]]-a[d1[front1]]>maxim && abs(d[back]-d1[back1])<=k){
            maxim=a[d[front]]-a[d1[front1]];
        }
       if(d[front] == i-k)
           front++;
	   if(d[front1] == i-k)
           front1++;
   }
     
   fout<<maxim;
     
  return 0;
}

nu iau un test...testul 4...imi puteti spune ce gresesc? Multumesc!
am rezolvat pana la urma 

[editat de moderator] foloseste tag-ul "code" cand postezi cod pe forum!

[•AlexandruValeanu]

Imi poate spune si mie cineva cu gresesc sau un hint despre rezolvare?

[•repp4radu]

In general cand vrei sa iti spuna lumea ce gresesti ar fi util sa descri ce faci in sursa ta pentru ca este mult mai incomod de interpretat o sursa decat o idee.

[•PlayLikeNeverB4]

Tocmai ti s-a spus mai sus ca mai bine sa descrii algoritmul decat sa postezi sursa 

Nu iei in considerare cazul in care e un locuitor cu varsta mare dupa care unul cu varsta mica. Indiciu: iti trebuie doua deque.

[•Djok]

Pentru testul exemplu, nu ar trebui sa fie raspunsul 5?
sau k=3?