399 Sum2

[•danielp]

Aici puteţi discuta despre problema Sum2.

[•Florian]

Cred k nu ar strica inlocuirea lui "are" ku "ale" din enunt,,,desi pe mine nu ma deranjeaza

Apropos, ce complexitate ar trebui sa aiba un algoritm de 100?

[•devilkind]

o(n), desi e posibil sa intre si n log n.

[•Florian]

Aha...mersi.. .o sa incep implementarea, din moment ce-mi dau seama despre ce este vb...

[•gabitzish1]

Am facut prima data un program cu complexitate patratica pt a afla suma... luam primele 2 teste si TLE pt restul... am incercat dupa aceea o complexitate liniara, iau 70p, WA pe primele 2 si ultimul test...... ce ar putea fi gresit? 


Later edit: am rezolvat primele doua teste.. mai e ultimul... e vre'un caz special?

[•programator]

Nu pricep un lucru: la problema asta, subsir inseamna subsecventa [adik sir de elemente care apar pe pozitii consecutive in sirul initial ]  ?  Daca nu, ar putea cineva sa-mi explice exemplul?

[•gabitzish1]

Se da un sir de numere intregi. Se cauta un subsir cu lungimea cuprinsa intre L si U format din elemente consecutive ale sirului initial cu suma elementelor maxima.

Subsir nu inseamna sir format din elemente care apar pe pozitii consecutive in sirul initial => nu e subsecventa (asta in cazul general), dar avand in vedere ca in enunt se precizeaza ca este format din elemente consecutive, in cazul problemei Sum2 subsirul e o subsecventa. In exemplul dat, subsirul este format din ultimele 3 elemente.

Ps: poate sa imi spuna cineva c greseli pot avea astfel incat cade ultimul test.. iau doar 90 puncte si Wa pe ultimul  .. help.. pls

[•ssergiuss]

Ceva mi se pare dubios la testele acestei probleme. Am rezolvat problema punand conditia ca secventa de suma maxima sa fie de lungime maxim u (fara sa verific daca are lungimea mai mare decat l) si am luat 100  .

[•c_e_manu]

Poate sa-mi dea cineva o idee de rezolvare cu deque? Nu de alta, dar are link de la arhiva educationala de la problema deque 

Multumesc!

[•Mishu91]

Ideea e sa iti faci niste sume partiale, iar pentru a afla subsecventa de suma maxima care se termina pe pozitia i, tre' sa afli cea mai mica suma partiala dintre pozitiile i-L si i-U. Si pentru a determina acea suma ai nevoie de deque. Sper ca ai inteles 

[•Marius]

Poate sa-mi dea cineva o idee de rezolvare cu deque? Nu de alta, dar are link de la arhiva educationala de la problema deque 

Multumesc!

De ce nu citește nimeni articolele? Ai aici rezolvarea problemei sum2. Și dacă nu pricepi deque, mai cauți prin articole.

[•popoiu.george]

Am citit articolul cu probleme cu subsecvente si nu prea inteleg cum sa folosesc dequeul aici. Pt fiecare i trebuie sa cautam subsecventa de suma maxima intre i-U si i-L, dar nu trebuie sa parcurgem cu un j pentru a face asta?

Daca nu e asa, imi spuneti si mie va rog cum sa fac? 

[•pauldb]

Ideea e sa folosesti deque-ul pentru a evita parcurgerea intervalului respectiv. Gandeste-te cum l-ai putea aplica pe vectorul de sume partiale.

[•popoiu.george]

Am gasit ceva asemanator cu problema asta in topicul de la problema Subsecventa3, dar tot nu ma prind.  

Un hint referitor la ce ar trebui sa tin in Deque?

[•andunhill]

Cred ca trebuie inbunatatite testele. Cu sursa de 100 pt pe testul

Cod:

2 1 2
-20 -10 

imi da gresit.

[•zizou_ady]

mi-ar putea da si mie cnv testele va rog:D.

[•Mishu91]

Testele oficiale - nicio sansa.
Dar iti poti face o sursa brute-force de complexitate O(N^2) si un generator de teste, cu ajutorul carora sa iti verifici programul de complexitate optima 

[•rares192]

Eu tot pun intr-un deque pana ajung la dimensiunea U si dupa aceea tot extrag primu element din deque si inserez la final mai departe si fac sp[Q.back() ] - sp[Q.front() - 1] , unde sp e vectorul de sume partiale..si iau 50 de puncte. Cred ca la un moment dat o sa aiba deque-ul doar dimensiunea U ..cum pot face fara sa parcurg deque-ul ?

