This was more of a physics problem than an algorithm question. I was actually surprised to see this question in the list, but it got me qualified (I suppose) for the next round :p You just need to find the position and velocity of the center of mass (COM). You can do this by finding the average position (p) and average velocity (v) of the flies by summing them and dividing by N. Then you may apply d2 and t formulas at this page:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html <http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html>x0 is 0,0,0 (our position, origin) x1 is the initial position of COM (p). x2 = x1 + v (eg. position of COM after 1 second, v is the velocity of COM). If t turns out to be negative, this means that the minimum distance was achieved before t=0. That means you will have the initial position as the minimum distance and t=0 as the time to reach that distance. My assumption is that the intention of asking this question was something else, but the guys who prepared the question (Bartholomeow? :) somehow missed this point. Or they just wanted to let us in. Thanks guys ! :) On Sun, Sep 13, 2009 at 9:35 PM, tbischel <[email protected]> wrote: > > Adding LP to your personal library is a good idea, but ultimately not > needed here. The motion of the center of mass for the swarm is > linear, because all the fireflies don't change direction or speed. So > the problem comes down to finding the closest point on the line > showing the motion of the swarm to the orgin. This is just a dot- > product trick, solving for time using the average direction dotted > with the position (or a vector from the orgin to the position), which > should be zero. > --Tyler > > On Sep 13, 12:46 pm, Nathaniel Tucker <[email protected]> wrote: > > I focused on the other problems this round, because I have never > > implemented a linear program before. Do you know of a good source to > > learn about coding learning programming algorithms? I figure I should > > add LP to my library. > > > > Good luck with future endeavors! > > > > On Sep 13, 4:39 am, Mike <[email protected]> wrote: > > > > > > > > > Hello, > > > > > Although I've solved the problem mathematically correct, some of the > > > values were in this format: 5.6843418860808015E-14 and it seems the > > > verifier didn't recognize it... I was so close :) but anyway, I gained > > > a lot of experience from this contest, and I will surely participate > > > next time. Great job Google ! and congrats to everyone who qualified > > > in Round 2 ! > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
