wu :: forums « wu :: forums - Select points » Welcome, Guest. Please Login or Register. May 25th, 2024, 12:33pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Eigenray, towr, SMQ, Icarus, Grimbal, william wu, ThudnBlunder)    Select points « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Select points  (Read 8295 times)
birbal
Full Member

Gender:
Posts: 250
 Select points   « on: Dec 3rd, 2012, 11:26am » Quote Modify

Given a 1-D space and m point on it. Task is to select n point (n <= m) such that minimum distance between any two of the selected points is maximized.
 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Select points   « Reply #1 on: Dec 3rd, 2012, 1:32pm » Quote Modify

Why say a "1-D space", when you can say a "line" ?

There's a number of ways to approach it; dynamic programming should work.
Or you could do a binary search for the minimal distance, by seeing if for a given distance you can find m points so distanced (which you can do greedily). You can make a first estimate based on the maximum and minimum.

The problem sounds like something I've seen on the forum before..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
wiley
Newbie

Posts: 12
 Re: Select points   « Reply #2 on: Dec 5th, 2012, 9:21am » Quote Modify

With DP, are you thinking of brute-force algo and leveraging DP to avoid re-calculation of sub-problems?
 IP Logged
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #3 on: Dec 11th, 2012, 2:37am » Quote Modify

Trying to solve this using binary search on distance range. The sub problem would be to find n points of the given m points such that minimum distance between any two points is k. How efficiently can we solve this problem ?
 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Select points   « Reply #4 on: Dec 11th, 2012, 9:17am » Quote Modify

on Dec 11th, 2012, 2:37am, birbal wrote:
 Trying to solve this using binary search on distance range. The sub problem would be to find n points of the given m points such that minimum distance between any two points is k. How efficiently can we solve this problem ?
At most linear, since you can just do it greedily. You could to this with binary search as well, in which case it'd be O(n log n)
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #5 on: Dec 11th, 2012, 9:53am » Quote Modify

on Dec 11th, 2012, 9:17am, towr wrote:
 At most linear, since you can just do it greedily. You could to this with binary search as well, in which case it'd be O(n log n)

I see...Start from first point, pick next point at a distance of >= k and repeat this until you find n points.
How can this be done by binary search ?
 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Select points   « Reply #6 on: Dec 11th, 2012, 10:27am » Quote Modify

If your current point is x, you want to find the first element greater than or equal to x+k, so you just search for it with binary search.
Then you have to repeat that m times, to get all m points that are spaced at least k apart.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #7 on: Dec 11th, 2012, 10:47am » Quote Modify

on Dec 11th, 2012, 10:27am, towr wrote:
 If your current point is x, you want to find the first element greater than or equal to x+k, so you just search for it with binary search.   Then you have to repeat that m times, to get all m points that are spaced at least k apart.

Great....so this is O(n log n). Other approach could be (assuming points are sorted) If we are at any point x - keep moving until we find next point at least at x+k. For this approach we will need to go through all m points to find n points which are at least k distant.
 IP Logged

The only thing we have to fear is fear itself!
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #8 on: Dec 13th, 2012, 10:49am » Quote Modify

on Dec 3rd, 2012, 1:32pm, towr wrote:
 Why say a "1-D space", when you can say a "line" ?   There's a number of ways to approach it; dynamic programming should work.   Or you could do a binary search for the minimal distance, by seeing if for a given distance you can find m points so distanced (which you can do greedily). You can make a first estimate based on the maximum and minimum.   The problem sounds like something I've seen on the forum before..

What is the DP solution for this ?
 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Select points   « Reply #9 on: Dec 13th, 2012, 11:45am » Quote Modify

on Dec 13th, 2012, 10:49am, birbal wrote:
 What is the DP solution for this ?

min_spacing([a..c]) = minargb: a<b<c max( min_spacing([a...b]) , min_spacing([b...c])
So you should be able to build a table with partial results for it..
 « Last Edit: Dec 13th, 2012, 11:45am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #10 on: Dec 15th, 2012, 1:00pm » Quote Modify

on Dec 13th, 2012, 11:45am, towr wrote:
 min_spacing([a..c]) = minargb: a

Can you explain in more detail? What is a,b,c and minarg b: ?
 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Select points   « Reply #11 on: Dec 15th, 2012, 1:32pm » Quote Modify

a,b,c are points on the line; or equivalent elements in the (sorted) array that represent the points on the line.
The minarg thing might actually be an error, I think that's actually for finding the minimizing variable, whereas I do want to find the minimum. But I want to find the minimum for varying b. There may be multiple choices for a point b between a and c, and you want to find the one that gives the minimum spacing, which is the maximum of the minimum-spacing over a..b and b..c
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #12 on: Dec 23rd, 2012, 6:10am » Quote Modify

Code:
 int SelectPoints(int *points, int n, int m) { int *maxDist = new int [n]; for(int i=1; i= i-1; j--) { int max = 0; for(int k = j-1; k >= i-2; k--) { int temp = min(points[j] - points[k], maxDist[k]); if(temp > max) { max = temp; } } maxDist[j] = max; } } return maxDist[n-1]; }

