I solved Mister B and PR Shifts using trie ... Time complexity of my code is O(n * log(n)) where maximum n = 1000000, but it takes about 1543 ms at least to get the answer, so can anyone please tell me why? Update.. some users advised me to use array instead of pointers with dynamic memory allocation and thats what I did this is the best code I came up with so far .. no dynamic memory allocating . no pointers but my code still too slow and I don't know why http://mirror.codeforces.com/contest/819/submission/28646689
root = new trie_nod(21);Memory allocation is costly in terms of runtime. You can avoid it by keeping a static pool of nodes and assigning from there.
Did you implement an array based link list ever? Try to do the same for trie.
no I did not :/ . can you explain that with an example or provide me a link please?
Lets define a structure like,
Now when you add a new character you do not need to allocate new memory for it. The memory is already allocated. Just use the node trie[used] for that one and do used++.
Try checking some submission of top users. They may have a nice template for you.
thank you ... it's better .. but still too slow. I edited my submission: is this a right implementation?
Well. In my implementation I usually do not use any pointer. But that's not a problem. The implementation looks fine as there is no dynamic allocation now.
Maybe there is some hidden factor that you didn't consider when you analysed the runtime.
that is right.. but what factor that could be?
Auto comment: topic has been updated by DiaaEddin (previous revision, new revision, compare).