It's not right..... On Sun, Jan 30, 2011 at 4:19 PM, Nich01as <nicholas.zha...@gmail.com> wrote:
> @Wei.Qi > the algorithm is right, but the running time is ...? > > > define Pi the amount of petrol each pumps has. > Di is the distance between Ith and i+1th pumps. > > then we can double the circle, we can get to sequence > p1, p2, p3, p4...pn, p1, p2, p3..pn > d1, d2, d3, d4...dn, d1, d2, d3..dn > > the problem will become to find a subsequence in above sequences with > length N > where sum(P(start, start+i)) >= sum(D(start, start+i)) for any 0<=i<N. > > change those two sequences to below one. > p1-d1, p1+p2-d1-d2, p1+p2+p3-d1-d2-d3 ..... p1+p2+..+p2-d1-d2...-dn > make the sequence as > s1, s2, s3, s4...sn, s1, s2..sn > > finally the problem becomes to find a subsquence in Sn start at element j > where S(j+i) >= Sj and Sj >= 0. > So it can be solved in NlogN.... > > On Sun, Jan 30, 2011 at 1:47 PM, nishaanth <nishaant...@gmail.com> wrote: > >> @Wei.Qi.... Can you clarify when your algorithm terminates and also what >> is the running time of the algorithm ? >> >> >> On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang <zhangyunq...@gmail.com> wrote: >> >>> can you prove it? >>> >>> On Jan 29, 2011 6:38 PM, "Wei.QI" <qiw...@gmail.com> wrote: >>> > >>> > Starting with any pump A, try to finish the circle, if at pump B that >>> can not reach pump B+1, it means all pumps from A to B can not finish the >>> circle (it will go broke at pump B), then just start with B+1. After go >>> through all the pumps start from some pump, we got an answer. if we go back >>> to pump A and later, still can not find an answer, there is no answer. >>> > >>> > On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava < >>> richi.sankalp1...@gmail.com> wrote: >>> >> >>> >> I'm sure you have misstated the problem statement >>> >> >>> >> just find out the total path length and return the first petrol pump >>> >> which gives you the required milage >>> >> go greedy >>> >> >>> >> On Jan 28, 5:09 pm, bittu <shashank7andr...@gmail.com> wrote: >>> >> > There are N petrol pumps along a circular path. Every petrol pump >>> >> > gives some amount of fixed petrol. Need not to be unique and in no >>> >> > particular order means it is random. We have a car and we need to >>> find >>> >> > a petrol pump which can provide so much of petrol that we can take a >>> >> > full of the circle. Mileage of car is fixed. >>> >> > Distance between adjacent petrol pumps are given. >>> >> > >>> >> > Thanks & Regards >>> >> > Shashank >>> >> >>> >> -- >>> >> 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> S.Nishaanth, >> Computer Science and engineering, >> IIT Madras. >> >> -- >> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Southeast University > Nicholas.Zhaoyu > -- Southeast University Nicholas.Zhaoyu -- 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.
