Jim_Moriarty_'s blog

Help with ICPC Problem "MY ANCESTOR"
By Jim_Moriarty_, history, 4 years ago, In English

This original problem is titled ‘My Ancestor’ and was used in the Thailand ICPC National Contest 2009. Abridged problem description: Given a weighted (family) tree of up to N ≤ 80K vertices with a special trait: Vertex values are increasing from root to leaves. Find the ancestor vertex closest to the root from a starting vertex v that has weight at least P. There are up to Q ≤ 20K such offline queries.

I am also unable to find the actual link of the problem and hence the solution. Actually this problem is given in steven and felix book.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's for $$$O(log^2N)$$$ per query. Since paths are increasing from root, we essentially want to do a binary search over the path from $$$v$$$ to root. When we binary search to $$$k = (hi + lo)/2$$$, how do we find the $$$k$$$-th ancestor? We can use binary lifting, the same technique as used in the LCA algorithm.

Here's for $$$O(logN)$$$ per query. We can still use binary lifting as in algorithm 1, but we only iterate over each $$$k$$$ that are powers of two, and then if decide if we want to lift $$$v$$$ up $$$k$$$ levels or not.

Both of this is online.

Sorry, but I'm not able to find the original problems either :(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also here's $$$O(logN)$$$ offline but is easier and doesn't require binary lifting (though if you don't know binary lifting then you should probably learn it anyway, fairly common and appears in the recent div3).

    Do a DFS traversal on the tree, maintaining an array of ancestors to the current vertex. When we enter a vertex, push its value into the array. When we exit the vertex, pop the value out of the array. The code goes something like this

    dfs(u):
	append val[u] into the back of arr
	for each children v of u:
		dfs(v)
	pop the back element out of arr

    Now we can process queries offline. When we reach the vertex $$$v$$$ that has queries, the array arr already contains the path from $$$1$$$ to $$$v$$$. Just binary search like online algo 1 and find the answer.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't understand why it have that complexity, because for DFS travesal has O(N), and then for each query it does a binary search which ends up being like O(QlogN)+O(N).

      I know that is O(log N) because this problem is given in steven and felix book but I don't understand, thanks.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +6 Vote: I do not like it

        Yes, I meant $$$O(logN)$$$ per query. So your complexity of $$$O(QlogN) + O(N)$$$ (for the offline algo) is correct.

        In the online algo however, we need to do a DFS, then to preprocess the binary lifting table containing the $$$2^k$$$-th ancestors for each node (this is the table used in the common LCA algorithm). This is $$$O(NlogN)$$$ for the preprocessing, so the online ones end up being $$$O(NlogN + QlogN)$$$ (or $$$O(NlogN + Qlog^2N)$$$).

        I wasn't clear about this, sorry :D

        → Reply