pengyule's blog

I have a question about CF#745(div.2)F Subsequence
By pengyule, history, 3 years ago, In English

Hi. The tutorial said that the total time complexity of the solution is $$$O(n^2)$$$, but there seems to be 2 layers of "for"s in each turn of "dfs", which seems to be $$$O(n^3)$$$. Though it must be less than $$$O(n^3)$$$, could anyone please analyse detailedly of the problem? THX!

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

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

I think it is approximately 1^2+2^2+3^2+...+n^2 which is almost n^3

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

Notice that the value of sz[u] is updated after the "for"s, so if the cartesian tree is a chain, the outer "for" will only repeat twice. I think the worst case is that the cartesian tree is a complete binary tree (or something like that), which makes its time complexity $$$\sum\limits_{i=0}^{\log{n}}\left(2^i\right)^2$$$, which is approximately $$$O(n^2)$$$.

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

    That sum is $$$\displaystyle{\sum_{i=0}^{\log_2n}4^i = 4^{\log_2n}\sum_{i=0}^{\log_2n}\dfrac1{4^i}} = \left(2^{\log_2n}\right)^2 \cdot \dfrac13 = \dfrac13n^2 = \mathcal{O}(n^2)$$$, so it is quadratic time.

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

    I've understood through another kind of solution and your explanation, thanks a lot!

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

It is the classic "combining subtrees" technique. An easy way to think about it is to consider that since the dp for a single subtree is O(size[cur in tree] * size[cur in subtree]), you can think of the dp of each stage as proportional to the number of paths from a node in the current tree to a node in the subtree. This then sums to the total paths between two nodes in the tree as a whole, since each path is counted only once, and the total number of paths is obviously O(n^2).

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

Auto comment: topic has been updated by pengyule (previous revision, new revision, compare).

→ Reply