How to solve it in O(N)
Hi everybody!
I solved this problem, but my algo is O(n log n) and it works 0.14 seconds.
Idea of my algorithm is to find two vectors witch sum is not greater than L and change them on their sum. It it possible to prove that such two vectors exists if there are more than two vectors in set. Do this procedure while we can find such two vectors.
But many people solved it much better... I want to know this solution.
Re: How to solve it in O(N)
Consider that for any vectors a,b,c, |a|,|b|,|c| <= L exists integers u, v, w, |u|,|v|,|w|=1, |ua+vb+wc|<=L
Re: How to solve it in O(N)
Your algo should be O(n) ;)
I don't quite understand how write it with complexity of O(n log n)
Re: How to solve it in O(N)
It is not right: what are u, v, w for
a = (5,0)
b = (0,0)
c = (0,5)???
L = 5, of course
Re: How to solve it in O(N)
Many people above have solved this problem, but they didn't express their thought well.
The key is this:
if there are AT LEAST 3 vectors in the set with module not exceeed L,
we can ALWAYS choose 2 of them and, with choosing the direction, make the module of their sum not exceed L.
Thus, we can reduce the amount of vectors by this until there are only TWO.
At last, for any two vectors which has the module not longer than L,
we can make the module of their sum not exceed L*sqrt(2).
And that's all the key.
What's left is to find a way to programme.
Maybe it will help you, maybe not for my poor English.
Re: How to solve it in O(N)
Thank you for well-expressed idea. It really helps to understand the idea of solution to the problem.
Re: How to solve it in O(N)
Yep =)
Re: How to solve it in O(N)
2 Victor Barinov (TNU): complexity of my solution is not O(NlogN), but even O(N^2)! And it's AC 0.015 sec. Just use the same heuristics as in disjoint sets.
Re: How to solve it in O(N)
Edited by author 04.07.2009 18:52
Edited by author 04.07.2009 18:56
Re: How to solve it in O(N)
Can somebody, please, prove the idea described by 198808xc?
P.S. I've solved this problem using lot of cheating (brute force+random sort+heuristic) and would like to know, what is right solution.
P.P.S. To prove it we should just realize the fact, that there is always 2 vectors, such, that angle between them is >=120 degrees. So their sum is <=L.
Edited by author 14.07.2009 19:24
Re: How to solve it in O(N)
If you only two vectors, you're out of luck of getting |X+Y| and |X-Y| <= L when angle between them is more than 60 degrees (so together with their sum/diff they form an equilateral triangle). Now if you have 3 vectors, these 3 vectors and their reflections form a lotus (or a hexagon) which covers everything, so there will always be a pair with |X+Y| or |X-Y| <= L. When you're down to just 2 vectors, the worst situation is 90 degree angle which yields sqrt(2)*L.
