This year, rank 1000 in Round 2 became an especially important cutoff point — contestants had to place at least 1000th to earn advancement to Round 3 and the Distributed Code Jam Online Round, as well as the 2018 Code Jam T-shirt. With 4500 eligible contestants, though, it wasn't going to be easy, and there were also four problems to contend with!
We hope you warmed up with Falling Balls, which allowed for complicated constructions but was solvable with a straightforward greedy one. Graceful Chainsaw Jugglers and Costume Change required some original insights and some familiarity with typical techniques in the algorithmic toolbox like dynamic programming and matching. The graph problem Gridception was the toughest of the set; even once you saw the solution, there was plenty of implementation work left!
Unlike many of our previous Round 2s, this set lacked a killer problem, and our awesome contestants racked up almost 250 perfect scores! Our four-time defending world champion Gennady.Korotkevich secured first place, solving all four problems in just over 40 minutes. Um_nik and cki86201 were close behind, coming in with penalty times around the 43 and 46 minute marks. The cutoff for advancement appears to be 44 points (Falling Balls plus Costume Change) plus sufficient solving speed; as usual, official results will be mailed out soon.
Our top 1000 contestants have a weekend with two rounds (Code Jam and Distributed Code Jam) coming up in three weeks. After that, we will know who will be heading to Toronto!
Cast
Falling Balls: Written by Pablo Heiber.
Graceful Chainsaw Jugglers: Written by Pablo Heiber and Ian Tullis.
Costume Change: Written by Jonathan Irvin Gunawan.
Gridception: Written by Pablo Heiber and Ian Tullis.
All four problems prepared by Jonathan Irvin Gunawan.
Solutions and other problem preparation and review by Liang Bai, Jackson Gatenby, Md Mahbubul Hasan, Brian Hirashiki, Trung Thanh Nguyen, Ray Robinson, Kevin Tran, and Erick Wong.
Analysis authors:
A certain toy consists of a grid of 2 or more columns and 1 or more rows,
where each cell of the grid contains either a \
ramp or a
/
ramp, or is empty. The leftmost and rightmost columns are
empty and the bottom row is also empty. Balls are dropped into the top row
and fall vertically, sliding on ramps. To prevent balls from getting stuck,
a cell with a \
ramp is never immediately to the left of a cell
with a /
ramp.
When a ball is dropped into the top row, it moves deterministically as follows:
\
ramp moves to the cell
immediately below and to the right of its current cell./
ramp moves to the cell
immediately below and to the left of its current cell.To see the mechanism to its full extent, the user drops exactly one ball into each column. Balls do not interfere with each other, and it is possible for a cell to contain multiple balls.
Your friend has a toy with C columns and an unknown number of rows. They just dropped one ball into the top row of each column, and waited for all balls to stop moving. Then, they counted how many balls ended up in each of the cells of the bottom row, and gave you those results... but you think it is possible that they made a mistake. Can you create a layout that is consistent with the results and uses as few rows as possible, or determine that no such layout exists?
For example, if your friend reported the values 3 0 0 2 0 1
,
one possible solution would be the following. (Note that it is not necessary
to use a minimal number of ramps, or for every ramp to affect the balls.)
.//\..
./\./.
......
Here are the paths that the balls would take when falling through that grid:
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer C: the number of columns in your friend's falling ball toy. Then, there is one more line containing C integers B_{i}. The i-th of these integers represents the number of balls that ended up in the i-th cell from the left of the bottom row of your friend's falling ball toy, according to the data they gave you.
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
, or the number of rows in
your layout, as described above. If y
is not
IMPOSSIBLE
, output y
more rows, representing the
rows of your proposed falling ball toy layout, in order from top to bottom.
Use .
to represent a cell with no ramp, and \
or
/
to represent the ramps. The layout must obey all of the rules
in the problem statement.
1 ≤ T ≤ 100.
0 ≤ B_{i} ≤ C, for all i.
The sum (over all i from 1 to C, inclusive) of all
B_{i} values = C.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
2 ≤ C ≤ 5.
2 ≤ C ≤ 100.
3 4 1 1 1 1 3 0 2 1 6 3 0 0 2 0 1
Case #1: 1 .... Case #2: IMPOSSIBLE Case #3: 3 .//\.. ./\./. ......
Note that the last sample case would not appear in Test set 1.
The following layout is the only valid solution for Sample Case #1. (There must be at least one row, and including any more rows would make the solution use more rows than needed. It is not legal to include any ramps in the bottom row.)
....
In Sample Case #2, there is no way to prevent the leftmost ball from falling to the bottom of its column without adding a ramp, but ramps cannot be added to that column.
Sample Case #3 is the one described at the end of the problem statement. Note
that the following invalid layout for Sample Case #3 breaks several
rules: it has more rows than needed, it has ramps in the three illegal zones
(left column, right column, bottom row), and it contains a \
ramp immediately to the left of a /
ramp.
\\..\/
../.\/
./../.
..../.
You are the manager of the Graceful Chainsaw Jugglers performance group, and you are trying to succeed in the very competitive chainsaw juggling business. You have an unlimited number of identical talented jugglers, and each of them knows how to juggle any number of chainsaws. To run a show, you will choose some number of jugglers, and then distribute your red chainsaws and blue chainsaws among them, so that each juggler gets at least one chainsaw. For example, one juggler might juggle two red chainsaws and three blue chainsaws, and another juggler might juggle just one red chainsaw. During the show, each chainsaw is used by only one juggler; the jugglers do not pass chainsaws around, because it is already hard enough just to juggle them!
According to your market research, your audience is happiest when the show uses as many jugglers and chainsaws as possible, but the audience also demands variety: no two jugglers in the show can use both the same number of red chainsaws and the same number of blue chainsaws.
You have R red chainsaws and B blue chainsaws, and you must use all of them in the show. What is the largest number of jugglers that you can use in the show while satisfying the audience's demands?
The first line of the input gives the number of test cases, T; T test cases follow. Each test case consists of one line with two integers R and B: the numbers of red and blue chainsaws that you must use in the show.
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 number of jugglers that you can use in the show while
satisfying the audience's demands, as described above.
1 ≤ T ≤ 100.
R + B > 0.
Time limit: 25 seconds per test set.
Memory limit: 1GB.
0 ≤ R ≤ 50.
0 ≤ B ≤ 50.
0 ≤ R ≤ 500.
0 ≤ B ≤ 500.
2 2 0 4 5
Case #1: 1 Case #2: 5
In Sample Case #1, the only possible strategy is to give both red chainsaws to one juggler.
In Sample Case #2, one optimal strategy is to have:
Supervin is a well-known choreographer. Today is the N-th anniversary of his choreography career. To celebrate it, he is planning a dance on a stage that is a square grid of size N by N. Exactly one dancer will stand in each grid cell.
Each dancer will wear a costume; each costume has a single color, and is made out of either wool or cotton as its material. Supervin has N colors to choose from when designing the costumes for his dancers, indexed from 1 to N.
Each dancer wants to feel special. If two or more dancers share a row or column and also have costumes of the same color and material, they will no longer feel special.
Supervin wants all of his dancers to feel special. Therefore, Supervin is prepared to change the color and/or material of dancers' costumes so that no dancer shares a row or column with another dancer with the same costume (same color and same material). What is the minimum number of dancers whose costumes must be changed in order to make this happen? (Note that a change to both the color and material of a costume still counts as only one change.)
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer N: the side length (in unit cells) of the square grid of dancers. Then, N lines follow; each contains N non-zero integers A_{i, j}. The j-th value on the i-th line represents the costume of the dancer in the i-th row and j-th column of the grid. The magnitude of the value gives the color and the sign of the value gives the material (- for wool, + for cotton).
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 minimum number of dancers whose costumes must be changed, as described
above.
1 ≤ T ≤ 100.
-N ≤ A_{i, j} ≤ N, for all i, j.
A_{i, j} ≠ 0, for all i, j.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
2 ≤ N ≤ 4.
2 ≤ N ≤ 100.
4 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 2 2 -2 2
Case #1: 0 Case #2: 1 Case #3: 2 Case #4: 1
In Sample Case #1, no costumes need to be changed, since no dancer shares a row or column with another dancer with the same costume.
In Sample Case #2, one optimal solution is to change the value of A into the following (bold indicates changed values):
1 -2 2 1
Other optimal solutions are possible. Note that changing both the color and the material of a dancer's costume only counts as one change.
In Sample Case #3, one optimal solution is to change the value of A into the following (bold indicates changed values):
1 2 2 1
Other optimal solutions are possible.
In Sample Case #4, one optimal solution is to change the value of A into the following (bold indicates changed values):
2 -2 -2 2
Other optimal solutions are possible.
The master thief Jom Codd is able to infiltrate the dreams of others. Since dream-viewing technology is not very good yet, Codd sees a dream as a dream grid of unit cells, each of which is white or black.
Given a starting dream grid, Codd can go deeper by replacing each white cell with a 2x2 grid of white cells, and each black cell with a 2x2 grid of black cells; this creates a new dream grid that is four times larger. He can go deeper again from that grid, and so on. For example, given this starting dream grid:
BBB
BWB
BBB
then going deeper once produces this new dream grid:
BBBBBB
BBBBBB
BBWWBB
BBWWBB
BBBBBB
BBBBBB
and going deeper again produces this new dream grid:
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
and so on.
Codd has just infiltrated a dream and viewed its starting dream grid. He is on a very difficult mission, and he knows that he will need to go deeper many times. To help him navigate, he is looking at various patterns in the starting dream grid. A pattern consists of a single group of cells connected by shared edges (shared corners do not count as connections), plus their colors. A pattern might contain internal gaps (as long as the pattern's cells are a single connected group); such gaps are not considered part of the pattern. Two patterns are the same if and only if they have the same number and arrangement of cells (not reflected or rotated), with the same colors.
For example, in the grids above, the following 8-cell pattern is present in the starting grid:
BBB
B B
BBB
It is not present after going deeper once, but it is present after going deeper twice, and three times, and so on for every deeper dream grid.
Codd wants to find the largest pattern from the starting dream grid that will be present in at least a googol (10^{100}) of deeper dream grids. For the given example, the pattern above is the largest such pattern. Even though it is not present after going deeper once, it is present in at least a googol of deeper levels. Other such patterns of smaller sizes also meet this condition, but there is no 9-cell pattern that does; the only such pattern would have to be identical to the entire starting dream grid, and that pattern will never show up in any deeper dream grid, let alone in a googol of them.
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: the numbers of rows and columns, respectively, in the
dream grid. Each case continues with R more lines of C
characters each; every such character is either B
or
W
. These lines directly represent the dream grid.
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 possible size of at least one pattern that meets Codd's
requirements, as described above.
1 ≤ T ≤ 100.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ R ≤ 3.
1 ≤ C ≤ 4.
1 ≤ R ≤ 20.
1 ≤ C ≤ 20.
5 3 3 BBB BWB BBB 2 3 BBB WBW 1 1 W 3 3 WBW BWB WBW 2 4 BBWW BBWW
Case #1: 8 Case #2: 5 Case #3: 1 Case #4: 4 Case #5: 8
Sample Case #1 is the one described in the problem statement.
In Sample Case #2, one possible largest pattern is:
BBB
WB
Another equally large one is:
BBB
W W
In Sample Case #3, the entire starting dream grid is a largest pattern.
In Sample Case #4, note that the five W
s would not form a valid
pattern, because they are not connected. However, this is a largest pattern:
WB
BW
In Sample Case #5, the entire starting dream grid is a largest pattern.
Note that even though this grid happens to be what Codd would get by going
deeper starting from BW
, that is irrelevant; Codd will never "go
shallower".
We can narrow down the scope of Test set 1 with only a couple of insights:
IMPOSSIBLE
. (Later on in this analysis, it will become clear
that this is the only way for a case to be impossible!)So, we can experiment offline, generating potential ramp arrangements via simulation or by hand, until we are confident in our solutions for all cases, and then submit; since Test set 1 is Visible, we have little to lose. However, we can avoid this extra work, as follows...
Consider the paths that each ball might take through the toy, and notice
that whenever two balls' paths intersect, those balls must end up in the
same final column. (Because we can never have a \
ramp
immediately to the left of a /
ramp, paths cannot cross over
each other.)
So, for example, if your friend says there are exactly K balls in the leftmost column, they must have been the balls that were originally dropped into the K leftmost columns. Suppose that one of those balls had instead come from, e.g., the (K+1)-th column; then the path taken by that ball would have crossed all of the paths taken by the balls in the K leftmost columns, so all K+1 of the balls would have ended up in the leftmost column, which is a contradiction.
With those observations in mind, let us think of the i-th column as both a
source of one ball and a potential target of
B_{i} balls (if B_{i} > 0). We can scan our
friend's list from left to right, and when we encounter a positive
B_{i} value, we allocate the B_{i} leftmost
source columns that we have not used so far to target column i. So, for
example, if we have the data 3 2 0 0 0 0 2 1
, we map the source
column range [1, 3] to target column 1, the source column range [4, 5] to
target column 2, the source column range [6, 7] to target column 7, and the
source column range [8, 8] to target column 8.
Once we have this mapping, we can move on to designing the toy to ensure that every source column's ball will end up at the bottom of the appropriate target column. We will start with an empty top row, and add ramps and more rows as needed.
For each source column range, we check whether the left endpoint is to the
left of the target. If it is not, we do nothing. Suppose, on the other hand,
that it is L columns to the left of the target. Then we add L \
ramps, starting in the top row and the left endpoint's column, and proceeding
diagonally, moving one cell to the right and one cell down each time. Notice
that this line of ramps will catch all balls in that source column range that
need to move to the right, so we do not need to explicitly worry about those
balls. Then, we draw similar diagonal lines of /
ramps running
down and to the left from our right endpoints. Finally, if our bottom row is
not empty, we add an empty bottom row, as the rules require.
Can we convince ourselves that this construction is optimal? We have already shown that the mapping of source columns to target columns is forced. Consider the largest absolute difference, in columns, between a target column and one of the endpoints of the range of source columns mapped to it. (In our example above, this value is |5 - 2| = 3.) The toy must have at least this many rows (in addition to the empty bottom row), because a ball can only interact with one ramp per row, and each ramp only moves a ball one cell in the desired direction. Observe that our construction uses exactly this many rows, plus the required empty bottom row. For our example, our method produces:
.././\..
././....
../.....
........
Notice that there is no danger of creating a \/
pattern within a
range, since no target position could cause that.
We can identify each juggler by a pair of integers (b, r) where 0 ≤ b ≤ B and 0 ≤ r ≤ R. The pair (0, 0) does not identify a valid juggler, although we could assume that it does and, since we can always add (0, 0) to any valid configuration that does not contain it, just solve the modified problem and subtract 1 to obtain the final answer. We can then focus on finding the size of the largest subset of V = [0; B] × [0; R] such that the sum of the first component of each element is B, and the sum of the second component of each element is R. Let us call b,r-valid to a set of distinct pairs that fulfills the sum conditions for specific b and r.
For Test set 1, we can first notice that the size of V is small. Therefore, we can do a dynamic programming iterating through V and deciding, for each pair, whether to include it or not. As part of the state we have to also include how many blue and red jugglers we can still include. Therefore, we enumerate V in any order v_{1}, v_{2}, ..., v_{(B+1) × R+1}, and then we compute a function f(i, b, r) defined as the size of the largest b,r-valid subset of {v_{1}, v_{2}, ..., v_{i}}.
We can see that f has also a recursive definition as follows:
The definition above is incomplete because it's not checking for indefinitions. A simple solution is to just define every undefined case as -infinity, or for this particular problem, - B - R.
Memoizing this recursive definition leads to an implementation that takes time proportional to the size of the domain of f, which is (B+1)^{2} × (R+1)^{2}, which is likely fast enough to solve Test set 1. If your implementation and language of choice are both on the slow side, it's possible that you need some additional insight to make it through the time limit. One simple trick is that the function f actually solves all possible test cases, since the set V is fixed. So, you can reuse the memoization table for all test cases and save 99% of the work compared to solving each test case from scratch. You can even compute the entire table before submitting, and include it in your source code, although you should be wary of this strategy in general since it might cause your source file to exceed the 1 MB limit specified in our rules.
For Test set 2, we will definitely need the additional insight of not resetting the memoization table for each test case. However, the important additional insight is more specific to the problem.
First, let us define weak-b,r-valid sets as sets of distinct pairs of non-negative integers such that the sum of the values of the left sides of each pair is less than or equal to b, the sum of the values of the right sides of each pair is less than or equal to r. Of course, every b,r-valid set is also a weak-b,r-valid set, but the converse is not true.
One important property of weak-b,r-valid sets is that for fixed b and r, the size X of the largest weak-b,r-valid set is equal to the size Y of the largest b,r-valid set. We can prove that by noticing: (1) Y ≤ X because every b,r-valid set is a weak-b,r-valid set; and (2) X ≤ Y because if we let S be a weak-b,r-valid set of size X and then take an element (i,j) of S such that i is maximum, and j is maximum among those with maximum i, we can construct S' = S - {(i,j)} ∪ {(i + db, j + dr)} where db and dr are the difference between the sums of the left/right values of the pairs and b/r, respectively. By construction, S' is b,r-valid, and by the maximality of the choice of (i,j), (i + db, j + dr) is not in S - {(i,j)}, and thus, the sizes of S and S' are equal.
Let us now define minimal-weak-b,r-valid sets as weak-b,r-valid sets S such that for any (i,j) in S with i > 0, (i-1, j) is also in S, and analogously, for any (i,j) in S with j > 0, (i, j-1) is also in S. Similarly to the above, we can prove that the size of the largest minimal-weak-b,r-valid set for fixed b and r is the same as the size of the largest weak-b,r-valid sets by constructing a minimal-weak-b,r-valid sets of size X from a given weak-b,r-valid set S of size X. Let (i,j) in S be such that the minimality of the definition is violated (if such exists). Then, replace (i,j) in S for either (i-1,j) or (j-1,i) as appropriate to obtain another weak-b,r-valid set of the same size. This step strictly decreases the sum of the values of all pairs in S, thus, at some point, there are no such (i,j) to choose for and we successfully obtained a minimal-weak-b,r-valid set of size X.
The problem that remains is to find the size of the largest minimal-weak-b,r-valid set for given b and r. By the minimality condition, if (i,j) is in such largest set, so are (i-1, j), (i-2,j) (i,j-1), (i,j-2), (i-1, j-1), .... To formalize, (i,j) being present in a minimal-weak-b,r-valid set prescribes the presence of (i+1) × (j+1) pairs including itself. We can bound the sum of the left side values of all those pairs by (j+1) × (1 + 2 + ... + i) = (j+1) × i × (i+1) / 2, and analogously the sum of the right sides by (i+1) × j × (j+1) / 2. This means that instead of the set V from the solution above, we can use V', composed of the pairs in V that are under these bounds. This makes the size of V' be approximately O(B^{1/3} × R^{1/3}) when B and R are close, which is a big reduction from the size of V which is O(B × R). The overall complexity of the resulting algorithm for all test cases is then O(B^{4/3} × R^{4/3}), which is fast enough to pass Test set 2.
Trying every possible costume on every dancer will be too slow, even for this test set. Therefore, we need another solution.
To solve this test set, we can first observe that this problem is equivalent to the following: Find the largest subset of dancers such that no two dancers in the subset have the same costume type and share the same row or column.
If we find such a subset, we can change the costume types of the dancers not in the subset so that they follow the rules. We can iterate through the dancers in any order (e.g. row-major). If the current dancer is in the subset, we leave the costume as it is. Otherwise, we pick a new costume type for that dancer. Since a dancer can be in the same row or column as at most 2N - 2 other dancers, and since there are 2N costume types, it will always be possible to find a valid type to change to.
So, we can iterate through every subset of of dancers and check whether there are two dancers in the subset having the same costume type and sharing the same row or column. This solution runs in O(2^{N2} × N^{2}) time.
To solve this test set, we need a much more efficient way of finding the subset mentioned above. We can solve the problem independently for each costume type. Let f(x) be the largest subset of dancers who are wearing a costume with type x, such that no two dancers in the subset share a row or column. Then the size of our desired subset will be Σ f(i) for -N ≤ i ≤ N, i ≠ 0.
How can we find f(x)? Let us create a bipartite graph as follows:
A simple maximum cardinality bipartite matching algorithm runs in O(VE), where V is the number of vertices and E is the number of edges. Since V = O(N) and the sum of E among all costume types is N^{2}, this solution runs in O(N^{3}), which is fast enough to solve test set 2.
This test set can be solved using complete search. We can try enumerating every possible connected pattern. For each possible connected pattern, we check whether that pattern exists in the grid which has been deepened twice. Among all connected patterns which exist in the grid which has been deepened twice, we take the one with the largest number of cells. The correctness of this algorithm will be proved later in this section.
Note that it is not sufficient to check the pattern in the grid which has been deepened only once. The first sample case in the problem description shows that there is a pattern which does not exist in the grid which has been deepened once, but the pattern exists in the grid which has been deepened more than once.
Why is it sufficient to check the pattern in the grid which has been deepened twice? We can first observe that a grid which has been deepened X times consists of blocks of cells. Each block is a square of cells of the same color with side length 2^{X}. This does mean any pattern of size at most 3 × 4 can fit in the same block in the grid which has been deepened twice, whereas this might not be the case in the grid which has been deepened once.
Moreover, any pattern of size at most 3 × 4 overlaps with at least one and at most four blocks in the grid which has been deepened twice. This is also the case in the grid which has been deepened more than twice. Therefore, the set of patterns of size at most 3 × 4 which exists in the grid which has been deepened twice is equivalent to the set of patterns of size at most 3 × 4 which exists in the grid which has been deepened X times for any X > 2. Therefore, it is sufficient to check the pattern in the grid which has been deepened twice.
There are at most O(2^{R × C}) patterns. Therefore, there are not more than O(2^{R × C}) possible connected patterns. For each pattern, we can first check whether it is connected, and if it is, we can then check whether that pattern exists in the grid which has been deepened twice in O(R × C) time. Therefore, the total complexity of this solution is O(2^{R × C} × R × C) which is fast enough to solve test set 1.
Since R and C can be up to 20, the exponential solution will not run in time. Therefore, we must not enumerate every possible connected pattern. To solve this test set, we can first observe that a block of cells in the grid which has been deepened at least a googol times will have a side length larger than the size of any possible pattern.
The observation in the previous paragraph ensures that every possible pattern can overlap with at most four blocks of cells in the deepened grid. This means that Codd's pattern needs to be divisible into four quadrants by a horizontal and a vertical line where each cell of the pattern in the same quadrant has the same color. Moreover, that particular combination of four colors has to exist in the original grid.
Therefore, we can consider every possible quadrant center and combination of colors (there are up to O(2^{4} × R × C)). For each quadrant center and combination of colors, we want to get the largest connected component where each cell in this connected component has the same color as the color assigned to the quadrant it belongs to.
For each possible quadrant center and combination of colors, we need O(R × C) time to find the largest connected component. Therefore, this solution will run in O(2^{4} × R^{2} × C^{2}) time.