@ankur, does this actually connects from start station to end station?? i think ur solution creates path which could be discontinuous, but we want end to end connected path surender On Sat, Sep 17, 2011 at 5:39 AM, Ankur Garg <ankurga...@gmail.com> wrote:
> Some typos in my solution :( > Use a Max heap.. > > first take the first 10 stations and build a* Max *heap O(10)..Heap > contains distance between 2 stations . Initial Heap will contain 10 *minimum > *distances with maximum of those at the top . Now 11 th comes u compare > with the root of the heap . If its less than that than replace it with the > top and run heapify (O(log10) ) ..keep doing the same . In the end u have 10 > stations with min distance between them > > Complexity O(10) + O(log(10)) = O(1) ..Comparision takes constant time > > So total complexity O(1) > > Regards > Ankur > > On Sat, Sep 17, 2011 at 5:00 AM, Dave <dave_and_da...@juno.com> wrote: > >> @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 <p9047551...@gmail.com> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
