shelob's blog

COT2 — Count on a tree II on SPOJ
By shelob, history, 9 years ago, In English

I've been struggling with this problem for days now, and there isn't any decent discussion / editorial available on the internet as well. Any pointers / hints for the solution?

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

»
9 years ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

Do you know smth about HLD? You can read about it here : http://blog.anudeep2011.com/heavy-light-decomposition/ . It's classic HLD BUT: your data structure must can calculate number of distinct number on the interval. Persistent segment tree can help you with it. http://codeforces.net/blog/entry/8962 — in this blog you can find how to calculate number of distinct numbers on the interval. Solution: HLD + ( Persistent segment tree or Fenwick Tree ) HLD + Fenwick Tree must be much easier to implement.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    Yes I know about HLD. After decomposition when we get the chains, we lay them side-by-side in our 'base array' (over which we maintain our required data-structure). But I'm getting stuck at the query part? Each path in the query can be broken down into some chains so we've to query over each chain and combine the results to get the number of distinct numbers. How to do this? Any specifics will be greatly appreciated.

    EDIT : In other words, we are not asked to find the distinct numbers in a contiguous segment but the number of distinct numbers over a collection of disjoint contiguous segments.

    → Reply
»
9 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Not sure if it's possible with HLD, but here is how I solved it.

First we will solve the 1D version of this problem using what is sometimes called Mo's algorithm. Sort all queries (l,r) by (l/SQRTN, r). This basically puts each query into a block of size SQRTN based on its left index and then within each block queries are sorted by right index. To get from one query to the next query, we will have to add/remove some numbers on the left and add/remove some numbers to the right. If we keep track of the counts of each number, we can update the number of distinct numbers after adding/removing a single number in constant time. Since within each block the left indices differ by at most SQRTN and the right index is always moving right, overall this runs in O(M SQRTN). (There is a faster way of solving this problem but that idea doesn't seem to translate well onto a tree?)

How do we use this to solve the problem on a tree? The standard method of linearizing a tree by using its dfs traversal doesn't work, as nodes that are O(1) apart in the traversal can be O(N) apart in the actual tree. We want nodes that are O(1) apart in our traversal to also be O(1) apart in the tree. To do this, we will slightly modify the standard dfs traversal, by adding nodes at even depth to our traversal as we go down, and nodes at odd depth to our traversal as we go up, kind of "hopping" down and up the tree. This ensures that nodes right next to each other in the traversal are at most 3 nodes apart in the actual tree. So we can sort queries using our traversal, and to get from one query to the next, we will have to add/remove nodes in the actual tree. Since within each block the left nodes are at most SQRTN distance apart and the right node essentially traverses the tree, overall this runs in O(M SQRTN).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Wow, that's really clever :). I was requested by shelob to take a look at that problem, but I couldn't solve it. What is funny is that I came up with generalization of Mo's algorithm to trees something like ~3 years ago :D. My way was to divide the tree to subtrees of depth (that is easy by greedy algo) and then we can easily answer queries if we group points belonging to the same subtree, however it's not that easy to implement. As I think about your solution this seems nicer, however it looks like it could be simplified even further. In standard way of linearizing tree we do something like

    int d;
void Dfs(int v) {
  pre[v] = d;
  d++;
  (dfs_to_sons)
}

    however we can do something like

    int d;
void Dfs(int v) {
  pre[v] = d;
  d++;
  (dfs_to_sons)
  d++;
}

    and we achieve the same goal without adding any more nodes, just adding one line "d++" :). Some numbers will be missing, but that does not break anything.

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

      as I understood yzyz's solution he's not adding more nodes too, what is doing is like 

      int d;
void Dfs(int v) {
  if(depth of v is even){
    pre[v] = d;
    d++;
  }
  (dfs_to_sons)
  if(depth of v is odd){
    pre[v] = d;
    d++;
  }
}

      also could you explain how is your way guarantee O(M sqrt N) although there can still adjacent nodes can still be O(N) far from each other

      UPD: ok I got how, it's like Euler tour :)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        Ah, yes, that was already pretty late, so I didn't clearly get yzyz's idea.

        Btw in my version I think that abs(pre[u] - pre[v]) ≥ dis(u, v) is satisfied and that should be sufficient, right?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          yes I got that thanks

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

          An easier way to word it is that a contiguous portion of our ordering must be a connected component in the tree.

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

    Can you explain how you make transition from one query to the next?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    if not too much trouble could you please elaborate your tour with an example tree and show how the linear representation would look like ??

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Judge gives runtime error please see my code i have used mo's algorithm i could not identify error thanks in advance please see https://ideone.com/MG3XbK

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

Mo on tree

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

In the HLD tutorial here. I saw the suggested problems include COT2.

So I wonder if anybody solved it with HLD. If yes, can you give me a detailed solution for HLD? The point of finding "the number of distinct numbers over a collection of disjoint contiguous segments.".

Thanks a lot <3 <3.

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I solved it using MO's algorithm. Here is the link:

https://github.com/saurabhshadow/Sport-Programming/blob/master/Practice/MO's%20Algo/COT2.cpp

→ Reply