For the admins, the big question in this contest was whether anyone would solve Problem D, King. Despite the confidence that you'll see in the problem's editorial, we strongly suspected that this would be the first problem in Google Code Jam 2008 that would go unsolved. The point value for its large dataset reflected our pessimism: it was worth as much as the other three larges put together!
By the end of the contest, we had our answer: nobody had successfully solved D-large, and the AMER local onsites were our first match where nobody solved every problem. When we looked at some submissions, though, we found a story behind the scenes: Ying, with great determination and only slightly too much confidence, went for D immediately. Among the few attempts on D-large (others of which used random methods), his was the only one that hit on the key of the solution. Unfortunately a single error in a single line made his program fail on a single test case, and he was left with too little time to solve the other problems.
The problems here were, in our view, the hardest among the three regional onsites, and every problem required some careful thinking or implementation. Only nine contestants submitted everything except D-large; some had minor errors, and only three solved all seven datasets. In the end Bohua claimed victory in this match, almost 8 minutes faster than second-place SkidanovAlexander.
Credits
Problem A. Mixing Bowls Written by John Dethridge. Prepared by Igor Naverniouk and Lovro Puzar.
Problem B. Code Sequence Written by John Dethridge. Prepared by Bartholomew Furrow and Lovro Puzar.
Problem C. Test Passing Probability Written by Robert Renaud. Prepared by Robert Renaud and Marius Andrei.
Problem D. King Written by Cosmin Negruseri. Prepared by Tomek Czajka and Bartholomew Furrow.
Contest analysis presented by Sebastian Kanthak, Bartholomew Furrow, Xiaomin Chen, and Cosmin Negruseri.
You are following a recipe to create your lunch.
The recipe is a mixture made by combining ingredients together in a bowl. Each ingredient will be either:
To make a mixture, you need to have all its ingredients ready, take an empty bowl and mix the ingredients in it. It is not possible to make mixtures by adding ingredients to an already-existing mixture in a bowl.
For example, if you want to make CAKE (a mixture) out of CAKEMIX (a mixture) and lies (a basic ingredient), then you must first make CAKEMIX in its own bowl, then add the CAKEMIX and lies to a second bowl to make the CAKE.
Once you have used a mixture as an ingredient and emptied the bowl it was prepared in, you can re-use that bowl for another mixture. So the number of bowls you need to prepare the recipe will depend on the order in which you decide to make mixtures.
Determine the minimum number of bowls you will need.
The first line will contain an integer C, the number of test cases in the input file.
For each test case, there will be:
The tokens on one line will be separated by single spaces.
The first mixture in a test case is the recipe you are making.
The names of mixtures are strings of between 1 and 20 UPPERCASE letters.
The names of basic ingredients are strings of between 1 and 20 lowercase letters.
Each mixture is used in exactly one other mixture, except for the recipe, which is not used in any other mixture. Each ingredient will appear at most once in the ingredient list for a mixture. No mixture will (directly or indirectly) require itself as an ingredient.
For each test case, output one line containing "Case #X: Y" where X is the number of the test case, starting from 1, and Y is the minimum number of mixing bowls required.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ C ≤ 10
2 ≤ M ≤ 10
1 ≤ N ≤ 10
1 ≤ N ≤ 1000
2 3 SOUP 3 STOCK salt water STOCK 2 chicken VEGETABLES VEGETABLES 2 celery onions 5 MILKSHAKE 4 milk icecream FLAVOR FRUIT FRUIT 2 banana berries FLAVOR 2 SPICES CHOCOLATE SPICES 2 nutmeg cinnamon CHOCOLATE 2 cocoa syrup
Case #1: 2 Case #2: 3
In the first case, to satisfy your craving for SOUP, you follow these steps:
In the second case, you have a choice of whether to make FLAVOR or FRUIT first before mixing them with milk and icecream to make MILKSHAKE.
If we make FRUIT first, we use four bowls:
However if we make FRUIT after FLAVOR, we use three bowls:
You are trying to compute the next number in a sequence Sn generated by a secret code. You know that the code was generated according to the following procedure.
First, for each k between 0 and 29, choose a number Ck between 0 and 10006 (inclusive).
Then, for each integer n between 0 and 1 000 000 000 (inclusive):
You will be given a series of consecutive values of sequence S, but you don't know at which point in the sequence your numbers begin (although you do know that there is at least one more number in the sequence), and you don't know what values of Ck were chosen when the sequence was generated.
Find the next number in the sequence, or output UNKNOWN if this cannot be determined from the input data.
The first line will contain an integer T, the number of test cases in the input file.
For each test case, there will be:
For each test case, output one line containing "Case #X: Y" where X is the number of the test case, starting from 1, and Y is the next number in the sequence, or the string UNKNOWN if the next number cannot be determined.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 20
1 ≤ N ≤ 5
1 ≤ N ≤ 1000
3 7 1 2 3 4 5 6 7 4 1 10 11 200 4 1000 1520 7520 7521
Case #1: UNKNOWN Case #2: 201 Case #3: 3514
In the first case, C0, C1 and C2 might have been 1, 2 and 4, and the values of Sn we have starting at n=1. If this is correct, we don't know C3, so the next number in the sequence could be anything! Therefore the answer is unknown.
In the second case, we cannot know all the values of Ck or even what n is, but we can prove that in any sequence, if 1, 10, 11, 200 occur in order, then the next value will always be 201.
Dave is taking a multiple choice test on the Internet. Dave possibly gets many opportunities to submit his answers to the test, but he passes only if he gets all the questions correct. He must answer every question on the test to make a submission. The only information he receives after he submits is whether he has passed.
For each question, he estimates the probability that each of 4 responses is correct, independent of his responses to other questions. Given a fixed number of submissions he can make, Dave wants to choose his responses so that he maximizes the probability of passing the test.
What is the probability that Dave will pass the test if he chooses his responses optimally?
The first line of input gives the number of cases, C. C test cases follow.
Each test case starts with a line containing M and Q. Dave is allowed to make M submissions to solve the test. There are Q questions on the test. Q lines follow, each containing 4 probabilities of correctness. There will be at most 6 digits after the decimal point. The probabilities for each line are non-negative and sum to 1.
For each test case, output one line containing "Case #X: Y"
where X is the number of the test case (starting from 1), and
Y is the probability of success.
Answers with a relative or absolute error of at most 10−6
will be considered correct.
Memory limit: 1GB.
1 ≤ C ≤ 100
Time limit: 60 seconds.
1 ≤ Q ≤ 6
1 ≤ M ≤ 1000
Time limit: 180 seconds.
1 ≤ Q ≤ 30
1 ≤ M ≤ 10000
3 10 2 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 64 3 0.3 0.4 0.0 0.3 1.0 0.0 0.0 0.0 0.2 0.2 0.2 0.4 3 2 0.5 0.17 0.17 0.16 0.5 0.25 0.25 0.0
Case #1: 0.625 Case #2: 1.0 Case #3: 0.5
Alice and Bob want to play a game. The game is played on a chessboard with R rows and C columns, for a total of RC squares. Some of these squares are burned.
A king will be placed on an unburned square of the board, and Alice and Bob will make successive moves with the king.
In a move, the player must move the king to any of its 8 neighboring squares, with the following two conditions:
If a player can't make a move, he or she loses the game. Alice will move first; you need to determine who will win, assuming both players play optimally.
The first line of input gives the number of cases, N.
N test cases follow. The first line of each case will contain two integers, R and C. The next R lines will contain strings of length C, representing the C squares of each row. Each string will contain only the characters '.', '#' and 'K':
There will be only one 'K' character in each test case.
For each test case, output one line containing "Case #X: " (where X is the case number, starting from 1) followed by A if Alice wins, or B if Bob wins.
Memory limit: 1GB.
1 ≤ N ≤ 100
Time limit: 30 seconds.
1 ≤ R, C ≤ 4
Time limit: 180 seconds.
1 ≤ R, C ≤ 15
2 2 2 K. .# 4 2 K# .# .# .#
Case #1: B Case #2: A
Looking at the restrictions on the recipe, it should be obvious that the recipes form a tree. It is also clear that basic ingredients can be ignored: You just throw them into whatever bowl you're currently working on.
Lets consider a recipe with k mixtures m1, ..., mk. How many bowls do we need to prepare this recipe? It does not make sense to work on more than one mixture at a time, so let's try preparing the mixtures in the given order.
We'll need b1 bowls to prepare the first mixture. For the second mixture, we can reuse these bowls, except for one bowl that we need to hold the first mixture. While preparing the third mixture (which requires b3 bowls in itself) we will need two additional bowls to hold the first two mixtures, and so on. Finally, once we have prepared all the mixtures, they sit in k different bowls, and we'll need one additional bowl to put everything together, and finish the recipe.
How many bowls did we use in total? Keeping in mind that we can reuse bowls from the previous step (except for the bowls to hold finished mixtures), we will need b = max(bi + i - 1) bowls to prepare all mixtures, for a total of max(b, k + 1) to put everything together.
Looking at this formula, it is obvious that the number of bowls will be minimized if we prepare the mixtures requiring the most bowls first. Thus, our algorithm will first invoke itself recursively for every ingredient, sort the results in descending order, and then use the formula given above to return a result.
Normally when you count in base 2, each bit is worth a fixed amount: {..., 8, 4, 2, 1}. So when you count 0000, 0001, 0010, 0011, and so on, you get the sequence [0, 1, 2, 3, ...]. In this problem, we ask you to consider what would happen if the bits were worth hidden amounts, "bit values," specified by us. For example, if the bits were worth {..., 200, 10, 1}, then you could get the sequence [0, 1, 10, 11, 200, 201, ...].
What this problem asks you to do is find the next number in the generated sequence. To make things more difficult, we don't necessarily start at 0000 or 0001, so what may seem obvious:
[1, 10, 11, 200, 201, ?, ...]
...may not be. This could have come from the bit values {..., 200, 10, 1}, which would give 210; but it could also have come from bit values {..., -1180, 1190, 990, 190, 1}. If we start counting from 10000, that gives:
[-1180, -1179, -990, -989, -190, -189, 0, 1, 10, 11, 200, 201, 1000]
So how do we solve the problem? Let's have a look at the generated sequence above, and look for interesting features. One thing that may strike you is that every second number is 1 higher than the last, so let's look at the sequence of differences between adjacent numbers:
(1, 189, 1, 799, 1, 189, 1, 9, 1, 189, 1, 799)
The differences of 1 make a lot of sense: every second increase in a binary number just changes the lowest bit from 0 to 1. So if your sequence of differences looks like (x, a, x, b), or (a, x, b), then the next difference must be x. Figuring that out should let you solve the small input.
But how far can we take this? Let's eliminate all the times only the lowest bit was changed. This leaves us with the following sequence of differences:
(189, 799, 189, 9, 189, 799)
Every second number there is a 189. That makes sense too: every fourth increase in a binary number is the same, changing the lowest two bits from 01 to 10. Likewise, every eighth increase changes the lowest three bits from 011 to 100.
So where does this leave us? Looking for repetition; seeing if we can use it; and if not, eliminating it. For example, if our generated sequence is:
[0, 1, 3, 4, 7, 8, 17, 18, 21, 22, 24, 25]
Our sequence of differences is:
(1, 2, 1, 3, 1, 9, 1, 3, 1, 2, 1)
Since the sequence ends with the repeated number, 1, we don't know yet what comes next. Eliminating the 1s, we arrive at:
(2, 3, 9, 3, 2)
Aha! The next difference must be 3, and the answer is 28. If that hadn't worked, we would have kept going recursively until we found the answer.
But what if the sequence of differences is:
(1, 2, 1, 2, 1)
Here, we can't tell if the lowest bit was changing for a difference of 1 or a difference of 2, so we can't say for sure what's next. We (eventually) arrive at the same problem in all of the following sequences of differences:
(1, 2) (3) (4, 3, 4) (5, 4, 5, 3, 5, 4, 5) (6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6)
Here it's IMPOSSIBLE to find the answer: that (1, 2) could be (1, 2, 1) or (1, 2, 10, 2). (4, 3, 4) could have come from:
10001 10010 10011 10100 10101 (4, 3, 4, 3)
or from:
00100 00101 00110 00111 01000 (4, 3, 4, ?)
There's no way to tell where you are in the range [0, 1000000000], so you could be about to hit a whole new bit and you wouldn't know it.
When we add up the values of our bits, we work modulo 10007. I used negative numbers earlier because the concept is well-defined in mod space: "-1180" mod 10007 is 8827, which is to say that adding 8827 to anything higher than 1180 is the same as subtracting 1180 from it.
One of the nice things about Code Jam is that you can test your assumptions. When writing the input generator for this problem, I asserted that the difference must look like [x, a, x, b, x, c, ...] or [a, x, b, x, c, x, ...]. This let me catch a bug in my code: I wasn't taking the differences mod 10007! In a live contest, I would have had time to fix that and submit.
Finally, there's one limit that's a red herring: that the sequence can't go past 109. It isn't hard to convince yourself that the restriction is meaningless: any sequence of length 1000 can't affect more than 11 separate bits, so it doesn't matter if the highest bit is #13 or #32.
There are 4Q points in the space, each of which contains an answer combination -- one answer for each of the Q questions. Because the answers to the questions are independent of each other, the probability of success at each point can be computed simply as the product of the probabilities from each problem.
So the simple mathematical model involves 4Q points, each with a probability value. There is a single, hidden good point among the 4Q points; you may pick up to M points; and you win the game if one of them is the good point. After you select a point, you learn if it is good or not, but that does not change the relative probabilities of the remaining points. The best strategy is simply looking at the points in the order of their probability. Your task in this problem is to compute the summation of the highest (up to) M among the 4Q values.
While Q looks moderate, 4Q steps of computation can be a huge task that is probably not within your computer's capacity (or any computer's). The important restriction in this problem is the fact that M is also moderate, and we can compute the highest M values one by one.
One solution uses a priority queue L that keeps all the answer combination candidates for the next highest value -- after we computed the first k values. A bit of thought should convince your that the next-highest (the k+1th) combination must be gotten by taking one of the first k combinations, and moving the answer to one of the questions one step "worse", to the next-most-probable answer. So in each step we can get the first element S (the one with the highest probability) from L, then add (up to) Q new candidates back to L. Each of the new candidates is created by moving one answer in S one step worse. The size of L will never exceed MQ, and the time complexity is O(MQ log MQ).
Another solution has an even simpler implementation: the idea is to add the questions one by one. For the first k questions, there are 4k possible solution combinations, each with its own probability of answering all of the first k questions correctly. When we add the k+1th question, the new set of possible solution combinations, along with its probabilities, can be calculated by taking each of the 4k previous values and multiplying it by the four probabilities for each answer to question k+1. We can easily compute all of these values and truncate to the top M, then repeat the process for the remaining questions. The truncation is O(M log M), and this process is repeated Q times, for a total time complexity of O(QM log M).
Discrete Probability - Joint Distribution
The problem corresponds to a relatively unknown game named Slither. This game was popularized by Martin Gardner in one of his columns written for Scientific American. It wasn't solved then, but eventually William Anderson developed a solution. Of course Code Jam participants are much smarter, so we thought the problem would easily get solved in two hours.
I'll explain first the solution for a simpler variant of the problem. Suppose we have a 3x3 board with the king being in one of the corner cells. Now let's cover the rest of the board with dominoes of size 2x1. This tiling of the board shows us a winning strategy for the second player. Each time the first player moves to one cell of a domino, the second player will move to the other cell of that domino. Since the second player can always make a move after the first player moves, the second player has a winning strategy.
The general solution goes along the same lines: the domino tiling corresponds to a maximum matching. We think of the board as a graph where the cells are the nodes, and neighboring cells have edges between them. The dominoes, then, correspond to edges in the maximum matching.
The solution is given by the following theorem: "The first player has a winning strategy if and only if all maximum matchings contain the king's node" .
This means that no alternating path starting from the king's node ends in a vertex that is not in the matching, because if it ended in a unmatched vertex we could construct another matching with the same number of edges that doesn't use the king's node. Thus the first player could always move along a matched edge.
If there is a maximum matching that doesn't contain the king's node, then in this graph every alternating path that starts from the kings node ends in a matched node, otherwise we could increase the size of the matching which contradicts the assumption that the matching is maximum. Thus now the second player can always move in the second node of the matching edges. So the second player has a winning strategy.
The graph in our problem is not bipartite so we can't use the standard algorithm for bipartite matching. Instead we use a solution that combines brute force and dynamic programming. Our solution will be exponential rather than polynomial, but the size of the problem is small so we can afford it. We go row by row from left to right, and for each cell (i, j) and each subset S of {0, 1, .. n - 1} we compute the best matching that has the following nodes matched already: nodes on the active line ([i][0..j], [i-1][j+1 .. n - 1]) that correspond to the numbers in S, and matched nodes from before the active line.
Here's Derek Kisman's code that implements this solution:
#include <algorithm>
#include <iostream>
using namespace std;
int gx, gy;
char g[15][15];
char memo[15][15][1<<16];
char doit(int x, int y, int b) {
if (x == gx) {
x = 0;
if (++y == gy) return 0;
}
char& ret = memo[x][y][b];
if (ret != -1) return ret;
int b2 = (b<<1) & ((1<<(gx+1))-1);
if (g[y][x] != '.') {
ret = doit(x+1, y, b2);
} else {
ret = doit(x+1, y, b2+1);
if (x && (b&1)) ret >?= 1 + doit(x+1, y, b2-2);
if (x && (b&(1<<gx)))
ret >?= 1 + doit(x+1, y, b2);
if (b&(1<<(gx-1)))
ret >?= 1 + doit(x+1, y, b2-(1<<gx));
if (x < gx-1 && (b&(1<<(gx-2))))
ret >?= 1 + doit(x+1, y, b2-(1<<(gx-1)));
}
return ret;
}
main() {
int N, prob=1;
for (cin >> N; N--;) {
cin >> gy >> gx;
int kx, ky;
for (int y = 0; y < gy; y++)
for (int x = 0; x < gx; x++) {
cin >> g[y][x];
if (g[y][x] == 'K') {kx = x; ky = y;}
}
memset(memo, -1, sizeof(memo));
int m1 = doit(0, 0, 0);
g[ky][kx] = '.';
memset(memo, -1, sizeof(memo));
int m2 = doit(0, 0, 0);
cout << "Case #" << prob++
<< ": " << ((m2 > m1) ? 'A' : 'B')
<< endl;
}
}