ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1147. Shaping Regions

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