The answer is the number of strings that are at most distance K away, minus the number of periodic strings that are at most distance K away.
The number of periodic strings that are at most distance K away is equal to the sum over all factors P of N of the number of strings that are at most distance K away and are periodic of period exactly equal to P. The number of strings that are at most distance K away and are periodic of period exactly equal to P is equal to the number of strings that are at most distance K away and of period dividing P minus the sum over all factors Q of P of the number of strings that are at most distance K away and of period exactly equal to K. Then it gets complicated... On 28 Sep 2012, at 02:46, Jeong Heon <[email protected]> wrote: > due to your testcases have very small N(less than 20), you better try flip up > to K bits then check it's periodic or not. > > time complexity should be 2^N * (number of divisors of N) * N, so it won't > work in N>20 maybe. > > 2012/9/27 Tushar Vaidya <[email protected]> > Please help me on this problem............... > > Bob has received a binary string of length N transmitted by Alice. He knows > that due to errors in transmission, up to K bits might have been corrupted > (and hence flipped). However, he also knows that the string Alice had > intended to transmit was not periodic. A string is not periodic if it cannot > be represented as a smaller string concatenated some number of times. For > example, "0001", "0110" are not periodic while "00000", "010101" are periodic > strings. Now he wonders how many possible strings could Alice have > transmitted. > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msg/google-code/-/81HRIgKA9DoJ. > For more options, visit https://groups.google.com/groups/opt_out. > > > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
