Блог пользователя pengyule

I have a question about CF#745(div.2)F Subsequence
Автор pengyule, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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)$$$.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить