OK, the qualification round is over, so here's how I solved all the problems:
A. Standing Ovation: Make a single pass through the list from 0 to max shyness, keeping track of (shyness level minus total audience members less shy than this), which is the number of additional 0-shy members needed to get the people at this shyness to stand when all less-shy people are standing. The maximum of this quantity is the answer. B. Infinite House of Pancakes: Always do all the special minutes at the start; this gives the diners you give extra pancakes to the most time to eat them. Always give pancakes to a diner with an empty plate, since there is an unlimited supply of those. Likewise, you only want to cut down the largest stacks, and if you cut one stack of a given size, you must cut all stacks of that size to get any possible benefit. Given that, define a maximum allowed stack size. Start with it equal to the maximum of the provided stack sizes (so there are no special minutes and the time required is this stack size), and iterate down to a maximum stack size of 1. For each maximum stack size, start with time = this stack size, and then iterate through the list of stack sizes, determining how many pieces you need to cut each stack into so that all are at or under this limit. Add the required special minutes to perform this operation. Print the smallest time you calculate for any of these maximum stack sizes. C. Dijkstra: Because quaternions are associative, if you divide the sequence into three portions, the first of which multiplies to i, the second to j, and the last to k, then the first two sections combined will multiply to ij, which is k, and all three combined multiply to -1. Also, since the 4th power of any of the quaternions we can encounter is 1, if we don't encounter the i product within 4 iterations of the string, we never will. If we don't then get the ij product before the end of the 8th iteration, we never will. And the product of the whole thing must be -1, but we can reduce it modulo 4 (but keeping at least 8 iterations. As a result, that scary limit of 10^16 iterations for the large case just doesn't matter. Write a procedure to do quaternion multiplication, and run through the string however many times (keeping in mind the above limits), calculating the running product, and also keeping track of which state you are in: haven't encountered the i product, got i but not ij, or got ij. At the end, if you didn't find ij or if the final product is not -1, then it's impossible. D. Ominous Omino: Just solve all the cases by hand and write a program which consists checking the various conditions: (1) If R*C is not divisible by X, then the grid can't be tiled at all. (2) if X >= 7 then Richard can give a polyomino with a hole that can never be filled. (3) if X >= max(R,C) then Richard wins by choosing the straight polyomino, which cannot fit in the grid. (4) If floor((X+1)/2) >= min(R,C) then Richard can choose an L-shaped polyomino with equal or almost-equal arms which can never fit in the grid. (5) If X is 1 or 2 (and if Richard didn't already win X=2 on an odd x odd grid), then these rectangular polyominoes always tile the grid. Gabriel wins. (6) If X is 3 and Richard didn't win by some method above, Gabriel wins. The straight 3 tiles all grids where one dimension is a multiple of 3, and for the bent 3, Gabriel puts 2 of them together to make a 2x3 rectangle and then fills the rest of the grid with straight 3s. (Richard has already won the 1-unit-wide grids with case 4 above.) (7) For X=4, if one dimension is 2, Richard wins by picking the S tetromino. Any placement of this piece divides the grid into two pieces with an odd number of squares in each. Otherwise, the grid is at least 3x4, and it is easy to put the given tetromino in the corner, divide the rest of the 3x4 into two tetrominoes, and fill the rest of the grid with straight tetrominoes. (8) For X=5, Richard wins the 3x5 grid with the W pentomino much like the previous case. But unlike that case, for the 3x10 grid, there's enough room to slide the given piece to make the space on each side of it be a multiple of 5, and then it is easy to partition the area. The 4x5 and larger cases are also easy wins for Gabriel. (9) For X-6, Richard wins all the 3-wide grids by picking the T-shaped hexomino which is 3 units tall and 4 units wide. This divides the remaining space into 3k+2 and 3k+4, which will never be a multiple of 6. Gabriel wins all grids which are at least 4 in both dimensions. On Sat, Apr 11, 2015 at 10:48 PM, al mashud <[email protected]> wrote: > which algorithms can be used for solving problem B,C and D...? > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/f47a547a-72a4-4761-9b0e-1a027030eb76%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMAzhzjhC%2BQDD30z9%3Dhq%2BxeUhLVx4D_JjojpQOfT1DLvZw%3DFMg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
