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 1332. Genie Bomber

How solve this problem with N <= 1000?
Posted by Matov Dmitry 19 Jun 2006 11:43
Does anybody know an algorithm with lower than O(N^3) complexity?
Just read HybridTheory's subject about it
Posted by Alexey 19 Jun 2006 15:50
Re: Just read HybridTheory's subject about it
Posted by Matov Dmitry 19 Jun 2006 18:05
I've already read this subject. And I can't imagine where did you find there the algorithm with lower than N^3 complexity.
Sorry, my mistake. I really don't know.
Posted by Alexey 19 Jun 2006 18:36
Re: How solve this problem with N <= 1000?
Posted by Aybek Bukabayev 19 Jun 2006 20:32
Re: How solve this problem with N <= 1000?
Posted by Burunduk1 20 Jun 2006 02:06
O(N^2logN)

Fix one point on the circle. This point becomes the begin of coordinates.
For each other point calculate interval of angles were center can be.
Now that you have intervals on the circle and you have to find
point which is covered by maximum number of intervals.
Re: How solve this problem with N <= 1000?
Posted by Matov Dmitry 20 Jun 2006 13:42
Thank you a lot. I got AC.