The contest analysis doesn't mention that the greedy part of the binary search solution can be done in O(C) (instead of O(N)), which for the given limits is extremely quick.
We move the first person in each group as described (as far left as possible while staying D away from the previous person), but we can then calculate where the last person should end up ( n-1 * D away, if n is the number of people in the group) and we only need to check that this position is reachable in time from the current position. Something similar can be done for the "mathematical" solution because if q and r are in the same group, then x_p,q < x_p,r and x_q,s > x_r,s (where p < q < r < s, using Pq = Pr). Therefore we need consider only x_i,j where i is the first member of some group and j is the last (and of course i < j); this is O(C^2) in the straightforward way and can be improved to O(C) with some more analysis (I think). -- 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.
