"The distance among time is neither in decreasing or increasing order." i can show you by using your argument, this will inevitably arrive at some sort of minimum distance. if you think of distance as positive value, then by your argument, there will be a point when the distance come to zero in the past or future, that would mean 0 is the minimum distance. but if you think of distance having positive and negative value, then in absolute sense of distance | d |, 0 is the minimum distance.
On Wed, Sep 16, 2009 at 1:45 AM, Renato Wolp <[email protected]> wrote: > Yes, during contest I preferred to write a ternary search besides the > geometry solution. Ironically, I couldn't fix the precision of the answer in > time =) > And I still don't see why binary search should work here... The distance > among time is neither in decreasing or increasing order. > > 2009/9/15 Carlos Guia <[email protected]> > >> It can be solved with geometry, but I think writing ternary search is >> faster for many people(myself included) than doing the math on paper, also >> may be less error prone, it is easy to make a little mistake when doing math >> under pressure. And if I know 2 ways that will work, then I prefer the one >> that optimizes the solving speed. But for practice I think is better to try >> both, as having sharp math skills is very important anyway. >> Carlos Guía >> >> >> >> On Tue, Sep 15, 2009 at 9:41 AM, Andrea <[email protected]> wrote: >> >>> >>> On Sep 14, 6:52 pm, Renato Wolp <[email protected]> wrote: >>> > Should binary search work in this problem? I think it has to be a >>> ternary >>> > search... >>> > >>> >>> I think binary/ternary search is overkill. It is solvable using basic >>> geometry in O(1) for the minimum distance and time. Of course you need >>> first to get center of mass position and vector in O(N). >>> >>> You can find a (I hope) clear explanation of the geometric solution >>> method with the working python code here: http://e.nigma.be/archives/35 >>> >>> -- >>> Andrea >>> >>> >> >> >> > > > -- > Renato. > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" 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/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
