SPOJ QTREE

general
, ,
1

I am getting TLE for this SOLUTION. I tried to use heavy-light decomposition to solve it. Can anyone point to where the solution is slow ? Here is the reference solution, i did almost identical things. Please help
About implementation:

  1. Segment tree is 0 base-indexed.
  2. location[i] gives the index of edge in the segment tree, i-j where j is near the root and
  3. nodes and query all are 1 base-indexed.

comment if you need more clarification :slight_smile:

2

Here are some of the places where I found an error in your code:

  1. LCA Calculation : Anudeep’s code does LCA calculation in O(log n) using a precomputation of O(n log n). See lines 222- 226 in his code for details. Your code is too slow for this which can take O(n) in worst case.

  2. Line number 99 - 106 : HLD function. The special case should directly call the HLD, else should come outside the if condition. See Anudeep’s code for further clarification.

I think all these changes may be enough. If you feel your question was answered mark it as accepted.

3 Likes
3

@likecs

I don’t know how to say it politely, but you are wrong at point 1 and your point 2 does not affect the solution, please take it in a spirited manner. I got AC and let me explain why your point 1 and 2 do not hold ground.

  1. LCA Calculation: The LCA function was almost correct, it had a bug on line 109

    while(HEAD[i] != HEAD[j]){

     if (L[j] > L[i]) swap(i, j) ;
 //code

    }

in the if statement, instead of comparing height of nodes, we had to compare height of Head of the chain to which node i and j belongs to. This procedure would give straight O(logn) worst case for finding LCA. Anudeep’s code is kind of overkill, we can find LCA using the Heavy chain information, in the same time.

  1. There are two version of HLD, as far as i know.
  • The one in which the child having size at least half of as that of parent is considered heavy.
  • The one in which the child having the subtree size greater then that of all its siblings.(Anudeep version)

In the former, there may or may not be a heavy child of a node, as you don’t usually encounter such nodes(unless the tree is horribly unbalanced). So there are more light edges in this version than Anudeep’s version.

In the later version, we are assured the every node is going to have a heavy child, because of the definition of maximum, in case of a tie, you can choose arbitrarily. Except the leaf node because they don’t even have a child at first place.

So if you don’t find a “Special Child” than you don’t have to care about anything, you can just exit the function as it is surely a leaf node, else call HLD on that “Special Child” and also on its other siblings. So, in Anudeep’s solution even leaf node goes to the “for” loop to discover they aren’t actually meant to.

In Anudeep’s version there are longer chains and less light edges than the former case, but it does not change the asymptotics of the algoritm/DS.

To assure you, i changes his code here LINK , i removed the pre-computation part, changed the LCA function and the “if” statement in HLD finction. it got AC(0.38s), Anudeep’s took 0.44s. :slight_smile:

So, in short it was just my wrong/bugged LCA function :frowning: .

Here is my AC version of the code SOLUTION.

I don’t know which version is faster( obviously because of constants and not asymptotically) and why. So feel free if you can throw some light on this. Thanks for taking time to look into my code and for the suggestions. Long may Anudeep Reign :slight_smile:

1 Like