USACO 2022 US Open Contest, Bronze Problem 3. Alchemy

USACO 2022 US Open Contest, Bronze Problem 3. Alchemy

Always keen to learn new hobbies, Bessie the cow is learning how to transform metals. She has aiai (0ai1040≤ai≤104) units of metal ii for 1iN1001≤i≤N≤100. Furthermore, she knows KK (1K<N1≤K<N) recipes where she can combine one unit each of several metals to make one unit of a metal with a higher number than all constituent metals. It is additionally guaranteed that for each metal, Bessie knows at most one recipe to make it.

Compute the maximum number of units of metal NN Bessie can possibly have after some series of transformations.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN.

The second line contains NN integers, aiai.

The third line contains KK.

The next KK lines start with two integers LL and MM (M1M≥1), followed by MM integers. The last MM integers represent the constituent metals in the recipe that are used to form one unit of metal LL. It is guaranteed that LL is larger than the MM last integers.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the maximum number of units of metal NN Bessie can possibly have after applying some series of zero or more transformations.

SAMPLE INPUT:

5
2 0 0 1 0
3
5 2 3 4
2 1 1
3 1 2


SAMPLE OUTPUT:

1


In this example, the following is an optimal series of transformations:

1. Transform one unit of metal 1 into metal 2.
2. Transform one unit of metal 2 into metal 3.
3. Transform one unit of metal 3 and metal 4 into metal 5.

Now Bessie is left with one unit of metal 1 and one unit of metal 5. She cannot form any additional units of metal 5.

SCORING:

• In test case 2, for 1i<N1≤i<N, one unit of metal ii can be transformed into one unit of metal i+1i+1.
• In test cases 3 and 4, each recipe transforms one unit of one metal into another.
• Test cases 5 through 11 satisfy no additional constraints.

Problem credits: Nick Wu

USACO 2022 US Open Contest, Bronze Problem 3. Alchemy 题解(翰林国际教育提供，仅供参考)

[/hide]
(Analysis by Nick Wu)
For notational convenience, if i>j, we'll say that metal i is more valuable than metal j. Note that all recipes take a single unit of some metals and produce one unit of a metal that is more valuable than all of the original metals.

To solve test case 2, every unit of metal can be converted into a unit of metal N, so the answer is the number of units of metal that Bessie has.

To solve test cases 3 and 4, if there is no recipe that can make metal N, then the answer is simply the number of units of metal N that Bessie starts out with. Otherwise, there is some less valuable metal that can be turned directly into metal N, so all of those units can also be converted into metal N. If that less valuable metal has no recipe, then we are done. Otherwise, we repeat this process and sum up the counts of the less valuable metals until we reach one which can't be made.

To solve the problem fully, we'll take advantage of how recipes can only turn less valuable metals into more valuable metals. If we want to gain one unit of metal N, we must use that recipe, and so that means we need one unit of some less valuable metals. If we already have one of each unit of the less valuable metals, we can directly consume those. If we don't have a unit of some metal, and no recipe for that metal exists, we cannot make any more of metal N, and the process ends. If there is a recipe, then we need one unit of each of the metals that are ingredients in that recipe.

Since more valuable metals cannot be used as ingredients in recipes for less valuable metals, we can loop over the metals in order from metal N down to metal 1, tracking at each point in time how many units of each metal we need in order to make one unit of metal N.

The while loop runs at most N⋅max(ai) times and takes O(N) time per iteration, for a time complexity of O(N2⋅max(ai)).

C++ code that does this iteratively:

#include <bits/stdc++.h>

using namespace std;

int main() {
int n;
cin >> n;
vector have(n);
for(auto& x: have) cin >> x;
int k;
cin >> k;
vector<vector> need(n);
while(k--) {
int want, m;
cin >> want >> m;
need[--want].resize(m);
for(auto& x: need[want]) {
cin >> x;
x--;
}
}
int ret = 0;
while(true) {
vector consume(n);
consume[n-1]++;
bool good = true;
for(int i = n-1; i >= 0; i--) {
if(consume[i] <= have[i]) {
have[i] -= consume[i];
continue;
}
if(need[i].size() == 0) {
good = false;
break;
}
int take = min(consume[i], have[i]);
consume[i] -= take;
have[i] -= take;
for(int out: need[i]) consume[out] += consume[i];
}
if(good) ret++;
else break;
}
cout << ret << "\n";
}
Java code that does this recursively:

import java.io.*;
import java.util.*;
public class Alchemy {
public static void main(String[] args) throws IOException {
int[] have = new int[n];
for(int i = 0; i < n; i++) have[i] = Integer.parseInt(st.nextToken()); int ans = 0; int[][] recipes = new int[n][]; int k = Integer.parseInt(in.readLine()); while(k-- > 0) {