3
$\begingroup$

The problem is defined as:

Given a set of $N$ points $(x_1, x_2, x_3, \ldots, x_n)$ and $L$ the fixed length of a segment.

Find the number of maximum points which you can cover with a segment line of length $L$.

Ranges

$1 \leq N \leq 100 000$

$1 \leq L \leq 10^{10}$

$0 \leq x_i \leq 10^{10}$

I call sub-optimal ranges, ranges which are in the form $[x_n,x_n+L]$. The optimal range is the one which contains the maximum points of all ranges.

I've tried to consider the problem using that algorithm (pseudo-code):

Let be S, the set which contains all the N points.
Let be R, the set which contains ranges.
Let be maxPoints, the number of maximum points that we can have (set it to 0).
For all points p I have in my set S
     Store in R the range $[p, p+L]$
For all ranges r I have in my set R
     nPoints = 0
     For all points p I have in my set S
         If the point p is in the range r, then increment nPoints
     maxPoints = maximum value between maxPoints and nPoints
Display maxPoints

I think that the complexity of this algorithm is $O(N^{2})$, is there a way to make it faster? And is it really correct (in the sense, that it solves all cases of this problem).

$\endgroup$
  • $\begingroup$ 1. I don't understand the problem specification. What about the value of $x_1,\dots$ -- are they given? Why is that on a separate line from "Given..."? 2. Code is off-topic here. Please use pseudocode, not a real programming language (like Python), and make sure the pseudocode is written at a conceptual level. We want something concise that focuses on the idea, not implementation details. So, describe the main idea in English before showing any pseudocode. 3. What's your question? This is a question-and-answer site: we insist that you ask a specific, answerable question. $\endgroup$ – D.W. Apr 4 '15 at 23:55
  • $\begingroup$ I'll edit to answer you expectations. $\endgroup$ – Raito Apr 4 '15 at 23:56
  • $\begingroup$ @D.W. Is it better now? $\endgroup$ – Raito Apr 5 '15 at 0:04
  • $\begingroup$ Thank you, that's heading in the right direction. But I'm not entirely clear on the pseudocode yet. Line 1 mentions "all sub-optimal ranges"; what is a sub-optimal range? Line 2 refers to a set S, without defining what S is -- what's S? Please define all notation before use, and use notation consistently. Also, see if you can ask a more well-defined question. "Is my approach good?" is subjective. On the other hand, "Can you solve this problem in $o(n^2)$ time? Can you solve it in $O(\log n)$ time?" would be fine. Lastly, I suggest you try to compute the running time of your algorithm. $\endgroup$ – D.W. Apr 5 '15 at 0:10
  • $\begingroup$ Here's a first hint: compute the running time of your algorithm, as a function of $n$. A second hint, to help you find a better algorithm: build a balanced binary tree. Spend some time pondering that hint, and see what you can come up with. $\endgroup$ – D.W. Apr 5 '15 at 0:13
1
$\begingroup$

You haven't explained how to implement how many there is point in the range r. You do this operation N times, so unless it takes $O(1)$, your algorithm won't be $O(N)$.

There is a simple algorithm that runs in time $O(N\log N)$:

  1. Sort the input points.
  2. Go over all the points in order, maintaining a data structure keeping track of the points at distance at most $L$ from the current point.

You can implement each iteration of the second step in amortized $O(\log N)$ using a balanced binary search tree.

Can we do it asymptotically faster? In many restriction computation model, the problem of element uniqueness (given a list of integers, determine whether they are all unique) requires $\Omega(N\log N)$ operations. Since element uniqueness reduces to your problem, in these models your problem requires $\Omega(N\log N)$, so the algorithm broadly outlined above is asymptotically optimal.

Of course, in practice you might benefit from algorithms which are more sensitive to the input distributions. In fact, assuming the answer is $M$, the algorithm outlined above runs in time $O(N\log M)$. If you expect $M$ to be very small, it might be worthwhile to use a list rather than a balanced binary search tree.

$\endgroup$
  • $\begingroup$ I've edited to explain more what is this operation and fixed the complexity. $\endgroup$ – Raito Apr 5 '15 at 13:47
  • $\begingroup$ I didn't understand that each iteration of the second step can be made in amortized $O(\log N)$ using a balanced binary search tree. So, we don't go over all the points, but we do kind of binary search? $\endgroup$ – Raito Apr 5 '15 at 14:23
  • $\begingroup$ I'll let you fill in the details. Each point is added once and removed once from the tree, and this is why the total running time is $O(N\log N)$. $\endgroup$ – Yuval Filmus Apr 5 '15 at 21:27
  • $\begingroup$ EDIT: Nevermind. Stupid question. $\endgroup$ – Raito Apr 5 '15 at 21:43
  • $\begingroup$ I'm having issue to understand how you keep track of the points at distance at most $L$ from the current point, without using a AVL tree. I'm trying to see if it can be done just with plain lists (even if the complexity isn't good, I want to understand first). Could you show me some pseudocode to illustrate how it would be done? $\endgroup$ – Raito Apr 5 '15 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.