Results of March Monthly Contest
Ok everyone, I am going to post the results as well as my solutions in this thread. I'll start with the medium since noone posted code for that one, then the hard one, then tomorrow I'll post the results of the easy problem.
Medium Problem
Like I said when I posted this problem, I was a little torn about the difficulty of this problem. Since nobody posted code I now know it should have been listed as difficult, but once you see how this problem can be solved in only a couple of lines you'll see why I thought it might be easy.
Solving the number of combinations can be very difficult if you try to brute force it. You could recursively try every combination of animals but you'll soon find that you'll quickly max out your time. It turns out this problem can be solved very easily using a technique called dynamic programming. I'm not gonna lecture on it so if interested I'd recommend reading up on it, but its a powerful way to solve seemingly impossible problems. Its similar to recursion in that you break the problem up into smaller and smaller parts, but you use an intuitive data storage to prevent recalculating the same results over and over again.
Heres an example thats similar to my problem. How many different ways can you combine US coins to equal 17 cents? Again you could try every possible combination of coins but thats far too much work. Heres how to do it with dynamic programming:
Start off with an array of zeros of size n+1 where n is your target number. In this case we are looking for 17 cents, so our array would be size 18. Now what does this array represent? At each index, its the total number of combinations to get to that point. So index 10 is the number of combinations to 10 cents, etc. What we care about is index 17 or the last index. At this point everything is zero since we haven't calculated anything yet. First thing is to set index 0 to 1 since we automatically know that theres only one combination to get zero cents, and thats no coins at all. So our array looks like this:
Code:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Now you loop through the array with each coin type. Now heres the tricky part, at each spot in the array you know how many combinations it takes to get there since its the value of the index you are at. So if you are array[7] and the value is 5, then you know that there are five different combinations that get you to there. Now say you are looping through with pennies, if you know theres five ways to get where you are now, then add a penny to each of those and you know that theres five combinations to get to array[8]. If array[8] already had 3 combinations of its own, you now know theres 5+3 combinations to get to array[8]. Get the idea? So heres the basic algorithm:
Code:
// target is value we are shooting for
int howMany(int target)
{
int coins[5]={1,5,10,25,50}; // coin values
int combinations[500]={0}; // big array to keep the combos :D
combinations[0]=1;
for (int i=0; i<5; i++)
for (int j=0; j<target; j++)
combinations[j+coins[i]]+=combinations[j];
return combinations[target];
}
It can be optimized further but you get the idea. So after pennies our array looks like this:
Code:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
After nickels:
Code:
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4
After dimes:
Code:
1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6
And no reason to do quarters or half dollars. So returning array[17] gives us 6 which is the correct number of combination of coins to 17 cents.
So if you can understand this one, it should be easy to figure out how to solve my problem. Since we need to know the number of combinations of feet AND heads, we now use a two dimensional array, where array[h][f] is the number of combinations that have h heads and f feet.
Heres my code to solve the problem (again which could be optimized further but no real need):
Code:
// target is value we are shooting for
int numberCombinations(int maxAnimals, int maxFeet, vector<int> animals)
{
int combinations[500][500]={0}; // again lazy, could be dynamically created
combinations[0][0]=1;
for (int i=0; i<animals.size(); i++)
for (int curHeads=0; curHeads<=maxAnimals; curHeads++)
for (int curFeet=0; curFeet<=maxFeet; curFeet++)
combinations[curHeads+1][curFeet+animals[i]]+=combinations[curHeads][curFeet];
return combinations[maxAnimals][maxFeet];
}
