Round 1B started off with Rounding Error, which explored a phenomenon that often arises when interpreting poll results. A greedy insight was required to solve the third test set. Mysterious Road Signs challenged contestants to understand a strange situation involving signpost numbering. Finally, Transmutation was a tough graph problem about producing as much lead as possible; contestants had to narrow down the set of possible choices in an efficient way.
This round proved to be really tough for a Round 1. None of the problems was really easy in the way some Round 1 problem usually is. To add to that, 2 out of 3 problems had an extra test set, making a perfect score even harder to attain. We had rounds in the past with few perfect scores, but they were usually due to a single particularly hard problem. This round featured a good number of solutions for each problem individually, but a relatively low number of 37 perfect scores. overtroll was the first to get there in just under an hour with no penalty attempts, to claim first place.
In the end, 25 points and some speed and accuracy was needed to get into the top 1500. In most cases, that means solving Rounding Error, but you would also advance with a full solution of any of the other two problems. It was even possible to advance with just visible points, if you managed to get some points from every problem.
1500 more contestants have advanced to Round 2, and there are 1500 more spots available in Round 1C, coming up in a week. Good luck!
Cast
Rounding Error: Written by Ian Tullis. Prepared by Micah Stairs.
Mysterious Road Signs: Written by Md Mahbubul Hasan. Prepared by Shane Carr and Jonathan Irvin Gunawan.
Transmutation: Written by Pablo Heiber. Prepared by Pablo Heiber and Ian Tullis.
Solutions and other problem preparation and review by Liang Bai, Shane Carr, John Dethridge, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Jason Shao, Micah Stairs, and Erick Wong.
Analysis authors:
To finally settle the age-old question of which programming language is the best, you are asking a total of N people to tell you their favorite language. This is an open-ended question: each person is free to name any language, and there are infinitely many languages in the world.
Some people have already responded, and you have gathered this information as
a list of counts. For example, 1 2 means that you have asked 3
people so far, and one picked a particular language, and the other two picked
some other language.
You plan to publish the results in a table listing each language and the percentage of people who picked it. You will round each percentage to the nearest integer, rounding up any percentage with a decimal part equal to or greater than 0.5. So, for example, 12.5% would round up to 13%, 99.5% would round up to 100%, and 12.4999% would round down to 12%.
In surveys like this, sometimes the rounded percentages do not add up to exactly 100. After you are done surveying the remaining people, what is the largest value that the rounded percentages could possibly add up to?
The first line of the input gives the number of test cases, T. T test cases follow; each consists of two lines. The first line consists of two integers N and L: the total number of people in the survey, and the total number of different languages represented among the people who have already responded. The second line consists of L integers Ci; the i-th of these is the number of people who said that the i-th of the represented languages was their favorite.
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 largest value that the percentages could possibly add up to, as
described above.
1 ≤ T ≤ 100.
1 ≤ L < N.
1 ≤ Ci, for all i.
The sum of all Ci values < N.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
2 ≤ N ≤ 25.
2 ≤ N ≤ 250.
2 ≤ N ≤ 105.
4 3 2 1 1 10 3 1 3 2 6 2 3 1 9 8 1 1 1 1 1 1 1 1
Case #1: 100 Case #2: 100 Case #3: 101 Case #4: 99
In Sample Case #1, two people have already responded, and they have chosen different languages. One person has not yet responded. If that person chooses a third language, then the rounded percentages will add up to 33 + 33 + 33 = 99. However, if that person chooses one of the already-chosen languages, then the rounded percentages will add up to 67 + 33 = 100. So 100 is the maximum possible sum.
In Sample Case #2, regardless of what the other four people choose, the percentages for the various languages will always be exact multiples of 10 that do not need to be rounded, and they will add up to exactly 100.
In Sample Case #3, one optimal scenario is as follows: each of the remaining two people chooses an unchosen language, so the rounded percentages add up to 50 + 17 + 17 + 17 = 101.
In Sample Case #4, whether or not the remaining person chooses an already-chosen language, the rounded percentages will add up to 99.
The town of Signfield is on a perfectly straight and infinitely long road running from west to east. Along that road, there is a sequence of S mysterious road signs with numbers on both sides. The i-th sign (numbered in order from west to east) is at a point Di kilometers east of Signfield, and has a number Ai on the west-facing side and a number Bi on the east-facing side.
Nobody in Signfield knows what these signs are trying to say. You think that the numbers on the west sides of the signs are intended for drivers traveling east, and that they represent distances to some particular destination. Similarly, you think that the numbers on the east sides of the signs are for drivers traveling west, and that they represent distances to some particular destination. You suspect that not all of the signs may be consistent with this theory, though.
To start testing your theory, you are interested in finding valid sets of signs that obey the following rules:
What is the largest possible number of signs in a valid set as described above, and how many different valid sets of that size are there?
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing one integer S: the number of road signs. Then, S more lines follow. The i-th of these lines represents the i-th sign (in west-to-east order), and contains three integers Di, Ai, and Bi: the sign's distance (in kilometers) east of Signfield, the number on its west side, and the number on its east side.
For each test case, output one line containing Case #x: y z,
where x is the test case number (starting from 1), and
y and z are the largest possible number of signs
in a valid set and the number of valid sets of that size, as described in
the problem statement.
1 ≤ T ≤ 60.
1 ≤ Di ≤ 106, for all i.
Di < Dj, for all i < j.
1 ≤ Ai ≤ 106, for all i.
1 ≤ Bi ≤ 106, for all i.
Time limit (for each test set): 10 seconds.
Memory limit: 1GB.
1 ≤ S ≤ 100 for all test cases.
1 ≤ S ≤ 100 for all but 3 test cases.
S = 105 for 3 test cases.
3 1 1 1 1 5 2 7 12 6 3 11 8 10 1 11 11 12 13 9 14 5 1 3 3 2 2 2 3 1 1 4 2 2 5 3 3
Case #1: 1 1 Case #2: 3 2 Case #3: 5 1
In Sample Case #1, there is only one sign. If we choose just that sign as our set, there are many possible values of M and N that work — for example:
So, the set consisting of just that one sign is valid. That is the only set
of that length, so the answer is 1 1.
In Sample Case #2, note that the first, second, fourth, and fifth signs would be consistent with M = 9 and N = -1, but they do not form a contiguous subsequence. (The 1 on the back of the third sign cannot be used as if it were on the front.) As it turns out, there is no valid set of four signs. There are two different valid sets of three signs. Note that although there are two different M/N pairs that make the second set of three signs valid, that set counts only once:
In Sample Case #3, the entire sequence is a valid set, with M = 4 and N = 2.
You are the most skilled alchemist of a country that considers metals such as gold, platinum, and silver to be uninteresting, but highly values 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 metal in the treasury to make as much lead as possible.
For each metal (including lead), you know exactly one formula that lets you create one gram of that metal by destroying one gram each of two ingredient metals. (If you are wondering about the principle of mass conservation, the other gram is lost in useless waste 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 the required ingredients each time.
If you make optimal choices, what is the largest total amount of lead you can end up with? Note that it is possible that you may have some metals other than lead left over after you are done.
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 indicates that you can create one gram of metal i by destroying 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) and y
is the largest amount of lead, in grams, that you can end up with.
1 ≤ T ≤ 100.
1 ≤ Ri1 < Ri2 ≤ M,
for all i.
Time limit: 5 seconds per test set.
Memory limit: 1GB.
2 ≤ M ≤ 8.
0 ≤ Gi ≤ 8, for all i.
2 ≤ M ≤ 100.
0 ≤ Gi ≤ 100, for all i.
2 ≤ M ≤ 100.
0 ≤ Gi ≤ 109, for all i.
3 3 2 3 1 3 1 2 5 2 3 5 3 4 3 4 4 5 3 5 1 3 0 8 6 2 4 4 3 4 2 3 2 3 2 3 0 1 1 0
Case #1: 7 Case #2: 4 Case #3: 0
In Sample Case #1, the optimal strategy is to use 2 grams of metals 2 and 3 to produce 2 more grams of lead, for a total of 7 grams of lead.
In Sample Case #2, the optimal strategy is to first use 2 grams of metal 3 and 2 grams of metal 5 to produce 2 grams of metal 4, and then use 4 grams of metal 3 and 4 grams of metal 4 to produce 4 grams of lead. Note that it is possible for two formulas to have the same two ingredients (you just use different alchemical techniques). Also note that not every metal is necessarily an ingredient in some other formula; in this case, metal 2 is never an ingredient.
In Sample Case #3, note that it is possible for a metal to be used to produce itself. (Sometimes the laws of alchemy may be silly!) Unfortunately, it is not possible to produce any lead in this case. Note that since formulas only work on single-gram quantities, you cannot, for example, use 0.5 grams of each of metals 2 and 3 to create 0.5 grams of metal 4, and then use 0.5 grams of each of metals 3 and 4 to create 0.5 grams of lead.
This test set can be solved using a complete search. We can try every possible partition of N voters among N languages. If two partitions differ only in the order of their languages, then we consider those partitions equivalent.
Therefore, we can consider a partition as an N-tuple (x1, x2, ..., xN), where xi ≥ xi + 1 and Σ xi = N.
Even with N = 25, there are no more than 2,000 different partitions. For each partition, we can use the following greedy algorithm to check whether the partition can be achieved by only adding voters: let us sort the Ci values in non-increasing order — that is, such that Ci ≥ Ci + 1. Then the partition can be achieved by only adding voters if and only if xi ≥ Ci for all 1 ≤ i ≤ L. Among all such partitions, we can find the largest percentage sum, which is our answer.
For this test set, we can remove our assumption that a partition and C must be sorted non-increasingly. Therefore, we consider a partition of N voters to N languages as (x1, x2, ..., xN), where Σ xi = N.
To solve this test set, we can use dynamic programming (DP). We define a function f(a, b) as the following:
Among all partitions (x1, x2, ..., xa) such that Σ (1 ≤ i ≤ a) xi = b and xi ≥ Ci for all 1 ≤ i ≤ a, what is the maximum Σ (1 ≤ i ≤ a) round(xi / N × 100) possible? If there is no satisfying partition, then f(a, b) = -∞. We can assume Ci = 0 for i > L.
We can first handle the base case of the function. We can easily compute f(1, b) since there is only at most one satisfying partition. Therefore, f(1, b) = round(b / N × 100) if b ≥ C1, or -∞ otherwise.
The recurrence f(a, b) of this function can be computed by considering all possible values of xa. Let i be the value of xa. Therefore, xa contributed round(i / N × 100) to the total percentage, and there are (b - i) votes left to be distributed among x1, x2, ..., xa - 1. Therefore, for a > 1, f(a, b) = max (Ca ≤ i ≤ b) (round(i / N × 100) + f(a - 1, b - i)).
Since we want to distribute N voters to x1, x2, ..., xN, the answer for the problem is f(N, N).
Function f has O(N2) possible states and each state takes O(N) time to compute. Therefore, this solution runs in O(N3) time.
We can solve this test set with a greedy strategy. For each language, we will either be rounding the percentage up or down. We get the maximum answer when as many of these as possible are rounded up.
Therefore, we can ignore any languages that are already being rounded up. Since there can be arbitrarily many languages, nothing ever forces us to disturb these languages by adding another vote—it's no worse to add that vote to some new language instead. We figure out how many more votes each language (including languages nobody has even mentioned yet) would need in order for it to be rounded up.
We greedily satisfy as many of these as possible, starting with the ones that take the fewest additional votes. This solution runs in O(N × log(N)) time.
First, let's break down what the problem is asking us to find. We are asked to identify sets of contiguous signs, where each set is defined by four variables:
In order for a set to be valid, each sign in the set must be truthful to eastbound travelers, westbound travelers, or both. Given the four variables above, we can evaluate a set of signs for validity in O(j–i) time. We can bound the number of possible values for M and N by S by taking the set of all westbound or eastbound destinations displayed by at least one sign. Since i and j are also bounded by S, we would need O(S5) time for this solution, which is not sufficient for Test Set 1.
To improve our brute-force solution, we can be more clever with how we pick M and N. The first sign in a set tells us a lot of information: namely, it defines what either M or N must be (one of the two destinations on the sign, or else the sign wouldn't be able to be in the set). Suppose we fix M based on the first sign. Now, we can walk through the rest of the signs in the set until we find a sign whose eastbound destination is not M; use that sign's westbound destination as N. Continue walking until we reach a sign that does not share either M or N, in which case the set is invalid, or until we reach the end of the set, in which case the set is valid. We can perform the analogous process by fixing N based on the first sign. This “two-pass” set evaluation algorithm runs in O(S) time, since sets have size O(S).
Since there are O(S2) sets of signs and we can evaluate each set for validity in O(S) time, we have a O(S3) algorithm, which is fast enough for Test Set 1.
Clearly the cubic solution won't work on Test Set 2. It turns out that a quadratic solution coded in a fast language with a sufficient amount of pruning can pass Test Set 2. However, in this analysis, we will describe a O(S log S) solution followed by a linear-time O(S) solution, both of which comfortably finish in time when evaluating Test Set 2.
The O(S log S) solution is a classic application of divide and conquer. Cut the list of signs in half, except for a single sign at the center, which we will call the “midpoint” sign. Recursively apply the algorithm to the western half and the eastern half of signs. Then, use a modified version of the previously described two-pass algorithm to find the best set containing the midpoint: first, fix M to the midpoint's eastbound destination. Since we are looking for long segments, we can greedily add as many signs to the set as possible. Walk the list of signs both westward and eastward until reaching a sign on each end that does not share the same eastbound destination (M value) with the midpoint. Let N1 equal the westbound destination of the western boundary (the first sign to the west that did not match M) and let N2 equal the westbound destination of the eastern boundary (the firsts sign to the east that did not match M). Find M1 and M2 using an analogous procedure: return to the midpoint, walk westward and eastward until reaching signs that do not share a westbound destination (N value) with the midpoint, and let M1 and M2 be the eastbound destination of the signs at the western boundary and eastern boundary, respectively. We now have four possible M/N pairs: (M, N1), (M, N2), (M1, N), and (M2, N). We can greedily walk east and west from the midpoint with each of the four pairs to find the longest set containing the midpoint. This “four-pass” step for D&C runs in linear time. Now that we have found the longest set(s) containing the midpoint as well as (recursively) the longest sets from the western and eastern halves of signs, we can combine these results to get the longest sets for the whole dataset. This yields an algorithm requiring T(S) operations to compute an input of size S, for a function T that satisfies T(S) = 2T(S/2) + O(S). Using the Master Theorem we get that T(S) = O(S log S).
The linear-time solution does a single pass, identifying all possible long segments. Start by walking forward from the first sign. Maintain two “candidates”, called the “M-candidate” and the “N-candidate”, with the following properties:
With these invariants, the set of signs starting at start and ending after the current index is guaranteed to be a valid set.
To maintain the invariants when reading a new sign, we can use the following procedure to create the new the M-candidate (the procedure for creating the new N-candidate is analogous):
Consider the following illustration:
The illustration shows six zero-indexed signs and the destinations for those six signs. The signs are connected by lines that show which candidates are used when calculating the candidates for the next step. The candidates after reading the sixth sign (index 5) are shown at the end. On top we have the M-candidate with M=9 and N=2. The candidate starts at index 3, because the sign at index 2 does not have a compatible westbound or eastbound destination for that candidate. The illustration also demonstrates how xstart=5 is the start of the most recent string of westbound destination M matches, which in this case is only the current sign. The N-candidate goes all the way back to start index 1 with M=8 and N=0.
Since calculating the new candidates takes constant time, and we have to read each sign in sequence, this is an O(S) solution.
There are two more tips that can aid in solutions to this problem. First is that we don't ever need to remember Ai, Bi, and Di directly; we only care about the westbound and eastbound destinations. You could therefore compute those destinations upon reading in the data and store them in a list of pairs. The second tip is that there is a lot of opportunity for pruning: if you maintain a global list of the best known sets of signs, you never need to look at any candidate sets that are smaller than the current best, allowing you to prune away a lot of segments that you no longer need to evaluate. All of the solutions described here except for the O(S) solution can take advantage of pruning.
This is a very tricky problem with lots of pitfalls to consider.
Plain brute force is sufficient to pass this data set. There are many ways
to approach it that would work, though. One intuitive approach would be to
create one gram of lead (metal 1) as often as possible.
Suppose Create(i) is a function that takes
a metal i as parameter and returns true if it can create one gram of the
i-th metal and false otherwise. Then, we can call Create(1)
repeatedly until it returns false, and output the number of calls that returned
true. An implementation of Create(i) works as follows:
Create(P) and Create(Q).
However, there is slight problem with the above function. When we are not be able to create metal 1, this function will never end, it will keep trying to create the metals. Consider a simple example: there are 3 metals and for each of them the other two are the ingredients. Suppose, the amount of the metals are now 0 but we are trying to create lead. In such case, it will try to create the other two metals recursively, which will eventually try to create the lead again and so on. One way to fix it would be to check if we tried to create this i-th metal in the current call stack. If we already tried to create the i-th metal and while doing so we looked into its ingredient elements and again arrived at the i-th metal, that means it is not possible to create the i-th metal (and eventually the lead) anymore. Another way that is simpler to code is to limit the depth of the recursive call to M, because after M recursive calls we are guaranteed to repeat at least one metal.
The runtime of the above solution is not very large. The recursive call stack
is up to M calls deep and at each level we call Create twice recursively.
We may imagine it as a binary tree. The number of leaf nodes is at most
2M which makes the total less than 2M+1. So, a
Create(1) call
takes O(2M) time. There may be at most 8 grams of each of these metals.
So we will call Create(1) function about 8M times. For M = 8,
this means the body of the function executes 8 × 8 × 28, which is
not too large.
The approach above is of course too slow for the second test set. We can do a top-down approach as follows: we maintain a current "recipe" to create lead. The initial recipe is just use 1 gram of lead to create 1 gram of lead. The invariant is that the current recipe is always optimal, that is, any other way to create lead that can be done with the current supply is an expansion of the recipe. An expansion of a recipe is the result of zero or more applications of replacing 1 gram of a metal in the recipe by 1 gram of each of the two metals required to make it. This invariant is clearly true for the initial recipe.
As a first step, we make as much lead as we can with the current recipe, which we already mentioned is optimal. After doing that, the supply of one or more of the metals in the recipe is less than the recipe requirements of each. That means that any recipe that works is an expansion of replacing 1 gram of each of those metals for its ingredients. We perform one of those replacements to get a new optimal recipe and repeat.
Notice that the total amount of grams of metal in the recipe only increases and the same number in the supply only decreases or stays the same (if we make no lead in a step). So, when the amount in the recipe surpasses the amount in the supply we can stop, since we won't be able to make another gram of lead.
Let S be the sum of all Gi, that is, the amount of grams of metal in the initial supply. Each step above takes O(M) if we represent the recipe as a vector of size M with the required grams of each metal in the recipe. Checking how much lead we can do requires a single pass to find the limiting ingredient, and finding an ingredient that we need to replace requires another pass. Making the replacement of a single ingredient takes constant time. Since after each step the total amount of grams of metal in the recipe increases by at least 1, and the supply does not increase, the number of steps until the stopping condition is at most S. This makes the running time of this algorithm O(MS) which is enough to pass for M ≤ 100 and S ≤ 10000.
Since S can be up to 1011 for test set 3, we can't really use the approach above. Adding a lot of prunning to it to prevent really long cycles of replacements to happen can work, but it's hard to know exactly how much prunning is required unless we take a systematic approach. Fortunately, using binary search can simplify this a lot. First, we consider the simplified problem of deciding if it is possible to make L grams of lead, for an arbitrary L. If we can solve that efficiently, a simple binary search within the range [0, S] finished the problem, and multiplies the time complexity by a (relatively) small log S.
For a fixed L, we start by adjusting our supply by making the amount of lead G1 - L. That may leave us with lead debt instead of lead supply. We now iterate paying off debt until either we cannot or we have no debt left. If we cannot pay off some debt, then we cannot make L grams of lead. If we find ourselves with no debt left, we can make L grams of lead. While we iterate, we will adjust the supply G and the recipes R, that start as given in the input.
For each step of pay off, find an ingredient i such that Gi < 0. If there are none, we paid off all debt and we are done. If there is, we go through the recipe to make metal i. If the recipe contains metal i itself, we can't pay off the debt and we are done. Otherwise, for each k grams required of metal j in the recipe, we do Gj := Gj + k × Gi (remember Gi is negative). That is, we push the debt of metal i to requiring amounts of metals from its recipe. Finally we can set Gi := 0. If we ever need i in the future, we know we will again need to go through its recipe, so we replace any k grams of i in the recipe of any ingredient by i's recipe multiplied by k. In this way, metal i will never be required in the future.
A step of payoff takes O(M2) time: finding a metal in debt takes time linear on M, and so do adjusting all ingredients (remember we represent recipes by a vector of size M with the grams required for each metal). Replacing metal i in a single recipe takes time linear on M too, and we have to do it for each other of up to M metals, yielding O(M2) time for the step.
During each step of payoff one metal disappears from the recipes. Since at most M - 1 metals can disappear (when there is only one metal i left, its recipe is guaranteed to contain metal i itself and we'll stop, since recipes only grow and thus are never empty) the total number of payoff steps is O(M). This makes the overall time to check an arbitrary L O(M3), and the overall time for the entire algorithm O(M3 log S), which is fast enough to solve the hardest test set.