014 Secventa

[•amadaeus]

Pai implementezi o rezolvare brute-force (care sigur te conduce la solutia corecta) si faci si un generator de teste. Pentru fiecare test, compari rezultatul obtinut prin brute-force cu rezultatul programului pe care vrei sa il verifici (poti face si un script bash care face chestia asta de 100 de ori, adica genereaza cate un test, ruleaza brute-ul, ruleaza programul tau si compara rezultatele).

[•gabitzish1]

adik programul brut force ar insemna o rezolvare copilareasca (in sensul k luam totul pas cu pas) , presupunand o complexitate mare...

[•Bluedrop_demon]

Dap! 

[•gabitzish1]

o sa trebuiasca sa ma obisnuiesc cu chestii de aastea.... un brut force nu necesita prea mult timp pt rezolvare? /:)

[•Bluedrop_demon]

Se poate intampla si asta, dar de cele mai multe ori nu.

De exemplu un backtracking daca il stii bine il scrii in 10 minute maxim si dupa aia poti sta sa astepti 10-20 minute sa rezolve un test. (In acest timp poti lucra la altceva lasandu-l sa ruleze intr-o alta fereastra). Apoi te uiti ce rezultat a dat si vezi daca poti descoperi o formula sau o dinamica... ceva cu complexitate mai mica.

La fel si la grafuri... daca ti se cere un anumit drum pe 100000 de noduri stii ca trebuie sa gasesti un algoritm foarte rapid, dar pana una alta bagi un Roy-Floyd ca poate apare o relatie 

[•stef2n]

La fel si la grafuri... daca ti se cere un anumit drum pe 100000 de noduri stii ca trebuie sa gasesti un algoritm foarte rapid, dar pana una alta bagi un Roy-Floyd ca poate apare o relatie 

Ai de gand sa astepti un Roy-Floyd pe 100000 de noduri?
P.S. Scuze ca e cam off-topic reply-ul meu.

[•Bluedrop_demon]

Tot off topic scuze: Pai vroiam sa subliniez ca intr-adevar poti sa si astepti mult. Dar daca folosesti brute-force uneori nu ai de ales 

[•nparfene2004]

Iau 90 de puncte la problema... Nu mai stiu ce sa optimizez...

Fac O(n) cu deque... orice element intra in deque o data si iese cel mult o data, deci cam un milion de operatii. De ce atunci TLE la un test mare? Eu credeam ca pe linux fac in 0.18 sec mai mult de 10 milioane de operatii (nu impartiri). Nu?

[•Mishu91]

Incearca sa parsezi citirea

[•nparfene2004]

Scuze, ce inseamna sa parsez citirea? un exemplu?

[•gabor_oliviu1991]

citesti numarul ca sir de caractere, si dupa il transformi in numar propriu-zis.

[•nparfene2004]

Adica

scanf("%s",sir) ;
x = atoi(sir) ;

prin asta s-ar intelege parsare?

[•sima_cotizo]

Da, dar foloseste fgets() in loc de scanf() si poti incerca si sa implementezi atoi() de mana (cred ca e mai rapid).

[•Sorin_Ionut]

Parsarea chiar face difrenta in problema asta (  doar pt cei cu 90p )
Sursa fara parsare http://infoarena.ro/job_detail/288827 (90p)
Sursa cu parsare http://infoarena.ro/job_detail/288886 (100p) detasat 
Uitati-va numai la timpi (parsare face totul , algoritmul este aceelasi (deque))
Pt cine nu stie sa faca parsare , dati-mi un pm si va ajut !
 Multa bafta !

[•Alexa_ioana_14]

Fara parsare obtin 80p. Cu parsare 50 [pe restul WA]
Cam asa arata parsarea pe care o fac:

Cod:

scanf("%d%d\n",&n,&k);
	fgets(s,N,stdin);
	for (int i=0; s[i]&&s[i]!=10; ++i)
	{
		int nr=0;
		int semn=1;
		if (s[i]=='-')
		{
			semn=-1;++i;
		}
		bool ok=false;
		while(s[i]>='0'&&s[i]<='9'&&s[i]&&s[i]!=10)
		{
			nr=nr*10+(s[i]-'0');++i;ok=true;
		}
		if (ok)
		v[++num]=nr*semn;
	}

Imi poate spune cineva unde gresesc? pls

[•narcyyssss]

  ](*,)nu inteleg de ce nu primesc mai mult decat 30 de  puncte am folosit doar  2 structuri repetitive

[•SpiderMan]

Problema se face cu ajutorul unui deque.

[•toni2007]

Problema se face cu ajutorul unui deque.

Se face fara deque.

[•devilkind]

@toni: Esti sigur? Nu stiu ce solutie ai tu dar sunt destul de sigur ca merge si cu deque. De altfel as fi curios cum o faci fara deque.

[•toni2007]

Da, ai dreptate, se pare ca eu o facusem prost. Aseara m-am uitat pe sursa mea (de prin 2008), si in loc sa scot din deque din dreapta, eu cautam binar pozitia si setam capatul din dreapta acolo. Am crezut ca e o coada cu ceva smen.

[•pauldb]

1 - 0 la spiderman.

[•SpiderMan]

1 - 0 la spiderman.

Nu cred ca asta poate fi tratata ca o "batalie", poate ca el initial a vrut sa ajute, intentia conteaza .

[•toni2007]

1 - 0 la spiderman.

Corect

[•valentin.harsan]

af facut o sursa cu deque  COD:

Cod:

#include<iostream>
#include<fstream>
using namespace std;
const int N=500001;
int a,s,smax,dr,st=1,d[N],v[N],n,k;
void stanga (int i) {
	while ((i-d[st]>=k) && (v[d[st]]<v[d[st+1]])) {
		++st;
	}
}

void dreapta (int i) {
	while (st<=dr && v[d[dr]]>=v[i]) {
		--dr;
	}
}

void adauga (int i) {
	d[++dr]=i;
}

ifstream aa("secventa.in");
ofstream ss("secventa.out");
int main () {
	smax=-10000;
	int i;
	aa >> n >> k;
	for (i=1;i<=n;++i) {
		aa >> v[i ];
		stanga(i);
		dreapta(i);
		adauga(i);
		if (i>=k && v[d[st]]>smax) {
			smax=v[d[st]];
			a=i-k+1;
			s=i;
		}
	}
	ss << a << " " << s << " " << smax; 
	return 0;
}

si iau 10 pct. nu inteleg unde am gresit.
ma poate ajuta cineva?

Editat de moderator: foloseste tagurile [ code ] si [ /code ] cand postezi cod. Lasa spatiu intre parantezele drepte si litera i, ca altfel textul ce urmeaza va fi italic.

[•pauldb]

Functia dreapta e problema. Incearca sa citesti mai multe aici.