kifk's blog

By kifk, 35 hours 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
  • +38
  • Vote: I do not like it

»
26 hours 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.

  • »
    »
    23 hours 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

»
16 hours 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.

  • »
    »
    11 hours 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.