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 1422. Fireflies

What complexity is accepteble for this problem? (+)
Posted by Victor Barinov (TNU) 4 Apr 2006 03:44
I have written 2 algos already:
first - O( n^3 ) - TLE #9
second - O( n^2 * log( n^2 ) ) - also TLE #9

I don't know what to do... Please help!!!
Re: What complexity is accepteble for this problem? (+)
Posted by Pio (Pio@mail.by) 4 Apr 2006 16:03
it's very strange, because I solved this problem and my AC-algo O(n^2*log(n)) has time - 0.859.
Re: What complexity is accepteble for this problem? (+)
Posted by currently unnamed... 4 Apr 2006 18:31
Some of O(n^2logn) programs got AC and some not.
But O(n^2) programs will be quicker of course.
How to do it in O( n^2 ) ??? (-)
Posted by Victor Barinov (TNU) 5 Apr 2006 01:11
Re: What complexity is accepteble for this problem? (+)
Posted by KAV 12 Apr 2006 18:25
I wrote O(N^2*logN), but still TLE 9 :(
AC (+)
Posted by Victor Barinov (TNU) 12 Apr 2006 20:26
I got AC with algo O ( n^2 * log( n ) )
I avoided all operations with fractional numbers.
I want to know more efficient algos. Especially solutions of  Walrus  and  currently unnamed...  Can you tell about it?

Thanks Bye.

P.S. Maybe we'll discus this problem - everyone discribes his algo with his optimizations?

P.P.S sorry for BAD English :-)

Edited by author 12.04.2006 20:27
Re: AC (+)
Posted by Walrus 13 May 2006 13:32
Try to avoid all division operations.
It could speed up your program :)
Re: AC (+)
Posted by Alexander Prudaev 3 Sep 2006 21:37
Victor Barinov (TNU) wrote 12 April 2006 20:26
I got AC with algo O ( n^2 * log( n ) )
I avoided all operations with fractional numbers.
I want to know more efficient algos. Especially solutions of  Walrus  and  currently unnamed...  Can you tell about it?

Thanks Bye.

P.S. Maybe we'll discus this problem - everyone discribes his algo with his optimizations?

you first. How do it in O(N^2 * log(N)) ?

Edited by author 03.09.2006 21:37
Re: AC (+)
Posted by iezahel 5 Sep 2006 14:47
Hi, my algo is O(N^2lg(N)) using stl map, but it runs very slowly. I am actually doing this: for every point, I move this point at position (0,0,0) and then sort the other points by the angle they have with Ox, Oy and Oz(I think this angles are called directory cosine) (I am using NO float point arithmetic to do this)... could someone help me, where could I optimize more ???
Re: AC (+)
Posted by Marko Tintor 8 Oct 2006 20:52
It can be done in O(n^2) with hash table instead of sorting.
Re: AC (+)
Posted by Lomir 2 Feb 2007 06:22
For future solvers. DO NOT USE MAPS HERE.
O(n^2 * ln n) get AC in 1.5 with vector normalisation and full floating points arithmetic.