We are told in the problem that quaternion multiplication is associative: a*(b*c)=(a*b)*c. While we have to keep the factors in order left to right, we can perform the multiplications within that sequence in any order. So, if x is the result of multiplying out one instance of the repeating sequence, then the product of the entire sequence would be x*x*x*x*x*x*...
The only quaternion values we can encounter are 1, -1, i, -i, j, -j, k, and -k. Look at the multiplication table given in the problem, and notice that multiplying any quaternion by itself (x*x) gives either 1 or -1. The negatives aren't listed, but multiplying both factors by -1 does not change the product. So the fourth power of a quaternion, that is, x*x*x*x, or (x*x)*(x*x), is either 1*1 or (-1)*(-1) which are both 1. Multiplying 1 by any quaternion (with the 1 on either side of the multiplication) does nothing. So if any of the groups which have to multiply to make i, j, or k contains 4 or more full copies of the repeating sequence, we can ignore those 4 copies, because multiplying them first gives a 1 which does not affect the rest of the product. That said, if the input string is 12 or more copies of the same sequence, then at least 4 of those copies must end up in one of the three substrings which multiply to i, j, or k, and we can calculate the result quicker by skipping the entire set of 4 sequences. Likewise, if this occurs in the i or j substring, we can shorten it by 4 full sequences, and add those to the k substring to get an equivalent solution. And when calculating k, we can omit calculating the last 4N full sequences and still get the right answer. This means that for any solution, there is an equivalent solution in which the i, j, and k substrings are each less than 4 full copies of the sequence, and the combination of these is 4N full sequences less than what was originally given. Since each of the three is less than 4 full sequences, the result will be less than 12 full sequences. So if the input has 12 or more copies of the sequence, replace the number of copies X with 8 + X mod 4. Then you can apply the small solution to a string of no more than 110000 quaternions. This should still run quickly enough, even though it is potentially 11 times as long as the limit of the short solution was. On Sun, Apr 12, 2015 at 3:23 AM, altaf hussain <[email protected]> wrote: > On Sunday, April 12, 2015 at 8:38:08 AM UTC+5, /dev/joe wrote: > > 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. > > 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/CAMAzhzjaHpBf5u6%2BUB622iZUydnRdFcwEuqZUuVkMqfcyk29kQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
