I didn't think of it at the time, but a greedy divide and conquer algorithm works.
Initial energy is E, and the best strategy has final energy 0. But solve a more general problem with other given values of initial and final energy. The algorithm is to choose the task of greatest value. Determine the maximum energy available for this task given the initial energy, and the minimum energy possible after this task given the constraint to meet the final energy. The difference is the energy to spend on the chosen task. Compute the gain obtained for this task, and recursively solve the problem for the tasks before and the tasks after the chosen task. I expect with cunning one could solve this way in O(N log N) steps, but simple linear searches to find the maximum value task will give a worst case of O(N^2). -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/INpFJGdzgLwJ. For more options, visit https://groups.google.com/groups/opt_out.
