
November 1st, 2011, 11:53 PM
#1
Lowest distance
Hi.
I've got the problem to solve:
We've got n numbers. The "distance" between two numbers d(A,B) is the amount of prime numbers (got after factorization) of the number A*B/GCD(A,B)^2. We have to output (for every given numbers) the lowest position of number whose distance between the actual number is lowest. Of course the position of actual number can't be the same as the position of number to output (but the values can).
For example:
We've got six numbers:
1,2,3,4,5,6
And the correct output is: 2,1,1,2,1,2.
I've already written the algorithm working in O(n^2)  which compares every numbers, counts the minimal distance and position and output it. But unfortunately that's too slow. I need someting working in O(nlogn). Could somebody help me with this problem?
Thanks and sorry for my bad English.

November 3rd, 2011, 08:54 AM
#2
Re: Lowest distance
Originally Posted by boost
I've already written the algorithm working in O(n^2)  which compares every numbers, counts the minimal distance and position and output it. But unfortunately that's too slow. I need someting working in O(nlogn). Could somebody help me with this problem?
How do you know an algorithm that is faster than O(n^2) exists?
The way you presented the problem, you should calculate n^2 (seemingly unrelated) distances. How do you intend to do that faster than O(n^2)?
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky

November 3rd, 2011, 10:43 AM
#3
Re: Lowest distance
Simply... it's written that n<=100000, so it will take hours to count it with an algorithm running in O(n^2).
Originally it's said that "distance" between A and B is an amount of operations required to get number A from B. By operation we understand multiplication or factorization by some prime number.

November 6th, 2011, 05:01 AM
#4
Re: Lowest distance
Originally Posted by boost
Simply... it's written that n<=100000, so it will take hours to count it with an algorithm running in O(n^2).
I don't understand. How do you go from O(n^2) and n <= 100000 to hours? They are unrelated. Maybe your implementation is just inefficient.
Originally Posted by boost
Originally it's said that "distance" between A and B is an amount of operations required to get number A from B. By operation we understand multiplication or factorization by some prime number.
Perhaps a faster approach can be found by first factorizing each number into primes, then ordering them somehow, such that it becomes easy to find the closest number.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky

November 7th, 2011, 11:38 AM
#5
Re: Lowest distance
Originally Posted by boost
I've already written the algorithm working in O(n^2)  which compares every numbers, counts the minimal distance and position and output it. But unfortunately that's too slow. I need someting working in O(nlogn). Could somebody help me with this problem?
So you fully factorize all A*B/GCD(A,B)^2 numbers?
GCD calculation is fairly cheap but factorization is more expensive. Now since you're looking for the minimum distance it should be possible to quit a factorization as soon as it's established that the distance it represents is going to be longer than the current minumum distance. It won't change the O(N^2) complexity but it will reduce calculations substantially. Maybe it's enought to render your algorithm feasible for large N.
What's the background for this problem? Is there reason to assume that there's some deep number theoretical result available that could be used to lower the complexity of the algorithm you've come up with?
Last edited by nuzzle; November 8th, 2011 at 12:04 AM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
