# Solving an interesting algorithmic problem

The second problem on *Google CodeJam 2013, Round 1B* was interesting:
Problem B. Manage your Energy . The obvious solution of trying all the
possible cases and combinations would not work, unless the input had
very small limits (besides being not so easy to implement).

The solution, as described on the Contest Analysis was a *greedy
algorithm*: try to spend as much energy as possible for the activity
with the highest value, neglecting the other activities if needed;
then try to spend as much energy as possible for the activity with the
second highest values, neglecting the others if needed, and so on.

Actually, I suspected during the contest that a greedy algorithm may be the solution, however I couldn't find a way of implementing it properly. Even days after the contest I was not able to think of a suitable implementation. Only after seeing the solution on the Contest Analysis I could see how it could possibly be implemented (keeping a pair of constraints for each value on the list, and updating them while processing the list).

But then I saw a post on the CodeJam Community, that somebody had implemented a recursive solution, and then suddenly things became much clear and cleaner. Usually the recursive solutions are more elegant and more easy to understand and implement, and this is true for this case as well.

Below is the recursive implementation that I did to solve this problem:

400: Invalid request

But there was something more interesting to this problem. Usually, the
good (fast) solution, as described on the CodeJam Analysis, is of
complexity **O(N*N)**. Using special implementation techniques it could
also be improved to **O(N*logN)**. But during the contest there was
somebody that had solved it with a linear algorithm, complexity
**O(N)**! This was surprising because even the contest organizers were
not aware of such a solution before the contest!

Below is my implementation of this solution of complexity **O(N)**:

400: Invalid request