Problem C ? On Wed, May 9, 2012 at 11:15 AM, Luke Pebody <[email protected]> wrote:
> Problem A: > > Performing a Depth First Search or Breadth First Search for each vertex, > stopping once you have a repetition takes time at most O(N^2). Quicker ways > exist. > > Problem B: > > Let us suppose there exists any method of getting you to your home (at > distance D) at time T, and let us suppose that at time t you are at > position x(t). Then D must be at most aT^2/2. Suppose that y(t) is where > you would be if you waited for time T-sqrt(2D/a) and then just accelerated > at full acceleration until you reached home. > > Then you can show y(t) <= x(t) for all t and y(t)=D. Thus, since x(t) > doesn't bump into the car, nor does y(t). > > So there is an optimal solution that just waits at the start for a while, > and then accelerates full throttle. > > Each given location of the other car (before your house) and the time it > takes the other car to reach your house, all give you lower bounds on how > long you must wait. Wait the longest of those. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" 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. > > -- Thanks & Regards, *Satyajit Bhadange Software Programmer* *Problems & Solutions* <http://www.satyajit-algorithms.com> -- You received this message because you are subscribed to the Google Groups "Google Code Jam" 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.
