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 -~----------~----~----~----~------~----~------~--~---
