# Programming Challenges: The Programming Contest Training Manual (Texts in Computer Science)

All Stack Overflow 9
This Month Stack Overflow 1

Programming Challenges: The Programming Contest Training Manual (Texts in Computer Science)

3.5

Review Date:

Your best bet for improving your problem solving is not reading books, but just doing lots of practice programs.

https://codegolf.stackexchange.com/ is a site you can look at.

These books will give you a large list of problems that if you get one of them and work through it you will be in a good mindset for problem solving (These books are not free):

Some free sites:

It is very hard to learn how to problem solve just from a book, as all people think differently. Try doing questions for fun and you will learn to problem solve.

Dynamic programming is a useful type of algorithm that can be used to optimize hard problems by breaking them up into smaller subproblems. By storing and re-using partial solutions, it manages to avoid the pitfalls of using a greedy algorithm. There are two kinds of dynamic programming, bottom-up and top-down.

In order for a problem to be solvable using dynamic programming, the problem must possess the property of what is called an optimal substructure. This means that, if the problem was broken up into a series of subproblems and the optimal solution for each subproblem was found, then the resulting solution would be realized through the solution to these subproblems. A problem that does not have this structure cannot be solved with dynamic programming.

# Top-Down

Top-down is better known as memoization. It is the idea of storing past calculations in order to avoid re-calculating them each time.

Given a recursive function, say:

``````fib(n) = 0 if n = 0
1 if n = 1
fib(n - 1) + fib(n - 2) if n >= 2
``````

We can easily write this recursively from its mathematic form as:

``````function fib(n)
if(n == 0 || n == 1)
n
else
fib(n-1) + fib(n-2)
``````

Now, anyone that has been programming for awhile or knows a thing or two about algorithmic efficiency will tell you that this is a terrible idea. The reason is that, at each step, you must to re-calculate the value of fib(i), where i is 2..n-2.

A more efficient example of this is storing these values, creating a top-down dynamic programming algorithm.

``````m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
if(m[n] does not exist)
m[n] = fib(n-1) + fib(n-2)
``````

By doing this, we calculate fib(i) at most once.

# Bottom-Up

Bottom-up uses the same technique of memoization that is used in top-down. The difference, however, is that bottom-up uses comparative sub-problems known as recurrences to optimize your final result.

In most bottom-up dynamic programming problems, you are often trying to either minimize or maximize a decision. You are given two (or more) options at any given point and you have to decide which is more optimal for the problem you're trying to solve. These decisions, however, are based on previous choices you made.

By making the most optimal decision at each point (each subproblem), you are making sure that your overall result is the most optimal.

The most difficult part of these problems is finding the recurrence relationships for solving your problem.

To pay for a bunch of algorithm textbooks, you plan to rob a store that has n items. The problem is that your tiny knapsack can only hold at most W kg. Knowing the weight (w[i]) and value (v[i]) of each item, you want to maximize the value of your stolen goods that all together weight at most W. For each item, you must make a binary choice - take it or leave it.

Now, you need to find what the subproblem is. Being a very bright thief, you realize that the maximum value of a given item, i, with a maximum weight, w, can be represented m[i, w]. In addition, m[0, w] (0 items at most weight w) and m[i, 0] (i items with 0 max weight) will always be equal to 0 value.

so,

``````m[i, w] = 0 if i = 0 or w = 0
``````

With your thinking full-face mask on, you notice that if you have filled your bag with as much weight as you can, a new item can't be considered unless its weight is less than or equal to the difference between your max weight and the current weight of the bag. Another case where you might want to consider an item is if it has less than or equal weight of an item in the bag but more value.

`````` m[i, w] = 0 if i = 0 or w = 0
m[i - 1, w] if w[i] > w
max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w
``````

These are the recurrence relations described above. Once you have these relations, writing the algorithm is very easy (and short!).

``````v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack

m[n, n] = array(int, int)
function knapsack
for w=0..W
m[0, w] = 0
for i=1 to n
m[i, 0] = 0
for w=1..W
if w[i] <= w
if v[i] + m[i-1, w - w[i]] > m[i-1, w]
m[i, w] = v[i] + m[i-1, w - w[i]]
else
m[i, w] = m[i-1, w]
else
m[i, w] = c[i-1, w]

return m[n, n]
``````

# Example Problems

Luckily, dynamic programming has become really in when it comes to competitive programming. Check out Dynamic Programming on UVAJudge for some practice problems that will test your ability to implement and find recurrences for dynamic programming problems.

Code Kata is in my recent bookmarks.

There is also a good selection of programming puzzle books out there:

...among others.

I think the best way to learn algorithms are through the various competition sites.

• USACO - my personal favorite, as it gives a clear path through the material