345 Nasa

[•bogdan2412]

Aici puteţi discuta despre problema Nasa.

[•cos_min]

Am rezolvare O(b*sqrt(b)) iau 20 pcte, restu tle.

Ce complexitate este necesara ??

le. am reusit sa modific si am ajuns pe undeva la O(b), dar nu imi intra in timp totusi ca nu stiu cum sa tin minte daca un element a mai fost sau nu folosit in alg meu.

[•azotlichid]

B poate lua valori cam mari (2*10^9 e cam mult, nu?). Tine cont de faptul ca diferenta dintre B si A este acceptabila pentru a procesa numai valorile din acel interval.

[•Florian]

Eu nu prea imi dau seama cu pot sa optimizez ! Iau doar 20 de puncte.  Un hint ceva...?

[•DITzoneC]

Gandeste-te cum se poate adapta ciurul lui Erathostene la aceasta problema.

[•Florian]

Gandeste-te cum se poate adapta ciurul lui Erathostene la aceasta problema.

Cred k am gasit raspunsul! Multumesc! Insa totusi am o nelamurire...pentru asta nu ar trebui un vector de vreo 100 de milioane....? [nu kred k suporta evaluatorul....]   


[Later edit] Cred k merge dak aloc dinamic. [faza ku *a=new int[100mil] ]

[•astronomy]

Nu conteaza daca aloci dinamic sau static, tot intra in calcul la memorie. Vezi si articolul de pe site despre ciur, acolo ar trebui sa gasesti niste indicatii

[•Florian]

Nu conteaza daca aloci dinamic sau static, tot intra in calcul la memorie.

Asa e! In mod normal asa ar trebui sa se intample. Insa, la problema "2sec" din arhiva, am trimis o sursa cu alocare statica, in care am declarat un vector de tip int de 1 milion si primeam KBS pe toate testele [ceea ce nu e normal, cred], iar apoi am trimis aceeasi sursa, insa am declarat dinamic vectorul [cu new] si ..spre surprinderea mea luasem 100. Nu inteleg de ce s-a intamplat asta...

Vezi si articolul de pe site despre ciur, acolo ar trebui sa gasesti niste indicatii

 Nu prea inteleg limbajul ala java...imi dau seama k trebuie sa ma folosesc de forma de restrangere a memoriei folosite [faza cu :un singur bit in locul unui char intreg, aplicat vectorului boolean]! Deci, se restrang dimensiunile vectorului, insa nu inteleg pe ce elemente trebuie sa lucrez cu 1 si 0, pt k din moment ce am restrans dimensiunile trebuie sa restrang si asta... Este clar k in loc de 8 biti pt un singur element folosesc 8 biti pt 8 elemente [sau ceva de genu asta]...insa cum traduc asta in c++? 

[•astronomy]

Reprezentarea binara a unui octet e formata dintr-un sir de 8 biti de 0 sau 1. Cum ai spus si tu acum ai nevoie doar de un bit pentru fiecare numar, deci de 8 biti (un octet) pentru fiecare 8 numere. De acum e clar, numerele 0, 1 .. 7 vor corespunde primului octet, numerele 8, 9, 10.. 15 celui de-al doilea octet etc. In general un numar X va corespunde celui de-al (X/8)-lea octet si va fi pe bitul (X%8) al acestui octet.

[•Florian]

Am facut asemenea ciurului lui eratostene. Am lucrat pe biti, deci ma incadrez in memorie. Cand gasesc un numar i, care e patrat perfect, ii marchez multiplii care se afla pe intervalul [a,b]. La sfarsit, nu fac decat sa numar cate valori de 0 am. Ideea e ca am complexitate cam de O(b*sqrt(b-a)), si iau doar 4 teste..restu tle. Cum as putea sa scot O(b-a)? 

[•bogdan2412]

Numerele patrate perfecte <= B le gasesti in O( sqrt(B) ), iar daca faci ciur, pt fiecare patrat perfect parcurgi un numar din ce in ce mai mic de elemente din intervalul [A, B].. In total parcurgi (B - A) * (1 / (2^2) + 1 / (3^2) + 1 / (4^2) + ... ) elemente care e O(B - A)

[•Florian]

