782 Densitate

[•wefgef]

Aici puteti discuta despre problema Densitate.

[•catalin93]

Am si eu o problema cu sursa mea... ideea e ca TLE nu da ... numerele sunt pana la 500.000 ceea ce inseamna ca intra in int... si totusi nu imi da...  as avea si eu nevoie de un sfat pentru ca am incercat teste gasite pe net cand am cautat teorema numerelor prime
"Number of primes < 10^n.
0, 4, 25, 168, 1229, 9592, 78498,"
exact asa imi da... unde gresesc?

Cod:

...

[•crus]

cred ca trebuie sa afisezi x [ b ] - x [ a-1 ] ...

[•catalin93]

de ce? ca fii atent... am editat foru asa...

Cod:

for(i=1;i<=q;++i)
	{
		scanf("%d%d",&a,&b);
		s = x[b] - x[a];
		if((c[a] == false) || (c[b] == false) )
			s++;
		printf("%d\n",s);
		
	}

ca am citit pe celalat topic ca in cazul in care capetele sunt prime se iau si ele in calcul ... si acum am dat toate testele care mi-au trecut prin cap si da bine... unde gresesc?

cred ca trebuie sa afisezi x [ b ] - x [ a-1 ] ...

daca reusesti sa-mi explici de ce rationamentu meu lua 0 puncte si ceea ce mi-ai zis tu sa schimb ia 100 iti ridic statuie
 

[edit] nu posta de 2 ori consecutiv, foloseste butonul de editare a mesajului

[•crus]

pai, ideea e urmatoarea...tu retii in x[ i ] cate numere prime ai intre 1 si i deci intre a si b ai un numar de numere prime egal cu
x [ b ] care este numarul de prime in intervalul [1,b] din care scazi x [ a-1 ], care este egal cu numarul de numere prime din intervalul [1,a-1], si raman numerele prime din intervalul [a,b]. Tu facand operatia x [ b ] - x [ a ] calculai numarul de numere prime din intervalul [a+1,b]

[•catalin93]

aaa...  e logic mersi mult inca odata pentru ajutor
apropo... acu eu ar trebui sa scot sursa din primul mesaj sau cu ajutorul a ceea ce ai zis tu toti o sa ia 100 nu?

[•c_e_manu]

cica o sa ai statuie cristi 

sa-mi zici cand e dezvaluirea

[•crus]

 

[•Tamasionutz]

Ciurul lui Eratosthenes nu e suficient de rapid ?? Am incercat cu asta si mi-au iesit 40 puncte, la restul mi-a dat "Time limit exceeded" ... Am vrut si eu sa fac asa, adica sa calculez pentru fiecare numar cate nr prime se afla intre 1 si el, dar am considerat-o mai inceata decat ciurul. E mai inceata sau mai rapida (inca nu am inteles bine complexitatile si optimizarile, dar invat pe parcurs ) ....

[•c_e_manu]

cand ai nevoie de mai multe numere, ciurul isi face foarte bine treaba... doar ca aici nu ai nevoie doar de ciur...trebuie sa-ti mai dai seama de ceva... dar numerele prime tot cu ciurul le calculezi... daca nu te descurci poti sa te uiti in articolul cu solutii

[•Mishu91]

daca nu te descurci poti sa te uiti in articolul cu solutii

Unde se poate gasi? 

[•c_e_manu]

nu e tot, dar http://infoarena.ro/algoritmiada-2009/runda-1/solutii

[•SilverMoon]

cand ai nevoie de mai multe numere, ciurul isi face foarte bine treaba... doar ca aici nu ai nevoie doar de ciur...trebuie sa-ti mai dai seama de ceva... dar numerele prime tot cu ciurul le calculezi... daca nu te descurci poti sa te uiti in articolul cu solutii

Da, adica faci preprocesare si trimiti sursa cu un vector v[500000], unde v[i ] = nr de nr prime pana la i. Cu asta ai rezolvat problema in O(n). Bad point: sursa cam mare (multi KB), s-ar putea sa n-o primeasca.

[•c_e_manu]

