i dont know why so many people got tle using dynamic memory allocation 
my solution (using dma) passed in time
Yes @retrograd explained it accurately.
Just consider each element of the array as free nodes. So when u need a new node just use the currently available element by giving ar[i].right(or left)=cur_index ;
cur_index++;
This way you are saving time required for dynamic allocation(which is slow enough to cost you TLE here).
Can anyone tell me why my solution passed, even after having the hieght of the tree 27 and not 30?
also, do we have to make 2 tries, one for calculating lbest[i] and one for rbest[i], or just one trie is sufficient(if yes then how would we calculate the other best of the other part using that tree)?
I kept getting TLE for task 18 under subtask 2 the whole time. I used the same approach as above. Can anybody tell me where I went wrong?
This is my solution: https://www.codechef.com/viewsolution/8165745
well,
i was thinking about any other method to solve this problem because i was getting TLE in 18 subtask using structure (link list) then i decided to use array because struct. is slow but problem was limited array size. then i use array as link list to minimize the no of node instead of storing address of child node i stored index of child node this was new thing for me 
using structure :-https://www.codechef.com/viewsolution/8162203
using array :-https://www.codechef.com/viewsolution/8166130
2 Likes
can anyone explain the logic how to use trie to solve this problem ??
1 Like
Although its fine, but i believe " if(ans2[i-1]>tans) ans2[i]=ans2[i-1]; " should actually be " if(ans2[i+1]>tans) ans2[i]=ans2[i+1]; " . Isnt it ?
Check this video editorial for stepwise explaination of the solution and check the other videos also …
Happy Coding
1 Like
A suggestion: I think the most time consuming part of the program is converting the integer to its reverse in binary. Earlier, I was using a vector and doing it and it gave me a TLE for both, DMA and array method. So, I suggest you to use
bitset<32> vals = num;
This reduced the runtime to half.