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.
