355 Namlei

[•bogdan2412]

Aici puteţi discuta despre problema Namlei.

[•astronomy]

Se poate cumva mai bine de O(N*K^3+C*logN*K^3) ? Unde C este numarul total de operatii. Nu mai stiu ce optimizari sa incerc, si tot nu imi intra pe 2 teste. Daca asta e complexitatea, imi da cineva o idee de optimizare va rog?

[•bogdan2412]

Nu prea cred ca se poate Am aceeasi complexitate si eu..
Daca faci inmultire de matrici incearca sa schimbi ordinea forurilor . Am observat o crestere mare in performanta ( de la 1.0 sec la 0.8 ) ... oricum merge si fara optimizari dubioase .

Deocamdata sunt 2 surse care merg in timp

[•gcosmin]

cam stransa limita...
eu ca sa intre in timp am scos modulo-u la 997...
am precalculat intr-un vector de 1 000 000

Cod:

 a[ i ] = i % 997 

(dar nici asta nu l-am facut cu modulo ci incremental)

Cod:

 { a[ i ] = a[i - 1] + 1; a[i] -= (a[i] >= 997) ? 997 : 0; } 

si cand fac inmultirea pe matrice ma folosesc de vectorul asta ca sa fac modulo...

[•sima_cotizo]

Daca faci inmultire de matrici incearca sa schimbi ordinea forurilor . Am observat o crestere mare in performanta ( de la 1.0 sec la 0.8 ) ... oricum merge si fara optimizari dubioase .

Luam si eu 80 si faceam forurile (i,j,k) ... le-am schimbat ordinea in (k,i,j) si am luat 100... sunt curios de ce, practic de fiecare data o matirce e parcursa in ordinea "normala", una e parcursa "normal" pe linii si alta pe coloane... deci in cache cam tot aia ar fi, nu ?

[•danalex97]

Limita mi se pare destul de stransa. O sursa ce defineste matricea ca structura ( struct in C++ ) si are complexitatea O(N*K^3+operatii*log N*K^3) ia doar 50p.