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