Numerele patrate perfecte <= B le gasesti in O( sqrt(B) ), iar daca faci ciur, pt fiecare patrat perfect parcurgi un numar din ce in ce mai mic de elemente din intervalul [A, B].. In total parcurgi (B - A) * (1 / (2^2) + 1 / (3^2) + 1 / (4^2) + ... ) elemente care e O(B - A)

Am inteles. Eu greseam la gasirea patratelor perfecte...faceam parcurgere + verificare... Acu am reusit sa scot complexitatea ideala, insa iau kill by signal pe vreo 15 teste:| Memorie folosita este int de 100 milioane/32 (cu operatiile pe biti). Sunt aproape sigur ca nu depasesc limitele vreunui vector... Oare care e problema? 

[•wefgef]

Cand lucrezi pe biti e indicat sa folosesti unsigned int, iar in loc de 1 << 31 sa ai ((unsigned)1) << 31.

[•savim]

Problema merge cel mai bine cu 1<<32, si cu unsigned long, daca puneam 1<<31 imi iesea din timp pe ultimele teste.

[•ciprianf]

Am rezolvare in O(sqrt B *(B-A)) si iau 60 de pcte cu TLE. Aveti vreo idee unde gresesc?Lucrez pe char de 8 biti.

Cod:

for(i=2;i<=n;i++){ // n=sqrt(b);
		z=i*i;
		if(z<a)
			if(a%z) x=a/z+1;
			else x=a/z;
		else x=1;
		while((long long)z*x<=b){
			rezolva(z*x);
			x++;
		}
	}

Fctia rezolv marcheaza z*x care apartine int[a,b]

[•wefgef]

Daca stai putin si calculezi, vezi ca e prea mare complexitatea ta pentru 100 de puncte. Ti-a explicat Bogdan mai sus ce trebuie sa faci pentru 100 de puncte.

[•ciprianf]

Am citit postul lui dar nu prea inteleg cum ajunge la complexitate totala finala O(B-A). Adica ia fiecare nr patrat perfect <=B ( O(sqrtB) ) si pt fiecare face ciur => O(sqrtB * (B-A)/(nr patrat perfect)) . Unde gresesc?

[•pauldb]

Cred ca tu ai complexitatea corecta O(B-A), dar nu iti dai seama. Din cauza ca patratele perfecte cresc destul de repede, complexitatea finala este O(B-A), nu O(sqrt(B) * (B-A)).

[•ciprianf]

Da, cred ca ai dreptate...dar atunci dc nu iau 100? Ai vreo idee? Folosesc cumva o operatie costisitoare?

[•pauldb]

Ai putea optimiza codul de mai sus in cateva locuri.

Cod:

z=i*i;
if(z<a)
	if(a%z) x=a/z+1;
	else x=a/z;
else x=1;

Aici operatiile '/' si '%' consuma mult timp. Nu cred ca necesita prea multa ingeniozitate o metoda de a scapa de ele.

Cod:

while((long long)z*x<=b){
	rezolva(z*x);
	x++;
}

Si aici, eu as prefera sa fac adunari decat inmultiri (nu stiu daca se va simti diferenta).
Cat despre functia rezolva nu stiu daca poti imbunatati lucrurile si acolo. Incearca sa eviti '/' si '%' si sa folosesti operatiile pe biti daca e cazul.

[•toni2007]

Da, cred ca ai dreptate...dar atunci dc nu iau 100? Ai vreo idee? Folosesc cumva o operatie costisitoare?

Poti face ciurul doar cu patratele numerelor prime, celelalte numere fiind deja eliminate inainte

[•ciprianf]

Am reusit, multumesc mult amandurora

[•freak93]

Ati putea micsora limita de timp la 0.1 secunde pentru ai forta pe oameni sa gaseasca o solutie mai buna

[•aladin]

Nu stiu de ce primesc Memory limit exceeded pe ultimele 16 teste...Am declarate static 5 variabile int si un vector de 100 milioane tot int.Trb declarate dinamic? poate sa ma ajute cineva?.....Si cat va da pt  1556 100001556? Mie imi da 60792690. Pls HELP!!!ö

[•Florian]

(100 mil * 4 / 1024) kilobytes = prea mult