pshishod2645's blog

By pshishod2645, history, 3 months ago, In English,

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?

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

You missed to update MAXsize inside the dfs. Thus your heavy[] has wrong values.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try stress testing your code. Then put a timer in various sections to identify the bottleneck.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    LanceTheDragonTrainer Sorry if it's silly, but I don't know what is stress testing. Could you please elaborate a bit on this

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      https://en.wikipedia.org/wiki/Stress_testing

      Anyway, 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 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think your question has already been answered)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)