The last of our Round 1s began with A Whole New Word; for those of you who know the song "A Whole New World", good luck getting it out of your heads! Lollipop Shop was another interactive problem with a somewhat intuitive solution; it also might have gotten you thinking about a certain 1950s song. Ant Stack was much harder than either of the previous two problems, but still approachable with enough thought and patience. It was easy to underestimate the limits of the second test set and time out!
This round was easier than 1B, and only 20 minutes into the contest, every problem had been solved by someone. Eryx was the first to snag a perfect score, after 35 minutes and 24 seconds. Full solutions to the first two problems generally sufficed to crack the top 1500.
That concludes Round 1 of Code Jam 2018! We will see our 1500 advancers from Round 1C, along with the combined 3000 advancers from Rounds 1A and 1B, in Round 2 in two weeks. 1000 of them will emerge with T-shirts and places in Round 3 and the Distributed Code Jam Online Round. For those of you who did not make it through the Round 1s, we encourage you to try again next year. Even making it through the Qual Round and giving Round 1 your all is a significant achievement!
Cast
A Whole New Word: Written and prepared by Jonathan Irvin Gunawan.
Lollipop Shop: Written and prepared by John Dethridge.
Ant Stack: Written by Pablo Heiber. Prepared by Kevin Tran.
Solutions and other problem preparation and review by Liang Bai, John Dethridge, Md Mahbubul Hasan, Robin Lee, Igor Naverniouk, Trung Thanh Nguyen, and Anqi (Joyce) Yang.
Analysis authors:
Vincent and Desta are childhood friends. Today, Vincent is showing N distinct L-letter words to Desta by using some letter tiles. Each tile contains one uppercase English alphabet letter, and one number between 1 and L. A word consists of the letters spelled out by L tiles with numbers from 1 through L, in order. (Vincent's words are not necessarily real English words.)
For example, if Vincent has N = 3 words with L = 4, and the
words are {CAKE, TORN, SHOW}, then
Vincent must show the following to Desta:
Desta feels that creating words must be easy, and he wants to create a new word that obeys the rules above and is not one of Vincent's existing words. However, Desta does not have any tiles of his own, so he must use some of Vincent's tiles.
For instance, if Vincent has the words from the previous example, then Desta
can make a new word such as CORN or SAKE or
CHRE (Desta's words are also not necessarily real English words).
Each of the example is illustrated in the following image:
Note that the three rows in the image above are independent. Desta only needs to make one new word.
However, in the above example, Desta cannot make WAKE, for
example, because there is no W tile with a number 1. Nor can he make
COO, since it is not the right length.
Notice that it may be impossible for Desta to make a new word. For example, if
Vincent has only one word, then Desta cannot make anything new. Or, if Vincent
has the words {AA, AB, BA,
BB}, then any word that Desta can form is already present.
Help Desta to choose a word that he can show to Vincent using only the tiles used by Vincent, or indicate that it is impossible to do so.
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 L: the number of Vincent's words, and the length of each word. Then, N more lines follow. The i-th of these lines contains a string of L uppercase English letters representing the i-th of Vincent's words.
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 valid word to be chosen by Desta, or - (a single dash
character of ASCII value 45) if there is no valid word to be chosen by Desta.
If there is more than one valid word that Desta can make, you can output any
of them.
1 ≤ T ≤ 100.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
No two of Vincent's words are the same.
1 ≤ N ≤ 262.
1 ≤ L ≤ 2.
1 ≤ N ≤ 2000.
1 ≤ L ≤ 10.
5 4 1 A B C D 4 2 WW AA SS DD 4 2 AA AB BA BB 3 4 CAKE TORN SHOW 5 7 HELPIAM TRAPPED INSIDEA CODEJAM FACTORY
Case #1: - Case #2: WA Case #3: - Case #4: CORN Case #5: HOLIDAY
Note that the last two sample cases would not appear in test set 1.
In Sample Case #1, the only words that can be construted using the tiles used
by Vincent are A, B, C, D.
However, all of those words already appear in Vincent's list of words, so
Desta is not allowed to choose them.
In Sample Case #2, there are 12 possible new words that Desta can make, one of
which is WA.
Sample Case #3 was explained in the problem description above; there is no new word that Desta can make.
Sample Case #4 was explained in the problem description above; other answers
such as SAKE are possible.
In Sample Case #5, other answers such as TRAPJAM are possible.
You own a lollipop shop. At the start of the day, you make N lollipops, each of a single unique flavor, like huckleberry, cherry or lime. N customers come into the shop during the day, one at a time. Each customer gives you a list of which of your lollipop flavors they like. You can sell them one lollipop of any of those flavors, as long as you have not already sold someone else the same flavor earlier in the day (since there is only one lollipop of each flavor). If none of the flavors they like are still available, you cannot sell them a lollipop, and they leave your shop disappointed.
You do not know what each customer's flavor preferences are going to be until they arrive. Each customer decides if they like or dislike each flavor randomly, independently of whether they like any other flavor, or what flavors anyone else likes. However, your market studies have shown that some flavors may have a higher probability of being liked in general! For example, the lime flavor might have a 10% chance of being liked by any particular customer, whereas that chance might be 1% for the cherry flavor. These values are always chosen independently and uniformly at random from the interval [0.005, 0.1].
Obviously, you want to sell lollipops to as many of the N customers as possible! But, since you do not know what flavors your customers will ask for ahead of time, you cannot always make an optimal decision — sometimes you might sell a customer one flavor, and then later wish you had sold them another.
Suppose that you somehow knew all the customers' preferences in advance and could plan ahead; then there is some maximum number M of lollipops that you could possibly sell. You do not know the customers' preferences in advance, but we require you to sell a number of lollipops that is at least 90% of M for each input case.
This problem is interactive, which means that the concepts of input and output are different than in standard Code Jam problems. You will interact with a separate process that both provides you with information and evaluates your responses. All information comes into your program via standard input; anything that you need to communicate should be sent via standard output. Remember that many programming languages buffer the output by default, so make sure your output actually goes out (for instance, by flushing the buffer) before blocking to wait for a response. See the FAQ for an explanation of what it means to flush the buffer. Anything your program sends through standard error is ignored, but it might consume some memory and be counted against your memory limit, so do not overflow it.
Initially, your program should read a single line containing a single integer T indicating the number of test cases. Then, you need to process T test cases.
For each test case, your program should read a single line with one integer N, the number of lollipops (which is the same as the number of customers).
Then, for each of the customers, your program should read a single line, which will contain space-separated integers. The first integer is D, the number of flavors that customer likes. Then, D integers follow, the ID numbers of those flavors, in strictly increasing order. Flavors have unique ID numbers in the range [0, N - 1]. Note that D might be zero for some or all customers.
After each of these lines, your program must write a single line to standard
output, containing the ID number of one of the D flavors to sell to the
customer, or -1 if no lollipop is to be sold to the customer.
After you have written the Nth line for the test case,
your program should terminate if it was the last test case; otherwise, it
should start reading data for the next test case.
If your program gets something wrong (e.g., tries to sell a customer a flavor
that was already sold, or tries to sell a customer a flavor they don't like,
or uses the wrong output format, or outputs an out-of-bounds value), the
judge will send -1 to your input
stream and it will not send any other output after that. 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
the appropriate verdict (Wrong Answer, Runtime Error, etc.) instead of a Time
Limit Exceeded error. As usual, if the total time or memory is exceeded, or
your program gets a runtime error, you will receive the appropriate verdict.
Not selling enough lollipops for a test case will not cause you to get the
-1 message.
You should not send additional information to the judge after processing all test cases. In other words, if your program keeps printing to standard output after the last test case, you will get a Wrong Answer judgment.
At the start of each test case, the judge will determine all customers' preferences. That is, it will use a (hidden) list of probabilities Pi between 0.005 and 0.1, one for each flavor; each customer has a probability Pi of liking the i-th flavor. That is, the random variables indicating whether customer j likes flavor i are independent and identically distributed. These preferences are constant throughout the test and will not be modified e.g. in response to your choices.
T = 50.
N = 200.
0 ≤ D ≤ N.
Time limit (for the entire test set): 25 seconds.
Memory limit: 1GB.
Note that this sample interaction has smaller values of T and N than the real data. The local testing tool also uses smaller cases.
t = readline_int() // reads 10 into t n = readline_int() // reads 4 into n (four customers & flavors) prefs = readline_int_list() // reads 1 2 (customer only likes flavor 2) printline 2 to stdout // sells this customer flavor 2 flush stdout prefs = readline_int_list() // reads 0 (customer likes nothing) printline -1 to stdout // no flavor to sell to the customer! flush stdout prefs = readline_int_list() // reads 1 2 (customer only likes flavor 2) printline -1 to stdout // already used flavor 2, so no flavor to sell flush stdout prefs = readline_int_list() // reads 2 1 3 (customer likes 1 and 3) printline 3 to stdout // note: we could have also sold flavor 1 flush stdout n = readline_int() // (start of case 2) reads 1 prefs = readline_int_list() // reads 1 0 printline -1 to stdout // non-optimal but legal choice flush stdout n = readline_int() // (start of case 3) reads 5 prefs = readline_int_list() // reads 2 1 3 printline 1 to stdout flush stdout prefs = readline_int_list() // reads 2 1 2 printline 1 to stdout // error -- tried to give same flavor twice! flush stdout prefs = readline_int_list() // reads -1 (judge has given up on us) exit // exits to avoid an ambiguous TLE error
The pseudocode above demonstrates the following scenario.
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.
Scott has an ant farm containing N ants. Each ant has a certain length and weight.
Today, as a challenge for the ants, Scott has placed some food at the top of the ant farm. The ants will try to reach it by arranging themselves into a vertical stack, with each ant in the stack directly holding the next on its back. In this way, each ant bears the weight of all ants above it. Scott's ants are very strong for their size and are able to carry up to 6 times their own weight. For example, an ant that weights 8 milligrams can carry two other ants weighing 24 milligrams each! Each ant also has a body length; the exact lengths are not important, except that they are all different.
What is the maximum number of these ants that can form such a stack?
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with an integer N: the number of ants in the colony. Then, a second line follows containing N integers W1, W2, ..., WN, where Wi is the weight in milligrams of the i-th ant. The ants are listed in strictly increasing order of length. Notice that no actual length values are given; only the order is important.
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 the given ants that can form a stack
that obeys the rules above.
7 ≤ T ≤ 100.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
For exactly 6 cases, N = 100; for the other T - 6 cases,
2 ≤ N ≤ 50.
1 ≤ Wi ≤ 1000, for all i.
For exactly 6 cases, N = 105; for the other T - 6
cases, 2 ≤ N ≤ 500.
1 ≤ Wi ≤ 109, for all i.
3 2 9 1 3 8 4 100 9 10 10 10 10 10 10 10 10 100
Case #1: 1 Case #2: 3 Case #3: 8
In Sample Case #1, there are two ants. The first weighs 9 mg; the second weighs 1 mg, and is longer than the first ant. The first ant is strong enough to hold the second ant (since it can hold up to 9 × 6 mg), but it cannot, because the second ant is longer. The second ant is not strong enough to hold the first ant (since it can only hold up to 1 × 6 mg, which is less than 9 mg). So it is only possible to make a "stack" of one of the two ants.
In Sample Case #2, it is possible for all three ants to form a stack, with the third holding up the second, which holds up the first.
In Sample Case #3, the optimal solution has the ninth ant on the bottom, and then seven of the other ants above it.
Since L ≤ 2, this test set can be solved using a complete search. First, we collect the letters that appear among the first characters of the input words in a set C1 and the letters that appear among the second characters of the input words in a set C2. Any candidate new word has the form c1c2, where c1 is in C1 and c2 is in C2. For each candidate new word, we check whether this word is in the input. We can output any candidate new word which does not appear in the input as our answer. If every candidate new word already appears in the input, the case is impossible.
Since there are only at most 262 different candidate words that we need to try, this solution will run very quickly.
In early rounds of Code Jam, a complete search will often work for the first test set, but will generally not work for subsequent test sets. This problem is an exception! Our approach above will work just fine for test set 2.
We can create sets C1, C2, ..., CL as in the solution above, and then use them to generate candidate words as before, one at a time. If we encounter a word that is not in the input, we can return it as our answer. If it turns out that there are exactly N candidate words (which implies that every word that could be generated is already in the input), the case is impossible. Otherwise, we can be sure that we will have found an answer by the time we generate and check the (N + 1)th candidate word, since there are only N words in the input list.
This problem's acceptance condition is based on competitive analysis. The problem is a bit tough to test locally, even for an interactive problem. It is easy to generate a particular set of customer preferences, but determining the maximum possible number of lollipops we can sell requires bipartite matching. However, we do not necessarily need to do that; since there is only one test set, which is Visible, we have some room for experimentation and for small leaps of faith.
A solution that just picks random legal flavors is not good enough to pass, so we need a couple of insights:
Therefore, our best strategy is to always sell a lollipop if possible; whenever there are multiple flavors to choose from, we choose one of the flavors that we have seen the minimal number of times among previous customers' preferences. In problems like this, when we have to break a tie, we should do so at random just in case the problem setters have tried to anticipate and thwart particular strategies like always choosing the smallest ID number. (In this problem, it would have been impossible for the setters to penalize that, though!)
Notice that our solution would not work for an arbitrary list of probabilities, even with 200 customers. If every probability is 0.02, for example, our strategy loses its power (since all flavors are equally likely), and each flavor appears frequently enough to make our strategy do much worse than matching, but infrequently enough that we have very few chances to make the right choices. However, the problem guarantees that the probabilities are drawn randomly from the range [0.005, 0.1]. This should give us enough confidence that the probabilities will be different enough for our strategy to exploit.
The algorithm we have described can be shown to be at least as good as any other solution. But what if we had been less certain? In a problem with only Visible test sets, it is generally better to try (at the risk of a 4 minute penalty) than to spend more than 4 minutes worrying.
To solve this test set, we can use dynamic programming (DP). We define a function f(x, y) as the maximum number of ants that can form a stack (following the stack requirements given in the problem statement), in which we only consider ants from the first ant to the x-th ant, inclusive, and the sum of the ants' weight is not more than y.
We can compute the value of f(x, y) by considering two cases:
Between the two cases (or only one case if y < Wx), we take the larger value as the value of f(x, y).
The answer for the problem is the value of f(N, ∞). Since there are O(N) possible values for x, O(max(W)) possible values for y, and O(1) iterations for each computation of f(x, y), this solution runs in O(N × max(W)) time.
There is also another solution involving another DP formulation f', where f'(x, y) only considers ants from the x-th ant to the N-th ant (instead of the first ant to the x-th ant).
To solve this test set, we need to find the value of K, the maximum possible answer to the problem. To have a stack with as many ants as possible, where the upper-bound of the ants' weight is fixed by a constant (i.e. 109 in this problem), we greedily put the lightest ant possible on the bottom of the stack. In other words, a stack with as many ants as possible will have ants with weights something like (1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, ...). We stop as soon as we need to add an ant with a weight more than 109. By creating a simple script, we can determine that the value of K is 139, much smaller than N.
Therefore, we can solve this test set with another DP formula. We define a function g(x, y) as the minimum sum of the weights of the ants that can form a stack of y ants where only the ants from the first ant to the x-th ant are considered, or ∞ if no such stack exists.
Again, we can compute the value of g(x, y) by considering two cases:
Between the two cases (or only one case if g(x - 1, y - 1) > 6Wx), we take the smaller value as the value of g(x, y).
The answer for the problem is the largest possible value S where g(N, S) < ∞. Since there are O(N) possible values for x, O(K) possible values for y, and O(1) iterations for each computation of g(x, y), this solution runs in O(NK) time.