|
|
back to boardSorry for my impudence but my AC program has O(N^2*ln(N)) and takes 234 ms with GREAT optimization (and with memory too). Your solutions (by velocity characteristics) has O(N^2) difficulty and O(N) memory.
First, we should watch all differences between elements (O(N^2)) and then find greatest sequence (O(ln(N))). In process of finding such sequence we should know all differences (O(N^2) memory).
Am I mistaken in something? Could you tell me, in what destination I should think to get quick solution. I have thought up O(N^2) algo! Now time is 0.109 ms. But it eats O(N^2) memory:(
Edited by author 28.07.2016 15:40 I only store N minimal differences, initially a1-a0,a2-a1,...,a(n-1)-a(n-2) (given a0..a(n-1) sorted sequence). Store it in heap (pyramide), get top (minimal) difference and change it from a(j)-a(i) to a(j+1)-a(i) and push down to the heap's bottom. My N*N*logN runs in 0.125 |
|
|
