infoarena

Aici puteti discuta despre problema Subsir1000 (http://infoarena.ro/problema/subsir1000).

Interesanta problema... Dar nu imi dau seama ce caz particular poate avea. ](*,)

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

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

O idee pentru 100 ? Dinamica clasica nu e prea eficienta :)

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. 

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?

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.

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

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

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


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

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

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.

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.