Our first Round 1 of 2019 presented three problems that looked complex, but all of them could be tackled with short solutions! Pylons mashed together two sci-fi pop culture franchises and asked you to hop around a grid in a safe way; it could be solved constructively, but it much easier if you thought about brute force, which is sometimes the right approach in the real world and even in coding contests! Golf Gophers allowed a lot of flexibility in interacting with a system, but the best approach turned out not to require much of it. Finally, Alien Rhyme could be solved using a trie.
Because all three problems could be solved with the right insights and short pieces of code, we were not too surprised to see a perfect score come in after only 25 minutes and 41 seconds. We were even less surprised that it came from last year's (and the previous year's, etc.) Code Jam champion, Gennady.Korotkevich. Fittingly enough, the next perfect score (at 31:59) came from last year's Distributed Code Jam champion, Radewoosh. ksun48 was the third to a perfect score, at 37:03. In all, we had almost 300 perfect scores! Somewhat unusually for a Code Jam round, our third (and highest-valued) problem got more submissions than either of the first two — perhaps it was a little more approachable for experienced competitive programmers.
Thanks to everyone for competing! We got at least one full submission in 23 different languages. The cutoff for the top 1500 tentatively appears to be 45 points plus a sufficiently small penalty time. As usual, it will be a few days before we finalize results, but the top 1500 will advance to Round 2 and earn a shot to pick up a Code Jam T-shirt. Anyone who did not advance will have two more chances to do so; Round 1B is coming up in two weeks!
Cast
Pylons: Written by Ian Tullis. Prepared by Jonathan Irvin Gunawan and Pi-Hsun Shih.
Golf Gophers: Written by Ian Tullis. Prepared by Pablo Heiber.
Alien Rhyme: Written by Pablo Heiber. Prepared by Micah Stairs.
Solutions and other problem preparation and review by Patrick Au, Liang Bai, Darcy Best, Carlos Guia, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Andy Huang, Pi-Hsun Shih, Anubhav Srivastava, Reyno Tilikaynen, Kevin Tran, and Adilet Zhaxybay.
Analysis authors:
Our Battlestarcraft Algorithmica ship is being chased through space by persistent robots called Pylons! We have just teleported to a new galaxy to try to shake them off of our tail, and we want to stay here for as long as possible so we can buy time to plan our next move... but we do not want to get caught!
This galaxy is a flat grid of R rows and C columns; the rows are numbered from 1 to R from top to bottom, and the columns are numbered from 1 to C from left to right. We can choose which cell to start in, and we must continue to jump between cells until we have visited each cell in the galaxy exactly once. That is, we can never revisit a cell, including our starting cell.
We do not want to make it too easy for the Pylons to guess where we will go next. Each time we jump from our current cell, we must choose a destination cell that does not share a row, column, or diagonal with that current cell. Let (i, j) denote the cell in the i-th row and j-th column; then a jump from a current cell (r, c) to a destination cell (r', c') is invalid if and only if any of these is true:
Can you help us find an order in which to visit each of the R × C cells, such that the move between any pair of consecutive cells in the sequence is valid? Or is it impossible for us to escape from the Pylons?
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing two integers R and C: the numbers of rows and columns in this galaxy.
For each test case, output one line containing Case #x: y,
where y is a string of uppercase letters: either
POSSIBLE or IMPOSSIBLE, according to whether it is
possible to fulfill the conditions in the problem statement. Then, if it is
possible, output R × C more lines. The i-th of these
lines represents the i-th cell you will visit (counting starting from 1), and
should contain two integers ri and ci: the row and
column of that cell. Note that the first of these lines represents your
chosen starting cell.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
T = 16.
2 ≤ R ≤ 5.
2 ≤ C ≤ 5.
1 ≤ T ≤ 100.
2 ≤ R ≤ 20.
2 ≤ C ≤ 20.
2 2 2 2 5
Case #1: IMPOSSIBLE Case #2: POSSIBLE 2 3 1 1 2 4 1 2 2 5 1 3 2 1 1 5 2 2 1 4
In Sample Case #1, no matter which starting cell we choose, we have nowhere to jump, since all of the remaining cells share a row, column, or diagonal with our starting cell.
In Sample Case #2, we have chosen the cell in row 2, column 3 as our starting cell. Notice that it is fine for our final cell to share a row, column, or diagonal with our starting cell. The following diagram shows the order in which the cells are visited:
| 2 | 4 | 6 | 10 | 8 |
| 7 | 9 | 1 | 3 | 5 |
Last year, a bunch of pesky gophers took up residence in our orchard. We tried to change our line of work by opening up a miniature golf course, but it looks like the gophers have followed us here! Once again, we need to figure out how many gophers there are, but we cannot observe them directly because they are secretive and nocturnal, whereas we like to sleep at night. We do know there are between 1 and M gophers, inclusive.
Our mini golf course is famous for having a small electronic windmill on each of its 18 holes. The i-th windmill has 2 ≤ Bi ≤ 18 blades, which are numbered from 0 to Bi-1, clockwise. Each night, before going to sleep, we turn off the windmills and set each one such that blade 0 is pointing downward, which is important so that the windmills can charge up properly for the next day. However, we have noticed that when we wake up, the windmills have been disturbed. Since our mini golf course is in a windless area, we think the mischievous gophers must be responsible!
We know that every night, all of the gophers emerge, one by one; each of them chooses one of the windmills independently and uniformly at random and rotates it counterclockwise by one blade. So, for example, for a windmill with 3 blades for which 0 is pointing downward, the first gopher to interact with it turns it so that 1 is pointing downward, and then the next gophers to interact with that windmill make the downward-pointing blade have number 2, then 0, then 1, and so on.
We have devised a plan. We designed our windmills so that we can easily change the number of blades (to modulate the difficulty of our course), and we will now take advantage of this! Each night, before going to sleep, we can choose the number of blades on each of the 18 windmills, within the given limits; we do not have to use the same number of blades on each windmill, or make the same choices every night. In the morning, we will observe the number on each windmill's downward-pointing blade.
We have N nights in which to figure out G, the number of gophers. Can you help us?
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, your program should read a single line containing three integers T, N and M, the number of test cases, the number of nights allowed per test case and the maximum number of gophers, respectively. Then, you need to process T test cases.
In each test case, your program processes up to N + 1 exchanges with our judge. You may make up to N exchanges of the following form:
-1.
On each night, for each gopher, the choice of which windmill the gopher turns is uniform at (pseudo)-random, and independent of any other choice by any gopher (including itself) on any night.
After making between 0 and N exchanges as explained above, you must make one more exchange of the following form:
1 if
your answer is correct, and -1 if it is not (or you have
provided a malformed line).
After the judge sends -1 to your input stream (because of either
invalid data or an incorrect answer), it will not send any other output.
If your program continues to wait for the judge after receiving
-1, your program will time out, resulting in a Time Limit
Exceeded error. Notice that it is your responsibility to have your program
exit in time to receive a Wrong Answer judgment instead of a Time Limit
Exceeded error. As usual, if the memory limit is exceeded, or your program
gets a runtime error, you will receive the appropriate judgment.
1 ≤ T ≤ 20.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
N = 365.
M = 100.
N = 7.
M = 106.
You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.
Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.
This interaction corresponds to Test set 1. Suppose that, unbeknownst to us, the judge has decided that there are 10 gophers.
t, n, m = readline_int_list() // Reads 20 into t, 365 into n and 100 into m.
// Choose numbers of blades for day 1.
printline 2 2 2 2 18 3 3 3 3 3 3 4 4 4 4 5 2 2 to stdout
flush stdout
// Reads 0 0 0 0 0 0 1 2 1 0 1 2 0 0 0 0 1 0 into res.
res = readline_int_list()
// Choose numbers of blades for day 2.
printline 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 to stdout
flush stdout
// Reads 0 1 1 2 0 0 1 0 0 0 0 0 0 1 0 0 0 0 into res.
res = readline_int_list()
printline 8 to stdout // We make a wrong guess even though we could
flush stdout // have investigated for up to 363 more nights.
verdict = readline_int() // Reads -1 into verdict (judge has decided our
// solution is incorrect)
exit // Exits to avoid an ambiguous TLE error
Notice that even though the guess was consistent with the information we received from the judge, we were still wrong because we did not find the correct value.
During some extraterrestrial exploration, you found evidence of alien poetry! Your team of
linguists has determined that each word in the alien language has an accent on exactly one
position (letter) in the word; the part of the word starting from the accented letter is called
the accent-suffix. Two words are said to rhyme if both of their accent-suffixes are equal.
For example, the words PROL and TARPOL rhyme if the accented letter
in both is the O or the L, but they do not rhyme if the accented
letters are the Rs, or the R in PROL and the
P in TARPOL, or the O in PROL and the
L in TARPOL.
You have recovered a list of N words that may be part of an alien poem. Unfortunately, you do not know which is the accented letter for each word. You believe that you can discard zero or more of these words, assign accented letters to the remaining words, and then arrange those words into pairs such that each word rhymes only with the other word in its pair, and with none of the words in other pairs.
You want to know the largest number of words that can be arranged into pairs in this way.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with a single integer N. Then, N lines follow, each of which contains a string Wi of uppercase English letters, representing a distinct word. Notice that the same word can have different accentuations in different test cases.
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 size of the largest subset
of words meeting the criteria described above.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ length of Wi ≤ 50, for all i.
Wi consists of uppercase English letters, for all i.
Wi ≠ Wj, for all i ≠ j.
(Words are not repeated within a test case.)
2 ≤ N ≤ 6.
2 ≤ N ≤ 1000.
4 2 TARPOL PROL 3 TARPOR PROL TARPRO 6 CODEJAM JAM HAM NALAM HUM NOLOM 4 PI HI WI FI
Case #1: 2 Case #2: 0 Case #3: 6 Case #4: 2
In Sample Case #1, the two words can rhyme with an appropriate accent assignment, as described above, so the largest subset is the entire input.
In Sample Case #2, no two words can rhyme regardless of how we assign accents, because any two suffixes will differ at least in the last letter. Therefore, the largest subset is the empty one, of size 0.
In Sample Case #3, we can use the entire set of words if we accentuate
CODEJAM and JAM at the Js,
HAM and NALAM at their last As and HUM
and NOLOM at the Ms.
In Sample Case #4, any two words can be made to rhyme, but always by making the accented letter
the I. Therefore, if we add two pairs to the subset, words from different pairs
will rhyme. We can, thus, only form a subset of size 2, by choosing any 2 of the input words.
There are a few impossible cases for this problem. If we experiment with some small grids, we can find that in addition to the 2 x 2 grid given as a sample case, the 2 x 3, 2 x 4, and 3 x 3 cases have no solution. (Because of symmetry, the 3 x 2 and 4 x 2 cases are also impossible.)
In the 2 x 3 grid, we can notice that the middle cell of the top row shares a row, column, or diagonal with every other cell; the same is true of the central cell of the 3 x 3 grid. In each case, we cannot go from that cell to any other cells, or vice versa, so the grid is unsolvable.
In the 2 x 4 grid, we can try starting in the second cell of the top row; then we find that we are forced into a series of three moves that eventually take us to the third cell of the bottom row, from which there are no other moves; we can never move out of that set of four cells that we visited. Since the same is true of the other set of four cells, there is no solution.
The other cases in test set 1 are all solvable, though. One strategy is to make mostly "knight moves" — two unit cells in one direction, and one unit cell in the other. We may not be able to solve a grid using only knight moves — see this article for more information — so we can sprinkle in other legal moves as well. For instance, we can solve the 3 x 4 case by visiting the cells in the following order:
02 05 10 07
09 12 01 04
06 03 08 11
And here is a solution for the 3 x 5 case, which makes many steps that are wider than knight moves:
04 14 09 12 07
06 11 01 15 03
02 08 13 10 05
Because of symmetry, the only remaining cases are 2 x 5, 4 x 4, and 4 x 5, and we can solve these by hand if we choose, or we can use a brute force algorithm.
There are multiple strategies for dealing with test set 2. One class of approach is constructive. For example, we can devise general solutions for 2 x N and 3 x N grids, for arbitrary N, and then divide up the grid into horizontal strips of height 2, plus one more strip of height 3 if needed. Unfortunately, this can be tricky to get right. We need to make sure that the solutions to the subproblems do not violate the rules — the last move in one subproblem cannot be in the same row, column, or diagonal as the first move in another. Moreover, we might struggle to come up with our general 2 x N and 3 x N solutions.
The Code Jam team's first successful constructive solution included multiple cases for 2 x N (depending on whether N is odd, 0 mod 4, or 2 mod 4), and multiple cases for 3 x N (which entailed adding pairs of columns to the left and right of our hardcoded 3 x 4 and 3 x 5 solutions, bouncing between those columns to avoid breaking rules). It also made each such solution start near the left edge of each strip and end near the right edge, to avoid diagonal interactions among subproblems / strips.
Is there an easier way? Let's take a step back. The problem imposes some constraints, but one can observe that it is not too difficult to solve the larger test set 1 cases by hand. This suggests that there are many possible solutions, and we might expect even more as the grid's dimensions get larger. (We could use Ore's theorem to establish the existence of at least one solution for sufficiently large grids.) So, our intuition might suggest at this point that the best approach is some kind of brute force.
We might consider using backtracking solutions. One possible concern is that these solutions, whether they are breadth-first or depth-first, proceed in an orderly fashion that might be more likely to leave us with tough "endgames" in which the constraints are impossible. For example, if our solution somehow solves all but the bottom row of the grid, then all hope for the universe is lost!
We can try these solutions anyway, or we can rely on our occasional friend, randomness! We can pick a random starting cell, repeatedly choose valid moves uniformly at random from the space of all allowed moves from our current cell, and, if we run out of available moves, give up and start over. For any case except for the impossible ones mentioned above, this approach finds a solution very quickly.
Many problems cannot be approached with random or brute-force solutions, but identifying the problems that can be (in Code Jam or the real world) is a useful skill!
We are aware of other approaches. For example, we know that there is at least one implementation of the following idea that solves every possible test in the test set 1 and 2 limits: repeatedly greedily select an unvisited cell that has the largest count of unvisited "neighbors", where we define a cell's neighbors as those cells that share a row, column, or diagonal with that cell. (We can either rule out specific impossible cases beforehand, since there are not very many, or infer impossibility by comparing the number of unvisited cells with the largest count of unvisited neighbors.)
Although we do not provide a proof here, intuitively, it is advantageous to prevent any one row, column, or diagonal from having too many unvisited cells, relative to other rows, columns, and diagonals. For example, if we are close to the end of our journey, and a majority of our remaining unvisited cells are in the same column, we are doomed.
Given the relatively small number of possible test cases for this problem, it is not too hard to check all of them to verify that a solution works, and that may be much easier than proving correctness! That is a rare luxury to have for a Code Jam problem!
The difficulty of this problem stems from the fact that the windmills can loop around. If we have a windmill with 5 blades, and we find it with blade number 2 pointing downward in the morning, does that mean that 2 gophers rotated it? or that 7 did? or 12? In general, if a windmill has B blades, and we find it in position P, all that we can say for sure is that some number (P + K × B) of gophers (for some integer K) tampered with it during the night.
Because of this, we might reason that we should put as many blades as possible (that is, 18) on each windmill, and then hope that none of those windmills is visited by more than 17 gophers, in which case the total number of rotations of all blades equals the total number of gophers. This turns out to be a reasonable hope! It is hard to directly calculate the probability that none of the 18 blades will be turned more than 17 times on a given night, but a quick simulation can tell us that even in the worst case of 100 gophers, the probability of this happening is about 0.00017. Since we can run this same experiment 365 times and take the maximum result that we find, the chances of a wrong answer (due to getting a misleading result all 365 times) are infinitesimally small.
In test set 2, we only have 7 nights to work with, and the number of gophers can be quite large, so we cannot reasonably hope that the windmills will not loop. Now what? We might consider using different numbers of blades on each windmill during a given night, but it's hard to see how that buys us anything.
Suppose that, on one night, we try putting two blades on every windmill. At first this doesn't seem to help — shouldn't the resulting data should be almost pure noise? However, we can observe that if the number of gophers is odd, the total number of turns (across all windmills) will be odd, and if the number of gophers is even, that total number will be even. So we have a way of determining the parity of the number of gophers, no matter how they happen to turn the blades!
We can extend this idea to find out how many gophers there are modulo any number of our choice between 2 and 18. Since we only get 7 nights, though, we should choose our numbers carefully. One promising idea is to make them all prime, and there are seven primes in the range we can use: 2, 3, 5, 7, 11, 13, and 17. Then we can try to use the construction suggested by the Chinese remainder theorem to uniquely determine the number of gophers. However, this method would only work for any number of gophers up to 2 × 3 × ... × 17 = 510510; it cannot distinguish 510511 gophers from 1 gopher! We are in trouble, since we might have up to 106 gophers.
The final insight that we need is that the Chinese remainder theorem only requires its moduli to all be relatively prime, not necessarily prime. So we can use 16 in place of 2, and 9 in place of 3. This lets us identify any number of gophers up to 5 × 7 × 9 × 11 × 13 × 16 × 17 = 12252240, which easily covers what we need. (We can also get away with using the numbers 12 through 18, for example; we leave the details to the reader.)
Notice that we do not really need to do any calculations based on the Chinese remainder theorem; since the number of possible answers is relatively small, we can check all of them until we find the one that has the appropriate residue for each of our chosen moduli.
To prove that the probability of at least one blade rotating more than 17 times is about 0.00017, we can solve a related problem:
"Count the number of integer arrays of length L such that each array element is one of 1, 2, ..., U and each number appears at most B times in the array."
This related problem is equivalent to counting integer partitions with constraints on the size of each partition.
We can solve this related problem using
Dynamic Programming.
First, we choose how many times U appears in the array; say it
appears K times, with 0 ≤ K ≤ min(B,L). Once we know K,
we have to choose where those K values go. Using
combinations,
we can see that there are C(L, K) possible options. For
each option, we can treat the L-K other spaces as an array that must
contain the numbers 1, 2, ..., U-1 such that no number appears more
than B times, which is a subproblem of our original problem, so we may
recurse. If we sum over all possible values for K, we have the total number
of valid arrays.
If we solve the above problem with L = 100, U = 18, B = 17, we see that there are 336647783248234011860927063629187654598455062446560501834487820535956663161762533555609870639313859125191714928476256971520000 (or approximately 3.366 × 10125) arrays such that no number appears more than 17 times. These arrays can represent which windmill the gophers select in a good configuration out of the 18100 possible configurations. This gives us the probability quoted above.
In the first test set there are only up to N = 6 words with up to 50 characters in each of them. We can simply use brute force to try all ways of grouping words into pairs (allowing some words not to be in any pair – we will effectively discard these words), try all choices of an accent-suffix for every pair, and check that none of the pairs have the same accent-suffix. Finally, we choose the maximum size across all valid groupings.
Let's notice how the size of an accent-suffix affects the chance of multiple words
sharing it. In case we have words CODEJAM, JAM, HUM
and HAM, accent-suffix JAM can be part of only two words,
whereas a shorter accent-suffix M fits all four words. This leads
to the following observation: for two words that we want to pair, it is never
suboptimal to choose their longest available common suffix as the accent-suffix
– this way we are still making sure that they rhyme, and we are allowing shorter
accent-suffixes to be used by other pairs. Notice that any other pair that could
use the longer suffix can also use any shorter suffix. For example, if we want
words CODEJAM and JAM rhyme, we should choose
JAM as their accent-suffix, and allow
suffix M to be potentially used by HUM
and HAM.
In this problem it is all about common suffixes of the words. In order to
better operate with word suffixes, let's actually reverse the words first (so now
original word suffixes are prefixes of reversed words), and build a
trie (also often called prefix tree)
on the reversed words. This is how a trie containing the words CODEJAM,
JAM, HUM and HAM looks:
Let's also mark the trie nodes where some of the input words end. Since we are guaranteed that all the words are unique, we can use a simple boolean flag. In the picture above, trie nodes where a word ends are marked in red.
Now we can solve the problem as follows: for a trie node v, let f(v) be
the minimum possible number of unpaired words that use accent-suffixes whose reverses
end in the node v or the subtree under it.
The answer to the problem is then N - f(root), since f(root) represents
all usable accent-suffixes.
How do we calculate the values of f(v)? If v does not have
any children nodes, we set f(v) to be 1, since we know that in our trie all
leaf nodes are the end of a word. If node v has children, we can calculate
f(v) with the following algorithm assigning the result to r:
r = sum(f(c) for all c where c is a child node of v) if node v is marked (there is a word that ends at v): r = r + 1 if v is not the root and f(v) ≥ 2: r = r - 2
First, we simply count the number of unpaired words recursively. Finally, we let two of those words be paired using the prefix that ends in the node v, which represents suffixes of original words, as the accent-suffix.
In our example trie we would get the following values of f(v):
Proving the algorithm above correctly calculates f(v) is straightforward. First notice that only
words that are represented in the trie at or below v are pairable with the set of accent-suffixes
represented by v or its subtree. Then we can proceed by induction: f is pretty clearly correct
for a single node tree, as there is no pairing possible. Assume by the inductive hypotheses
f works correctly on all proper subtrees under v. The pairing implied by the construction of f(v)
— adding any remaining pair of words to the recursive result —
is valid: we are only pairing two words with the accent-suffix
represented by v, and the rest is valid by the inductive hypotheses.
To show that the pairing it is also of maximum size, notice that,
by inductive hypothesis, there is no way to pair more than
sum(f(c) for all c where c is a child node of v) words with accent-suffixes
that are represented by the subtree but not by v directly. This is because words in different
subtrees of v cannot be matched with a longer accent-suffix than the one represented by v, and
the accent-suffix represented by v can add at most a single pair to the total.
Note how we calculate the values of f(v) in a recursive manner,
and f(v) is calculated exactly once for each possible v.
Since the algorithm itself takes constant time in addition to the time of the recursion,
we can calculate all f(v) values in O(T) time,
where T is a total number of nodes in the trie. We can bound T
by the total length of all words, or by N × m where m is the maximum word length.
Finally, there are less efficient but simpler implementations that also work. For example, sort the reversed words alphabetically and take any two adjacent words with a longest common prefix, pair them, remove them from the list, and repeat. This simple-to-implement algorithm basically constructs the same pairing our recursive formulation does. This shifts some implementation complexity onto the correctness proof. If you are faster with proofs than with code, it might be an overall gain in solving speed.