Discussion @ 1147. Shaping Regions @ Timus Online Judge

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.

Posted by Yu YuanMing 2 Jul 2004 22:00

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.

Posted by Chan-Min Kim 11 Jun 2005 17:00

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 :)

Posted by Yu Yuanming 11 Jun 2005 19:14

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

Posted by Yu Yuanming 16 Jun 2005 07:41

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

Posted by Yu Yuanming 16 Jun 2005 07:42

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

Discussion of Problem 1147. Shaping Regions