REBXOR - Editorial

@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 :slight_smile: 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.