1086 Secvdist

[•pauldb]

Aici puteţi discuta despre problema Secvdist.

[•eudanip]

In concurs am luat 90 pct iar acuma 100 cu aceeasi sursa. Ma oftic dar ce pot sa zic. Sa incercati sa rezolvati si voi problema asta cu evaluatorul.

[•eudanip]

Am vazut ca ati reevaluat. Multumesc .

[•bogdan2412]

Am vazut ca ati reevaluat. Multumesc .

Nu inteleg de ce s-a intamplat asta. Acum oricat de mult reevaluez iei 100. Daca mai are cineva aceeasi problema cu vreuna din problemele de la runda asta, sa spuna cat de curand.

[•bent_larsen]

Cu NlogN mai mult de 60 de pct nu se putea lua ? Eu credeam ca intra sigur in timp.

[•andrei.12]

Solutia comisiei de complexitate O(NlogN) ia tot 60 de puncte. Solutia oficiala a problemei are complexitate O(N).

[•elfus]

Buna ziua , as fi interesat de rezolvarea oficiala O(N). Se va posta in viitor un articol oficial cu solutia comisiei? Multumesc anticipat.

[•MciprianM]

Aici zice Filip Buruiana ca probabil se va scrie un articol http://infoarena.ro/forum/index.php?topic=5100.msg42955#msg42955.
Ca sa intelegi mai bine solutia in O(n), iti recomand sa citesti: http://infoarena.ro/problema/deque din arhiva educationala

[•vladtarniceru]

am si eu o intrebare: rezolvarea cu deque e buna si intra la limita nu? (adica eu am luat prima data 90, apoi am retrimis aceeasi sursa si am luat 100) 

[•Florian]

Depinde de implementare. Mie mi-a intrat in cca 0.4 sec. Oricum, rezolvarea corecta e cu deque.

[•PlayLikeNeverB4]

Nu e la limita deloc.

[•maritim]

Ok ... nu inteleg. Imi poate explica cineva ce este gresit la rezolvarea mea va rog ?

Cod:

int solve(void)
{
	Deckmin[1] = A[1]; //vectorul unde se pastreaza max
	Deckmax[1] = A[1]; //vectorul unde se pastreaza min
	int c = 1;
	Pmin[1] = 1; //vectorul unde editez lungimile secventei pentru deque min
	Pmax[1] = 1; //vectorul unde editez lungimile secventei pentru deque max
	for(int i=2;i<=N;i++)
	{
		Backmin ++;
		while(Backmin>=Frontmin && Deckmin[--Backmin] > A[i]);
		Deckmin[++Backmin] = A[i];
		Pmin[Backmin] = ++c;
		Backmax ++;
		while(Backmax>=Frontmax && Deckmax[--Backmax] < A[i]);
		Deckmax[++Backmax] = A[i];
		Pmax[Backmax] = c;
		if(Deckmax[Frontmax]-Deckmin[Frontmin]>K)
		{
			if(Frontmin == Backmin)
			{
				while(Deckmax[++Frontmax]-Deckmin[Frontmin]>K);
				c -= Pmax[Frontmax];
			}
			else
			{
				while(Deckmax[Frontmax]-Deckmin[++Frontmin]>K);
				c -= Pmin[Frontmin];
			}
			c ++;
		}
		if(MAX<c)
			MAX = c;
	}
	return 0;
}

L.E. : ... ulterior mi-am dat seama ca incercarea mea de rezolvare este utopica. Distantele dintre secvente se calculeaza altfel, deque-ul e bun .

[•danalex97]

Un sfat ... Faceti deque fara STL la probleme de acest gen.

[•ctlin04]

Va rog uitativa cineva pe sursa mea si ajutatima sa vad ce imi scapa, pe toate testele mele merge bine insa evaluatorul imi da numai 10 puncte, restul incorect  
Cod:

Cod:

Program secvdist;
type tip1=record
             v,p:longint;
             end;
     tip=array [0..1000000] of tip1;
 var a:array [0..1000000] of longint;
    b1:array [1..1 shl 17] of char;
    min,max:tip;
    i,j,n,k,l,c1,c2,co1,co2,sol:longint;
    fi,fo:text;
procedure introdu(var b:tip; x:longint; op:byte);
begin
 if op=1 then begin
               if x<b[co1].v then begin inc(co1); b[co1].v:=x; end
                else begin
                      while (co1>=c1) and (x>=b[co1].v) do dec(co1);
                       inc(co1); b[co1].v:=x;
                      end;
                b[co1].p:=i;
                end
 else begin
         if x>b[co2].v then begin inc(co2); b[co2].v:=x; end
                else begin
                      while (co2>=c2) and (x<=b[co2].v) do dec(co2);
                       inc(co2); b[co2].v:=x;
                      end;
                b[co2].p:=i;
                end;
end;
procedure schimba;
 begin
  if i-l>sol then sol:=i-l;
   while max[c1].v-min[c2].v>k do
    if max[c1].p<min[c2].p then inc(c1) else inc(c2);
  if max[c1].p<min[c2].p then l:=max[c1].p else l:=min[c2].p;
end;
begin
 assign(fi,'secvdist.in');
  assign(fo,'secvdist.out');
 settextbuf(fi,b1);
 reset(fi); rewrite(fo); readln(fi,n,k);
  for i:=1 to n do read(fi,a[ i ]);
   l:=1; c1:=1; c2:=1; co1:=1; co2:=1; min[c1].v:=a[1]; max[c1].v:=a[1]; min[1].p:=1; max[1].p:=1;
  for i:=2 to n do begin
                   introdu(max,a[ i ] ,1);
                    introdu(min,a[ i ] ,0);
                   if max[c1].v-min[c2].v>k then schimba;
                   end;
    if i-l+1>sol then sol:=i-l+1;
   write(fo,sol);
 close(fo);
end.

[•danalex97]

Am facut destul de recent problema , dar mi se pare ca e un detaliu nesemnificativ ce gresesti tu. Incearca sa "reimplementezi". Daca nu iti iese trimite-mi un pm si iti dau sursa mea daca iti e de folos. ( lucrez in C++ dar sursa e fara stl )
 
PS: Vezi ca iti trebuie 2 deque. Succes  .

[•ctlin04]

Defapt eu tin 2 dequuri unul este min, iar celalalt e max, dar mi se pare ca as putea gresi cind reactualizez solutia in procedura schimba, dequul trebue sa fie bun, problema e ca nu gasesc nici un test care sa-mi dea un rezultat gresit, ms pentru raspuns  
As fi recunoscator daca totusi mi-ai trimite sursa la adresa [email protected], ms anticipat 

[•idomiralin]

As avea si eu o nelamurire:

Nu inteleg de ce iau TLE pe testul 9, desi am facut solutia optima cu 2 deque-uri fara stl. Am facut inainte si cu stl si iau TLE pe testul 10.
Daca stie cineva care ar putea fi problema, as fi recunoscator.

[•wefgef]

Am modificat limita de timp, ar trebui sa intre acum.

[•idomiralin]

A intrat acuma. Mersi wefgef!