sorry, read wrongly. On Wed, Sep 16, 2009 at 10:00 AM, Hawston LLH <[email protected]> wrote:
> "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 -~----------~----~----~----~------~----~------~--~---
