You can check my solution, it's O(N). First I precalculate the group sizes for every starting group. It gives two arrays - cost[N] - how many fits to the run - next[N] - which group will be at the start in next run This can be done incrementally and it takes max 2N time.
With those arrays one run is O(1) and the loop can be optimized to O(N) as described in the analysis. There you have O(N) in total. On May 9, 8:21 pm, "coder.ankur" <[email protected]> wrote: > Can anybody explain how the problem can be optimized to O(N) as > mentioned in the the last of contest analysis for this problem. > > -- > 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 > athttp://groups.google.com/group/google-code?hl=en. -- 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.
