@Pankaj: Let's number the stations from 0 to 101, where stations 0 and 101 are the end stations and stations 1 through 100 are the intermediate stations. Let a[i], i = 1, 2, ..., 100 be the distance of station i from station 0, and finally assume that the a's are increasing, i.e., that the stations are presented in order. We want to find i[1], i[2], ..., i[10] such that 0 = i[0] < i[1] < i[2] < ... < i[10] < i[11] <= 101. Given any x, 0 < x <= a[101] (the distance between the end stations), we can find the last station that is within x of station 0. Call this station i1. In other words, a[i1] <= x but a[i1+1] > x. Now find the last station that is within x of station i[1] and call it i[2]. Etc until you find the last station that is within x of station i10. If you get to station 101 in the process, the rest of the i's = 101. This can be done with a linear search in O(100), or using 10 binary searches in O(10 log 100). Now the problem is to find the smallest x such that I[11] = 101. We can do this with a binary search on x. Initialize xmin = a[101]/11 (that would have the 10 intermediate stations equally spaced) and xmax = a[101] and begin a loop. Let x = xmin + (xmax - xmin)/2. If x == xmin or x == xmax, break; xmax is the minimax distance between stations and i[1], ..., i[10] are the stations. Otherwise, calculate i[1] through i[11] as above. If i[11] < 101, then x is too small, so set xmin = x and loop. If i[11] = 101, then x is too large, so set xmax = x and loop.
Dave On Sep 16, 1:22 pm, pankaj kumar <[email protected]> wrote: > You are given two end points ( consider them as two end stations > at some distance ) there are 100 stations between these two . Now you > need to build a train track between these two end points which > includes only 10 stations and not more than that . Now the objective > is to find such 10 stations such that the maximum distance between any > two consecutive stations is minimum . > > mine solution is > > find all possible subset of 10 elements and answer is that subset > for which sum (of distance between > consecutive stations )is minimum.. > is it correct or any other solution. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
