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

×

MANCBST - Editorial

PROBLEM LINK:

Practice
Contest

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

PROBLEM

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

PREREQUISITES

Knowledge of "online" FFT trick.

EXPLANATION

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 AND TESTER'S SOLUTIONS:

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 ♦♦
19.3k348495534
accept rate: 36%

edited 20 Feb, 16:44


Alternate (much simpler?) solution using generating functions: https://www.codechef.com/viewsolution/18002620

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 http://codeforces.com/problemset/problem/438/E for more details)

link

answered 01 Apr, 09:47

pranet's gravatar image

6★pranet
494
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 10 Jan, 11:27

mariyawilliams's gravatar image

0★mariyawilliams
(suspended)
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×15,005
×325
×105
×75
×14
×7

question asked: 28 Dec '17, 14:43

question was seen: 731 times

last updated: 01 Apr, 09:47