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
2 Likes
can anyone explain the logic how to use trie to solve this problem ??
1 Like
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.
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
1 Like
@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
I think, I got it Thanks!
Can you please explain your idea here.Thanks!
Here in your code few things can be optimized , try static allocation instead of dynamic memory allocation, static memory allocation is faster , and wont result in segmentation fault as there are only two leaves, and padding can be till 30 bits ,30 is enough eventhough anything above that shouldnt make much difference
1 Like
Constant factors do matter
@dkrdharmesh Instead of using lists that dynamically allocate with pointers, he used so-called “statically allocated list”. Let’s take a simpler example:
Say you have to program a linked list. You can do it in a classic way, with pointers and allocations, or you cat allocate an array of “nodes”, and instead of pointers you use indices to that array. Take this example:
2 Likes
CODE:
struct Node { int inf, nxt };
Node Nodes[MAXNODES];
int nodes_count, head = 0;
void insert(int head, int value) {
Nodes[++nodes_count] = Node(value, head) // Create a new node with info field value and next field equal to head of list
head = nodes_count // Redirect the head pointer (index) to the new node -- this inserts at front of list
}
To iterate, you just do something like:
for(int p = head; p; p = Nodes[p].nxt) {
//Nodes[p].inf will be the value, for example
}
You can do this with any dyn-alloc data structure. It’s faster.
3 Likes
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).
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 ?
Awesome problem.
Just solved it.