1116 Subsir1000

[•pauldb]

Aici puteti discuta despre problema Subsir1000.

[•VisuianMihai]

Interesanta problema... Dar nu imi dau seama ce caz particular poate avea.

[•VisuianMihai]

numarul 1 si alt numar se considera prime intre ele??

[•mathboy]

Se precizeaza in enunt ca testele contin doar numere din intervalul [2, N], asadar nu trebuie luat in calcul numarul 1.

[•PlayLikeNeverB4]

O idee pentru 100 ? Dinamica clasica nu e prea eficienta

[•klamathix]

Folosesti un vector len[ i ] = lungimea maxima a unui sir care se termina intr-un numar care il are ca factor prim pe i.
Cand calculezi best[]-ul pentru un numar iterezi prin toti factorii sai primi si iti alegi len[]-ul maxim. 

[•PlayLikeNeverB4]

Fac factorii primi cu ciur. Pentru fiecare numar iterez prin factorii primi, determin len-ul maxim (Max), apoi fac update la len-urile tuturor factorilor primi =Max +1 si best[i]=Max+1. La final determin maximul dintre best-uri. Unde pot optimiza?

[•jupanubv92]

Aproape aşa am facut şi eu , şi am luat 100 de p. Diferenţa dintre soluţia mea şi a ta constă in faptul ca tu pentru un numar X il descompui in factori primi cu ciur, şi eu il descompun in sqrt(x). Deci cu N*sqrt(N) iei 100 de p. Pentru fiecare numar, îi aflu factorii primi în sqrt(N) şi aflu maximul din len-ul ala al tău, apoi dupa ce afli maximul poti sa faci update la len-uri, dar vezi sa faci update doar la len-urile care sunt factori primi pentru elementul curent.  Cam aşa ar trebui sa iei 100.

[•PlayLikeNeverB4]

Mi-a iesit Mersi de pont.

Ma seaca deja ciurul asta. De la ce numere in sus are rost sa-l folosesc? Ori de cate ori ma decid sa-l folosesc, parca mai mult incetineste

[•SpiderMan]

Cand N e mai mare sa zicem de 10 000 000, cam asa ceva .

[•dushmi]

Fac factorii primi cu ciur. Pentru fiecare numar iterez prin factorii primi, determin len-ul maxim (Max), apoi fac update la len-urile tuturor factorilor primi =Max +1 si best[i]=Max+1. La final determin maximul dintre best-uri. Unde pot optimiza?

Pai sa stii ca si solutia asta era buna. Eu asa am facut-o si am luat 100... Incearca sa tii factorii primi intr-o lista pentru fiecare numar si update-ul la liste sa il faci in acelasi timp cu ciurul. Gandeste-te ca, in algoritmul de ciur, cand marchezi toti multiplii unui numar prim acestia vor fi divizibili cu numar prim curent...

Cand N e mai mare sa zicem de 10 000 000, cam asa ceva .

Mhm ... Eu in general folosesc ciur tot timpul cand am destula memorie si nu am avut niciodata probleme... Nu cred ca e vreo problema in care sa mearga mai repede fara ciur, dar poate ma insel

[•SpiderMan]

Uneori, ia mai mult ciurul decat algoritmul in sine ..... depinde de situatie.

[•popoiu.george]

Eu fac mai intai ciur pentru a determina numerele prime din invervalul [2, N] si nu reusesc sa ies din 10p si 30p cu WA, respectiv TLE.

Daca pentru a determina divizorii primi a lui A parcurg [2, sqrt(A)] si verific daca numarul este divizor si prim iau 10p cu WA, iar daca parcurg tot intervalul [2, A] ca sa vad care sunt primi si sunt si divizori iau 30p cu TLE.

Mi se pare o problema banala si nu stiu ce gresesc.

PS. Cum se pot afla factorii primi ai lui A in sqrt(A) ? Un link sau niste explicatii ar fi de mare ajutor.

[•klamathix]

Pai nu e mare filozofie. Treaba e ca un numar poate avea cel mult un factor prim > sqrt(x), ceea ce e destul de evident.
Iei la rand toate numerele de la 2 la sqrt(A) si daca gasesti un divizor, ai gasit un divizor prim si imparti numarul la el cat de mult poti.
La final iti ramane A fie 1, daca avea toti factorii <= sqrt(A) , fie iti ramane in A exact ultimul factor prim. Probabil ca tu il ratezi pe asta.