In centroid decomposition say we do a work of O(n) per centroid tree then we get a time complexity of O(nlgn) because of the HP n + 2*n/2 + 4*n/4 + .. which comes out to n + n + n + ... lgn times. But if I traverse a fixed array of size 100000 for every centoid tree then will the complexity become 10^5 + 2*10^5 + .... ? which would be (1 + 2 + 3 + .. lgn)10^5

Is this analysis correct? And how to avoid the problem of tle if it arises (is using map useful for such cases?)

For a person who can do div 2 A and B comfortably and sometimes C, does practicing on D make sense. Will participating in div 1 virtual so that I start from div 2 C (div 1 A) help or should I stick to solving only C and D? Thank you.

This problem has a dp solution. DP table can be dp[900][200000] so that is MLE. But there is an observation that level i depends only on level i-1 so dp[2][200000] is sufficient. My question is how to implement this in top down approach with memoization. Is it possible in such questions to write a top down approach or we have to go with bottom up. Thank you.

In Dinic algorithm for maximum flow, we in dfs we write the function as

for(int &t = ptr[source]; t < neighbours of source ; ++t)

I read that ptr is an array used to make finding the blocking flow in O(m) rather than O(m2). Why does this work and what is the exact use of keeping the ptr array. How does this array work?

I was studying Dinic Algorithm for maximum flow. In that if you increase the flow of an edge u-v then we decrease the flow of v-u by the same value. What is the intuition behind that. Isn't it a directed graph. If I visualize it as a pipe with oil/water flowing through the network and if u-v has 5 litres flowing how can i say -5 liters is flowing though v-u. Thank You.

My solution click to this hackerrank problem click

I use trie policy data structure but it is tle since distance operator is O(n) ... any help how to implement using it or it is not possible?

I came across this implementation of treap split function

void split(pnode root, int key, pnode &l, pnode &r){
    if(!root){
        l = NULL;
        r = NULL;
    }
    else if(key < root->key){
        split(root->l,key,l,root->l);
        r = root;
    }
    else{
        split(root->r,key,root->r,r);
        l = root;
    }
}

where pnode is pointer to node. I have a difficulty in understanding the call to split function. if key < root->key, I understood that we need to make root as the root of the right subtree so r = root. And we need to split left child. So split(root->l,key,?,?) the doubt is why we pass l as left pointer and root->l as right pointer. Thank you

I am a beginner so soory if the question sound too easy. If in the question it is given there are n cities and n-1 roads connecting them, solve something. The input is given as n (the number of cities) followed by n-1 roads (format u v meaning that there is a bidirectional road from u to v). How do I represent such a tree. I want a parent array to store the parent of each node. But how do I get the parent of each node assuming the root of tree is 1 always. An adjacency list stores for each vertex all the neighbouring vertices but it doesn't have any info about parent. Now if I want to find LCA in such a case, I need the parent array. So how to go about that. Thanks.

Here is the link: RoadOrFlightHard I got the solution but it takes dp[400000][40][2] which is very huge as far as memory is concerned. In the editorial they have added a line that city(i) calculation depends on city(i+1). I was not able to get that observation and I am not getting how to implement it. I saw one code but still did not understand. Thank You.

By Graham Scan O(n*n*logn) would be possible for online construction of convex hull. Can you help me with O(n*n) algorithm. Also what is the difference between 2D CH construction and 3D CH construction

And in graham scan there is a function to sort according to polar order which i did not understand. Please help.

bool polar_order(Point a, Point b){
        //ccw is a function that returns 0 if collinear -1 if counter-clockwise and 1 if clockwise
        //pivot is the lowest y-coordinate point(tie broken by lowest x-coordinate)
	int order = ccw(pivot,a,b);
	if(order==0)
		return sqrdist(pivot,a) < sqrdist(pivot,b);
	return (order==-1);
}

Also if there are some problems you know of convex hull, please share them. Thank you.