MrAutro's blog

help needed in a problem
By MrAutro, history, 5 years ago, In English

Hello I managed to understand the problem and what it needs but my idea is to use Catalan numbers to count number of binary trees but in problem it wants to count the number of BS trees of length n with height at least h and root and leafs included but I could not discard or exclude all count of trees of height less than h from Catalan numbers

Any hint please I will be thankful and grateful and thanks in advance

https://mirror.codeforces.com/problemset/problem/9/D

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As you said you can't discard from Catalan numbers. I don't know any way to do this either. So you can assume this task is not related to Catalan. Actualy this task has an editorial.

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

    I didn't understand the editorial for sorry

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

      Where exactly misunderstanding? There just really simple recursion:

      T(n, h) — number of trees with n vertexes and height of h
      T(0, 0) = 1, T(0, i) = T(i, 0) = 0
      Fixing root m and parity all possible trees at trees of two types:

      1) Height of left subtree is h — 1 and height of right subtree is belongs to [0..h-1] 2) Height of left subtree is less than h — 1 and height of right subtree is exactly h — 1.

      → Reply