We must have been hungry when we designed the problems for Round 1A! Waffle Choppers was a slight twist on our usual pancake theme, and it may have looked a bit easier than it really was. Bit Party paid homage to a certain Canadian treat, and could be solved by using binary search in the right way. Finally, Edgy Baking was a problem about cutting cookies, but that didn't mean that contestants had to write a "cookie-cutter" solution! A dynamic programming approach was possible, but there were other possible strategies as well; see our analysis for an interesting one.
Some of our contestants gobbled up these problems rather quickly! vepifanov submitted three correct solutions for a perfect score and the lowest penalty time (34 minutes and 36 seconds). Well over 400 contestants achieved perfect scores!
Under the new Code Jam 2018 rules, 1500 contestants advance from each of the round 1s; the cutoff for this round ended up being 50 points plus enough speed. Those top 1500 contestants from this round are (provisionally) on to Round 2! For everyone else, there are still two more chances to advance: Round 1B and Round 1C. Check out our schedule, and mark your calendars!
Cast
Waffle Choppers: Written by Pablo Heiber and Ian Tullis. Prepared by Micah Stairs.
Bit Party: Written by Pablo Heiber. Prepared by Jonathan Irvin Gunawan.
Edgy Baking: Written by Kevin Tran. Prepared by Micah Stairs.
Solutions and other problem preparation and review by Liang Bai, Shane Carr, Md Mahbubul Hasan, Roman Obukhivskyi, Ray Robinson, and Regis Schiavi.
Analysis authors:
The diners at the Infinite House of Pancakes have gotten tired of circular pancakes, so the chefs are about to offer a new menu option: waffles! As a publicity stunt, they have made one large waffle that is a grid of square cells with R rows and C columns. Each cell of the waffle is either empty, or contains a single chocolate chip.
Now it is time for the chefs to divide up the waffle among their hungry diners. A horizontal cut runs along the entire gridline between two of the rows; a vertical cut runs along the entire gridline between two of the columns. For efficiency's sake, one chef will make exactly H different horizontal cuts and another chef will make exactly V different vertical cuts. This will conveniently create one piece for each of the (H + 1) × (V + 1) diners. The pieces will not necessarily all be of equal sizes, but that is fine; market research has shown that the diners do not care about that.
What the diners do care about is the number of chocolate chips they get, so each piece must have exactly the same number of chocolate chips. Can you determine whether the chefs can accomplish this goal using the given numbers of horizontal and vertical cuts?
The first line of the input gives the number of test cases, T;
T test cases follow. Each begins with one line containing four
integers R, C, H, and V: the number of rows and
columns in the waffle, and the exact numbers of horizontal and vertical cuts
that the chefs must make. Then, there are R more lines of C
characters each; the j-th character in the i-th of these lines represents the
cell in the i-th row and the j-th column of the waffle. Each character is
either @, which means the cell has a chocolate chip, or
., which means the cell is empty.
For each test case, output one line containing Case #x: y,
where x is the test case number (starting from 1) and
y is POSSIBLE if the chefs can accomplish the goal
as described above, or IMPOSSIBLE if they cannot.
1 ≤ T ≤ 100.
Time limit: 6 seconds per test set.
Memory limit: 1GB.
2 ≤ R ≤ 10.
2 ≤ C ≤ 10.
H = 1.
V = 1.
2 ≤ R ≤ 100.
2 ≤ C ≤ 100.
1 ≤ H < R.
1 ≤ V < C.
6 3 6 1 1 .@@..@ .....@ @.@.@@ 4 3 1 1 @@@ @.@ @.@ @@@ 4 5 1 1 ..... ..... ..... ..... 4 4 1 1 ..@@ ..@@ @@.. @@.. 3 4 2 2 @.@@ @@.@ @.@@ 3 4 1 2 .@.@ @.@. .@.@
Case #1: POSSIBLE Case #2: IMPOSSIBLE Case #3: POSSIBLE Case #4: IMPOSSIBLE Case #5: POSSIBLE Case #6: IMPOSSIBLE
Note that the last two sample cases would not appear in test set 1.
In Sample Case #1, one possible strategy is to make the horizontal cut between the second and third rows from the top, and make the vertical cut between the fourth and fifth columns from the left. That creates the following pieces, each of which has exactly two chocolate chips:
.@@. .@
.... .@
@.@. @@
In Sample Case #2, no matter where you make the horizontal cut and the vertical cut, you will create pieces with unequal numbers of chocolate chips, so the case is impossible.
In Sample Case #3, there are no chocolate chips in the waffle. Any cutting strategy creates pieces which have the same number of chocolate chips (zero), so the diners are happy... but maybe not as happy as they would have been if they had gotten chocolate chips!
In Sample Case #4, just as in Sample Case #2, you cannot succeed regardless of where you make your horizontal cut and your vertical cut.
In Sample Case #5, the chefs can make the only two possible horizontal cuts, and make the two vertical cuts to the right of the first and third columns.
Although Sample Case #6 would be possible for other numbers of horizontal and vertical cuts, remember that you must use exactly H horizontal cuts and exactly V vertical cuts. No matter where you make your one horizontal cut and two vertical cuts, you cannot succeed.
These days, robots can drive cars, but can they throw a good party? The Code Jam team's research into this topic is still at an early stage. We just deployed R robot shoppers to our local supermarket to buy party supplies for our World Finals in Toronto, but their first-order model of a Canadian party was very simple: they just bought B "bits" (a bit being a small donut-like treat found in the area). We will work on improving their AI later, but for now, we want to help them purchase all of those bits as quickly as possible.
The supermarket has C cashiers who can scan customers' purchases. The i-th cashier will:
That is, a customer who brings N bits to the i-th cashier (where N must be less than or equal to Mi) will spend a total of Si × N + Pi seconds interacting with that cashier.
Before the robots interact with any cashiers, you will distribute the bits among the robots however you want. (Bits must remain intact; you cannot break them up into fractional pieces!) Any robot that gets no bits will not get to interact with a cashier, and will go away disappointed.
Then, for each robot with at least one bit, you will choose a different single cashier. (Two robots cannot use the same cashier, and a robot cannot use more than one cashier.) The robots all start interacting with their cashiers at time 0. Note that once a robot finishes interacting with its cashier, it cannot be given more bits and cannot interact with other cashiers.
If you help the robots make optimal choices, what is the earliest time at which all of the robots can finish interacting with their cashiers?
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with three integers R, B, and C: the numbers of robot shoppers, bits, and cashiers. Then, there are C more lines. The i-th of these represents the i-th cashier, and it has three integers Mi, Si, and Pi: the maximum number of bits, scan time per bit (in seconds), and payment/packaging time (in seconds) for that cashier, 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 the earliest time (in seconds) at which all robots can finish interacting
with their cashiers.
1 ≤ T ≤ 100.
1 ≤ Mi ≤ 109, for all i.
1 ≤ Si ≤ 109, for all i.
1 ≤ Pi ≤ 109, for all i.
The sum of the R largest values of Mi ≥
B. (It is possible for at least one subset of R cashiers to
handle all of the bits.)
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ R ≤ C ≤ 5.
1 ≤ B ≤ 20.
1 ≤ R ≤ C ≤ 1000.
1 ≤ B ≤ 109.
3 2 2 2 1 2 3 1 1 2 2 2 2 1 2 3 2 1 2 3 4 5 2 3 3 2 1 5 2 4 2 2 2 4 2 5 1
Case #1: 5 Case #2: 4 Case #3: 7
In Sample Case #1, there are two robots, two bits, and two cashiers, and each cashier can only handle one item. So, you must give one bit to each robot. Cashier 1 takes 5 seconds, and Cashier 2 takes 3 seconds, so the time required is 5 seconds.
Sample Case #2 is similar to the previous case, except that now Cashier 2 can handle up to 2 items. So, it is best to give all the bits to one robot and have that robot use Cashier 2. This takes 1 second per item plus 2 seconds = 4 seconds.
In Sample Case #3, the optimal strategy is to send one robot with 2 bits to cashier 2, and two robots with 1 bit each to any of the other cashiers.
The baker Mr. Maillard has rolled out some cookie dough and cut it up to create N cookies, each of which is a rectangle. He was just about to put them in the oven when he remembered that the crispy, caramelized edges of cookies taste particularly delicious. Specifically, he thinks he would be happiest if the sum of the perimeters of all the cookies were as close as possible to P millimeters (mm), without going over. (If the batch of cookies is too edgy, it might burn!)
For each cookie, Mr. Maillard can decide whether to leave it as is, or make a single straight cut to separate it into two (not necessarily rectangular) halves with equal area. (Note that such a cut must necessarily go through the center of the cookie.) The two new cookies created in this way cannot themselves be cut again.
If Mr. Maillard makes optimal decisions, what is the closest he can come to P without exceeding it?
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 N and P: the number of cookies, and the desired perimeter sum (in mm), respectively. Then, N lines follow. The i-th of these has two integers Wi and Hi: the width and height (both in mm) of the i-th cookie.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is a real number: the largest possible sum (in mm) of the perimeters of all
cookies (after Mr. Maillard is done cutting) that does not exceed P.
y will be considered correct if it is within an absolute or
relative error of 10-6 of the correct answer. See the
FAQ
for an explanation of what that means, and what formats of real numbers we
accept.
1 ≤ T ≤ 100.
1 ≤ N ≤ 100.
1 ≤ Wi ≤ 250, for all i.
1 ≤ Hi ≤ 250, for all i.
P ≥ 2 × the sum of (Wi +
Hi) over all i. (P is at least as large as the
sum of the perimeters of all cookies before any cuts are made.)
P ≤ 108.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
Wi = Wj, for all i and j.
Hi = Hj, for all i and j.
(All of the provided cookies have the same dimensions.)
No additional limits beyond the general ones. (In particular, the provided cookies do not all necessarily have the same dimensions.)
4 1 7 1 1 2 920 50 120 50 120 1 32 7 4 3 240 10 20 20 30 30 10
Case #1: 6.828427 Case #2: 920.000000 Case #3: 32.000000 Case #4: 240.000000
Note that the last sample case would not appear in test set 1.
In Sample Case #1, there is only one cookie, and it is a square with side length 1. Mr. Maillard can cut from one corner to a diagonally opposite corner, which creates two right triangles, each of which has side lengths 1, 1, and sqrt(2). Then the perimeter sum is 4 + 2 × sqrt(2); this is smaller than P = 7, but it is not possible to get any closer.
In Sample Case #2, Mr. Maillard can cut the first cookie along its longer axis to create two new 25 x 120 rectangles, and leave the second cookie alone. The total perimeter is then 580 + 340 = 920, which is exactly P.
In Sample Case #3, Mr. Maillard can cut the cookie to make two trapezoids, each of which has side lengths of 2, 4, 5, and 5. Then the new perimeter sum is 32, which is exactly P.
In Sample Case #4, the initial perimeter sum is exactly P, so Mr. Maillard should not make any cuts.
In test set 1, we are asked to make only one horizontal cut and only
one vertical cut. There are R - 1 possible horizontal cuts and
C - 1 possible vertical cuts, so there are a total of (R - 1)
× (C - 1) different ways to make the two cuts. Since R
and C are both at most 10, there are at most 81 ways, and we can
try each one of them separately. For each way, we can count up the chocolate
chips in each of the four resulting pieces. If we ever find a way in which
that number is the same for all four pieces, the answer is
POSSIBLE; otherwise, it is IMPOSSIBLE.
In test set 2, we may have to make many horizontal and vertical cuts, and there are too many ways to do this to check. The worst cases occur when H is close to half of (R - 1), and V is close to half of (C - 1); there could be over 1057 ways of making the cuts! So we need another approach.
Let us consider only the horizontal cuts, ignoring the vertical cuts for the
moment. These horizontal cuts break the waffle into two or more horizontal
"slices". Each of these slices will turn into exactly V + 1 pieces
when we make our vertical cuts. Here is the critical observation: if the
case is POSSIBLE, all of those pieces must have exactly the
same number of chips, and since each horizontal slice will produce exactly
the same number of pieces, all of those horizontal slices must have exactly
the same number of chips. Moreover, we know exactly what that number is; if
there are a total of C chips in the waffle, each of the H + 1
horizontal slices must have exactly C / (H + 1) chips, or else the
case is IMPOSSIBLE.
This observation is so powerful that it tells us where we have to make the
cuts if the case is POSSIBLE! We can make a list of the numbers
of chips in each row, then turn that list into a cumulative sum of the total
number of chips seen so far. For example, for a waffle with seven rows
containing 3, 7, 6, 2, 2, 0, and 10 chips, respectively, the cumulative sum
list would be: [3, 10, 16, 18, 20, 20, 30]. In that example, if H = 2,
we know we have to make cuts immediately below rows that bring the total sum
to 10 and 20, and we can do so by cutting immediately below the second and
fifth rows. (Note that we could instead make our second cut below the sixth
row, but this would make no difference.) If H = 1, though, we need to
make our one cut immediately below a row that brings the total sum to 15, and
there is no such row. So, after this step, either we will know that the case
is IMPOSSIBLE, or we will know exactly where to make our
horizontal cuts.
Then, we can consider only vertical cuts, using a similar method, and either
learn where to make them, or learn that the case is IMPOSSIBLE.
Even if we know where to make the horizontal and vertical cuts, though, we
are not done yet! These cuts might not actually create pieces with the same
number of chips. For example, for H = 1, V = 1, and this
waffle:
..@@
..@@
@@..
@@..
we will learn that if the case is POSSIBLE, we must make our
horizontal cut below the second row, and our vertical cut to the right of
the second column. But this creates two pieces with four chips each and two
pieces with no chips at all, so the case must be IMPOSSIBLE.
To check that each piece has the same number of chips, we can start by
turning the list of horizontal cuts into a list of intervals; for example,
if we cut below the second and fifth rows in the [3, 10, 16, 18, 20, 20, 30]
example from above, then we have the inclusive intervals [1, 2], [3, 5], and
[6, 7]. We can do the same for the vertical cuts, and then perform a double
iteration over these two sets of intervals, checking each cell within each
pair of intervals. We know that each piece must have exactly (total # of
chips) / ((H + 1) × (V + 1)) chips if the case is
POSSIBLE, so if we ever find a slice in which this is not true,
the case is IMPOSSIBLE. Otherwise, we have finally shown that
the case really is POSSIBLE. (Once again, note that even if we
had a choice of where to make one or more of our cuts, this must have been
due to empty rows or columns, which do not influence the number of chips in
each piece.)
(There are other ways to check the pieces; for example, we can make one pass through the data, and, for each cell, calculate the number of chocolate chips in the rectangle that has that cell as its lower right corner, and the upper left corner of the waffle as its upper left corner. Then, to find the number of chips in a certain piece, we can add and subtract the appropriate rectangles from this set.)
In summary, this algorithm involves several steps:
Steps 1 and 5 above involve looking at each of the R × C cells of the waffle, whereas steps 2, 3, and 4 only involve looking at R or C values. So steps 1 and 5 dominate the running time, which is O(R × C). (We could not have done better than this anyway, since we clearly have to look at each cell of the waffle at least once to solve the problem.)
We might consider enumerating all the ways of assigning bits to cashiers, but with 20 bits and 5 cashiers, there could be as many as 520 ways — too many to check! We need to take advantage of the fact that the bits are interchangeable, and instead find all the ways to partition B bits among R of the C cashiers (since we will only be able to use as many cashiers as we have robots). Then, we can compute how much time each of those ways takes, and pick the minimum of those values.
We can calculate the number of ways to partition 20 bits among 5 robots using this method. It turns out there are only (24 choose 4) = 10,626 ways to check. If we have fewer robots than cashiers, then we need to introduce another multiplicative factor of (C choose R), but this cannot be larger than 10 in test set 1. Each check takes O(R) time, which is very small given that R is at most 5. So, test set 1 should be solvable well within the 15 second time limit, regardless of your language choice.
To solve this test set, we need to be able to answer the following question: Given a time limit T, is there a possible assignment of bits such that all the robots can finish interacting with their cashiers in no more than T seconds? Let f(T) be the answer to this question.
How can we find f(T)? The maximum number of bits that the i-th cashier can process in not more than T seconds is max(0, min(Mi, floor((T - Pi) / Si))). Let us call this value Capacityi.
Then, we want to know whether a total of B bits can be assigned to R robots, and each of those robot to a cashier, such that the number of bits processed by the i-th cashier is not more than Capacityi. To do this, we can greedily sort the Capacity values into nonincreasing order, and then assign the R robots to the first R cashiers. f(T) is true if and only if the total number of bits that can be processed by the first R cashiers is at least B. Therefore, we can compute the value of f(T) for any T in O(C log(C)) time (which is the time it takes to sort the Capacity values). (Aside: We can even avoid the sort, and instead partition in O(C) time, by using introselect, for example.)
Since we want to minimize the time taken for all robots to interact with their cashiers, we want to find the minimum possible value of T such that f(T) is true. That value of T will also satisfy the following:
A cookie with width W and height H has a perimeter of 2 × (W + H). If we make a straight cut of length C that divides the cookie in half, each piece will have one side of length C, and the remaining sides of the pieces will represent the perimeter of the original cookie. So, after cutting, we will have a combined perimeter X = 2 × (W + H + C).
Clearly X is smallest when we leave the cookie alone. However, if we want to minimize X given that we are making a cut, we must minimize C; no cut can be smaller than the smallest of W and H, so we should cut through the midpoints of the two larger sides, which gives the cut a size of the smaller of the two sides. Then X = 2 × (W + H + min(W, H)). On the other hand, if we want to make a cut that maximizes X, we must maximize C by cutting through two opposite corners of the cookie. Then C = sqrt(W2 + H2), so X = 2 × (W + H + sqrt(W2 + H2)). If we start our cut somewhere between one of those larger-side midpoints and a corner, we will get a value of X somewhere between these two extremes; since we can cut anywhere we want in that interval, we can get any intermediate value of X that we want.
So, depending on what we do with our cookie, its contribution to our overall perimeter sum will either be 2 × (W + H), or a value in the range 2 × (W + H) + [2 × min(W, H), 2 × sqrt(W2 + H2)]. From now on, we will abbreviate the extremes of that range as [L, R]. (We could divide all values in the problem by 2 as well, removing that factor, but we will retain it in this analysis for clarity.)
In test set 1, all of the cookies have the same dimensions; we will call them W and H. Let us define P' as P - 2 × (W + H) — that is, the amount of extra perimeter that we need to add to reach the target P. So, we can reformulate the problem as starting with a total perimeter of 0, and trying to reach P'. For each cookie, we can choose to either not cut it, which leaves our total perimeter unchanged, or cut it, which increases our total perimeter by some value of our choice in the range [L, R]. If we cut K cookies, then our total perimeter can be anywhere in the range [K × L, K × R], depending on how we make our cuts. We will think in terms of this range and not in terms of the individual cuts.
How many cookies should we cut? Of course, we should never cut so many that K × L exceeds P'. However, we might as well keep cutting cookies up until that point, since doing so both moves our range closer to the target and makes the range wider. So, we can solve for X in the equation X × L = P', and then choose K to be the floor of X — that is, floor(P' / L). (Since L is an integer representing one of the original side lengths, and P' is also guaranteed to be an integer, we should use integer-based division here to avoid the usual problems with flooring floating-point numbers!)
Then, we can check whether the range [K × L, K × R] includes P'. If it does, the answer is 0; otherwise, it is P' minus the right end of the range, i.e., P' - K × R. Even though R is generally not an integer, we do not need to worry about floating-point issues; even if P' is very close to K × R and we mistakenly conclude that it is not in the range, we will still get an answer that is sufficiently close to 0 under our floating point rules.
In test set 2, different cookies might have different dimensions, so we get different total ranges depending on which ones we cut. We have no a priori basis for deciding which cookies to cut, and we cannot directly check all 2100 possibilities, but we can use dynamic programming to ensure that we find the best possibility without explicitly checking them all; the problem is very similar to the knapsack problem. For each cookie, we are deciding whether to leave it as is, or cut it, which adds L to our total perimeter and gives us up to R - L units of additional "slack". Once we have finished deciding which cookies to cut, we can include as much or as little of this "slack" as we want. All other things being equal, having more slack is always better for us. The large limit on P may seem daunting, but you can convince yourself that the problem space is actually small enough for methods like this to work.
However, the problem can also be solved in a different way. As in the previous solution, each cookie corresponds to a range [L, R] by which we can increase the total perimeter if we decide to cut that cookie. Let S(K) be the list of intervals we can reach after processing the first K cookies. We start with S(0) = {[0, 0]}.
When we consider the K'th cookie, we can choose to cut it or not. Suppose that this cookie corresponds to the interval [L, R]. If we do not cut it, we can obtain any perimeter that is already in an interval in S(K - 1). If we do cut it, we can reach any interval in the set S' given by S' = {[l + L, r + R] : [l, r] is an interval in S(K - 1)}.
To get S(K), we first take the union of S(K - 1) and S', followed by merging overlapping intervals. For example, if S(K - 1) = {[0, 0], [3, 6]}, and we add the interval [L, R] = [1, 2], we obtain S' = {[1, 2], [4, 8]} and S(K) = {[0, 0], [1, 2], [3, 8]}. Note that the intervals [3, 6] from S(K - 1) and [4, 8] from S' merge into a single interval [3, 8] here.
We can drop any intervals that start after P', so that after processing all N cookies, the answer to the question will be the distance from P' to the last interval.
Without any further analysis, we might expect the size of S(N) to be 2N, as it could double in each step. It turns out that we can provide a much stronger bound of (log(P') / log(sqrt(2))) + 1.
We first need the observation that any interval [L, R] corresponding to a cookie will satisfy R ≥ sqrt(2) × L, where equality holds for a square. Using induction, we can infer that every interval [l, r] in each S(K) also satisfies r ≥ sqrt(2) × l.
The second observation is that all intervals in S(N) are disjoint. Let us now sort intervals in S(N) and enumerate them starting from [l0, r0]=[0, 0]. Then the observations together imply that l{i+1} > ri ≥ sqrt(2) × li. Since the lower bound of each interval is an integer, we also have l1 ≥ 1. Hence we have li ≥ sqrt(2)i-1. Since we can discard any intervals starting after P', we may assume that li ≤ P'. We conclude that there are at most (log(P') / log(sqrt(2))) + 1 intervals in S(N).
This solution takes O(N log(P')) time: for each of the N cookies, we have to perform one merging step that takes O(|S(K)|) time.
It can also be shown that |S(K)| ≤ 2K + 1. We leave this as an exercise to the reader!