In this blog post I'll go over the USACO Alchemy Bronze US Open 2022 Problem 3 using other resources and solutions.
A cow has some amount of several metals, each metal numbered from 1 through . A metal with a higher number has a higher value. The cow also knows several recipes for converting some one or more metals into a metal that is of more value than the ingredients. Our goal is to return the maximum number of metal the cow can get by applying transformations through the given recipe.
Let's visualize the recipe structure as a graph for the following recipes.
We cannot iterate bottom-up in this graph because we will not know where to start from, so we will have to start from the top. We have to do a depth-first search of this graph because each node depends on its children (if they exist).
Let's go through an example depth-first search for crafting 5. We start at 5, and move on to 4.
Next, we move to 1 and convert all of the 1 nodes into 4 nodes. Now, we have zero nodes with ID 1.
Now we move up and back to 3. However, 3 cannot be crafted because to make one metal 3 you need one metal 1 and one metal 2, however we used up all of our metal 1's to craft metal 4's. Handling all the dependency logic can become pretty complicated and we can end up in tons of edge cases.
If we look at the maximum units of metal the cow has for each metal type it's . What if we did a depth-first search (which takes which is operations) for each unit of metal we want to decrement? That will take us only operations. That will be underneath the operations limit that USACO gives us for C++. We can recursively go down the graph and increment the metal count by 1 if the ingredients are avaliable.
Let's go through an implementation in C++:
A lesson learned in this problem is to try and visualize the input. Also, check each and every possible naive method to see if it might be under the given time limit.