You are not logged in. Please login at to post your questions!


MANCBST - Editorial



Author: Satyaki Upadhyay
Tester: Misha Chorniy
Editorialist: Animesh Fatehpuria


Count number of semi-BSTs having exactly $n$ nodes. A semi-BST is a tree with $n$ nodes which satisfies the following conditions:

  • Each node contains a distinct value from $\{1, 2, 3, \dots, n\}$.
  • The root has at most two children.
  • The right subtree of the root (if it exists) is a valid semi-BST.
  • The left subtree of the root (if it exists) is any unordered rooted tree. That is, the children of a vertex are not ordered, and hence no concept of left or right child.
  • The BST property for the root is maintained, i.e. all the values in the left subtree of the root are lesser than that of the root and all the values in the right subtree of the root are greater than that of the root.

Constraints: $n \le 10^5,$ $\text{test cases} \le 10^5.$

Print the answer modulo $663224321$ i.e. $2^{19} \times 5 \times 11 \times 23 + 1$.


Knowledge of "online" FFT trick.


We first solve the problem in $O(n^2)$, and then optimize it using a trick.

An $O(n^2)$ Solution

We use a dynamic program similar to "count number of BSTs having $n$ nodes". Define $T(n)$ to be number of semi-BSTs of size $n$. To find a recurrence for $T(n)$, we will iterate over the number of nodes in the left subtree. Note that fixing the number of nodes in the left subtree determines the value of the root. Suppose we say that the left subtree has $i$ nodes. Then, the number of labeled trees with $i$ nodes is $i^{i - 2}$ by Cayley's Formula. Thus, the number of ways for us to choose a left subtree is $i \times i^{i - 2} = i^{i - 1}$ since we have $i$ choices for the root of the left subtree as well. By definition, the right subtree can be chosen in $T(n - 1 - i)$ ways. Note that these two are independent, making our recurrence:

$T(n) = \sum_{i = 0}^{n - 1} (i^{i - 1} \times T(n - 1 - i))$ with base cases $T(0) = T(1) = 1$.

Clearly, there are $O(n)$ states, and it takes $O(n)$ to compute each state. Therefore, this solution is $O(n^2)$.

Speedup using Online FFT

It turns out that we can speed up the above dynamic program using a trick known as online FFT. The special modulo would have given this hint as well! For reference, please solve this Codeforces problem. The editorial for this problem explains this trick!

Additionally, you can check out these brilliant slides written by Tanuj Khattar! Interestingly, his team TooWeakTooSlow were the only team to solve this problem in the onsite regional.

The final complexity would be $O(n \log^2{n})$.


Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 28 Dec '17, 14:43

admin's gravatar image

0★admin ♦♦
accept rate: 36%

edited 20 Feb '18, 16:44

Alternate (much simpler?) solution using generating functions:

Let s[i] = i * (i -1), and t[n] be the answer for n nodes.

S(z) = s[0] * x^0 + s[1] * x^1 + ..... T(z) = t[0] * x^0 + t[1] * x^1 + .....

T(z) = z * S(z) * T(z) + 1

T(z) = 1 / (1 - z * S(z))

Use polynomial inverse to get AC. (Refer for more details)


answered 01 Apr '18, 09:47

pranet's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 28 Dec '17, 14:43

question was seen: 1,258 times

last updated: 13 Jan, 20:21