Problem Description
You are given initial energy and initial experience along with lists representing opponents' energy and experience. To defeat an opponent, you must have strictly greater energy and experience than the opponent. While winning increases your experience (by the opponent's experience value) and decreases your energy (by the opponent's energy value), you can train before the competition to increase either energy or experience by 1 per hour. The goal is to find the minimum number of training hours required to defeat all opponents in order.
Key Insights
- To beat all opponents, ensure initial energy is greater than the total energy requirement. Specifically, you need at least (sum(energy) + 1) energy.
- For experience, since experience increases after each win, simulate the process opponent by opponent.
- If current experience is not strictly greater than the opponent’s experience, compute the training hours needed, update the current experience, and then continue to the next opponent.
- Use a greedy approach by simply addressing each deficit as it appears.
Space and Time Complexity
Time Complexity: O(n), where n is the number of opponents, as we iterate through the opponents once. Space Complexity: O(1), since we use only a constant amount of extra space.
Solution
We first calculate the additional hours required for energy by ensuring that our energy exceeds the sum of all opponents’ energy, plus one (since we require strictly greater energy). For experience, we simulate facing each opponent sequentially. At each step, if our current experience is less than or equal to the opponent's experience, we calculate the deficit (opponent’s experience - current experience + 1), add that to our training hours, and update our current experience as if we had trained. Then, after defeating the opponent, we add their experience to our current experience. This greedy simulation approach guarantees that we only train as much as needed.