If you take your solution for small, and just replace the multiplier by min(M,12 + M % 12) (can probably be made tighter) you should be able to solve the large in time.
I also checked the product of the input suffix matches the product of the output but I'm not sure this is required to meet the time constraints, worth checking. On Sunday, April 12, 2015 at 10:49:20 AM UTC+3, altaf hussain wrote: > On Sunday, April 12, 2015 at 8:38:08 AM UTC+5, /dev/joe wrote: > > 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. > > > > nice , will u please explain in detail Prob C . i passed its small input > ,making a single string and iterate it to find whether it can be divided into > i,j,k respectively . but i have confusion over large input . will u please > explain this logic > > " 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. " > thanks in advance -- 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/ea64002a-a697-4a4a-8ae5-f3fdf469f4ba%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
