## Saturday, May 4, 2013

### 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:

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):