infoarena

Aici puteţi discuta despre problema Nasa (http://infoarena.ro/problema/nasa).

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.

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. :quagmire:

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

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....]   :-k


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

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

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... :-k


 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++?  #-o

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.

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)?  :-k

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?  :?

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

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

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.

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

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.

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?

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)).

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

Ai putea optimiza codul de mai sus in cateva locuri.


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


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.

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

Am reusit, multumesc mult amandurora :yahoo:

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

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? :-k poate sa ma ajute cineva?.....Si cat va da pt  1556 100001556? Mie imi da 60792690. Pls HELP!!!ö

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

o alta idee??

Salut. Am incercat si eu problema asta si nu inteleg de ce iau killed by signal 11 pe multe teste. Eu fac ciurul pt patratele numerelor prime pana in sqrt(b) si pe urma impart intervalul [a,b] in intervale de maxim 10^6 numere care reunite dau intervalul [a,b](cv de genu: [a,b]=[a,a+10^6-1] reunit cu [a+10^6, a+2*10^6-1] reunit cu... [a+k*10^6,b] si pt fiecare ciur pe un interval mic folosesc un vector de char de dimensiune 2^20 (>10^6) Ma lamureste cineva va rog ce gresesc? Mersi anticipat!

Later edit:Tot ce greseam era o singura linie: poz2=(poz/nr[j]+1)*nr[j];  poz2 putea depasi int.Las comentariul in caz ca mai are cineva vreodata problema asta.

imi puteti spune pls cat spatiu ocupa o variabila de tip bool?    .. pt ca incerc sa folosesc un vector bool v[100 000 000] shi am memory limit exceeded

1 byte (octet). E normal sa iti iasa din memorie.

aha, k ms    mie mi s-a parut ca e un bit 1/8 byte adica

si atunci cam ce ai, ati sugera?

Bitset.

ok ms, imediat ce o sa aflu ce-i aia o sa incerc sa aplic

http://www.cplusplus.com/reference/stl/bitset/

Am scris o sursa in care am respectat indicatiile din comentariile anterioare (pt fiecare nr. prim <sqrt(b) am marcat multipli patratului acestuia din intervalul [a,b]) dar iau 60p cu restul TLE. Am citit despre anumite operatii pe biti dar nu imi dau seama ce operatii si unde sa le folosesc. Daca imi puteti da un mic hint despre aceste operatii,va rog :). Multumesc anticipat! :D

Si eu iau 60p , am facut un ciur cu nr prime si unul in care marchez nr de la A la B. Tot tle. Cine a mai rezolvat problema , va rog , putin ajutor...

Nustiu cum ai facut tu ca nu prea am chef sa ma uit pe sursa ta la ora asta, insa niste indicii pentru a lua 100 cred ca ar fi:
1. Mergi si controleaza doar multipli la patrate de numere prime;
2. Gindestete cum pentru un patrat fixat fie el p sa faci (b-a)/p oparatii pentru a-l prelucra;
3. Cind faci ciurul mergi doar pe numere impare cazul x=2 tratindu-l aparte, defapt aceasta optimizare m-a ajutat si pe mine sa iau 100 ca fara ea ultimul set de teste mergea la limita si e clar ca nu se nimerea ca sa mearga tot setul odata.
Cam asta. SPOR  :)

Mie mi-a intrat lejer cu o metoda neoptimizata, dar care nu folosea STL...Incearca sa faci bitset-ul de mana, ca nu-i mare chestie sa scrii 2 functii inline / macrouri. N-ai nevoie de long long...baga toate variabilele pe uint. Faci chestiile astea si dublezi viteza.

Am incercat ambele , ceva imi scapa  :-'. Daca imi poate da cineva sursa prin PM raman recunoscator. Nu ma prind nicicum.  :fool:

Ti-am trimis PM, dar ma uit ca si sursa ta e buna doar ca ultimul for e prea costisitor, trebue sa numeri numerele pe care le excluzi deodata cind prelucrezi patratele nr prime   :ok:

@Catalin: 10x.  :yahoo: Asta era.
@Steve: Ai dreptate , bitset de mana merge mult mai rapid.  =D&gt;

Buna seara.
Am complexitatea ceruta ,dar iau doar 20 pct cu Killed by signal.
Codul care imi nr numerele cerute:


BB=sqrt(B). vectorul ciur e de tip bitset si are 100 milioane de elemente :)

Vreo sugestie cum pot scapa de Killed By Signal?
Multumesc Anticipat!!!

Ai grija ce bagi in ciur2;in acel while cred ca la un momendat bagi numere mai mari ca si 100 de milioane; m-am uitat si peste ultima sursa trimisa de tine si ai la sfarsit for(int i=A; i<=B; ++i) if ( ciur2[ i ] ) blaala...; acel i depaseste 100 de milioane

Si cum as putea face astfel incat sa nu-mi depaseasca 100 mil?  eu  trebuie sa marchez toti multiplii numarului <=b si oricum trece de 100 milioane la un moment dat ](*,)
Mersi :)