4
$\begingroup$

The problem is defined as:

Given $N$ points on an infinite line, find the least number of line segments of length $L$ that cover all points (including endpoints) after changing one point.

That means that if I have the points $P = 1,10,15,28$ , $L = 10$ , 3 line segments are needed , changes will occur that the point $i$ will move to position $X$ , after each change , get the number of line segments needed.

Example:

$P = 1,5,11,21,25$ , $L = 6$ , Changes are

$$ 1 , 29 $$

$$ 2,36 $$

after change #1 : $P = 5,11,21,25,29$ , number of line segments needed is 3

after change #2 : $P = 11,21,25,29,36$ , number of line segments needed is 4

What would be the best approach to do this? , Given that number of points can be $50,000$ and the number of changes can be $50,000$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Point indexes are just a way of naming them. What matters in the algorithm is only their positions.

The first thing you need is the management of your points. You need a structure that sorts them according to position when given the initial list of positions (ascending or descending order, it does not matter). This structure must allow you to remove a point, and add it somewhere else at low cost to keep the list sorted when you operate a change. You will find many such structures in any course on data structures and algorithms.

Then you need a structure for representing segments that will group your points into a collection of buckets of points covered by the same segment. This collection of buckets is a covering. The construction of an optimal covering is easy. You can show easily that, given any covering, you can always replace the lefmost segment by a segment that start rightward at the leftmost point, to get another covering. From that you can show by induction that you can get an optimal covering by placing a segment so that its leftmost end is on the leftmost point, and then reapeat recursively starting at the lefftmost point not yet covered.

A symetric proof shows that you can alternatively start from the right. Actually, combining the two proofs, you can show that you can always chose your next segment either rightward from the leftmost point or leftward from the rightmost point, computing from both end towards the middle until the two computations "meet" somewhere in the middle (you can choose that "somewhere"). In all versions of the algorithm, the last segment added may cover points that are already covered (though it can be avoided for the unidirectionnal versions of the algorithm - it does not matter anyway).

We assume first you build your covering from the left only.

Each change is composed of two "half-changes", removal of the point from its former position followed by addition of the point in the sorting structure at its new position. After performing them, you have recompute your segments. You try to limit the new computation to an incremental change to the previous one, and you must have kept your collection of buckets. You start at the leftmost segment affected by the leftmost "half-change" (either addition or removal), and you recompute segments until you find a segment that is the same as for the previous covering (which ends a first incremental update), and you do some accounting to know whether and how that changes the number of segments. If the rightmost "half-change" has been passed in the process, you are also done for that change. Else you do the same for that second half-change, still recomputing from left to right as in the first computation of a minimal covering of segments.

The algorithm could alternatively compute coverings from right to left. It is the same in reversal.

Starting from both ends may make the algorithm a bit more complicated (you have to work out the changes for yourself), On the other hand it may improve it somewhat as it can avoid having to recompute all segments up to the right end in pathological cases of incremental recomputation: you are sure an incremental update will not exceed half the collection of points ( actually it is not exactly half, depending on how the "meeting point in the middle" is chosen). But I guess it is a minor improvement. You might be even more subtle in choosing the "middle place" and in possibly changing it when you move your points, to account for changes of the algorithm behavior according to point density. But this is marginal and requires a bit of analysis.

Note: the above works for addition and removal of points, without necessarily keeping a constant number of points, provided it is allowed by the structures that I left unspecified and up to your own choice. The fact that the number of points remains constant in the statement of your problem could be an indication that a specific method is expected that would make use of that fact.

P.S. What do you mean by best approach ? What is the criterion.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 1 - What's the time complexity for your algorithm? 2 - I meant that the speed of the algorithm has to be less than $N$, because the number of points and changes is pretty large. $\endgroup$
    – mohammed essam
    Jun 3, 2013 at 16:07
  • $\begingroup$ The initial algorithm for the first set of positions is linear in the number of points for the part that does the covering. However, you have also the cost of the initial sort and the cost of linearly scanning the set of positions, and that depends on the structure you have chosen for sorting. Each change has the cost of one insertion and one deletion in the sorting structure, and a cost similar to the initial cost for scanning part of the sorted list and updating the covering. On average, it is very unlikely that you have much to update, depending on segment length and point density. $\endgroup$
    – babou
    Jun 4, 2013 at 10:24
  • $\begingroup$ There is also the buckets dtructure, but that should be easy. $\endgroup$
    – babou
    Jun 4, 2013 at 10:26
  • $\begingroup$ but that would be $\Theta(N)$ per update, the worst case is that $N = 50,000$ , and $50,000$ updates, which will definitely get a TLE. $\endgroup$
    – mohammed essam
    Jun 4, 2013 at 15:16
  • $\begingroup$ First, as I said above, you can cut in half : 25000 rather than 50000. Second, unless you have pathological cases, the covering update for a change will terminate rather fast. I would guess actually that the mean complexity of covering update is a constant (I am not counting the cost of updating the sorting structure for the removal and addition) but I have not done the analysis. Now, it that really bothers you, it might be possible to improve the worst bound by using a dynamic programming structure for coverings. But I do not have time to explore that right now. (please, expand "TLE") $\endgroup$
    – babou
    Jun 5, 2013 at 8:37
0
$\begingroup$

You can cunstruct a max heap and a min heap. With the bottom up approach you can cunstruct it in O(n) time. For each point also keep maintaining a HashMap which stores its index. Since these are points they should not overlap (as I take them to)

This Can be done in O(n) time.

Now for each update query

All you have to do is get the element at index i from the HashMap. then delete it from both the heaps. O(log n). Also delete the key corresponding to this element from the HashMap. Now add the value (newVal, i) to the HashMap. O(1) for both delete and add. Now add the new point to both the heaps. O(log n).

And your answer is always the ceil of (top of max heap-top of min heap)/Length of segment. O(1)

Improve this answer
$\endgroup$
6
  • $\begingroup$ the problem is that $\Theta(N)$ time is relatively large , because there are up to 50,000 updates, and up to 50,000 points, that would be 2,500,000 , which is definitely a TLE approach. $\endgroup$
    – mohammed essam
    Jun 4, 2013 at 15:14
  • $\begingroup$ No O(n) is just for the cunstruction step. i.e. for 50,000 points. from there on each query takes just O(log n) time. that will get you AC rather than TLE. $\endgroup$
    – Alice
    Jun 4, 2013 at 16:30
  • $\begingroup$ WHat is the meaning of AC and TLE ? Thanks $\endgroup$
    – babou
    Jun 5, 2013 at 20:37
  • 2
    $\begingroup$ @babou TLE stands for Time Limit Exceeded and AC stands for Accepted. They are terms used in most of the online coding engines such as spoj, codechef, topcoder etc. $\endgroup$
    – Alice
    Jun 5, 2013 at 22:36
  • $\begingroup$ @Alice : Your answer is wrong, as ceil(maxtop - mintop) / L isn't always the right solution, if there are 2 points , one at x = 0 and another at x = 1000 and L = 5 , you would output 200 , while it only needs 2 segments... , The problem to me is to get the number of segments , not to sort the points , the lines don't have to be contagious. $\endgroup$
    – mohammed essam
    Jun 6, 2013 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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