infoarena

Aici puteţi discuta despre problema Descompuneri (http://infoarena.ro/problema/desc).

in enunt nu se specifica nici o restrictie pt descompuneri de genu :
pt n=36
descompunerea 1 * 36
si de aici am putea face 1*1*1*1*1*1*1...*1*1*1*36
presupun ca e o gresala, nu ?

Nu se specifica 1*36.. se specifica doar 36... Termenii sirului trebuie sa fie >1

se foloseste ciurul lui erathostene ?

http://info.devnet.ro/articole.php?page=art&art=78&artpage=5
O fi chiar asa de greu e sa citeste cate un articol-doua pe luna??

Am citit solutia oficiala.

Nu inteleg cum se poate construi matricea respectiva in O(D^2 log D) [sau O(D^2)] daca fiecare divizor al lui N il inmultesc cu fiecare si daca rezultatul este tot un divizor al lui N atunci am de actualizat D numere. Mie mi se pare ca O(D^3)...Am inteles eu gresit sau se poate optimiza?  :|

Daca rezultatul este un divizor al lui N ai de actualizat o singura pozitie in matrice. (Sa zicem ca ai inmultit cu divizorul i si ai obtinut divizorul j .. vei actualiza doar A [ i ] [ j ]  - adaugi aici valoarea din A [ i - 1 ] [ j / i ] )

Nu stiu ce se intampla cu solutia mea. Initial am implementat cautarea binara, dar am avut 7 TLE. Bun, apoi am facut cautarea aia liniara care se reia de la pasul precedent, la fel. Sunt destul de sigur ca am N^2... Am rulat si fara reconstituirea solutiei, e putin mai bine in ideea ca prind 4 teste. Parcurg matricea invers. Credeti ca daca as pune divizorii in ordine inversa si as parcurge normal ar merge mai rpd? Sugestii, va rog :)

Eu nu am citit problema, insa si pe mine m-au plesnit la alte probleme niste TLE atunci cand incercam sa parcurg o matrice pe coloane(inversand indicii) !

http://infoarena.ro/12-ponturi-pentru-programatorii-CC
Citeste pontul 3 !

Aici nu parcurg chiar invers, liniile le parcurg normal, coloanele le parcurg invers. Oricum, la problema asta imi lua cam mult scoaterea divizorilor lui n :P.... acum incerc sa fac in O(sqrt(n)). Voi cum ati scos...? Ca eu fac ceva mai ciobanesc ce implica si o sortare la urma :D

Daca un numar n se divide cu a, inseamna ca exista un numar b astfel incat a*b=n. Evident, cel putin unul din cele doua numere, a sau b, este <= cu sqrt(n). Astfel, trebuie doar sa afli toate numerele a intre 1 si sqrt(n) cu proprietatea ca n se divide cu a, ceilalti divizori fiind de forma n/a.

Cred ca trebuie marit putin timpul de executie.  :-'  Incercati sa implementati problema sau trimiteti orice sursa care a luat 100.  Eu am implementat-o si apoi am trimis o sursa de 100 ca sa vad dupa aceea unde am de optimizat si am constatat ca o sursa printre ultimele trimise care lua 100 acum ia doar 90.   :aha:
 

Ai dreptate. Am crescut limita la 0.5s.

Cred ca testele la problema asta nu sunt prea bune (si nici solutia).
Numarul cu cei mai multi divizori mai mic decat 10^12 este 963761198400, care are 6720 de divizori. Cam toate sursele isi declara limita sub acest numar. De asemenea, asa nu cred ca mai intra in memorie solutia cu O(D^2) memorie (si din cate vad toate sursele sunt pe aceasta solutie).