My replies inline ... -Bharath
2009/10/12 Hawston LLH <[email protected]> > Can someone explain point 2? > ".... And there are only O(sqrt(N)) palindromes up to N - so the number of > groups of consecutive zeros or ones in the first N characters is O(sqrt(N)). > consider N is some x digit number ... divide the digits into 2 parts .. first x/2 and the last x/2. Now assume that the first x/2 digits can be filled in k ways. For being a palindrome, the second x/2 is automatically decided. Otherwise, the second x/2 digits have their own k ways to be filled. Hence, there are roughly k palindromes in k^2 numbers. Hence O(sqrt(N)) palindromes up to N. > All groups except maybe two boundary ones fit into [L-1,R] segment > entirely...." > > what is the meaning of "All groups except maybe two boundary ones fit into > [L-1,R] segment entirely", is the group refers to group of ones > or zeros mentioned earlier? > Yes. consider [L-1,R] as 00000"0001111111100000000111"11111 here, you have 2 groups that fit entirely into the range. And the 2 boundary ones are not fitting. > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" 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 this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
