Google Code Jam 2014 Round 1C
I qualified for round 2 already, but I woke up less than an hour into the time of round 1C, and I decided to check out what one of these rounds looks like live when you aren't competing. The answer is that you can see the scoreboard and the problems, but you can't download inputs (must less submit results) until the round ends. This let me mock-compete, starting my own 2.5 hour clock when I was ready, and when the contest ended, I checked results for the first two problems, which I had then completed. If I had been competing, I would have gotten the points for those problems and nothing else, and finished around rank 210 counting the time I needed for debugging and one penalty I would have gotten for a wrong small result.
A. Part Elf
This one's pretty easy. We know the fraction has to be expressible as X/2^40, and if it's not, the result is impossible. For the large input, where the number may not be in lowest terms, reducing it to lowest terms may trip up some people, while others may have an efficient GCD function built into their language's standard library and use it. For this problem, a pretty simple method is possible without using a built-in function. Since we know the result must contain only a power of 2 in the denominator, divide out all the powers of 2 (up to 40 of them; the limit on Q precludes there being more) from the denominator, and whatever is left over must be a factor of the numerator. If it is, divide it out; if not, report impossible and move on. And it doesn't matter here that we didn't reduce the 2s to lowest terms, because we're going to put them back anyway.
Now put those powers of 2 back in the denominator, and multiply numerator and denominator by 2 until the denominator is 2^40. Now the numerator tells the number of her 40-generations-ago ancestors wher were elves. Figure the largest power of 2 which the numerator is greater than or equal to. If we grouped all those 2^n ancestors in one part of her family tree, she could get a full-blooded elf ancestor 40-n generations ago. That's it.
B. Reordering Train Cars
This was a solid medium-difficulty problem. To solve it, I began by counting up the following statistics on each letter (using x as the example letter):
Now in order for us to make any valid orderings at all, then for each letter there must be at most one start and one end. This means:
If we made it through all those cases without proving it impossible, for each letter count the number of train sets that consist only of that letter. If this is n, there are n! (n factorial) ways to arrange those sets. If there are no mixed train sets starting or ending with this letter, then add this as an additional complete set. Otherwise, this belongs attached to or inside one of the complete sets we computed previously.
Now if there are m complete sets, there are m! ways to arrange those. And m! times all the n!s from the single-letter train sets is the answer. Be sure to incorporate a check to ensure you don't overflow integers and take the result modulo 1,000,000,007. This aspect of the problem reminded me of the things seen in Project Euler.
C. Enclosure
This reminds me up the Minesweeper Master problem from this year's qualification round. There's a two-dimensional grid, and there are all sorts of tricky edge cases. Like in that problem, the small input (with maximum area 20) permits a brute force search of all ways to put stones on the board and count up enclosed spaces, while the large one requires you to do real work.
First off, the maximal area which can be enclosed by a set of stones is not a square area with its corners cut off, which is what some people might initially guess:
@@@
@...@
@...@
@...@
@@@
Instead, it's a diamond shape:
@
@.@
@...@
@.....@
@...@
@.@
@
By the time I finished my analysis of this one, my self-timed event time was up without me having a chance to actually write the program. I went on, though, and wrote a program in another hour and change I wrote and debugged and confirmed my method. Basically, it works like this:
If one of the dimensions is 1 or 2, you can't enclose any squares and the answer is K. Otherwise, start with a diamond made of 4 stones enclosing a 5th space, and proceed. Repeatedly add a stone and push out one side of the diamond. The exact result of this varies modulo 4 in the number of stones. While the grid is big enough:
Going from a diamond with 4k stones to shape with 4k+1 stones (in each diagram, % indicates the stones I am removing and # shows their new locations, including one added stone):
@
@.@
@...@
@.%#
@#
Going from a shape with 4k+1 stones to shape with 4k+2 stones (note that this increases the width by 1, but if you need one less space, you can make do with sliding that rightmost one back to the left, and not increasing the width):
@#
@.%#
@...%#
@..@
@@
Going from a shape with 4k+2 stones to shape with 4k+3 stones (this one increases the height, but again can avoid doing so if you need one less space:
#
#%@
#%..@
#%...@
@..@
@@
Going from a shape with 4k+3 stones to shape with 4k+4 stones. This one is tricky. If you can't increase the width or height, use the diagram on the left. If you can increase both, do so and use the diagram on the right to do it with one additional space covered.
#@ or @
#%.@ @.@
#%...@ @...@
@....@ @....%#
@..@ @..%#
@@ @%#
#
Now all this works fine as long as the grid is large enough for these shapes. When it's not, move into part B, where we assume the height is constrained by the smaller of the two given dimensions but the width is not. There are two cases here depending on whether the height is even or odd.
If it's even, we're going to be starting with the left diagram from the 4k+3 -> 4k+4 case above. Each move is going to add height/2 spaces by pushing one edge out, and when the number of stones goes from even to odd, this increases the width by 1 (again, optionally if we don't need all the spaces).
If it's odd, start with a diamond with k stones on each edge (4k-4 in all). The even->odd stone move adds k-1 spaces without changing the width, and the odd->even stone move adds k spaces, adding one to the width.
If we reach the width limit as well, move into part C. Here, determine from the diagrams above the number of stones along each diagonal edge of the shape when both limits have been reached and we want to extend the width further but cannot. If the longest such edge has k stones, add one stone and push the edge out to add k-1 spaces without increasing the width or height of the overall figure. This can continue all the way until you completely fill the edge of the rectangle, which is necessary if K=N*M.
In my program, I implemented the dimension-changing moves in two steps, first adding all but one of the spaces without increasing the size, and then if necessary adding the last stone and increasing the size, or aborting and moving into the next step if this would violate the size limit.
Although it seems kind of lazy to do it this way instead of computing the formulas for the sizes of all these shapes with some algebra, since the dimensions are limited to 1000 in the large case, this is no more than 2000 steps to reach the diamond that reaches the size limits (end of part B) and another 2000 steps to reach the bounding rectangle in part C, so it's actually pretty fast. (Less than this, since it's the area, not dimensions, which are limited to 1000, so my worst case is a 3x333 rectangle.) If they really wanted you to do the algebra, they should have made the dimensions go up to a billion or something. That, by the way, is the kind of thing to expect in a round 2 or 3.
A. Part Elf
This one's pretty easy. We know the fraction has to be expressible as X/2^40, and if it's not, the result is impossible. For the large input, where the number may not be in lowest terms, reducing it to lowest terms may trip up some people, while others may have an efficient GCD function built into their language's standard library and use it. For this problem, a pretty simple method is possible without using a built-in function. Since we know the result must contain only a power of 2 in the denominator, divide out all the powers of 2 (up to 40 of them; the limit on Q precludes there being more) from the denominator, and whatever is left over must be a factor of the numerator. If it is, divide it out; if not, report impossible and move on. And it doesn't matter here that we didn't reduce the 2s to lowest terms, because we're going to put them back anyway.
Now put those powers of 2 back in the denominator, and multiply numerator and denominator by 2 until the denominator is 2^40. Now the numerator tells the number of her 40-generations-ago ancestors wher were elves. Figure the largest power of 2 which the numerator is greater than or equal to. If we grouped all those 2^n ancestors in one part of her family tree, she could get a full-blooded elf ancestor 40-n generations ago. That's it.
B. Reordering Train Cars
This was a solid medium-difficulty problem. To solve it, I began by counting up the following statistics on each letter (using x as the example letter):
- S(x): The number of train sets which start but do not end with the letter
- E(x): The number of train sets which end with but do not start with the letter
- M(x): The number of train sets which contain the letter in the middle but do not start or end with it
- A(x): The number of train sets which all of the cars have this letter
Now in order for us to make any valid orderings at all, then for each letter there must be at most one start and one end. This means:
- S(x), E(x), and M(x) must be at most 1.
- If M(x) is 1 then S(x) and E(x) and A(x) must be 0.
If we made it through all those cases without proving it impossible, for each letter count the number of train sets that consist only of that letter. If this is n, there are n! (n factorial) ways to arrange those sets. If there are no mixed train sets starting or ending with this letter, then add this as an additional complete set. Otherwise, this belongs attached to or inside one of the complete sets we computed previously.
Now if there are m complete sets, there are m! ways to arrange those. And m! times all the n!s from the single-letter train sets is the answer. Be sure to incorporate a check to ensure you don't overflow integers and take the result modulo 1,000,000,007. This aspect of the problem reminded me of the things seen in Project Euler.
C. Enclosure
This reminds me up the Minesweeper Master problem from this year's qualification round. There's a two-dimensional grid, and there are all sorts of tricky edge cases. Like in that problem, the small input (with maximum area 20) permits a brute force search of all ways to put stones on the board and count up enclosed spaces, while the large one requires you to do real work.
First off, the maximal area which can be enclosed by a set of stones is not a square area with its corners cut off, which is what some people might initially guess:
@@@
@...@
@...@
@...@
@@@
Instead, it's a diamond shape:
@
@.@
@...@
@.....@
@...@
@.@
@
By the time I finished my analysis of this one, my self-timed event time was up without me having a chance to actually write the program. I went on, though, and wrote a program in another hour and change I wrote and debugged and confirmed my method. Basically, it works like this:
If one of the dimensions is 1 or 2, you can't enclose any squares and the answer is K. Otherwise, start with a diamond made of 4 stones enclosing a 5th space, and proceed. Repeatedly add a stone and push out one side of the diamond. The exact result of this varies modulo 4 in the number of stones. While the grid is big enough:
Going from a diamond with 4k stones to shape with 4k+1 stones (in each diagram, % indicates the stones I am removing and # shows their new locations, including one added stone):
@
@.@
@...@
@.%#
@#
Going from a shape with 4k+1 stones to shape with 4k+2 stones (note that this increases the width by 1, but if you need one less space, you can make do with sliding that rightmost one back to the left, and not increasing the width):
@#
@.%#
@...%#
@..@
@@
Going from a shape with 4k+2 stones to shape with 4k+3 stones (this one increases the height, but again can avoid doing so if you need one less space:
#
#%@
#%..@
#%...@
@..@
@@
Going from a shape with 4k+3 stones to shape with 4k+4 stones. This one is tricky. If you can't increase the width or height, use the diagram on the left. If you can increase both, do so and use the diagram on the right to do it with one additional space covered.
#@ or @
#%.@ @.@
#%...@ @...@
@....@ @....%#
@..@ @..%#
@@ @%#
#
Now all this works fine as long as the grid is large enough for these shapes. When it's not, move into part B, where we assume the height is constrained by the smaller of the two given dimensions but the width is not. There are two cases here depending on whether the height is even or odd.
If it's even, we're going to be starting with the left diagram from the 4k+3 -> 4k+4 case above. Each move is going to add height/2 spaces by pushing one edge out, and when the number of stones goes from even to odd, this increases the width by 1 (again, optionally if we don't need all the spaces).
If it's odd, start with a diamond with k stones on each edge (4k-4 in all). The even->odd stone move adds k-1 spaces without changing the width, and the odd->even stone move adds k spaces, adding one to the width.
If we reach the width limit as well, move into part C. Here, determine from the diagrams above the number of stones along each diagonal edge of the shape when both limits have been reached and we want to extend the width further but cannot. If the longest such edge has k stones, add one stone and push the edge out to add k-1 spaces without increasing the width or height of the overall figure. This can continue all the way until you completely fill the edge of the rectangle, which is necessary if K=N*M.
In my program, I implemented the dimension-changing moves in two steps, first adding all but one of the spaces without increasing the size, and then if necessary adding the last stone and increasing the size, or aborting and moving into the next step if this would violate the size limit.
Although it seems kind of lazy to do it this way instead of computing the formulas for the sizes of all these shapes with some algebra, since the dimensions are limited to 1000 in the large case, this is no more than 2000 steps to reach the diamond that reaches the size limits (end of part B) and another 2000 steps to reach the bounding rectangle in part C, so it's actually pretty fast. (Less than this, since it's the area, not dimensions, which are limited to 1000, so my worst case is a 3x333 rectangle.) If they really wanted you to do the algebra, they should have made the dimensions go up to a billion or something. That, by the way, is the kind of thing to expect in a round 2 or 3.