Round 1A is over, and it had a particularly tough C problem; only 124 contestants attempted the Large, and only 8 got it right! Believe it or not, this was not the most brutally difficult Round 1 problem in Code Jam history; that (dubious?) honor still goes to Pseudominion from Round 1A 2011.
Fortunately, problems A and B (and the Small of Problem C) were far more approachable. To advance, you needed to either get more than 56 points (e.g., by solving A, B, and C-small), or get 56 points by solving A and B with a total penalty time around two hours.
Alphabet Cake was a reminder that the GCJ staff is aware of forms of cake other than pan"cake"s. It allowed various approaches, including a nifty recursive one. Ratatouille was another food-related problem (we must have been unusually hungry this year!), and it involved wrangling ratios in recipes. Finally, Play the Dragon presented a game in which coming up with the right strategy would get you the Small, but only very careful implementation and attention to detail would slay the dreaded Large!
Congratulations to our top 1,000 in this round, who advanced to Round 2, and to Eryx, our winner, who finished with a commanding 40-minute lead over the field! (pperm, xyz11, Nore, kmjp and mk.al13n also pulled off perfect scores.) Even if you didn't advance, we still have Rounds 1B and 1C remaining. As usual, we encourage you to take a look at the analyses to check out our approaches and commentary.
Cast
Problem A (Alphabet Cake): Written by Pablo Heiber. Prepared by Jackson Gatenby and Lalit Kundu.
Problem B (Ratatouille): Written by Pablo Heiber. Prepared by Shane Carr.
Problem C (Play the Dragon): Written by David Arthur, Steve Thomas, and Ian Tullis. Prepared by John Dethridge.
Solutions and other problem preparation and review by Liang Bai, Md Mahbubul Hasan, Taman (Muhammed) Islam, Michael McMullen, Petr Mitrichev, Rohan Mukkamala, Igor Naverniouk, Dong Xiao, and Josef Ziegler.
Analysis authors:
You are catering a party for some children, and you are serving them a cake in the shape of a grid with R rows and C columns. Your assistant has started to decorate the cake by writing every child's initial in icing on exactly one cell of the cake. Each cell contains at most one initial, and since no two children share the same initial, no initial appears more than once on the cake.
Each child wants a single rectangular (grid-aligned) piece of cake that has their initial and no other child's initial(s). Can you find a way to assign every blank cell of the cake to one child, such that this goal is accomplished? It is guaranteed that this is always possible. There is no need to split the cake evenly among the children, and one or more of them may even get a 1-by-1 piece; this will be a valuable life lesson about unfairness.
The first line of the input gives the number of test cases, T.
T test cases follow. Each begins with one line with two integers
R and C. Then, there are R more lines of C
characters each, representing the cake. Each character is either an
uppercase English letter (which means that your assistant has already added
that letter to that cell) or ? (which means that that cell is
blank).
For each test case, output one line containing Case #x: and
nothing else. Then output R more lines of C characters each.
Your output grid must be identical to the input grid, but with every
? replaced with an uppercase English letter, representing that
that cell appears in the slice for the child who has that initial. You may
not add letters that did not originally appear in the input. In your grid,
for each letter, the region formed by all the cells containing that letter
must be a single grid-aligned rectangle.
If there are multiple possible answers, you may output any of them.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
There is at least one letter in the input grid.
No letter appears in more than one cell in the input grid.
It is guaranteed that at least one answer exists for each test case.
1 ≤ R ≤ 12.
1 ≤ C ≤ 12.
R × C ≤ 12.
1 ≤ R ≤ 25.
1 ≤ C ≤ 25.
3 3 3 G?? ?C? ??J 3 4 CODE ???? ?JAM 2 2 CA KE
Case #1: GGJ CCJ CCJ Case #2: CODE COAE JJAM Case #3: CA KE
The sample output displays one set of answers to the sample cases. Other answers may be possible.
You've discovered it: the ultimate recipe for ratatouille, the famous French dish! You know which ingredients to use, and how many grams of each one to use, in order to make one serving of ratatouille. But you believe that anyone can cook, and so you want to share the recipe with the world... and make some money in the process!
You have ordered some ingredient packages that are easy to ship. Each package contains some amount of one ingredient; different packages may have different amounts even if they contain the same ingredient. For convenience, you ordered the same number of packages of each ingredient.
You would like to use these packages to form as many ratatouille kits as possible to send to customers. A kit consists of exactly one package of each ingredient, and a label with the integer number of servings of ratatouille that the kit makes. Since you do not want to shortchange customers or waste food, each package must contain between 90 and 110 percent (inclusive) of the amount of that ingredient that is actually needed to make the number of servings of ratatouille on the kit's label.
For example, suppose that one serving of ratatouille takes 500 g of tomato and 300 g of onion. Suppose that you have a 900 g package of tomato and a 660 g package of onion. You could form these into a kit that makes two servings of ratatouille. To make two servings, 1000 g of tomato and 600 g of onion are required. Since the 900 g of tomato you have is within [90, 110]% of the 1000 g of tomato required, and the 660 g of onion you have is within [90, 110]% of the 600 g of onion required, this is acceptable. However, you could not say that the kit makes one or three servings of ratatouille, nor could you say that it makes 1.999 servings (the number of servings must be an integer).
Note that there are some sets of packages that could never form a kit. Continuing with our recipe above, if you have a 1500 g package of tomato and an 809 g package of onion, for example, there is no amount of servings that you can make. Three servings would take 1500 g of tomato and 900 g of onion, and the amount of onion is not within the [90, 110]% range. No other integer amount of servings works, either.
You want to share your recipe with as many customers as possible, so you want to produce the maximum number of valid kits. (Of course, each package can be used in at most one kit.) What is the largest number of kits that you can form? Note that you are not required to maximize the total number of servings of ratatouille formed.
The first line of the input gives the number of test cases, T. T test cases follow. Each case consists of the following:
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 maximum number of kits you can produce, as described above.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Ri ≤ 106, for all i.
1 ≤ Qij ≤ 106, for all i and j.
Time limit: 60 seconds.
1 ≤ N ≤ 2.
1 ≤ P ≤ 8.
Time limit: 120 seconds.
1 ≤ N ≤ 50.
1 ≤ P ≤ 50.
N × P ≤ 1000.
6 2 1 500 300 900 660 2 1 500 300 1500 809 2 2 50 100 450 449 1100 1101 2 1 500 300 300 500 1 8 10 11 13 17 11 16 14 12 18 3 3 70 80 90 1260 1500 700 800 1440 1600 1700 1620 900
Case #1: 1 Case #2: 0 Case #3: 1 Case #4: 0 Case #5: 3 Case #6: 3
Note that the last sample case would not appear in the Small dataset.
Sample cases #1 and #2 are the ones described in the problem statement.In sample case #3, you can form a kit out of the 450 g package of the first ingredient and the 1100 g package of the second ingredient, and say that the kit makes 10 servings of ratatouille. That number of servings requires 500 g of the first ingredient; you have 450 g, which is 90% of 500 and within the allowed limit. It requires 1000 g of the second ingredient; you have 1100 g, which is 110% of 1000 and within the allowed limit.
Once you form this kit, however, you cannot form the remaining packages into a kit. 449 g of the first ingredient and 1101 g of the second ingredient would not be able to form 10 (or any other number of) servings. In fact, the (450 g, 1100 g) kit is the only kit that can be formed from these packages.
In sample case #4, no kits can be formed. Note that the recipe requires particular amounts of particular ingredients in the given order; the ingredients are not interchangeable. This is fine French cuisine, after all!
In sample case #5, the recipe has only one ingredient — how elegantly simple! A single serving cannot use more than 11 g, and two servings cannot use fewer than 18 g. It is possible to form three kits: two with an 11 g package, and one with an 18 g package.
In sample case #6, you can form three valid kits: (700 g, 800 g, 900 g), which makes 10 servings, and (1500 g, 1600 g, 1700 g) and (1260 g, 1440 g, 1620 g), each of which makes 20 servings. Note that you could also say that the (1260 g, 1440 g, 1620 g) kit makes 17, 18, or 19 servings, but it does not matter how many servings a kit makes as long as the kit is valid.
You are a friendly dragon fighting to protect your lair from a greedy knight! You have Hd health points and an attack power of Ad, and the knight has Hk health points and an attack power of Ak. If your health drops to 0 or below at any point; you are knocked out and you instantly lose; if the knight's health drops to 0 or below at any point, the knight is knocked out and you win!
You will battle the knight in a series of turns. On each turn, you go first, and you can choose and execute any one of the following actions.
Then, if the knight's health is greater than 0 following your action, the knight will execute an Attack action. After that, the turn ends. (Note that a turn in which you defeat the knight still counts as a turn even though the knight does not get to act.)
Note that buffs stack with each other; every buff adds an additional B to your attack power. Similarly, debuffs stack with each other.
You would like to defeat the knight as fast as possible (if it is possible) so that you will not be late to help the villagers roast marshmallows at tonight's festival. Can you determine the minimum number of turns in which you can defeat the knight, or that it isIMPOSSIBLE to do so?
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with six integers Hd, Ad, Hk, Ak, B, and D, as described above.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is either IMPOSSIBLE if it is not possible to defeat the knight,
or the minimum number of turns needed to defeat the knight.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
Time limit: 60 seconds.
1 ≤ Hd ≤ 100.
1 ≤ Ad ≤ 100.
1 ≤ Hk ≤ 100.
1 ≤ Ak ≤ 100.
0 ≤ B ≤ 100.
0 ≤ D ≤ 100.
Time limit: 240 seconds.
1 ≤ Hd ≤ 109.
1 ≤ Ad ≤ 109.
1 ≤ Hk ≤ 109.
1 ≤ Ak ≤ 109.
0 ≤ B ≤ 109.
0 ≤ D ≤ 109.
4 11 5 16 5 0 0 3 1 3 2 2 0 3 1 3 2 1 0 2 1 5 1 1 1
Case #1: 5 Case #2: 2 Case #3: IMPOSSIBLE Case #4: 5
In Case #1, you have 11 health and 5 attack, and the knight has 16 health and 5 attack. One possible optimal sequence of actions is:
In Case #2, one possible optimal sequence of actions is:
In Case #3, the knight only needs two attacks to defeat you, and you cannot do enough damage fast enough to defeat the knight. You can indefinitely extend the combat by executing the Cure action after every attack, but it is impossible to actually defeat the knight.
In Case #4, one possible optimal sequence of actions is: Attack, Debuff, Buff, Attack, Attack.
In the Small dataset, the cake can consist of at most 12 units. A viable brute-force strategy is to try all ways of filling in every blank cell with each letter already appearing on the cake. If L letters are already present, then we have L possibilities for each of the remaining 12-L cells. Then, the number of combinations to try is L(12-L), which is a lot less than 1212. In this case, since L can range from 1 to 12, inclusive, the maximum value that this can take is 57 = 78125, which is a pretty small number for a computer.
One way to check a cake is to first make one pass through the cake, going left-to-right, top-to-bottom, and find each letter's upper leftmost position, lower rightmost position, and frequency. Then, for each letter, check that the rectangle defined by the upper leftmost position and lower rightmost position contains only that letter, and that its area equals the frequency count.
Another possible strategy is to start at a letter, draw a bounding box around
it that includes only ?s, move on to another letter, and so on.
In the Small dataset, there are relatively few choices for how to draw these
bounding boxes. As long as you use other pre-existing letters to prune the
possible bounding boxes for each letter, and you carefully check for overlaps
and unused cells, an exhaustive search should be fast enough.
There are non-exhaustive strategies similar to this that have the potential to fail, though. Consider this algorithm: for each letter, start with a 1-by-1 bounding box containing only that letter. Stretch the box as far as it will go to the top and bottom without hitting other letters, then stretch the box as far as it will go to the left and right without hitting other letters. Depending on the order in which you handle the letters, this can fail. For example, consider this case:
A?B
C??
??D
?EF
If the algorithm proceeds in left-to-right, top-to-bottom order, it will
fill up the grid as follows, leaving an unfilled ?:
AAB
C?B
CDD
CEF
Fittingly enough for a problem about cake, there is a simple divide-and-conquer strategy for the Large dataset. If the cake has only one letter on it, we can fill it up with that letter. Otherwise, we can make a horizontal or vertical cut that divides the cake into two sub-cakes, such that each part has at least one letter on it; this creates two more instances of the same problem. It is always possible to do this if there are at least two letters on the cake; one surefire way is to make a dividing cut that includes the right border of the leftmost of a pair of letters, or, if they are in the same column, the bottom border of the topmost of the pair.
There is a simple non-recursive approach as well. First, within each row, we can extend each existing letter into all cells to the right of that letter, until we reach another existing letter or the edge of the cake. Then, we can extend the leftmost existing letter (if any) into all cells to the left of that letter.
At this point, any rows that had no existing letters are still empty. We can make a pass through the grid from the second row to the bottom row, replacing each empty row with the row above it. Then we can make one more pass from the next-to-last row up to the top row, replacing each empty row with the row below it.
It is not difficult to prove that it is impossible for this strategy to produce a non-rectangular region for a letter, to produce disjoint regions for a letter, or to leave any cell unfilled.
The number of grams in a given package is not important in and of itself; what is important is which multiples of the recipe that package could be used in. If the base recipe requires 10 g of tomato, for instance, then a 201 g package of tomatoes can be used to make 19, 20, 21, or 22 times the recipe, but not any other multiple. So we can think of this package as the inclusive range [19, 22].
How can we find these ranges? Let Q be the amount in the package and R be the amount of that ingredient required by the base recipe. Then any allowable multiple m must satisfy both 0.9 × R × m < Q and Q < 1.1 × R × m. Simplifying and rearranging this, we get (10/11) × (Q/R) < m < (10/9) × (Q/R); any integer value of m that satisfies this inequality is part of the range, and we can find the lower and upper bounds of this range in constant time. (Note that a range might not include any integer values, e.g., for R = 10 and Q = 15.) It is possible to use integer division here and avoid floating point numbers entirely.
In the Small dataset, there can be at most two ingredients. If there is one ingredient, the problem is very simple: each package with a non-empty range (as described above) forms a kit, and each package with an empty range does not.
What if there are two ingredients? Then we need to pair up the packages into kits, but we must be careful, since not any assignment will be optimal. For example, suppose our recipe requires 5 g of A and 10 g of B, and we have the following packages: 45 and 50 of A, and 110 and 111 of B. Converting these to ranges, we get [9, 10] and [10, 11] for A, and [10, 12] and [11, 12] for B. If we pair the [10, 11] package of A with the [10, 12] package of B, then we will be left with a [9, 10] package of A and an [11, 12] package of B, and those cannot be paired. However, we can make two kits by pairing the [9, 10] package of A with the [10, 12] package of B, and the [10, 11] package of A with the [11, 12] package of B.
We could solve the problem via bipartite matching, but it is not needed. Since there can be at most 8 packages of each ingredient in the Small, it is possible to use brute force to try all 8! possible matchings and find the largest number of kits that can be formed.
The following greedy strategy works for the Large, for any number of ingredients:
This strategy would not necessarily be optimal for arbitrary ranges, but it is in this case thanks to the following property: if I1 and I2 are the ranges of valid multipliers for the same ingredient, and I1 is included in I2, then I1 and I2 have at least one endpoint in common. This is not hard to prove: if Ii comes from an original packet of size Si, if S1 ≤ S2, then the lower bound of I1 must be no greater than the lower bound of I2. Otherwise, S1 > S2, so the upper bound of I1 must be no less than the upper bound of I2. Let us call this property 0.
We need some preliminary properties of our greedy algorithm before the main proof:
Now we can combine all those properties and proceed by contradiction. Let M1, M2, ..., Mk be the smallest multipliers of the kits produced by our greedy algorithm, in non-decreasing order. Let N1, N2, ..., Nk, Nk+1 be the smallest multipliers of an assignment that produces one more kit, in non-decreasing order.
We can implement this strategy with a separate list for each ingredient, sorted first by nondecreasing lower end of range and then by nondecreasing upper end of range. We keep looking at the set of earliest ranges of the lists. If they all have an intersection, make them into a kit and remove them. Otherwise, remove the least useful range (the one with the smallest upper limit). We can speed this process up by using a priority queue, but with N × P ≤ 1000, such optimizations are not necessary.
The Small limits are large enough to foil pure simulation of all possible choices, so we need to have some insights before proceeding.
These observations add up to a strategy: spend some number D' of turns debuffing, then some number B' of turns buffing, then some number A' of turns attacking, and interleave cures only as needed to not be defeated. Since B' determines A', we only need to consider (D', B') pairs. Since Ak cannot exceed 100, there is no reason to ever do more than 100 debuffs or 100 buffs; moreover, the worst-case scenario can't possibly require more than a couple hundred turns (D' + B' + A'). We can place much smaller upper bounds than those with a little more thought, but it is already clear that direct simulation should be fast enough for the Small dataset.
So, we can proceed with translating the above strategy into code. We must take care to prioritize actions in the right order. In particular, we must avoid curing when we do not need to or failing to cure when we should. Once that is written, we can simulate each possible (D', B') pair and find the global minimum number of turns, or determine that the case is IMPOSSIBLE.
We noted above that all debuffs should come before all buffs/attacks, and that the number of buffs determines the number of attacks. In fact, the buff/attack part of the problem is independent of the debuff part of the problem. Changing the number of debuffs may change the number of cures, but regardless of how many times we debuff, we have nothing to gain by using more than the minimum number of buff + attack turns; that would just make us waste more turns curing.
We can find this minimum number of buff + attack turns as follows. First, we suppose that we will buff 0 times, and we determine the total number of attacks needed to defeat the knight. Then, we can repeatedly increase B' by 1 and calculate the number of attack turns A' required at that new level of attack power. As soon as this causes the total to get larger, we can stop (and take the previous total). It is safe to stop at that point because the total number of turns is given by
B' + ceil(Hk / (Ad + B' × B))
The B' part contributes a line with positive slope; the rest contributes a decaying step function. If that step function were a smooth curve, there would be one point at which the rate of decrease from the curve exactly matched the rate of increase from the linear part, and the function would take on our desired minimum there. Because of the discretization, there may actually be multiple values of B' that yield the minimum number of B' + A' turns, but it does not matter which one we choose; only the total matters.
Finding the minimum B' + A' in this way takes O(sqrt(N)) time, where N is the common upper limit for all of the parameters (109 for the Large). This is because once we have raised B' to about sqrt(N), we can defeat the knight in about sqrt(N) attack rounds, and there is no need to buff further. It is also possible to solve this part of the problem using binary search or ternary search, or by solving a quadratic equation.
What about the number D' of debuffs? The key observation here is that we do not need to consider every possible value of D'. For instance, suppose that Hd is 100, Ak = 50, and D = 1. Reducing Ak to 49 (which takes 1 turn of debuffing) is as good as reducing Ak to 48 or 34; in all of these cases, the dragon has to cure every other turn. However, reducing Ak to 33 (which takes 17 turns of debuffing) means that the dragon only has to cure on every third turn. We might as well only consider these threshold values of D' = 0, 1, 17, 26, 31...; we can leave out the others. We can find each of these values formulaically in constant time.
Once we have these values, we do not even need to simulate them independently. Note that a simulation with D' = 17 begins by looking like a simulation with D' = 1, since we have to do one debuff before we do the other sixteen. So we can perform a single simulation in which we keep track of a number T of turns used so far, and repeat the following:
It takes additional turns to debuff more, but that debuffing may "pay for itself" by saving curing turns during the buff + attack phase. Our strategy will find the right balance.
Instead of actually simulating the turns, we can take advantage of the way we have chosen threshold values of D': in the debuffing period between two of our values of D', the frequency of curing remains constant. So we can calculate the total number of debuff turns + cures via a formula, and we can do the same for the number of cures in the buff + attack phase. With this optimization, the complexity of this step is O(sqrt(N)); since we also took O(sqrt(N)) time to find the optimal number of B' + A' turns, the algorithm is O(sqrt(N)) overall.
All that remains is to actually implement the above, which is perhaps even harder than coming up with the algorithm; there are many opportunities to make off-by-one errors! Although this is not generally the case in Code Jam, in this particular problem, the limits do allow solutions with some but not all of the above insights, and additional low-level optimizations, to pass within the 8-minute window.