|
|
back to boardMy algorithm in worst case is O(n^3).But it seem to be impossible to appear. So the average time is O(n^2),and I got AC in 0.046sec. If someone has a better solution, would you please write it down? Thanks. Re: My algorithm in worst case is O(n^3).But it seem to be impossible to appear. So the average time is O(n^2),and I got AC in 0.046sec. I don`t no how u did.. but maybe you did it in exact O(n^2). I got AC too. and it seemed to be O(n^3), but it was O(n^2) always. I think it is such a good prob... I have known a better way :) Use 2D interval tree, just O(nlog2n) Re: I have known a better way :) Posted by kcm1700 13 Jun 2005 15:58 That`s good... O(n lg^2 n) algorithm using binary tree.... hmm.. it was tough work for me to make program for it.;( My opinion I think O(nlgn) is enough, not O(nlg^2n)... And the most important thing is that O(nlogn) algo can save a lot of memory...also, it is faster...:) My opinion 2D interval tree uses O(nlg^2)... Now I have a better way, it uses 1D interval tree I think O(nlgn) is enough, not O(nlg^2n)... And the most important thing is that O(nlogn) algo can save a lot of memory...also, it is faster...:) Edited by author 16.06.2005 07:45 |
|
|