i understand first statements and 2nd statement, seems to me, is just application of 1st statement, and both seems not explaining why [L-1, R] is used, that is strange to me.
On Mon, Oct 12, 2009 at 6:17 PM, Bharath Raghavendran <[email protected]>wrote: > 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 <[email protected]> > >> 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 < >> [email protected]> wrote: >> >>> 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 -~----------~----~----~----~------~----~------~--~---
