Cool. Thanks! 8-)
On Mon, Jan 7, 2013 at 3:10 PM, Luke Pebody <[email protected]> wrote: > 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<https://www.interviewstreet.com/challenges/dashboard/#problem/4ed3f9935ae8b>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. > > > -- 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.
