Tima10's blog

Count paths with a dominant element
By Tima10, 3 years ago, translation, In English

You are given a rooted tree with $$$n <= 1e5$$$ nodes. Each node has a number $$$a[i] <= n$$$ written on it. A path has a dominant element when the most frequently occuring element appears strictly more than $$$path length / 2$$$ times. Count how many paths with a dominant element there are.

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

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This problem is interesting. Do you have link to the problem ? I wanna test my algorithm before answer your question.

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

    Well, the problem is uploaded to a closed CF group, so I can't actually do much besides submit

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

      My algorithm is some what like segment tree, but not sure if it can pass

      struct Node {
    int value;
    int count;
    Node (int value = -1, int count = 0)
    : value(value), count(count) {}
};

Node operator + (const Node &left, const Node &right)
{
    if (left.count > right.count) 
        return Node(left.value, left.count - right.count);

    if (left.count < right.count) 
        return Node(right.value, right.count - left.count);

    return Node(left.value, left.count + right.count);
}

      Imagine there are $$$n$$$ players with their team flag, some of them might in the same team. And there is a game that

      • If two player fight with each other, they both get eleminated
      • If two teams are the same flag, then they merge with each other, with the size equal to sum of both single team
      • Else two teams fight with each other: each of these team's member fight with other team's member until at least one team is fully elimated
      • You can also define empty team with flag $$$= -1$$$ or/and count $$$= 0$$$ for convenient

      It is guarantee that if a team is dominant then after any kind of fight they can still last as final team. But just not the oposite, so you have to re-check.

      So a number is dominant in the path when

      • There is a team with $$$count > 0$$$
      • That team having apeared more than $$$\left \lfloor \frac{|path|}{2} \right \rfloor$$$

      The reason why you use this data structure is that you only need to check for one team only.

      This give some what $$$O(n^2 \log^2 n)$$$ algorithm to $$$O(P + n)$$$ algorithm (for $$$P = $$$ number of different path) . But I dont know if there is a way to count on the whole path instead of checking for each path

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

        I am not sure but there might be a better online data structure which can count for all paths in one substree. But for a complete-binary-tree then I think it is possible.

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

Solve for zeroes and ones, counting paths when 1 is the dominant element. (Not too hard. You can treat zeroes as -1, and you want to know how many paths have sum greater than 0.) Then, for any value, you could imagine that nodes with it are 1 and all the other ones are -1. This gives a quadratic solution.

If you want better, maybe you could utilize the small-to-large merging trick, solving each subtree for only the values that appear in it. (I'm not sure the "sets" required would be small enough, though.)

Another idea would be to solve for each value independently, on "compressed" trees, where all irrelevant-chains are "skipped", condensed into just an edge. The sum of sizes of all such trees would be linear, so you could just solve normally on each of these trees.

Probably there is also an easier solution.

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

    You can can prove that the small-to-large trick is faster than $$$O(n^2)$$$, if you implement it carefully. I claim that the number of insert operations becomes $$$O(n \sqrt{n} log(n))$$$.

    Suppose we divide the colors into heavy and light, based on if a color occurs more than $$$\sqrt{n}$$$ times or less. Say we build and store for each subtree a map that stores:

    {color, +1 for every node of this color — 1 for every other color} -> number of times such a path occurs in the subtree.

    If we look at all tuples {light color, sum}, the sum never has to smaller than $$$-\sqrt{n}$$$ and can never be bigger than $$$\sqrt{n}$$$ (Why?), so we don't store those. There are only $$$\sqrt{n}$$$ different heavy colors, thus they can also not make the number of tuples much larger. So in each subtree the number of elements in the data structure will be $$$O(\text{Subtree Size} \cdot \sqrt{n})$$$. And with the small to large merging, you will only need $$$O(n \sqrt{n} log(n))$$$ insert operations.

    Edit: Now that I think about it, I don't know how to implement the insert operations efficiently.

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

    Apparently you can solve this with $$$CD$$$ if you can solve for a single centroid in $$$O(sz\sqrt{sz})$$$. Total time complexity is $$$T(n) = 2T(n / 2) + n\sqrt{n}$$$, which according to WolframAlpha is $$$O(n\sqrt{n})$$$ with a constant of $$$4$$$ for my constraints.

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

      Makes sense. It crossed my mind but I wanted a nicer solution

      → Reply