+1 to the problem setter for this problem and +5 for the awesome test data. 
Learned a new way of creating binary trees without using dynamic memory allocation.
Used dynamic memory allocation and this happened : CodeChef: Practical coding for everyone
Used a different approach and Voila! CodeChef: Practical coding for everyone
This is one of the best problems i solved till date.
Can anybody help me finding where am I going wrong ?
https://www.codechef.com/viewsolution/8164680
Providing failed test case will be much appreciated.
Hi. I implement a Trie using a struct node and traversed it recursively while inserting and querying. I passed 18/19 tests but got TLE in one. Can anyone explain how can I improve this method to pass all the tests? I think the reason I’m getting TLE is because complexity is O(120 * N) = 1.2 * 10^7 But can anyone explain how can I improve on this?
Here is my solution
[1] Why it is giving TLE as time complexity is same as editorial.
[1]: https://www.codechef.com/viewsolution/8011026@anishshah I faced exactly the same problem. Dynamic memory allocation is costly. There is a better way of doing it.
Struct node {int x,y};
Maintain a array of node(of size 410^530 say) and a array index initialized to 1. Now whenever u need a new node just increment the array index and store the updated value in x or y variable of the current node. This way you can avoid dynamic allocation. See this CodeChef: Practical coding for everyone
I hope the code is clear enough.
I researched / problem solve the approach described in the editorial. Still, TLE on task 2. Times for task 1 suggest I was WAY over time on task 2. I am using python. Is this an impossible task on python or is there a much faster way to implement tries in that language? Thanks so much for any input.
I used the same approach with dynamic memory allocation and got TLE in 4 tasks of subtask 2.
my solution is : CodeChef: Practical coding for everyone
After that I realised an optimisation that maximum posible XOR for any subarray till i 0<=i<n is the value when all the k bits are one, where k is the number of bits in the maximum number in the array.
So whenever this value is encountered, maximum xor subarray after that index will be that value and their is no need to play with the tries further, I used this fact and execution time was nearly halved.
My final AC’ed solution is : CodeChef: Practical coding for everyone
I used this reference to study the concept of tries : http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems
my solution complexity : N+2Nlog Amax+2Nlog Amax ~ O(N log Amax)**
same approach I have I also implemented but I don’t know why test case : 18 gave TLE??
any genuine region??
i dont know why so many people got tle using dynamic memory allocation 
my solution (using dma) passed in time
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: CodeChef: Practical coding for everyone
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 :-CodeChef: Practical coding for everyone
using array :-CodeChef: Practical coding for everyone
can anyone explain the logic how to use trie to solve this problem ??
Check this video editorial for stepwise explaination of the solution and check the other videos also …
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.
Each insertion in Trie creates O(log(Max(A[i]))) New Nodes . So here N is 4 * 10 ^ 5 and log(Max[A[i]]) is 30 hence you need about 1.2 * 10 ^ 7 space
@grebnesieh Thanks a lot for teaching me this wonderful way. I always used dynamic memory allocation. This approach is new for me.
@rajat1603 Thank you. I get it now. Just one thing. 1.2*10^7 is for worst case right? I mean do we always need O(log(Max(A[i]))) space?
Your problem is the dynamic memory allocation (new). It’s to slow when called for each node seperately.
Allocate an vector of nodes and take nodes from this array, keeping track with a counter