Da, adica faci preprocesare si trimiti sursa cu un vector v[500000], unde v[i ] = nr de nr prime pana la i. Cu asta ai rezolvat problema in O(n). Bad point: sursa cam mare (multi KB), s-ar putea sa n-o primeasca.

rezolvarea dn articol se refera la o preprcesare a vectorului inainte de a intra in ciclu de q teste, nu o preprocesare a intregului vector, folosind un alt program.

[•Florian]

Eu am facut problema generand intr-un vector numerele prime prin intermediul ciurului. Apoi am aplicat doua cautari binare in vectorul de numere prime, pt fiecare pereche (a,b). A intrat fara probleme. 

[•catalin93]

ideea cea mai simpla dupa parerea mea e cea pe care am discutat-o la inceput... faci un vector de rezultate (int) in care pui nr de numere prime pana la nr curent... chiar daca numarul este compus
spre ex : i = 10
v[10] = 4
i= 11
v[11] = 5
e simplu si dupa calculezi cate numere sunt in interval ca daca faci doar ciur testele sunt date smecher.. te pune sa calculezi intre 1 si 11 si dupa 1 si 12.. 1 si 13.. si tot asa... si asa da TLE  

[•Florian]

ideea cea mai simpla dupa parerea mea e cea pe care am discutat-o la inceput... faci un vector de rezultate (int) in care pui nr de numere prime pana la nr curent... chiar daca numarul este compus
spre ex : i = 10
v[10] = 4
i= 11
v[11] = 5
e simplu si dupa calculezi cate numere sunt in interval ca daca faci doar ciur testele sunt date smecher.. te pune sa calculezi intre 1 si 11 si dupa 1 si 12.. 1 si 13.. si tot asa... si asa da TLE  

Nu ai inteles ce am spus. Eu nu fac ciur pt fiecare pereche de numere (a,b) ci fac ciur doar odata, la inceput, intre 1 si n. Iar intr-un vector retin numerele prime intre 1 si n. Acesta este vectorul pe care fac apoi cautarile binare. 

[•Pepelea_Flaviu]

merge si fara cautari binare

[•Florian]

merge si fara cautari binare

Nu zice nimeni ca nu merge si fara. Eu doar am prezentat o alta metoda de rezolvare. 

[•gabor_oliviu1991]

am si eu o intrebare...eu in concurs am facut o rezolvare mai putin ortodoxa si am preprocesat toate nr prime si leam bagat intr-un vector. ideea e ca sursa mea depaseae 256 de kb si nu ma lasa sa o trimit...bine, am mai scos din numere si pana la urma am scos 50 de puncte (TLE, nu am facut cautarea binara ). va rog sa imi ziceti daka as putea "inghesui" toate numerele prime...care sunt aprox. 47 000 fara ca sursa mea sa depaseasca 256 kb....merci anticipat

[•Pepelea_Flaviu]

dc nu ai calculat in acelasi program cu ciuru numerele prime.....ti s-a parut mai simplu sa bagi direct in sursa?

[•gabor_oliviu1991]

pe moment am avut si ideea de ciur dar am zis ca incerc cu preprocesare ca sigur scot maxim...da nu o fost asa...ce sa zic...dupa concurs am rezolvat-o cu ciur si acum ma intreb daka merge si cu preprocesare

[•c_e_manu]

sunt 41539 de nr prime... cel putin eu asa am gasit ... probabil s-a gandit si la faptul ca va economisi un timp destul de mare, daca nu mai foloseste ciurul...

[•Mishu91]

Avand in vedere ca N < 5 * 10⁵, iar complexitatea ciurului e aproape O(N) (v. postul de pe blog), formarea ciurului nu mananca foarte mult timp

[•gabor_oliviu1991]

am inteles ca ciurul e cea mai buna idee dar ce intreb eu e cu totul altceva... pot pune 41 si cate zice manu de nr prime in vector fara ca sursa mea sa depaseasca 256 de kbs?

P.S: am vazut ca ciurul nu manca mult timp ca pana la urma am luat 100 pe ea. dar cu preprocesare pot scoate 100?