### pshishod2645's blog

By pshishod2645, history, 3 weeks ago, ,

I was solving problem QTREE on spoj using HLD but repeatedly got TLE in it. My code

I tried of every simple optimisation I could think of (like using scanf instead of cin, char[] instead of string, etc.) but this wasn't much useful.

Anyone who knows how can it be further optimised?

•
• -2
•

 » 3 weeks ago, # |   +1 You missed to update MAXsize inside the dfs. Thus your heavy[] has wrong values.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 avwl017 just checked it and corrected it. It was actually a bug I didn't notice. Thanks for pointing it out. But even if it's there then also each node will be visited twice (once in outer loop and once in inner loop) so it doesn't change the time complexity. Again getting TLE :( . Btw updated the code
 » 3 weeks ago, # |   0 Try stress testing your code. Then put a timer in various sections to identify the bottleneck.
•  » » 3 weeks ago, # ^ |   0 LanceTheDragonTrainer Sorry if it's silly, but I don't know what is stress testing. Could you please elaborate a bit on this
•  » » » 3 weeks ago, # ^ |   +1 https://en.wikipedia.org/wiki/Stress_testingAnyway, I meant for you to use maximum bounds (as allowed by the input specs) to construct test cases and feed them into your program. Now, time your program at various sections and identify which sections are the bottleneck. Thereafter, find ways to eliminate those bottlenecks.
•  » » » 3 weeks ago, # ^ |   +1 I think if the previous commentator is gone, I can answer) I think, in this case, it means that you should write a proogram that would generate tests, run your solution on them, and thus find the tests on which it will work most then, when you have the tests, you can understand what exactly in your solution works for a long time
•  » » » » 3 weeks ago, # ^ |   0 ushakov.fedor I'm new to HLD, I implemented it by numbering the tree using a dfs and then using a single segment tree for the whole tree. I just want to know if using multiple segment trees (will it be more efficient, as build will take more time but query will take less), is efficient, then is the difference in their times is significant?
•  » » » » » 3 weeks ago, # ^ |   0 I personally solved this problem a long time ago using one segment tree only.If you are interested, see my solution below. Be warned though, the code is unnecessarily long as I wrote HLD and LCA as separate entities. My solution#include /* Library to perform heavy-light decomposition on general trees */ // To use this library, set the macro MAX_N >= n + 1 and LOG_N >= LOG(n+1) // Remember to set the segment tree size accordingly // Call resetHLD() to initialize the HLD data structures // Then call addHLDEdges to add edges to the HLD tree // Call the following functions in order: // buildLCATree(), HLD(), buildSegTree() to perform the HLD on the given tree // Root for LCATree and HLD must be the same // This library assumes that elements are all 1-indexed // All edge costs are also assumed to be non-negative 32-bit signed integers // Otherwise, appropriate invalid values must be set for invalid segment tree ranges- // and the w variable in the HLDQuery() paramter // If 64-bit signed integers are desired, user needs to tweak the relevant- // segment tree and HLD variables and functions // The given graph must be a TREE // Operations: // HLDQuery: queries a certain property of edges in the path from a to b --> O(log^2(n)) // To change the queried property, modify the HLDQuery function and the- // segment tree property // HLDUpdate: updates the weight/cost of a given edge --> O(log(n)) // Time-complexity: O(nlogn) due to construction of sparse table for LCA queries // Space-complexity: O(nlogn) --> due to construction of sparse table for LCA queries using namespace std; #define MAX_N 10005 #define LOG_N 14 // Variables for HLD algorithm int ssz[MAX_N], pos[MAX_N], id[MAX_N], head[MAX_N], chainlen[MAX_N]; vector< vector< pair > > tree; int ptr,segpos; // Variables for segment tree // Segment tree requires 2^x - 1 space, where 2^x >= 2n-1. // But we use 2^x - 1 >= 2n+1 where x is the height of the segment tree int segmentTree[32768], segArr[MAX_N]; // Variables for LCA algorithm int eui = 1; int lvl[2*MAX_N], par[MAX_N], euler[2*MAX_N], occ[MAX_N], ST[2*MAX_N][LOG_N]; // User defined variables vector< pair >edges; int n,a,b,c,t; string s; ///////////////////////////////////////// Start of LCA functions ///////////////////////////////////////////// void computeSparseTable() { for(int i = 1; i <= eui; i++) { ST[i][0] = i; } for(int j = 1; (1 << j) <= eui; j++) { for(int i = 1; (i + (1 << j) - 1) <= eui; i++) { if(lvl[ST[i][j-1]] <= lvl[ST[i+(1<<(j-1))][j-1]]) { ST[i][j] = ST[i][j-1]; } else { ST[i][j] = ST[i+(1<<(j-1))][j-1]; } } } } int rmq(int a,int b) { int k = (int) log2(b-a+1); if(lvl[ST[a][k]] <= lvl[ST[b-(1< y) swap(x,y); return euler[rmq(x,y)]; } void dfslvl(int cur=1,int pre=0,int depth=1) { ssz[cur] = 1; occ[cur] = eui; par[cur] = pre; euler[eui] = cur; lvl[eui++] = depth; vector< pair > adj = tree[cur]; int s1 = (int) adj.size(); for(int i = 0; i < s1; i++) { pair pp = adj[i]; int v = pp.first; if(v != pre) { dfslvl(v,cur,depth+1); ssz[cur] += ssz[v]; euler[eui] = cur; lvl[eui++] = depth; } } } void buildLCATree(int u=1) { dfslvl(u); computeSparseTable(); } /////////////////////////////////////// Start of Segment tree functions /////////////////////////////////////////// // Pre-condition: r = 1, lo = 1, hi = N // indexes 1 to N in segArr are already filled // Post-condition: Builds the segment tree using indexes 1 to N void buildSegTree(int r,int lo,int hi) { if(lo==hi) { segmentTree[r] = segArr[lo]; } else { buildSegTree(r<<1,lo,(lo+hi)>>1); buildSegTree((r<<1)|1,((lo+hi)>>1)+1,hi); segmentTree[r] = max(segmentTree[r<<1],segmentTree[(r<<1)|1]); } } // Pre-condition: r = 1, lo = 1, hi = N, a = left bound, b = right bound // val = new value // Post-condition: updates the range [a,b] by setting each of their values to val void updateSegTree(int r,int lo,int hi,int a,int b,int val) { if(lo > b || hi < a) { return; } else if(a <= lo && b >= hi) { segmentTree[r] = val; } else { int mid = (lo+hi)>>1; updateSegTree(r<<1,lo,mid,a,b,val); updateSegTree((r<<1)|1,mid+1,hi,a,b,val); segmentTree[r] = max(segmentTree[r<<1],segmentTree[(r<<1)|1]); } } // Pre-condition: r = 1, lo = 1, hi = N, a = left bound, b = right bound // Post-condition: performs a query on the range [a,b] int querySegTree(int r,int lo,int hi,int a,int b) { if(lo > b || hi < a) { return 0; } else if(a <= lo && b >= hi) { return segmentTree[r]; } else { int mid = (lo+hi)>>1; return max(querySegTree(r<<1,lo,mid,a,b),querySegTree((r<<1)|1,mid+1,hi,a,b)); } } ///////////////////////////////////////// Start of HLD functions ///////////////////////////////////////////// void HLD(int u=1,int p=0,int w=0,int chead=0) { int weight = -1, heavy = u; head[id[u]] = (chead ? chead : u); pos[u] = ++segpos; segArr[pos[u]] = w; chainlen[id[u]]++; vector< pair > adj = tree[u]; int s1 = (int) adj.size(); for(int i = 0; i < s1; i++) { pair pp = adj[i]; int v = pp.first, wt = pp.second; if(v != p && ssz[v] > weight) { weight = wt; heavy = v; } } if(weight != -1) { id[heavy] = id[u]; HLD(heavy,u,weight,head[id[u]]); } for(int i = 0; i < s1; i++) { pair pp = adj[i]; int v = pp.first, wt = pp.second; if(v != p && v != heavy) { id[v] = ++ptr; HLD(v,u,wt); } } } // Adds undirected edge to HLD tree // a,b and c represents src,dst and cost respectively void addHLDEdge(int a,int b,int c) { tree[a].push_back(make_pair(b,c)); tree[b].push_back(make_pair(a,c)); } int queryHLDHelper(int a,int b) { if(pos[a] > pos[b]) swap(a,b); if(id[a]==id[b]) { return querySegTree(1,1,n,pos[a]+1,pos[b]); } int ans = 0; if(head[id[b]]==b) { ans = querySegTree(1,1,n,pos[b],pos[b]); return max(ans,queryHLDHelper(a,par[b])); } else { ans = querySegTree(1,1,n,pos[head[id[b]]]+1,pos[b]); return max(ans,queryHLDHelper(a,head[id[b]])); } } int queryHLD(int a,int b) { int top = LCA(a,b); return max(queryHLDHelper(top,a),queryHLDHelper(top,b)); } void updateHLD(int a,int b,int val) { int u = (par[a] == b) ? a : b; updateSegTree(1,1,n,pos[u],pos[u],val); } void resetHLD(int n) { segpos = ptr = 0; eui = 1; tree.assign(n+1,vector< pair >()); } // Helper function for printing the real values of segArr void printST(int n) { for(int i = 1; i <= n; i++) { cout << setw(4) << querySegTree(1,1,n,i,i) << " "; } cout << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> t; while(t--) { cin >> n; resetHLD(n); edges.clear(); edges.push_back(make_pair(0,0)); for(int i = 0; i < n-1; i++) { cin >> a >> b >> c; addHLDEdge(a,b,c); edges.push_back(make_pair(a,b)); } buildLCATree(1); HLD(1); buildSegTree(1,1,n); while(cin >> s && s != "DONE") { cin >> a >> b; if(s == "QUERY") { cout << queryHLD(a,b) << "\n"; } else { updateHLD(edges[a].first,edges[a].second,b); } } } return 0; } 
•  » » » » » 3 weeks ago, # ^ |   0 I think your question has already been answered)
 » 3 weeks ago, # |   0 Never heard of HLD before. Googled it (means Heavy-Light Decomposition), read about in GeeksForGeeks, had to learn LCA (Lowest Common Ancestor) to code it, but LCA was easy (basically a disjoint sparse table): preprocess O(NlgN) and query O(1).I tried to code the HLD, but TLE like you... Thanks to LanceTheDragonTrainer showing his code, I finally understood the main idea of HLD. You should properly find and dfs the heavy child first than its siblings because of traversal order (used in segment tree for HLD queries). And you don't need to store the chains, just its head, because the path from head to any other node in the same chain is ordered in the segment tree, thus O(lg²N) for each query and O(lgN) for each change. Ideone link to my ACCed code 0.32 sec.I've just found now looking at the SPOJ comments this nice blog from anudeep. Next step to master it, solve more problems =)
