Well, I've thought of some solutions and I think maybe solution 4 would be the best :)
1. O(RN) naive search naive. 2. O(RlgN) binary search well, quite easy to think of. but according to the size of the test data, it is quite risky. 3. O(R+N) queue just computing the next[N] and value[N] array. Risky either. 4. O(NlgR) queue+doubling doubling next[lgnR][N] and value[lgnR][N] array. Can be improved by rolling the arrays. 5. O(N) queue+graph+math construting the next[N] array (edges) into a graph, and by computing cycles, we can do an effecient linear programming. Well, solution 5 may be the best in Time and Memory, solution 4 should be best for programmers 'cause it has the greatest balance in either Time, Memory and Code Length. * next[i] means the first group of the next rollercoasting round. value[i] means the earning of the round started by group i. :) -- 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.
