Google Code Jam 2013 is off and running! We have 17059 advancers out of 21962 people who correctly solved at least one input, and 45754 registrants. All those numbers are records for us!
We started with Tomek's variation on a game for children (who is this Tomek anyway?!), and then quickly delved into the riddles of lawnmowers, palindromes, and pirates. Overall, it was a pretty tough set this year, with problem D in particular being something that could have been a Finals problem. A huge congratulations to the 63 people who managed to solve everything!
There are three more rounds to go before the Finals, and we're just getting started. We hope to see all the advancers in the First Rounds!
Problem A. Tic-Tac-Toe-Tomek Written by Tomek Kulczyński and Bartholomew Furrow. Prepared by Onufry Wojtaszczyk and Bartholomew Furrow.
Problem B. Lawnmower Written by Onufry Wojtaszczyk. Prepared by Jan Kuipers and Onufry Wojtaszczyk.
Problem C. Fair and Square Written by Onufry Wojtaszczyk. Prepared by Nikolay Kurtov and Onufry Wojtaszczyk.
Problem D. Treasure Written by David Arthur. Prepared by Tomek Kulczyński and David Arthur.Contest analysis presented by Onufry Wojtaszczyk and David Arthur. Solutions and other problem preparation by Igor Naverniouk, Tomek Czajka, Karim Nosseir, Hao Pan, and Petr Mitrichev.
Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single 'T' symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X's symbol is 'X', and player O's symbol is 'O'.
After a player's move, if there is a row, column or a diagonal containing 4 of that player's symbols, or containing 3 of her symbols and the 'T' symbol, she wins and the game ends. Otherwise the game continues with the other player's move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.
Given a 4 x 4 board description containing 'X', 'O', 'T' and '.' characters (where '.' represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:
If there are empty cells, and the game is not over, you should output "Game has not completed", even if the outcome of the game is inevitable.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of 4 lines with 4 characters each, with each character being 'X', 'O', '.' or 'T' (quotes for clarity only). Each test case is followed by an empty line.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is one of the statuses given above. Make sure to get the statuses exactly right. When you run your code on the sample input, it should create the sample output exactly, including the "Case #1: ", the capital letter "O" rather than the number "0", and so on.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
The game board provided will represent a valid state that was reached through play of the game Tic-Tac-Toe-Tomek as described above.
1 ≤ T ≤ 10.
1 ≤ T ≤ 1000.
6 XXXT .... OO.. .... XOXT XXOO OXOX XXOO XOX. OX.. .... .... OOXX OXXX OX.T O..O XXXO ..O. .O.. T... OXXX XO.. ..O. ...O
Case #1: X won Case #2: Draw Case #3: Game has not completed Case #4: O won Case #5: O won Case #6: O won
Although your browser might not render an empty line after the last test case in the sample input, in a real input file there would be one.
Alice and Bob have a lawn in front of their house, shaped like an N metre by M metre rectangle. Each year, they try to cut the lawn in some interesting pattern. They used to do their cutting with shears, which was very time-consuming; but now they have a new automatic lawnmower with multiple settings, and they want to try it out.
The new lawnmower has a height setting - you can set it to any height h between 1 and 100 millimetres, and it will cut all the grass higher than h it encounters to height h. You run it by entering the lawn at any part of the edge of the lawn; then the lawnmower goes in a straight line, perpendicular to the edge of the lawn it entered, cutting grass in a swath 1m wide, until it exits the lawn on the other side. The lawnmower's height can be set only when it is not on the lawn.
Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it's possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.
The grass is initially 100mm high on the whole lawn.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers: N and M. Next follow N lines, with the ith line containing M integers ai,j each, the number ai,j describing the desired height of the grass in the jth square of the ith row.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either the word "YES" if it's possible to get the x-th pattern using the lawnmower, or "NO", if it's impossible (quotes for clarity only).
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ N, M ≤ 10.
1 ≤ ai,j ≤ 2.
1 ≤ N, M ≤ 100.
1 ≤ ai,j ≤ 100.
3 3 3 2 1 2 1 1 1 2 1 2 5 5 2 2 2 2 2 2 1 1 1 2 2 1 2 1 2 2 1 1 1 2 2 2 2 2 2 1 3 1 2 1
Case #1: YES Case #2: NO Case #3: YES
Little John likes palindromes, and thinks them to be fair (which is a fancy word for nice). A palindrome is just an integer that reads the same backwards and forwards - so 6, 11 and 121 are all palindromes, while 10, 12, 223 and 2244 are not (even though 010=10, we don't consider leading zeroes when determining whether a number is a palindrome).
He recently became interested in squares as well, and formed the definition of a fair and square number - it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are fair and square (being palindromes and squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are not fair and square: 16 is not a palindrome, 22 is not a square, and while 676 is a palindrome and a square number, it is the square of 26, which is not a palindrome.
Now he wants to search for bigger fair and square numbers. Your task is, given an interval Little John is searching through, to tell him how many fair and square numbers are there in the interval, so he knows when he has found them all.
Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has 1 Small input and 2 Large inputs. Once you have solved the Small input, you will be able to download any of the two Large inputs. As usual, you will be able to retry the Small input (with a time penalty), while you will get only one chance at each of the Large inputs.
The first line of the input gives the number of test cases, T. T lines follow. Each line contains two integers, A and B - the endpoints of the interval Little John is looking at.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of fair and square numbers greater than or equal to A and smaller than or equal to B.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ A ≤ B ≤ 1000.
1 ≤ T ≤ 10000.
1 ≤ A ≤ B ≤ 1014.
1 ≤ T ≤ 1000.
1 ≤ A ≤ B ≤ 10100.
3 1 4 10 120 100 1000
Case #1: 2 Case #2: 0 Case #3: 2
Following an old map, you have stumbled upon the Dread Pirate Larry's secret treasure trove!
The treasure trove consists of N locked chests, each of which can only be opened by a key of a specific type. Furthermore, once a key is used to open a chest, it can never be used again. Inside every chest, you will of course find lots of treasure, and you might also find one or more keys that you can use to open other chests. A chest may contain multiple keys of the same type, and you may hold any number of keys.
You already have at least one key and your map says what other keys can be found inside the various chests. With all this information, can you figure out how to unlock all the chests?
For example, suppose the treasure trove consists of four chests as described below, and you began with exactly one key of type 1:
Chest Number | Key Type To Open Chest | Key Types Inside --------------+--------------------------+------------------ 1 | 1 | None 2 | 1 | 1, 3 3 | 2 | None 4 | 3 | 2You can open all the chests in this example if you do them in the order 2, 1, 4, 3. If you start by opening chest #1 first, then you will have used up your only key, and you will be stuck.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing two positive integers K and N, representing the number of keys you start with and the number of chests you need to open.
This is followed by a line containing K integers, representing the types of the keys that you start with.
After that, there will be N lines, each representing a single chest. Each line will begin with integers Ti and Ki, indicating the key type needed to open the chest and the number of keys inside the chest. These two integers will be followed by Ki more integers, indicating the types of the keys contained within the chest.
For each test case, output one line containing "Case #x: C1 C2 ... CN", where x is the case number (starting from 1), and where Ci represents the index (starting from 1) of the ith chest that you should open.
If there are multiple ways of opening all the chests, choose the "lexicographically smallest" way. In other words, you should choose to make C1 as small as possible, and if there are multiple ways of making C1 as small as possible, choose the one that makes C2 as small as possible, and so on.
If there is no way to open all the chests, you should instead output one line containing "Case #x: IMPOSSIBLE".
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 25.
1 ≤ K.
All key types will be integers between 1 and 200 inclusive.
1 ≤ N ≤ 20.
In each test case, there will be at most 40 keys altogether.
1 ≤ N ≤ 200.
In each test case, there will be at most 400 keys altogether.
3 1 4 1 1 0 1 2 1 3 2 0 3 1 2 3 3 1 1 1 1 0 1 0 1 0 1 1 2 1 1 1
Case #1: 2 1 4 3 Case #2: 1 2 3 Case #3: IMPOSSIBLE
In this problem, you had to classify the state of a Tic-Tac-Toe game with a twist. The board is 4x4, and an extra symbol can appear on the board - a "T", which either player can use for victory.
Note that you are guaranteed by the problem description the input will always describe a board that was obtained by a correct sequence of moves. As the game ends when one player wins, this guarantees that only one player can have four symbols (or 3 symbols and a T) in a completed line.
Thus, the simplest way to check whether a player, say "X", won is to check all rows, columns and diagonals whether they contain only "T"s and "X"s. Do not forget to check both diagonals! If there is a row, column or diagonal containing no "."s or "O"s, we know that X won. Similarly, if there is a row, column or diagonal contianing no "X"s or "."s, O won.
If none of the players won, we only have to distinguish between a draw and a game not completed. This is relatively simple - if the board contains even a single ".", the game has not completed yet; otherwise it's a draw.
Note that your solutions are checked automatically, by a program. This means that your output has to be exactly matching the specification. A number of contestants had problems due to returning "O Won" instead of "O won" or "The game has not been completed" instead of "Game has not completed". In a programming competition it is important to follow the specification of the output as exactly as possible.
Here is a complete solution in Python for reference:
import sys def solve(b): for c in ['X', 'O']: wind1 = True wind2 = True for x in range(4): winh = True winv = True for y in range(4): if b[y][x]!=c and b[y][x]!='T': winv = False if b[x][y]!=c and b[x][y]!='T': winh = False if winh or winv: return c + ' won' if b[x][x]!=c and b[x][x]!='T': wind1 = False if b[3-x][x]!=c and b[3-x][x]!='T': wind2 = False if wind1 or wind2: return c + ' won' for x in range(4): for y in range(4): if b[y][x]=='.': return 'Game has not completed' return 'Draw' numcases = int(sys.stdin.readline()) for casenum in range(1,numcases+1): board =  for i in range(0,5): board.append(sys.stdin.readline().strip()) print 'Case #' + repr(casenum) + ': ' + solve(board)
For a problem like this, it can be helpful to think through a few cases. Let's look at the first two examples from the problem statement:
2 2 2 2 2 2 1 1 1 2 2 1 2 2 1 2 1 2 1 1 1 2 1 1 1 2 2 1 2 2 2 2 2 2
All the grass needs to be cut to either height 1 or 2. Thus, we can begin by cutting the whole lawn to height 2. The question that remains is which rows and which columns to cut to height 1. Note that if we cut a row (or column) to height 1, all the squares in this row or column will be height 1 in the final pattern since we can't grow grass back.
In the left example, we must at some point do a cut with the lawnmower at height 1. Otherwise, we would never get any grass that low. However, there is nowhere that it is safe to make a cut like that. Every row and every column has at least one square where we want the final grass height to be 2, so we can never run the lawnmower through that row or column while at height 1. This pattern is impossible.
In the second example, we also must do some cuts with the lawnmower at height 1. However, in this case, there are two places where we can safely make that cut: the middle row and the middle column. If we do both, we get the desired pattern.
More generally, there are some rows and columns we cannot cut to height 1. By avoiding those rows and columns, we ensure nothing will be made too low. What remains is to check if it is still possible to get all the grass low enough. Well, if our only goal is to get the grass low, we should do all the cuts we can!
This suggests the following approach:
For the large input, we can use almost the exact same strategy. You just have to think through what that means!
We can cut any row or column at a height that is equal to the maximum height appearing in this row (or column). As long as we follow this rule, we will never cut a square too low, and then as above, we just need to try to get everything low enough. For that purpose, we want to use all the cuts we can. The full algorithm is then:
The first thing to do in this problem (as in many other problems) is to make sure you read it carefully. Many contestants thought that 676 should be a fair and square number - after all, it is a square and a palindrome. It is not, however, a square of a palindrome, and this example is actually mentioned specifically in the problem statement!
Once you realize this, you can approach the small testcase by iterating over all the numbers Little John considers, and checking each one of them. You have to check for each number X whether it is a palindrome, and whether it is the square of a palindrome.
To check whether X is a palindrome, you can simply convert it to string format (the details here depend on the programming language you are using) and compare the first character to the last, the second to the second last, and so on.
To check whether X is the square of a palindrome, there are multiple options. One is to calculate the square root, and if the square root is an integer, check if it is a palindrome as described above. Another is simply to iterate over all numbers up to X, and for each palindrome, square it and see if the square is X. That's a perfectly good solution for the small input, but it will be too slow for the larger ones.
For the first large input, we need to deal with numbers up to 1014, and also with 10,000 test cases. A linear search of all numbers up to 1014 is not going to be fast enough, so we have to be smarter - we can't afford to check each number in the interval individually.
We don't really need to go all the way up to 1014 though! We are interested in numbers whose squares are Fair and Square and between A and B - and that means we have to check up to the square root of B only. That's only 107 numbers to check in the worst case.
We are not done though. While 107 numbers can be processed within the time limit, processing 10,000 cases like this is somewhat risky. There are two tricks you can notice to make your solution faster.
One trick is that we are interested not in all the numbers up to 107, but only in palindromes. We can generate all the palindromes much faster. Start by taking all the numbers up to 104, and then taking their mirror reflections (either duplicating the last number or not) to generate all palindromes of length up to 8 (and then square each and check whether it is a Fair and Square number in the interesting interval). This will cause us to evaluate only around 10,000 numbers for each test case, which is small enough that even a slow machine can deal with all the test cases in four minutes. You would need to use a reasonably efficient language however.
An alternative is to simply generate all the fair and square numbers up to 1014 before processing the test cases. There are relatively few of them — it turns out only 39. Thus, if you find all of them (in any fashion) before downloading the input file, you can easily give the correct answers to all the input cases.
Note that if you do this, you have to include the code you used to generate Fair and Square numbers - not just the code that includes the full list!
Now we come to the largest data set. Even combining both the tricks above is not enough - we need to go over 1025 palindromes to precompute everything. This will take a very long time in any language on any computer! A good idea here is to generate the first few Fair and Square numbers (and their square roots) to try and get an idea of what they look like. There are two things you can notice:
Let's try to understand why these things would be true.
Let's begin with the "odd number of digits". A square of a number with N digits will have either 2N - 1 or 2N digits, depending on whether there is a carry on the last position. Let's try to prove a carry never happens. Let X be Fair and Square, and let its square root be Y. Let the first digit of Y be c - then the first two digits of X are between c2 and (c+1)2. In particular:
This means there is no carry in the first digit.
Now since all the digits seem so small, maybe this means there is no carry at all? Note that if you take a palindrome and square it, and there's no carry, the result is a palindrome as well - so that would give us a nice characterization of Fair and Square numbers. Indeed, it turns out to be the case, and the proof follows.
Let Y have digits (ad)(ad-1)...(a0). Let bk = a0 * ak + a1 * ak-1 + ... + ak * a0. Note that bi is exactly the ith digit of X = Y2 when performing long multiplication, before carries are performed. Since aj = ad-j, we also have bi = b2d-i.
Now suppose there's a carry in the long multiplication (meaning some bj is greater than 9), and that we take a carry into digit i but no larger digits. We know digits i and 2d-i in X are equal, and are equal to bi plus whatever we carried into digit i. Since we carry nothing to digit i+1, bi is no larger than 9.
Now we will see that digit 2d-i of X has to equal b2d-i (which is equal to bi, and thus no larger than 9). For it to be different, we would have to carry something into digit 2d-i - but this would mean that bj is larger than 9 for some j < 2d-i, and hence b2d-j is also greater than 9 and we would have a carry after digit i.
Since X is a palindrome, this tells us that digit i of X is equal to bi, which means that no carry entered digit i, and we have a contradiction.
We conclude that no carries were performed in the long multiplication at all.
Thus, the Fair and Square numbers are exactly the palindromes with no carries inside. In particular, the middle digit of X is the sum of squares of all the digits of Y, so this sum has to be no larger than nine. We conclude that only 0, 1, 2, and 3 can appear in Y.
To find all Fair and Square numbers, it therefore suffices to consider only palindromes consisting of these four digits, with the sum of squares of digits at most 9. It turns out this is a small enough set that it can be directly searched, allowing us to generate the full list of all Fair and Square numbers up to 10100 in a few seconds - and thus allowing us to solve the largest dataset.
There are a few things we want to remind you of in the context of this problem:
This problem asks you to open the chests in the lexicographically smallest order. As if it's not hard enough to find just any old way to open the chests, we make you find a particular way! If you have not tried similar problems before, this part might seem especially daunting.
However, it's a red herring. Suppose you can answer the following simpler question: "Is it possible at all to open all the chests?". Then you can use that as a black box to find the lexicographically smallest way of opening them. Check whether you have the key to open chest #1 first, and whether the black box says it is possible to open all the remaining chests after doing so. If the answer to both questions is yes, then you should definitely start by opening chest #1. Otherwise, you have no choice but to try a different chest. Repeating this logic for every chest at every time, you can get the lexicographically smallest solution.
This is not very fast, but there aren't too many chests to worry about here, so that's okay. And that means, from now on, we can focus on the slightly simpler question: "Is it possible to open all the chests?".
Unfortunately, even this question is still pretty hard!
When dealing with a really tricky problem, it can sometimes be helpful to look at special cases to build up your intuition. Towards that end, let's suppose that you begin with exactly one key, that one chest is empty, and that all remaining chests also contain exactly one key. Why look at this case in particular? You'll see!
In this version of the problem, you will always have exactly one key at any given time. When you open a chest of type A containing a key of type B, you are switching from a key of type A to a key of type B. This suggests that we can represent the problem as a graph. We will have one vertex for each chest/key type, and for every chest, we will add a directed edge from the chest type to the contained key type.
You begin with a single key, and then you must choose a chest of the matching type, giving you a key of perhaps a different type. From there, you must choose a chest of the new type, and so on, eventually choosing every chest exactly once. In the graph formulation, you can think of this as beginning at the vertex corresponding to your starting key, and then repeatedly following edges, using each edge exactly once. In other words, you are looking for an Eulerian Path on the graph!
The good news here is that Eulerian Path is a famous problem and you can look up on the internet how to tell if one exists:
The bad news is that if this special case is already as hard as Eulerian Path, the full problem is going to be even harder!
If you come up with the previous observation, the first thing you might try is to reduce the full problem directly to Eulerian paths. Unfortunately, this is probably doomed to fail. Once you have multiple keys in a single chest, there is no graph structure to use. (Nothing we have found anyway!)
The better plan is to generalize only the conditions required for an Eulerian path to exist. In fact, those conditions can be described very naturally in terms of chests and keys:
Let's say a chest/key configuration is connected if it satisfies the second condition, and good if it satisfies both conditions. It turns out that it is possible to open all the chests if and only if the configuration is good!
And it is not too hard to check if a configuration is good - the first condition is just a count, and the second can be checked with a Breadth First Search or a Depth First Search. So all that remains for a complete solution is convincing ourselves that checking goodness is indeed equivalent to the original problem:
Claim: It is possible to open all the chests if and only if the configuration is good.
Proof: One direction is easy. If the configuration is not good, then we will never be able to open enough chests of one type, either because there are not enough keys, or because we can never reach even one of those keys.
For the other direction, let's suppose we have a good configuration. Nothing we do from this point on will change whether there are enough keys of each type. We will show there is always at least one chest we can open that also maintains the connectivity property. The resulting configuration would then also be good, so there would also be a chest we could open there that would maintain connectivity, and so on. Repeating, we can keep opening chests until there is nothing left.
So all we need to do is prove that there is at least one chest that can be opened without breaking connectivity. We know the configuration is connected initially. For each type T, there is a sequence of chests we can open to get a key of type T. To be precise, here exists a sequence of types T1, T2, ..., Tn, with the following properties:
Suppose you have a key of some arbitrary type A. If you already have all keys of type A, then you can open all the chests of type A, and doing so will certainly not break connectivity. So that case is easy.
Otherwise, there must exist some chest of type B containing a key of type A. Let T1, T2, ..., Tn-1=B, Tn=A denote a sequence of key types that you can go through to get a key of type B and then use that to get another key of type A. As mentioned above, we know such a sequence must exist. We can also assume that Ti != A for 1 < i < n. Otherwise, we could just chop off part of the sequence to get a faster method! Now we consider two cases:
Therefore, no matter what happens, you can always open a chest without breaking connectivity, and the claim is proven!