pshishod2645's blog

By pshishod2645, history, 3 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think your question has already been answered)

»
3 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 :)