We periodically include chemistry-themed problems in Code Jam, and Round 2 had three! The two parts of New Elements could be solved independently, but there were some commonalities, so solving one made it perhaps a bit easier to solve the other. Contransmutation was a spiritual successor to this problem from Round 1B 2018, and it was similarly challenging. We did take a break from the chemistry lab to interactively hack a vase contest in Pottery Lottery.
This was an uncharacteristically tight round, with the problems having a smaller spread of difficulties than usual. This was reflected in the full score for each problem being in the twenties. mnbvmar was the first to get a perfect score to claim first place, when there was a little over an hour left. ksun48 and xyz111 followed to claim second and third. Overall, only 26 contestants managed a perfect score. Getting even a single point was tough in this round, given it didn't feature any simple problems, and over 2400 contestants managed to score nonetheless. Congratulations!
Preliminary results indicate that 32 points and some speed are required to advance to the next round.
After the results have been finalized, the top 1000 contestants will win well-deserved Code Jam 2019 T-shirts, and will advance to Round 3, where 25 tickets to the World Finals await! Are you going to San Francisco?
Cast
New Elements, Part 1: Written by Pablo Heiber. Prepared by Jonathan Irvin Gunawan.
Pottery Lottery: Written by Ian Tullis. Prepared by John Dethridge and Pi-Hsun Shih.
New Elements, Part 2: Written by Pablo Heiber. Prepared by Micah Stairs.
Contransmutation: Written by Pablo Heiber. Prepared by Jonathan Irvin Gunawan and Darcy Best.
Solutions and other problem preparation and review by Liang Bai, Darcy Best, Timothy Buzzelli, John Dethridge, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Ray Robinson, Micah Stairs, Ian Tullis, Pi-Hsun Shih, and Adilet Zhaxybay.
Analysis authors:
The first two paragraphs (not counting this one) of this problem and "New Elements: Part 2" are identical. The problems can otherwise be solved independently; you do not need to read or solve one in order to read or solve the other.
Muriel is on the path to discovering two new elements that she has named Codium and Jamarium. She has not been able to isolate them yet, but she wants to start investigating some important properties, like their atomic weights, by indirect means. Since Muriel is working with a single isotope of Codium and a single isotope of Jamarium, their atomic weights are strictly positive integers.
Muriel managed to create N different molecules, each of which contains one or more atoms of Codium and one or more atoms of Jamarium, and no other elements. For each molecule, she knows how many atoms of each element are present in it. The molecular weight of a molecule is the sum of the atomic weights of all the atoms it contains.
As a first step towards figuring out exact molecular weights for the molecules and atomic weights for the two elements, Muriel wants to sort the molecules by strictly increasing molecular weight. To assess the difficulty of that task, she wants to know how many orders are valid considering only the information she has right now. An ordering of the molecules is considered valid if there exist values for the atomic weights of Codium and Jamarium such that the ordering is strictly increasing in molecular weight.
To give an example, we represent each molecule by the ordered pair of the number of atoms of Codium and Jamarium it contains. If Muriel has 3 molecules represented by (1, 1), (2, 1) and (1, 2), there are two possible orderings that can be strictly increasing in molecular weight: (1, 1), (1, 2), (2, 1) and (1, 1), (2, 1), (1, 2). The first ordering is valid for any assignment of atomic weights in which Codium is the heaviest of the two elements, and the second is valid for any assignment in which Jamarium is the heaviest. The only case remaining is when both Codium and Jamarium have the same atomic weight, in which case (1, 2) and (2, 1) have the same molecular weight, so no strictly increasing ordering can be produced for that scenario.
The first line of the input gives the number of test cases, T. T test cases follow. The first line of a test case contains a single integer N, the number of molecules. Each of the next N lines describes a different molecule with two integers Ci and Ji that represent the number of Codium and Jamarium atoms in the i-th molecule, respectively.
For each test case, output one line containing Case #x: y, where x
is the test case number (starting from 1) and y is the total number of valid orderings
as defined above.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ci ≤ 109, for all i.
1 ≤ Ji ≤ 109, for all i.
(Ci, Ji) ≠ (Cj, Jj)
for all i ≠ j. (All molecules are different.)
2 ≤ N ≤ 6.
2 ≤ N ≤ 300.
3 3 1 1 1 2 2 1 4 1 2 2 4 2 1 4 2 3 1 2 1 3 2 3
Case #1: 2 Case #2: 2 Case #3: 1
Sample Case #1 is explained in the statement.
In Sample Case #2, the two valid orderings are (1, 2), (2, 1), (2, 4), (4, 2) and (2, 1), (1, 2), (4, 2), (2, 4). Notice that the ordering (1, 2), (2, 1), (4, 2), (2, 4) is invalid because if (1, 2) is strictly less heavy than (2, 1), then (2, 4), which is exactly twice as heavy as (1, 2), must be strictly less heavy than (4, 2), which is exactly twice as heavy as (2, 1).
The Pottery Palace is going to run a lottery featuring some valuable vases by the artist Cody-Jamal. The lottery works as follows:
You have been hired to test the security of the lottery, and you will participate in some trial runs. The company will always assign you the number 100 — that is, you replace player 100.
You have found some ways to tamper with the lottery at night, but security is tight, so you can only do so much! Specifically, after each of the first 99 days of the lottery, you may do exactly one of the following:
You may perform different actions on different nights, and you may choose dynamically: you do not need to decide on all of your actions in advance.
On the 100th day, it is your turn to insert your token into a vase of your choice (you do not need to choose uniformly at random). You cannot perform any other actions on that day.
You know that if there is a winning vase with more than one token for the same player, it will be obvious that cheating has occurred and nobody will win. However, it does not matter if other vases contain more than one token for the same player because the organizers never see those tokens.
Your goal is to be a winner in at least 90% of the test cases.
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, your program should read a single line containing a single integer T indicating the number of test cases. Then, you need to process T test cases.
At the start of a test case, the judge outputs one line with one integer: the number of the current day. (The judge starts on day 1, and on the i-th day, it prints i.) After your program reads the integer, it should write a line containing two integers V and P, with 1 ≤ V ≤ 20, and 0 ≤ P ≤ 100. The judge will interpret these as follows:
Notice that on turn 100, you must put your own token in, so P must be 100.
Remember that on the i-th day, for 1 ≤ i ≤ 99, the judge simulates the action of the i-th player, as described in the statement. This happens before your own action on that day.
After you send your move for turn 100, your program should terminate if it was the last test case; otherwise, it should start reading data for the next test case. (Notice that the judge does not tell you whether you got each case correct or incorrect.) The judge will only check whether you have enough correct answers after you have attempted all T test cases, so you should not stop early! For example, if you answer the first 225 out of 250 cases correctly and then exit, or provide malformed input, your solution will not be considered correct.
If your program outputs something illegal (e.g., gives an invalid value for P
or V, or tries to inspect a vase on turn 100), the judge will send
one line containing -1 to your input stream, and it will not
send any other output after that. If your program continues to wait for the
judge after receiving -1, your program will time out, resulting
in a Time Limit Exceeded error. Notice that it is your responsibility to have
your program exit in time to receive a Wrong Answer judgment instead of a
Time Limit Exceeded error. As usual, if the total memory is exceeded, or your
program gets a runtime error, you will receive the appropriate judgment.
T = 250.
Time limit (for the entire test set): 40 seconds.
Memory limit: 1GB.
You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.
Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.
t = readline_int() // reads 250 into t
curr_day = readline_int() // reads 1 (day 1)
printline 8 100 to stdout // puts a token for player 100 into vase 8
flush stdout
curr_day = readline_int() // reads 2 (day 2)
printline 8 99 to stdout // puts a token for player 99 into vase 8
flush stdout
curr_day = readline_int() // reads 3 (day 3)
printline 8 100 to stdout // puts a token for player 100 into vase 8
flush stdout
curr_day = readline_int() // reads 4 (day 4)
printline 20 7 to stdout // puts a token for player 7 into vase 20
flush stdout
curr_day = readline_int() // reads 5 (day 5)
printline 8 0 to stdout // inspects vase 8
flush stdout
tokens = readline_int_list() // reads 5 2 5 99 100 100 (players 2 and 5
// happen to have chosen vase 8)
curr_day = readline_int() // reads 6 (day 6)
printline 8 101 to stdout // tries to add a token with a bad player number
flush stdout
curr_day = readline_int() // reads -1 (judge has decided our solution is
// incorrect)
exit // exits to avoid an ambiguous TLE error
The first two paragraphs (not counting this one) of this problem and "New Elements: Part 1" are identical. The problems can otherwise be solved independently; you do not need to read or solve one in order to read or solve the other.
Muriel is on the path to discovering two new elements that she has named Codium and Jamarium. She has not been able to isolate them yet, but she wants to start investigating some important properties, like their atomic weights, by indirect means. Since Muriel is working with a single isotope of Codium and a single isotope of Jamarium, their atomic weights are strictly positive integers.
Muriel managed to create N different molecules, each of which contains one or more atoms of Codium and one or more atoms of Jamarium, and no other elements. For each molecule, she knows how many atoms of each element are present in it. The molecular weight of a molecule is the sum of the atomic weights of all the atoms it contains.
As a first step, Muriel sorted the molecules by strictly increasing molecular weight. Now she wants to find out possible integer values for the atomic weights of both Codium and Jamarium that are consistent with the ordering. Since she is aware there could be many consistent pairs of values, she wants one that minimizes the atomic weight of Codium. If there are multiple pairs in which Codium's atomic weight is minimum, she wants the one in which Jamarium's atomic weight is minimum.
The first line of the input gives the number of test cases, T. T test cases follow. The first line of a test case contains a single integer N, the number of molecules. Each of the next N lines describes a different molecule with two integers Ci and Ji that represent the number of Codium and Jamarium atoms in the i-th molecule, respectively. The molecules are given in strictly increasing order of molecular weight.
For each test case, output one line containing Case #x: y, where x
is the test case number (starting from 1), and y is IMPOSSIBLE (in uppercase) if there is
no pair of integer atomic weights that would make the order of the molecules strictly
increasing in molecular weight. Otherwise, y should be two integers
c j where c is the atomic weight of Codium and j is the atomic weight of
Jamarium, chosen according to the rules above.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 10.
(Ci, Ji) ≠ (Cj, Jj)
for all i ≠ j. (All molecules are different.)
1 ≤ Ci ≤ 100, for all i.
1 ≤ Ji ≤ 100, for all i.
1 ≤ Ci ≤ 109, for all i.
1 ≤ Ji ≤ 109, for all i.
3 3 1 1 1 2 2 1 4 1 2 2 1 4 2 2 4 3 1 2 1 3 2 3
Case #1: 2 1 Case #2: IMPOSSIBLE Case #3: 1 1
In Sample Case #1, the difference between the last two molecules is having an extra atom of one element or the other. Given that the one having the extra Codium is heavier overall, we conclude that Codium must be heavier than Jamarium. The values 2 and 1 for the atomic weights of Codium and Jamarium make the molecular weights 1 × 2 + 1 × 1 = 3, 1 × 2 + 2 × 1 = 4, and 2 × 2 + 1 × 1 = 5, respecting the strict ordering. Since Codium is heavier than Jamarium in this case, 2 is Codium's minimum atomic weight, and 1 is of course Jamarium's minimum atomic weight.
Let a, b, c and d be the molecular weights of the molecules in Sample Case #2, in increasing order of molecular weight. By their atom contents, d = 2 × a and c = 2 × b. It follows from a < b that d = 2 × a < 2 × b = c, which means there is no pair of values for the atomic weights that would make the ordering strictly increasing.
In Sample Case #3, notice that the molecules happen to be sorted in strictly increasing order of total number of atoms. Therefore, assigning both elements an atomic weight of 1 makes the atomic weights be sorted in strictly increasing order.
Last year, we asked you to help us convert expensive metals into lead. (You do not need to know anything about the previous problem to solve this one.) But your country's leader is still greedy for more lead!
There are M metals known in the world; lead is metal number 1 on your periodic table. Your country's leader has asked you to use the metals in the treasury to make as much lead as possible.
For each metal (including lead), you know exactly one formula that lets you destroy one gram of that metal and create one gram each of two metals. (It is best not to think too much about the principle of mass conservation!) Note that it is possible that the formula for the i-th metal might produce the i-th metal as one of the products. The formulas do not work with partial grams. However, you can use each formula as often as you would like (or not at all), as long as you have a gram of the required ingredient.
If you make optimal choices, what is the largest number of grams of lead you can end up with, or is it unbounded? If it is not unbounded: since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime 109+7 (that is, 1000000007).
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with an integer M: the number of metals known in the world. Then there are M more lines with two integers Ri1 and Ri2 each; the i-th of these lines, counting starting from 1, indicates that you can destroy one gram of metal i to create one gram of metal Ri1 and one gram of metal Ri2. Finally, there is one line with M integers G1, G2, ..., GM; Gi is the number of grams of metal i in the treasury. Lead is metal 1.
For each test case, output one line containing Case #x: y where
x is the test case number (starting from 1). If there is no
bound on the maximum amount of lead that can be produced, y
must be UNBOUNDED. Otherwise, y must be
the largest amount of lead, in grams, that you can end up with, modulo the
prime 109+7 (that is, 1000000007).
1 ≤ Ri1 < Ri2 ≤ M,
for all i.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ M ≤ 10.
0 ≤ Gi ≤ 10, for all i.
1 ≤ T ≤ 100.
2 ≤ M ≤ 100.
0 ≤ Gi ≤ 109, for all i.
1 ≤ T ≤ 5.
2 ≤ M ≤ 105.
0 ≤ Gi ≤ 109, for all i.
3 2 1 2 1 2 1 0 2 1 2 1 2 0 0 4 2 4 3 4 2 4 2 3 10 10 10 10
Case #1: UNBOUNDED Case #2: 0 Case #3: 10
In Sample Case #1, you have one formula that turns 1 gram of lead into 1 gram of lead and 1 gram of the second metal, and another formula that turns 1 gram of the second metal into 1 gram of lead and 1 gram of the second metal. You can alternate between these formulas to produce as much of both metals as you want.
Sample Case #2 has the same formulas as Sample Case #1, but you have no metals to start with!
In Sample Case #3, none of the formulas help you produce more lead, so you cannot end up with more lead than you started with.
In the first test set, there can be at most six molecules, so we can easily check all 6! = 720 possible orderings of them. The nontrivial part is figuring out how to check an ordering. We cannot check all possible atomic weights, since they can be arbitrary integers, and those integers might need to be quite large (since the Ci and Ji values can be as large as 109).
For each ordering of molecules, we must determine whether there is at least one valid pair of atomic weights wC and wJ for Codium and Jamarium, respectively, such that the molecules are in strictly increasing order of molecular weight. We do not need to find particular values; we only need to show existence or non-existence.
Let k = wJ / wC. Then, if wC and wJ are valid for our ordering, we can substitute wJ = k × wC in the requirement for any pair of molecules (Ca, Ja), (Cb, Jb) such that a < b:
Ca × wC + Ja × kwC < Cb × wC + Jb × kwC
If Ja = Jb, then this reduces to Ca < Cb, which is a simple check; if it is false, then no set of atomic weights is valid, and we can stop checking this ordering. Otherwise, rearranging some terms and dividing, our expression becomes:
(Ca - Cb) / (Jb - Ja) < k,
if Ja < Jb, or
k < (Ca - Cb) / (Jb - Ja),
if Ja > Jb.
So, we can start by assuming that k can take on any value in an infinite range. Then, whenever we check a pair of molecules, we get a new (non-inclusive) upper or lower bound on the value of k, and we can update one end of the range accordingly. If we find that constraints force the range to be empty (e.g., because the upper end is forced to be smaller than the lower end), then no valid set of atomic weights exists. Otherwise, at least one does. Notice that even though the atomic weights of Codium and Jamarium must both be integers, any rational value of k corresponds to some pair of integers.
This is a quick set of checks, and it is even quicker if we realize that we only need to check consecutive pairs of molecules. However, as in any problem involving comparisons of fractional quantities, we must be careful to compute exact values instead of using floating-point approximations.
Considering the solution of Test set 1 in reverse can lead us to a solution for Test set 2. If we consider two arbitrary molecules with indices a and b, they can appear in two possible orderings. If one of them is impossible according to the math above, it means that the other is the ordering of the molecules for every possible assignment of atomic weights. If that's the case, we can ignore the pair of molecules (a, b). However, if both orderings are possible, we obtain a range of valid values for the ratio k of the form (0, Ra,b) for one ordering and a range of the form (Ra,b, +∞) for the other, where Ra,b = |(Ca - Cb) / (Ja - Jb)|. That means, for all orderings that correspond to atomic weights that yield a ratio strictly less than Ra,b, the molecules a and b appear in a specific relative order, and for all orderings that correspond to values yielding a ratio strictly greater than Ra,b, the molecules a and b appear in the other relative order. If the ratio is exactly Ra,b, the two molecules weigh exactly the same, so no ordering is valid.
By the previous paragraph, if we consider a function f from ratios into orderings, f is a piecewise constant function that is undefined at ratios Ra,b for any pair a, b and is constant in any interval that doesn't contain any such ratio. Moreover, the image of f over (0, Ra,b) consists of orderings with molecules a and b in one relative order and the image of f over (Ra,b, +∞) consists of orderings with molecules a and b in the other relative order. Therefore, no two elements in f's image are the same. The number of elements in f's image, which is the answer to the problem, is the number of different non-zero Ra,b values, plus 1. Notice that it is possible that Ra,b = Rc,d for different molecules a, b, c, d, and we need to count the number of unique values.
The algorithm to count the number of different values that are equal to Ra,b for some a, b is immediate: try every pair of molecules, calculate the ratio as explained for the Test set 1 solution (if there is one), and add it to a set of fractions to discard non-uniques. This algorithm takes a quadratic number of insertions into a set, which makes it quadratic or barely above quadratic overall depending on the set implementation that is used.
Our tempting first thought might be: why not just put one of our tokens in each vase? Then we can sit back and just wait to win, no matter which vase gets chosen. Who needs the other 80 days?
The flaw in this reasoning is that if multiple vases are tied for having the fewest tokens, there is no winner. A quick simulation can show us that there is only a unique winner around 57% of the time. So this approach has no hope of passing, and we have to work harder!
It might still seem that we can succeed without inspecting any vases. What if we just choose one vase up front — without loss of generality, we will pick vase #20 — and try to make it the winning vase? Over the course of the first 99 nights, we distribute fake tokens among the other 19 vases, as evenly as possible (to prevent any one of those vases from becoming more of a threat than the others). The labels on these fake tokens do not matter, since we are banking on vase 20 winning. Then, on the 100th night, we place our token in vase 20. Since each of the other 19 vases will be burdened with 5 (or maybe even 6) extra tokens, the odds are good that vase 20 will have the fewest, right?
Unfortunately, those odds aren't so good. Again, we can write a quick simulation to verify that our strategy will only succeed around 53% of the time — it's even worse than the strategy above! The average "burden" that we add to the other vases just isn't large enough compared to the random variation in the number of tokens per vase.
We will need to take advantage of our inspection ability, but when should we use it? There is not much value in inspecting early on in the lottery, since relatively few tokens will have been placed. On the other hand, if we inspect too late, we may not have enough nights left on which to react to whatever information we discover.
We can devise a version of our first approach that also incorporates inspection. In this approach, V and N are parameters that we will have to discover:
We might worry that our inspections are only snapshots in time that grow stale. By the time we inspect vase 20, our estimate for vase 1 is already out-of-date — what if more tokens have been added to it since then? To compare the estimates a little more fairly, we could adjust them by the expected number of tokens that have been added since the night of the estimate (i.e., the number of additional nights, divided by 20). This adjustment will be at most .95, which is less than a single full token, so the adjustments could only possibly be used to break ties among vases with the same number of tokens... and we can get the same effect by just choosing the vase with the highest-numbered ID in the event of a tie.
It is not too hard to simulate this process, so we can try out different values of V and N to see what yields the best results, and find that V = 14, N = 60 works about 95% of the time. That gives us, per the binomial distribution, about a 99.96% chance of solving at least 225 out of 250 cases correctly. Since the problem only has one Visible test set, we should just submit and hope for the best!
If we want to experiment further, there are even better solutions out there! Here is a variant of the above strategy; it succeeds over 98% of the time:
If we hang onto two candidates, it is less likely that both of them will accumulate a lot of tokens via bad luck during the second sabotage phase. We benefit from delaying our decision point for as long as possible, while still leaving enough time to deal with our runner-up.
Let wC be the atomic weight of Codium and wJ be the atomic weight of Jamarium according to the rules given in the problem statement. Let ΔCi equal Ci + 1 - Ci and ΔJi equal Ji + 1 - Ji, for all 1 ≤ i < N. As in our analysis for New Elements, Part 1, we have:
Therefore, we can get the lower bound and upper bound of wJ / wC just by looking at consecutive indices. We can initially set the lower bound (let us represent it with the reduced fraction LN / LD) to be 0 and the upper bound (let us represent it with the reduced fraction UN / UD) to be ∞. We update either LN / LD or UN / UD for each pair of consecutive indexes, just as in our analysis from Part 1.
Once we have LN / LD and UN / UD, we want to find a rational number wJ / wC such that LN / LD < wJ / wC < UN / UD. If LN / LD ≥ UN / UD, then there is certainly no solution. Otherwise, there must be at least one solution; for example, the mediant (LN + UN) / (LD + UD) is certainly between the bounds. However, the problem asks us to minimize wC and wJ (first wC, and then wJ).
Since ΔJi ≤ 99 in this test set, we get LD + UD ≤ 198. Therefore, we know that a solution with wC ≤ 198 exists. We can try all possible values from 1 to 198 as wC. For each choice of wC, we can derive the smallest wJ such that LN / LD < wJ / wC, and then we can check whether wJ / wC < UN / UD.
For each integer C (from 1 to LD + UD), we can check whether there is a rational number that is strictly between LN / LD and UN / UD, and has a denominator that is not more than C. To do that, we can find a rational number with denominator not more than C closest to the average of LN / LD and UN / UD. This is because all rational numbers that are strictly between LN / LD and UN / UD are closer to the average of LN / LD and UN / UD than all rational numbers that are not strictly between LN / LD and UN / UD. We can do so by using a library function like Python's fractions.limit_denominator, or by implementing our own approximation using continued fractions.
Once we can solve the problem given in the previous paragraph, we can use binary search to find wC as the smallest C such that a rational number with denominator not more than C, and strictly between LN / LD and UN / UD exists. Just as we did for the previous test set, we can derive the smallest wJ such that LN / LD < wJ / wC.
In Test Set 1 everything is small. One possible solution is to simulate the process. There is never a reason to not convert elements other than lead, so we should just apply the transformations over and over until no more lead can be created. If after a long time the amount of lead keeps growing, that means the total is unbounded. In the Test Set 2 section we do a formal analysis on bounds, but for this one, using an intuitive definition of "a lot" should suffice. If the amount is bounded, 1 gram of a metal can transform into at most 512 grams of lead, since it can only go through 9 splits before getting into a cycle. That means if we ever see more than 5120 grams of lead, the amount is unbounded.
However, the first example shows that we need to do a little more. What if lead itself can be used to get more lead? If that's possible, and we can get any lead at all, the final amount is definitely unbounded. If it is not possible, then we have no reason to ever consume lead. One way to check is to do the simulation above starting with 1 gram each of the two elements that lead is turned into. If that leads to 0 or 1 grams of lead, then lead cannot be used to get more lead. Otherwise, it can.
Test Set 2 is a lot larger, so a hand-wavy analysis and implementation will not work. However, we can use the same idea above more carefully. Since each metal takes at most M steps to turn into lead, we only need to do M iterations of a simulation, where a simulation involves going over all non-lead metals and converting all grams of them. This takes O(M2) time. To prevent the numbers from growing too big, we can simply do this process twice: the first pass creates as much lead as possible from non-cyclical sources, so if the second pass creates even more, then it must come from cyclical sources that ultimately yield an unbounded amount of lead. The second part, to check for lead creating more lead, is the same as before.
Notice that the result does not fit in 64 bit integers, though, and doing modulo all the time as usual doesn't work right away, since we cannot afford to equate "no X" with "109+7 grams of X" if X has the capability of creating unbounded amounts of lead (with X being lead itself, or some other metal). There are multiple ways to get around the problem, including using big integers, storing an additional bit for each result that represents whether it is an actual 0 value, and doing calculations modulo 109+7 × K for some large random prime K until the very end.
There are other solutions that only work for Test Sets 1 and 2, that are less efficient implementations of the solution for Test Set 3, that is explained below.
For Test Set 3, the solution looks quite different but it is actually similar. We check for cycles that may generate unbounded lead, and if there are none, we can do the simulation with a single iteration, ordering the metals appropriately. All of those things can be done in linear time, and we describe how below.
One useful thing to notice early on is that if we can determine that the amount of lead we can produce is bounded, the only formulas that are worth using are those that can eventually (perhaps in conjunction with other formulas) produce lead. Moreover, if the amount of lead is bounded, there is no point in using lead as an input to any formula, because even in the best case, every unit of lead will turn into one unit of lead and one unit of something else that cannot be converted to lead. (Otherwise, we could simply apply that series of formulas and generate as much lead as we want).
These observations imply that we can only get an unlimited amount of lead if some metal can produce itself and lead at the same time. In other words, there must be a series of formulas that takes one unit of some metal X and turns it into one unit of X and one unit of lead. In the process, we may end up with some other metals as well, but those don't matter. Notice that if that metal X directly produces metals A and B, then we require that either A produces X and B produces lead, or vice versa. This is because even if X is lead itself and either of A or B is also lead, without considering the other result, we are just destroying 1 unit of lead to get 1 unit of lead, so the total amount of lead doesn't change. In other words, in the unbounded case, after applying each formula, we need to work on both of the outputs, not just one of them.
Let Q be a graph in which each metal is represented by a node, and there is an edge from node u to node v if, by consuming 1 unit of u, we can produce 1 unit of v. Notice that if a metal i is initially not present (that is, Gi = 0), and it is not reachable in Q from some j with Gj > 0, then it is impossible to produce metal i. Therefore, we can remove any such metals at the outset. In what follows, we assume that Q contains no such metals.
Let Q' be the transpose of Q, and let L denote the node representing lead. Then, traversing Q' from node L defines a subgraph Q'L, where every node is a metal that can produce lead after a series of transformations. Now, let Pu be the number of simple paths (paths without cycles) from L to any other node u in Q'L. If the amount of lead is bounded, then Pu is the number of units of lead we can get from every unit of u. This follows from the fact that every (reversed) edge is a valid transformation where we start with 1 unit of some metal and produce 1 unit of some other metal, so along the path, we are using the results of previous transformations and not the very first unit of metal we started with. For example, let Q'L be the following graph:
There are 2 simple paths from 1 to 4, namely, 1 → 2 → 4 and 1 → 3 → 4. Now, 1 unit of metal 4 can be turned into 2 units of lead (1) as follows:
On the other hand, notice that the nodes that form a strongly connected component (SCC) in Q are a set of metals that can produce each other. More formally, if u and v belong to the same SCC, we can produce 1 unit of v from 1 unit of u, and vice versa. With these definitions, we can say that the amount of lead is unbounded if, for some node u in Q with v1 and v2 being the two outputs of node u's formula, either:
Otherwise, there is a limit on the amount of lead we can get, which can be computed by multiplying Pu by the initial number of units Gu for each u in Q'L.
We can compute all the SCCs in O(M) time using Tarjan's algorithm or Kosaraju's algorithm , since both the number of nodes and the number of edges in the graph are linear on M. Walking over the graphs defined above also takes O(M) time, and so does checking the unbounded condition. We can also compute all Pu in O(M) time by taking advantage of the fact that if the amount of lead is not unbounded, then there are no cycles in Q'L. (If a cycle existed in Q'L, then by reversing the edges, we get at least one metal for which the unbounded condition holds.) Therefore, the nodes on Q'L can be topologically sorted. That means we can compute a function F from vertices to the number of simple paths in linear time, using dynamic programming with this recursive definition:
Since the number of edges in every graph described above is also O(M), the whole problem can be solved in linear time.