You forgot 2 solutions. X. O(N^2) - calculate next[i] and value[i] for O(N^2), then find a cycle for O(N) and what happens before it for O(N). Y. O(NlogN) - as previous, but calculate next and value for O(NlogN)
On Sun, May 9, 2010 at 10:47 AM, guest <naieel...@gmail.com> wrote: > 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 google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- Best regards, Дектярев Михаил -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
