The Star Quest

24 May 2016

Exactly one month ago I started a quest on taking down each and every starred problem of the Competitive Programming (CP) book selected from the UVa online judge website. My objective with this endeavor is straightforward: keep my algorithmic skills sharp. I set out by making myself solve at least one problem a day. This sort of approach does not usually work well with me, because at some point along the way I’ll forget to solve a problem, and then I’ll just never remember to get back to it; ever. In practice, however, though I may have been skipping a day or two from time to time, I often end up solving more than one problem. All in all I’d say, given my objectives and my constraints, things have been going pretty well.

The following graph will help illustrate and allow us to better visualize the progress of this little quest of mine. Before beginning this I had solved exactly 51 problems, which led me to world ranking 16k in UVa. We see that now, a month from starting the project, I’ve solved 102 problems, twice what I started from, bringing me to the 8.6k rank. That’s some 50 problems in some 30 days; pretty good to me.

Read more

---

Dynamic Programming Memoization with Trees

08 Apr 2016

Recently I came by the House Robber III problem in LeetCode. The basic idea in this problem is you’re given a binary tree with weights on its vertices and asked to find an independent set that maximizes the sum of its weights. This is a dynamic programming problem rated medium in difficulty by the website.

This post starts with a brief overview on dynamic programming, and ends with an anecdote on how I tried two different implementations of dynamic programming memoization when solving the House Robber III problem. Although the actual algorithmic idea in both approaches is the same, the strategy used to store memozation matrices when entries are the nodes of a tree led to considerable differences in readability.

Read more