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.
