Mahdi_Hajibeygi's blog

Can anyone tell me any order for this algorithm?
By Mahdi_Hajibeygi, history, 5 years ago, In English

Hi

We have a problem on a tree.

Imagine order of our algorithm is:

Sigma x(i) ^ 2

That if we define sz[v] as number of vertices in subtree of v, x(i) is number of different sz[u] between v's children.

It's easy to see it's O(n * sqrt(n)).

But after this submission for problem 1179D I saw it was realy fast and now I think it might be better than O(n * sqrt(n)).

Any idea?

Thanks from 300iq we got that it's O(n.lg(n)) and after that by dragonslayerintraining smart proof we got it's even O(n.lg(lg(n)).

But even after these proofs I wasn't done so after running the code on problem 1179D in gym and lots of random tests the largest

Sigma x(i) ^ 2 I could find was 1032859 for n <= 500,000 (about 2 * n or n.lg(lg(n)) / 2) so now I think O(n.lg(lg(n))) might be best

order we can proof for this algorithm, how ever some one might proof it's some thing better like O(n.log*), O(n) or...

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

»
5 years ago, # |
  Vote: I like it +70 Vote: I do not like it

It is $$$O(n \log n)$$$.

Proof:

$$$\sum{x_v^2}$$$ is equal to the number of pairs of different subtree sizes of children of vertex $$$v$$$.

The number of pairs, such that at least one size in the pair is the maximum is $$$O(n)$$$, so we can ignore them.

Else, let's look at the fixed vertex and at the largest weight in the pair, if it is $$$x$$$ then there are $$$\leq x$$$ different pairs where this size can present.

So we can estimate the complexity as $$$O(n + \sum{sz_v} - \sum{sz_{p_v}})$$$, where $$$p_v$$$ is a son of $$$v$$$ with the largest subtree size.

As we know by Small-To-Large approach, this value is $$$O(n \log n)$$$.

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

I think I have a proof that it is $$$O(n\log\log{n})$$$.

Color a node black if its subtree has at least $$$\sqrt{n}$$$ nodes and white otherwise. The black nodes will form an induced subtree. Our goal is to show that the total cost for all the black nodes is $$$O(n)$$$. The $$$O(n\log\log{n})$$$ bound will follow by induction.

There are $$$O(\sqrt{n})$$$ black nodes with no black children. For all other black nodes, label one of their black children as primary. It can be shown there are $$$O(\sqrt{n})$$$ black nodes that are nonprimary.

For each black node, define $$$w_i$$$ to be the number of white nodes connected to it with no other black nodes in between. Clearly, $$$\Sigma w_i \le n$$$. The cost at a black node if we ignore all its nonprimary black children is $$$O(w_i)$$$, which sums to $$$O(n)$$$.

Now consider the additional cost a nonprimary black node contributes to its parent. Like in 300iq's solution, we will count pairs of distinct subtree sizes. For each nonprimary black node, we can pair it with its primary black sibling, a white sibling or another nonprimary black node in $$$O(\sqrt{n})$$$ ways. Since there are $$$O(\sqrt{n})$$$ nonprimary black nodes, the total cost increase is $$$O(n)$$$

The $$$O(n\log\log{n})$$$ bound will follow by induction on $$$n$$$ since we reduce $$$\log\log{n}$$$ by a constant when recursing.

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

Can someone show a simple proof of $$$\sum x(i)^2 <= N \sqrt{N}$$$ ?

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

    you can easily see x(v) is O(sqrt(n))

    now let X be maximum amount if x(i) ^ 2 / c(i) which c(i) is number of children of i.

    az x(i) <= c(i) and x(i) <= sqrt(n) we have X <= x(i) so X <= sqrt(n).

    now you can easily see Sigma x(i) ^ 2 <= n * X and finally Sigma x(i) ^ 2 <= n * sqrt(n)

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

    Think backwards, from the view of a child w of v. How much can w contribute to the sum? The answer is the number of siblings of w that have different subsize.

    Now if you have $$$M$$$ different subsize then your subsize is $$$O(M^2)$$$ at least so the number of siblings of any node with different subsize is $$$O(sqrt(N))$$$.

    Taken together, we get the complexity of $$$O(Nsqrt(N))$$$.

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

    Thanks, nice proofs!

    → Reply