Place n points at the maximum minimum distance
Given the distance d
(from 0
to d
) and 2 points s
and e
between which points cannot be placed (placing points on s
and e
is equal to a penalty, it is not allowed to place points between them). In the meantime, there is no need to know about it. ”
Place the n
points so that the distance between each point is as large as possible (distribute them as evenly as possible).
Display the minimum distance between two points.
Graphical representation, place the n
points on the black line (this is a 1-dimensional line) so that the maximum possible distance between every two points (absolute error is allowed up to 10^(-4)
).
Examples:
- d = 7, n = 2, s = 6, e = 7, yield: 7.0000000000
- d = 5, n = 3, s = 5, e = 5, output: 2.5000000006
- d = 3, n = 3, s = 0, e = 1, output: 1.5000000007
- d = 9, n = 10, s = 5, e = 6, output: 1.0000000001
- d = 6, n = 2, s = 1, e = 6, yield: 6.0000000000
- d = 5, n = 3, s = 4, e = 5, output: 2.5000000006
My approach:
I tried looking at the intervals separately, distributing the points (ideal distribution, lengthOfInterval
/ n
) on the first and second interval (from 0
to s
and e
to d
) and checking all distributions that sum up to n
, I would keep the pair (distribution, largest minimum distance) and select the pair with the greatest minimum distance. I don't know how to work with tolerance 10^(-4)
(how does this part even look in the code?) And I'm not sure if my approach is correct. Every suggestion is appreciated.
I am stuck on this question: /
source to share
You can use binary search for the possible sizes of the gaps between the dots (from 0
to d
) to converge towards the maximum size of the minimum size.
To determine the viability of any given whitespace size, you basically try to place dots to the left and right and see if the gap in the middle is large enough:
- Determine how many dots can be placed to the left of
s
(thiss/gapSize + 1
). - Determine how many points you need to place to the right of
e
(which isn - points on left
). - Determine how far each side will go.
- Check if the points on the right in the gap match
[e, d]
and if there is a differencegap size
between each side.
The code for this is: (note that I was working with the number of spaces instead of dots, which is only 1 less than the number of dots as this leads to simpler code)
double high = d, low = 0, epsilon = 0.000001;
while (low + epsilon < high)
{
double mid = (low + high)/2;
int gapsOnLeft = (int)(s/mid); // gaps = points - 1
if (gapsOnLeft + 1 > n)
gapsOnLeft = n - 1;
int gapsOnRight = n - gapsOnLeft - 2; // will be -1 when there no point on the right
double leftOffset = mid*gapsOnLeft;
// can be > d with no point on the right, which makes the below check work correctly
double rightOffset = d - mid*gapsOnRight;
if (leftOffset + mid <= rightOffset && rightOffset >= e)
low = mid;
else
high = mid;
}
System.out.println(low);
Complexity of time O(log d)
.
The problem with your approach is that it is difficult to figure out how large the gaps between the points are, so you won't know how many points have to go on either side of (s, e)
to end up with an optimal solution and deal correctly with both cases where s
both are e
really close. to a friend and when they are far from each other.
source to share
Binary search
It is very easy to find the number of points you can place if you set the minimum separation distance b / w with any pair l
.
If l = d, then no more than two points can be placed.
..
...
....
so just do a binary search on l.
The rough implementation is as follows.
low,high=0.00001,d
while(high-low>eps):
m = (low+high)/2
if((no. of points placed s.t any pair is at most m units away) >=n):
low=mid
else:
high=mid
source to share
TL; The DR: . Your approach doesn't always work (and you don't do it as fast as you could), you see a 3rd bullet point for the one that works (and uses 10 ^ (-4) data).
-
If it
[s, e]
is small and well placed, then the optimum is simply distributed evenly over the entire segment, the best value nowd/(n-1)
. But you will need to check that none of your elements are betweens
ande
. -
Your approach works if
s
ande
"far enough".
You can do this faster than what you seem to be suggesting by looking at the best splitting between two segments in time O(1)
: if you put elements n1
( 1<=n1<=n-1
) on the left you want to maximize min(s/(n1-1), (d-e)/(n-n1-1))
(one of these values is possibly +infinity
, and the other - not). The maximum of this function is obtained for s/(x-1) = (d-e)/(n-x-1)
, just calculate the corresponding value for x
, and its floor or ceiling is the best value for n1
. The resulting distance best = min(s/(n1-1), (d-e)/(n-n1-1))
Then you put points n1
on the left, starting at 0
, separated by the distance best
and to the n-n1
right, starting at d
, going left, dividing best
.
If the distance between the last point on the left and the first on the right is less than the better, then you have a problem, this approach does not work.
- The tricky case is that the two previous approaches failed: the hole is small and not well positioned. Then there are probably many ways to fix the problem. One is to use binary search to find the optimal space between two consecutive points. Given a candidate space,
sp
try to distribute the points on the line starting at 0, at intervalssp
as much as you can while staying below s. Do the same on the right, staying above e and above(last on the left + sp)
. If you have successfully placed at least n points, then it issp
too low. Otherwise, it is too big.
So you can use binary search to find the optimal one sp
like this: start at sp is possible in [max (s, de) / (n-1), d / (n-1)]. At each step, take the average of mid
your possible segment [x, y]
. Check if the real optimum is higher or lower mid
. According to your case, find the best option in [mid, y]
or [x, mid]
. Stop iff y-x < 10^(-4)
.
The two previous cases will also be found using this method, so you don't need to implement them unless you need the exact optimal value when possible (i.e. the first two cases).
source to share
It's pretty tricky except for the simple case (there is no period in the space):
double dMin = d / (n - 1.0);
if (Math.ceil(e / dMin - 1) * dMin <= s)
return dMin;
Continue with the edges, placing one point on one side and the rest of the points on the other:
dMin = Math.min((d - e) / (n - 2.0), e); // one point at 0
double dm = Math.min(s / (n - 2.0), d - s); // one point at d
if (dm > dMin) // 2nd configuration was better
dMin = dm;
And finally, for two or more points on both sides:
// left : right = (x - 1) : (n - x - 1)
// left * n - left * x - left = right * x - right
// x * (left + right) = left * n - left + right
// x = (left * n - left + right) / (left + right) = (left * n) / (left + right) - 1
int x = s * n / (d - e + s) - 1;
if (x < 2)
x = 2;
for (int y = x; y <= x + 2 && y < n - 1; y++) {
double dLeft = s / (y - 1.0);
double dRight = (d - e) / (n - y - 1.0);
dm = Math.min(dLeft, dRight);
if (dm > e - s) { // dm bigger than gap
if (dLeft > dRight)
dLeft = e / ((double) y);
else
dRight = (d - s) / ((double) n - y);
dm = Math.min(dLeft, dRight);
}
if (dm > dMin)
dMin = dm;
}
It would be O (1) space and time, but I'm not 100% positive if all cases are verified. Please let me know if this works. Checked for all test cases . The above works for n >= 2
if n is 2 it will be caught by the first check.
source to share