On Sunday, 28 April 2013 18:26:51 UTC+3, Vaibhav Tulsyan wrote: > I tried to compute all possible gains, summed them, found the max. Worked too > slow. Can you guys explain your methods?
You can arrive at an O(v) solution: Imagine you are at task i in your day, you have remaining energy E, maximum energy M and replenishment R, it will take you (M-E)/R tasks (rounding down) to replenish your energy should you decide not to spend any energy. We want to balance the following considerations: (1) we don't want to waste any energy (there is always more benefit in spending energy than in losing some surplus) (2) we want to spend as much energy as possible on the most important tasks We can achieve this with the following procedure: Consider the subset of v (tasks) starting from the task we must undertake now (task i) and ending in the task where, should we choose to be idle and starting with no energy, we will have replenished all our energy (M/R), in order to avoid wasting energy we have to expend at least E energy on some tasks in this subset. How do we decide how much energy to expend, and how to expend it? If we are the most important (v[i] is greater than any other v[j] in the subset), we can safely expend all our available energy (E) on our current task, since by the time we arrive at the first task not in our subset, we will have replenished all our energy, and expending any energy on a different task in our subset will be less rewarding than expending it on our current task. If there are other tasks in our subset that are more rewarding than our current task, we want to arrive at the earliest of those tasks with as much energy as possible, but we don't want to waste any energy - we consider the surplus of energy we would have if we arrived at that task without expending any energy with the formula E+distanceToNextLarger*R-Emax, if this is a positive number we will waste that much energy by arriving at that task without expending energy - so we can safely expend that much energy on our current task, while guaranteeing we will arrive at our next 'worthwhile' task with as much energy as possible. And that's it, this algorithm (probably more verbose than it has to be) guarantees us an optimal use of energy in O(v) (or O(v*t)) complexity and is fairly simple to implement - it's about 25 lines in python not counting loading and formatting the data. -- 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/-/KEpP9MeZNawJ. For more options, visit https://groups.google.com/groups/opt_out.
