Problem Of The Week: On Dynamic Programming!
This week, let's analyze a problem statement from the 2008 Topcoder Open Online Round 2 - Division I, Level Two - CreatureTraining.
The formal summary of the problem is as follows -
Given two arrays A and B of length N, where A[i] represents the count of 'creatures' at level i, you can select any creature and increment its level in one day.
In formal notation, this is the same as doing -
A[i] = A[i] - 1A[i+1] = A[i+1] + 1
Given D days, you want to maximize the final value of
sum ( A[i]*B[i] for 0 <= i < N )
Now, let's break this down.
You have D days. On any day, you can select some A[i] and train a creature to the next level.
Clearly, we have a lot of options to proceed - which leads us to ask the question, "Does the order of operations matter?" -- no.
This is because training a creature at level 2 and then training a creature at level 1 has the same end result as training a creature at level 1 and then training a creature at level 2.
This is because only the final counts matter, so as long as all operations are followed - the order does not matter.
This allows us to tackle the problem in a sequential way (i.e. either left-to-right or right-to-left) and just focus on finding the right operations, regardless of order.
Now, for any given A[i], we have min(A[i], D) options to train the creatures at the current level.
Meaning, assuming we select X creatures to train, we lose X days, and the count of creatures in the next level increments by a value of X.
Thus, if you'll notice, the key observation we can make here is that the procedure is recursive.
A recursive approach that tries all possibilities, would go as follows -
Select X creatures, train X creatures with a cost of X days
Iterate to next level and repeat.
Now, due to the exponential number of possibilities, it’s best we memorize our computed results, so as to save time.
But what are the factors that influence our possibilities? (i.e. what would be the state of our subproblem?)
Well, clearly two states would be - the current level we are at, and the number of days left.
But the previous level interacts with the current level, as whenever we train a creature we need to also store how many creatures of the previous level we trained, as that increases the count of the creatures in the current level.
Thus, our state would comprise of three parameters - the level we are currently at, the number of creatures we trained in the previous level, and the number of days left.
This third parameter also gives us the upper limit on how many creatures of the current level we can train, if we have too many creatures at the current level.
Thus, with these three parameters, we can form a recurrence relation as follows -
f(level, prv, days) = max((A[level] + prv - i)*B[level] + f(level+1, i, days-i))// where 0 < i <= min (A[level] + prv, days)
And there we have it, a dynamic programming solution which operates in O(N*D*D*D)!
ACRush solved this in just over 4 minutes during the live contest using the same approach, and his submission is available over here - http://community.topcoder.com/stat?c=problem_solution&cr=19849563&rd=12012&pm=8570