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.
