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 -~----------~----~----~----~------~----~------~--~---
