@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 -- 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.