•  » » 3 weeks ago, # ^ |   0 avwl017 I guess my dfs is all right now and I calculate heavy correctly, and yes I don't even store the chains but just their roots.I don't know why still I'm getting TLE, though I feel my approach is more efficient than yours as i don't use LCA, separately.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 There is a bug in the last line of your build function, > t[2*node] should be > t[2*node+1].I managed to understand now how your HLD works, it is a clever way to code iterative instead of recursive, now I see the point of your heavy[]. About the way you are finding LCA I don't fully understand, I'll analyze it more.
•  » » » » 3 weeks ago, # ^ |   0 avwl017 I corrected that bug now.Btw I don't find LCA, I just move up the chain every time in my find() funtction.
•  » » » 3 weeks ago, # ^ |   0 I'm commuting right now, but looking at your code, you missed to reset root[] = 0to the next test cases. Since you don't set chain zero for root and special childs it may cause TLE.
 » 3 weeks ago, # |   0 You missed to clear g[] to the next test cases. I've also removed your #define MAX() preprocessor to avoid same recursion call multiple times. Your code now gives WA with 0.28 sec. Ideone link
•  » » 3 weeks ago, # ^ |   0 Got ACCed 0.27 sec with your code now. The problem was the update function. You missed to update the parents node after finding the [idx, idx] node. Ideone link int update(int node, int start, int end, int idx, int val) { if (idx < start || idx > end) return t[node]; if (start == end) return t[node] = b[start] = val; int mid = (start + end) / 2; return t[node] = max( update(2*node, start, mid, idx, val), update(2*node + 1, mid + 1, end, idx, val) ); } 
•  » » » 3 weeks ago, # ^ |   0 A big thanks avwl017. Actually I figured it out earlier that the reason for TLE was g[i].clear.But then I was getting WA and now I know it was because of update function :)