Обсуждение @ 1332. Джинн-бомбардировки @ Timus Online Judge

How solve this problem with N <= 1000?

Послано Matov Dmitry 19 июн 2006 11:43

Does anybody know an algorithm with lower than O(N^3) complexity?

Just read HybridTheory's subject about it

Послано Alexey 19 июн 2006 15:50

Re: Just read HybridTheory's subject about it

Послано Matov Dmitry 19 июн 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.

Послано Alexey 19 июн 2006 18:36

Re: How solve this problem with N <= 1000?

Послано Aybek Bukabayev 19 июн 2006 20:32

Re: How solve this problem with N <= 1000?

Послано Burunduk1 20 июн 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?

Послано Matov Dmitry 20 июн 2006 13:42

Thank you a lot. I got AC.

Обсуждение задачи 1332. Джинн-бомбардировки