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 1130. Nikifor's Walk

How to solve it in O(N)
Posted by Victor Barinov (TNU) 20 Jun 2008 21:58
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)
Posted by [SPbSU ITMO] WiNGeR 21 Jun 2008 10:51
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)
Posted by AS1_PML#30 27 Jun 2008 14:20
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)
Posted by Vedernikoff Sergey 1 Jul 2008 22:36
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)
Posted by 198808xc 13 Aug 2008 07:13
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)
Posted by Denis Koshman 27 Aug 2008 07:10
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)
Posted by VNTU Vitaly(Traning) 4 Jul 2009 18:52

Edited by author 04.07.2009 18:52

Edited by author 04.07.2009 18:56
Re: How to solve it in O(N)
Posted by Oracle[Lviv NU] 14 Jul 2009 19:07
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)
Posted by Harkonnen 11 Aug 2022 04:22
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.