The answer to "What is the largest value of (a XOR x[i]) for s <= i <= e)?" can be answered one bit at a time:
* Let ans=0 and j=15. Clearly the largest value of (a XOR x[i])/2^j for s <= i <= e is ans. ( division here being integer division ) Clearly, if this is true, the largest value of (a XOR x[i])/2^(j-1) s <= i <= e is either 2ans or 2ans+1. Clearly, it is 2ans+1 if there exists s <= i <= e with x[i]/2^(j-1) equal to (a/2^j) XOR (2ans +1) and 2ans otherwise. * while (j > 0): *. ans = (2 * ans) + 1 *. j -= 1 *. if there does not exist s <= i <= j with x[i] / 2^j equal to (a / 2^j) XOR (2ans + 1), decrement ans. At the start of this loop, the largest value of (a XOR x[i]) / 2^j was ans, and we maintained this throughout the loop. At the end, j is 0, so the largest value of (a XOR x[i]) is ans. On 7 Jan 2013, at 01:10, Neal Zane <[email protected]> wrote: > Interesting, please? > > 8-) > > > On Mon, Jan 7, 2013 at 1:45 AM, Luke Pebody <[email protected]> wrote > My idea would be to make an ordered set of 3-tuples consisting of > > ( j, floor(x[i] / 2^j), i ) > > for 0 <= j < 14 and for 1 <= i <= n. > > Would you like to know more? > > > On Sun, Jan 6, 2013 at 1:26 AM, Neal Zane <[email protected]> wrote: > The lazy thing is to maintain a trie on each segment tree node. > My estimation is, each insertion takes 15 bit depth and traverses Log(N) > nodes (to the 17th level the max) and if the data were not ever compressed, > it takes N*17*15*sizeof(Trie node) maximum, taking about 200+M memory. And > mostly the trie has good compression rate. > For time complexity, as mentioned earlier. > > 8-) > > > On Sun, Jan 6, 2013 at 2:59 AM, Hussein El-Sayed <[email protected]> > wrote: > So, after solving it, i think your problem with the last case should be this > case. > > 1 > 100000 50000 > All Ns being 1 > All Qs being 15 1 100000 > > Thanks, > Hussein > > > On Sat, Jan 5, 2013 at 4:11 PM, Hussein El-Sayed <[email protected]> > wrote: > Sorry i mistakenly mentioned that building the tree is O(Lg N), its O(N*15). > > > On Sat, Jan 5, 2013 at 4:07 PM, Tushar Bindal <[email protected]> wrote: > I did not get lg(n) part > > I am creating a trie. INserting a number into the trie will take 15 steps. > > I have sorted the insertion and queries according to a keyso as to perform > only insertions upto the end index of a query and then perform the query > before further insertion. > > For each query, I search in the trie. It takes 15 steps. > > So the complexity tyurns out to be: > (N+Q)*lg(N+Q) for sorting > (N+Q)*15 for insertion and query in the trie. > > What optimizations should be done? > > i am getting TLE for 1 case. > > On Sat, Jan 5, 2013 at 6:39 PM, Hussein El-Sayed <[email protected]> > wrote: > I think building the trie will take Lg(N) and traversing it will take > 15*Lg(N).. doing that for Q queries will take Q*Lg(N)*15, and also for me N = > (1<<17).. > > I don't know why i got TLE. > > Thanks, > Hussein > > > On Sat, Jan 5, 2013 at 2:58 AM, Neal Zane <[email protected]> wrote: > O(Q*log(N)*15) too (for me N=constant(1<<17)). > Guess it's the implementation of the trie that blocks, or, is the building of > the system alright? > > 8-) > > > On Sat, Jan 5, 2013 at 5:10 AM, Hussein El-Sayed <[email protected]> > wrote: > But i implemented a trie with binary search, and i got TLE, i think its > Q*Lg(N)*15, which i don't think too much.. > > Can you tell me what is the order of growth of your algorithm? > > Thanks, > Hussein > > > On Fri, Jan 4, 2013 at 5:14 AM, Neal Zane <[email protected]> wrote: > segment tree + trie. kind of huge memory but it works. > > 8-) > > > On Thu, Jan 3, 2013 at 9:10 PM, Hussein El-Sayed <[email protected]> > wrote: > Hello Guys, > > I am trying to solve this problem at interviewstreet, but i am facing a small > problem. At first i thought that this problem could be solved using segment > trees, but i think that it needs an optimization. > > Can anybody suggest a solution? Or an idea of a solution? > > Thanks, > Hussein > -- > 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. > > > > -- > 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. > > > > -- > 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. > > > > > -- > 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. > > > > -- > 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. > > -- 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.