Is this code doing the same?
 IP Logged

The only thing we have to fear is fear itself!
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Select points   « Reply #13 on: Dec 23rd, 2012, 4:30pm » Quote Modify

I am not sure what you want to do, but it doesn't look too good.  You never consider point[j] - point[k] for j,k>n
 IP Logged
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #14 on: Dec 23rd, 2012, 8:16pm » Quote Modify

on Dec 23rd, 2012, 4:30pm, Grimbal wrote:
 I am not sure what you want to do, but it doesn't look too good.  You never consider point[j] - point[k] for j,k>n

oops...i think i changed m to n and n to m. Read m as n and n as m, it will make sense..
 IP Logged

The only thing we have to fear is fear itself!
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #15 on: Dec 23rd, 2012, 8:18pm » Quote Modify

Rewriting code with correct m, n meaning.
Code:
 int SelectPoints(int *points, int n, int m)   {   int *maxDist = new int [m];   for(int i=1; i= i-1; j--)   {   int max = 0;   for(int k = j-1; k >= i-2; k--)   {   int temp = min(points[j] - points[k], maxDist[k]);   if(temp > max)   {   max = temp;   }   }   maxDist[j] = max;   }   }   return maxDist[m-1];   }

 IP Logged

The only thing we have to fear is fear itself!
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: Select points   « Reply #16 on: Dec 24th, 2012, 3:59am » Quote Modify

In the meantime I realized you just inverted n and m.  It looks correct to me.

If I understand towr's idea correctly, it is not exactly the same.  Towr splits the problem in 2 halves and searches the optimal point b where to cut it.  You do the same, but on the right side you add a single interval.

Note that the optimal k can be found faster.  As k increases, maxDist[k] increases but point[j]-point[j] decreases.  So you could search the best k with a binary search.  Or maybe you could search sequentially from the optimal k you found for the previous value of j.  It shouldn't be far.
 « Last Edit: Dec 24th, 2012, 3:59am by Grimbal » IP Logged
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #17 on: Dec 24th, 2012, 8:46am » Quote Modify

on Dec 24th, 2012, 3:59am, Grimbal wrote:
 In the meantime I realized you just inverted n and m.  It looks correct to me.   If I understand towr's idea correctly, it is not exactly the same.  Towr splits the problem in 2 halves and searches the optimal point b where to cut it.  You do the same, but on the right side you add a single interval.   Note that the optimal k can be found faster.  As k increases, maxDist[k] increases but point[j]-point[j] decreases.  So you could search the best k with a binary search.  Or maybe you could search sequentially from the optimal k you found for the previous value of j.  It shouldn't be far.

Agreed. I did not pay attention to such optimisation, was just trying to convert idea to code.

 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Select points   « Reply #18 on: Dec 24th, 2012, 10:41am » Quote Modify

I don't think this idea will ever be as efficient as the other approach.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member

Gender:
Posts: 250
 Re: Select points   « Reply #19 on: Dec 24th, 2012, 12:05pm » Quote Modify

on Dec 24th, 2012, 10:41am, towr wrote:
 I don't think this idea will ever be as efficient as the other approach.

Can you convert your idea to code? It will be better undertandable that way
 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Select points   « Reply #20 on: Dec 24th, 2012, 1:06pm » Quote Modify

The following should give the gist of it (but it can probably be improved and there may be bugs.)

Python Code:
 def findMaxMinDistance(points, m):  upperlimit = round((points[-1]-points[0])/(m-1));  lowerlimit = upperlimit;  for i in range(1, len(points)):   lowerlimit = min(lowerlimit, points[i]-points[i-1]);    return findMaxMinDistanceBetween(points, m, lowerlimit, upperlimit);       def findMaxMinDistanceBetween(points, m, lowerlimit, upperlimit):  if lowerlimit >= upperlimit:    return upperlimit    hdist = round((lowerlimit+upperlimit+1)/2);  rdist = findPathMin(points, m, hdist);  if rdist == -1:   return findMaxMinDistanceBetween(points, m, lowerlimit, hdist-1);  else:   return findMaxMinDistanceBetween(points, m, rdist, upperlimit);       def findPathMin(points, m, distance):  prev = points[0];  nextEst = prev + distance;  minDist = points[-1];  m -=1;  for point in points[1:]:   if point >= nextEst:     minDist = min(minDist, point-prev)     m-=1;     prev = point     nextEst = prev + distance;  if m <= 0:   return minDist;  else:   return -1;
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »