542 Lsort

[•DITzoneC]

Aici puteţi discuta despre problema Lsort.

[•marcelcodrea]

Limita de timp pare foarte stransa pentru problema, pana si solutia lui Mugurel ia TLE pe 7 teste.
Exista vreo rezolvare mai eficienta decat O(N^2) sau secretul sta in optimizari marunte ?

[•pauldb]

E ok O(N^2), mie mi-a intrat lejer. Incearca sa nu folosesti prea multa memorie.

[•Florian]

Exact aceeasi problema o am si eu. Iau 55 de puncte, cu TLE pe restul testelor. Rezolvarea este O(N^2) ca timp, iar ca memorie folosesc doua matrice de 1000 x 1000. Ce ar trebui sa mai optimizez ca sa intre in timp ? 

[•marcelcodrea]

Sursa care ia 100 p foloseste 3 matrice cu 2 linii si N coloane. Operatiile se fac pe biti.
Daca vrei da-mi un PM si ti-o trimit. Oricum mie mi se par niste optimizari nerelevante pentru un concurs si cred ca importanta e ideea de dinamica din spatele problemei. La nationala luai 100 si daca implementai cu 2 matrice de 1000 x 1000.