[•pauldb]

Poate te ajuta acest articol sa intelegi cum ar trebui folosit deque-ul. Trebuie facut cam acelasi lucru cu ce e descris la problemele vila sau sir, doar ca pe vectorul de sume partiale.

[•rares192]

Multumesc mult !  Am luat 100.

[•scipianus]

Poate cineva sa imi dea un indiciu macar despre cum ar trebui abordata problema(cum trebuie folosit deque cu sumele partiale)   ?
Am incercat ceva variante de genul queue cu left si right,din care variantele mai dubioase care imi picau niste exemple au luat 50pct,iar varianta care trece exemplele mele si care imi pare mai in regula ia 10pct , dar bineinteles observ ca niciuna dintre ele nu poate gasi suma maxima in anumite cazuri 

Asta ar fi o sursa de 10pct(care bineinteles nici nu foloseste practic sumele partiale decat la o banala initializare)  

Cod:

        ifstream fin("sum2.in");
	fin>>n>>L>>U;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	fin.close();
	suma=sum[L];
	size=L;
	left=1;
	right=L;
	sol=sum[L];
	while(right<n && left<=right)
	{
		if(size<U)
		{
			done=false;
			while(a[right+1]>=0 && size<U && right<n)
			{
				done=true;
				right++;
				size++;
				suma=suma+a[right];
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
			if(done==false)
			{
				right++;
				size++;
				suma=suma+a[right];
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
		}
		if(size>L)
		{
			done=false;
			while(a[left]<=0 && size>L)
			{
				done=true;
				size--;
				suma=suma-a[left];
				left++;
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
			if(done==false)
			{
				size--;
				suma=suma-a[left];
				left++;
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
		}
	}
	ofstream fout("sum2.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;

Poate cineva sa ma ajute cu vreo idee?  

[•valentin.harsan]

stie cineva unde gresesc? am folosit deque cu sume partiale dar iau doar 50 

Cod:

#include<iostream>
#include<fstream>
#define N 100004

using namespace std;

ifstream in("sum2.in");
ofstream out("sum2.out");

int n,l,U,smax=-1000000,d[N],p=1,u,y[N];
short x[N];

inline void swap(int &a, int & b) {
	int t=a;
	a=b;
	b=t;
}

inline void add(const int &a) {
	d[++u]=a;
}

inline void stanga(int i) {
	if(p<=u && i - d[p]>= U)
		++p;
}

inline void dreapta() {
	while(u!=p && y[d[u]] <= y[d[u-1]]) {
		swap(d[u],d[u-1]);
		--u;
	}
}

void so() {
	int i;
	
	for(i=0;i<U-l-1;++i) {
		add(i);
		dreapta();
	}
	
	for(i=U;i<=n;++i) {
		stanga(i);
		add(i-l-1);
		dreapta();
		if(y[i]-y[d[p]]>smax)
			smax=y[i]-y[d[p]];
	}
	add(i-l-1);
	dreapta();
	if(y[i-1]-y[d[p]]>smax)
		smax=y[i-1]-y[d[p]];
}

int main() {
	int i;
	in >> n >> l >> U;
	
	for(i=1;i<=n;++i) {
		in >> x[i];
		y[i]=x[i] + y[i-1];
	}
	
	so();
	
	out << smax;
	
	return 0;
}

[•PlayLikeNeverB4]

Personal, consider ca implementarea ta a Deque-ului e mult prea complicata. Iti sugerez sa faci ca in sursa oficiala de la problema din Arhiva educationala.

Si in legatura cu programul tau, el pica niste teste banale.

Cod:

2 1 2
1000 -1000

Cod:

3 1 3
1000 1000 -1000

Cod:

9 2 3
100 100 -1000 10 -15 100 100 -15 1

Cred ca el cauta doar secvente de lungime U, in loc de [L,U].

[•maritim]

Deque-ul acela pastreaza doar minimul pe intervalul [i + L - U,i], pentru fiecare i de la [0,N-L] (pozitiile negative nu se iau in seama). Cred ca asa ar fi o descriere mai usoara a problemei . Dupa care cu minimul respectiv si i + L cred ca stiti ce sa faceti.
Spor la treaba !

[•valentin.harsan]

@PlayLikeNeverB4. ai luat acum 100 cu sursa mea modificata?

am corectat niste greseli si acum iau testele tale, da tot 50 iau  .
la al treilea trebuie sa dea 200, nu?