|
Yea... not sure of the solution to this.
We have a bounded interval, say [a,b]. The values of a and b are not particularly important. Let's say we are using [0,1000].
Within this bounded interval are some set number of other bounded intervals, which may or may not intersect with other bounded intervals. For example, one possible set of intervals is {[1,100],[2,36],[45,798]}.
From each bounded interval (not counting [0,1000]), you must pick exactly one point so that the least distance between two points is maximized.
What alogorithm would solve this?
EDIT: Attempt at clarification.
Basically he nth triangular number is the number of possible point pairs, each of which has a corresponding distance. For example, say we had [0,1] and [988,1000]. Then we would pick the points 0 and 1000, yielding a distance of 1000, because that choice of points means that the distance between the two closest points is maximized. We could have choise 1 and 988, but the distance would be decreased, so it's not the optimum choice.
Another way of putting it is that you want to choose the points so that the two closest ones are as far apart as possible.
 
|
|
|
I do not understand your english 
|
You need to articulate this more clearly
|
Plz don't tell me this is 9th grade kiddie Math for you Chinese people?
|
I am not sure if it is even a math problem, since the word "algorithm" is used. Other than that, I do not understand the problem.
Might as well type it in Chinese. =P
|
On August 27 2009 12:05 thoraxe wrote:
Plz don't tell me this is 9th grade kiddie Math for you Chinese people?
8th grade
|
just take the average? (e.g. (b+a)/2)
i probably don't understand the problem though, like everyone else
|
He must think homework is fun
|
On August 27 2009 11:46 EtherealDeath wrote:
Yea... not sure of the solution to this.
We have a bounded interval, say [a,b]. The values of a and b are not particularly important. Let's say we are using [0,1000].
Within this bounded interval are some number of other bounded intervals, which may or may not intersect with other bounded intervals.
From each bounded interval (not counting [0,1000]), you must pick one point from each bounded interval so that the least distance between two points is maximized.
What alogorithm would solve this?
The contrast between this thread's topic and its actual contents is staggering oo;
|
|
|
On August 27 2009 12:35 Maero wrote:
just take the average? (e.g. (b+a)/2)
i probably don't understand the problem though, like everyone else
That I know is definitely not the solution. Among other things the taking of the average makes no sense in that you would be picking one point, but there could many many different intervals, which would mean more than one point.
|
shouldnt it always be b-a? assuming we have infinitely many intervals.
|
Well, there's an obvious crappy algorithm.
It's easy to check whether you can pick points such that each pair is separated by a minimum distance of d. So you can do a binary search on d, and continue until you're as close to the exact answer as you're asked to get.
I'm looking for a better solution, but that will work.
|
I do not know (or believe) that there is a terribly simple formula for the answer.
If I just had to write a computer program to find an exact answer, I would proceed inductively. Suppose that there are n intervals, and that I have a computer program that can find the answer given n-1 intervals.
The computer program (call it P) that solves for n-1 intervals would receive input of the form [a_1,b_1],[a_2,b_2],...,[a_{n-1},b_{n-1}] where the a_i are inputted in nondecreasing order.
Furthermore, suppose the computer program P would give me my answer as a function of a_1, assuming a_1 <= a_2 and that the other a_i and b_i are fixed. The function would be piecewise linear and therefore easy to express.
I claim that, given P, it is easy to construct a similar program which works with an input of n intervals. The new program Q would insert a test value of a_1. Then it would run P on [a_2,b_2],...,[a_n,b_n], spitting out a function of a_2. It would compute the value of a_2 such that the maximum minimum distance spit out by that function is as close to |a_1-a_2| as possible, thus solving the problem for the test value of a_1. Through judicious choices of test values of a_1, the full function of a_1 could be discovered. This is because Q knows the answer it should spit out is a piecewise linear function of a_1 with the number of distinct linear components a bounded function of n.
|
On August 27 2009 13:49 Muirhead wrote:
I do not know (or believe) that there is a terribly simple formula for the answer.
If I just had to write a computer program to find an exact answer, I would proceed inductively. Suppose that there are n intervals, and that I have a computer program that can find the answer given n-1 intervals.
The computer program (call it P) that solves for n-1 intervals would receive input of the form [a_1,b_1],[a_2,b_2],...,[a_{n-1},b_{n-1}] where the a_i are inputted in nondecreasing order.
Furthermore, suppose the computer program P would give me my answer as a function of a_1, assuming a_1 <= a_2 and that the other a_i and b_i are fixed. The function would be piecewise linear and therefore easy to express.
I claim that, given P, it is easy to construct a similar program which works with an input of n intervals. The new program Q would insert a test value of a_1. Then it would run P on [a_2,b_2],...,[a_n,b_n], spitting out a function of a_2. It would compute the value of a_2 such that the maximum minimum distance spit out by that function is as close to |a_1-a_2| as possible, thus solving the problem for the test value of a_1. Through judicious choices of test values of a_1, the full function of a_1 could be discovered. This is because Q knows the answer it should spit out is a piecewise linear function of a_1 with the number of distinct linear components a bounded function of n.
Hm... I'm afraid I don't quite see the applicability of recursion on this problem. It seems that considering a_1 would not only change a_2 but also a_3, a_4,... which makes you recalculate everything, as the new minimum might not be between a_1 and a_2 but rather a_k and a_(k+t) for some k.
|
用中文说吧，我翻译
send me a pm to remind me to translate it.
|
This is sort of like Euler's method in calculus, except you're trying to find a specific number instead of the slope....
Then again, the slope is a specific number so maybe you can think about using that.
|
My argument definitely works. I know a lot of people on this site spurt nonsense solutions to these kinds of questions, but I do actually have a math/IMO background  . It's a little complicated, but if you think about it you'll understand it. I am well aware that changing a_1 can change every other a_i.
Alternatively, note that my argument proves that the coordinates of the solution points are rational linear combinations of the coordinates of the endpoints. Furthermore, the argument provides natural bounds on the denominators of the coefficients. Thus, we only need to check a finite number of d as in severedevil's argument.
|
Restating the problem more clearly for anyone still confused.
You are given an closed interval [a,b], and some number of closed subintervals S_i = [a_i, b_i].
For each S_i, choose a c_i contained in [a_i, b_i] such that min_{i,j} (c_i, c_j) is maximized.
Wait, that might not be any more clear at all, save for math people who already get it...
In other words, each subinterval gets a point. Choose the points so that the distance between the two closest points is maximized over all possible choices of points.
|
On August 27 2009 11:46 EtherealDeath wrote:
Within this bounded interval are some set number of other bounded intervals, which may or may not intersect with other bounded intervals. For example, one possible set of intervals is {[1,100],[2,36],[45,798]}.
If I understand this problem correctly, then in this example the choice of points would be {100, 2, 798}, where the third number (798) could really be anything from 192 to 798.
Is this right?
|
On August 27 2009 21:52 ninjafetus wrote:
Restating the problem more clearly for anyone still confused.
You are given an closed interval [a,b], and some number of closed subintervals S_i = [a_i, b_i].
For each S_i, choose a c_i contained in [a_i, b_i] such that min_{i,j} (c_i, c_j) is maximized.
Wait, that might not be any more clear at all, save for math people who already get it...
In other words, each subinterval gets a point. Choose the points so that the distance between the two closest points is maximized over all possible choices of points.
That was sooooo much clearer, thanks
|
On August 27 2009 18:56 Muirhead wrote:My argument definitely works. I know a lot of people on this site spurt nonsense solutions to these kinds of questions, but I do actually have a math/IMO background . It's a little complicated, but if you think about it you'll understand it. I am well aware that changing a_1 can change every other a_i. Alternatively, note that my argument proves that the coordinates of the solution points are rational linear combinations of the coordinates of the endpoints. Furthermore, the argument provides natural bounds on the denominators of the coefficients. Thus, we only need to check a finite number of d as in severedevil's argument.
Hm.. I am sort of seeing how it would be piecewise, but not totally confident on it yet. Will have to think about it some more when I can I suppose.
|
Well, I am not sure if I totally get it but basically that's a smart idea.
One problem could be from the sorting. Have you assumed that the smallest point in the optimum solution must be picked from [a1,b1] so that you can run P for [a2,b2] to [an,bn]? Think about this testing data:[1,10] [1,15] [3,20] [4,5]. The smallest point in the solution is 4 which is picked from [4,5] set. So actually we need do P for n-1 times.
Correct me muirhead if I didnot get you 
On August 27 2009 13:49 Muirhead wrote:
I do not know (or believe) that there is a terribly simple formula for the answer.
If I just had to write a computer program to find an exact answer, I would proceed inductively. Suppose that there are n intervals, and that I have a computer program that can find the answer given n-1 intervals.
The computer program (call it P) that solves for n-1 intervals would receive input of the form [a_1,b_1],[a_2,b_2],...,[a_{n-1},b_{n-1}] where the a_i are inputted in nondecreasing order.
Furthermore, suppose the computer program P would give me my answer as a function of a_1, assuming a_1 <= a_2 and that the other a_i and b_i are fixed. The function would be piecewise linear and therefore easy to express.
I claim that, given P, it is easy to construct a similar program which works with an input of n intervals. The new program Q would insert a test value of a_1. Then it would run P on [a_2,b_2],...,[a_n,b_n], spitting out a function of a_2. It would compute the value of a_2 such that the maximum minimum distance spit out by that function is as close to |a_1-a_2| as possible, thus solving the problem for the test value of a_1. Through judicious choices of test values of a_1, the full function of a_1 could be discovered. This is because Q knows the answer it should spit out is a piecewise linear function of a_1 with the number of distinct linear components a bounded function of n.
|
|
|
|
|
|
EPT
