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.
