here are the statements that show the relation : "[L,R] can be represented as [0,R] minus [0,L-1]; thus it contains an even number of palindromes if and only if [0,L-1] and [0,R] both contain even or both contain odd number of palindromes."
"We can also reduce the number of boundary groups to consider from two to one relying on the fact that the number of zeroes/ones in [L-1,R] is the number of zeroes/ones in [0,R] minus the number of zeroes/ones in [0,L-2]." I didn't read the analysis properly and hence not sure why its [L-1, R] and not [L,R] and so cant comment on that. Is this what you were looking for? 2009/10/12 Hawston LLH <haws...@gmail.com> > another question, in point 1, it deals with [0, X], where X from L-1 to R. > In point 2 here, it use [L-1,R], what is the relation or typo error? > > > On Mon, Oct 12, 2009 at 5:48 PM, Bharath Raghavendran < > rbharat...@gmail.com> wrote: > >> My replies inline ... >> >> -Bharath >> >> 2009/10/12 Hawston LLH <haws...@gmail.com> >> >>> 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 google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
