|
Titlul: 355 Namlei Scris de: Bogdan-Cristian Tataroiu din Martie 17, 2007, 12:20:43 Aici puteţi discuta despre problema Namlei (http://infoarena.ro/problema/namlei).
Titlul: Răspuns: 355 Namlei Scris de: Airinei Adrian din Martie 18, 2007, 21:09:58 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?
Titlul: Răspuns: 355 Namlei Scris de: Bogdan-Cristian Tataroiu din Martie 19, 2007, 10:02:12 Nu prea cred ca se poate :) Am aceeasi complexitate si eu..
Daca faci inmultire de matrici incearca sa schimbi ordinea forurilor :P . 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 :) Titlul: Răspuns: 355 Namlei Scris de: Gheorghe Cosmin din Martie 19, 2007, 12:37:05 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 Cod: { a[ i ] = a[i - 1] + 1; a[i] -= (a[i] >= 997) ? 997 : 0; } Titlul: Răspuns: 355 Namlei Scris de: Sima Cotizo din Iulie 30, 2008, 21:50:45 Daca faci inmultire de matrici incearca sa schimbi ordinea forurilor :P . 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 ? Titlul: Răspuns: 355 Namlei Scris de: Dan H Alexandru din Octombrie 10, 2014, 20:28:08 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.
|