Count Permutations - Editorial

Problem Link:
Contest
Practice

Author: Rajat De
Testor: Aman Kedia
Editorialist: Rishav Pati

Difficulty: Easy - Medium

Topics: Basic Combinatorics, Recusive Functions

Problem:-
Given a number n which is of the form 2^x - 1 or 2^x - 2 Find the number of permutations of [1 , n] such that when inserted into a binary search tree from leftmost element of the permutation to rightmost element of the permutation, the tree obtained is Balanced (It has a height of ceil(log(n + 1))).
Constraint: 1 \le n \le 10 ^ 6.

Quick Explanation:-
If f returned the answer when n is of the form 2^x - 1 and g when n is of the form 2^x - 2 then,

f(n) = f(n/2)^2 \times ^{n−1}C_{n/2}

and

g(n) = 2 \times f(n/2) \times g(n/2 − 1) × ^{n−1}C_{n/2}

Explanation:-
First notice that the maximum number of nodes a tree of height x can have is 2^x − 1.
So when n is of the form 2^x − 1 for some x, the height of the tree should be exactly x and
hence height of each subtree of each child of the root should be at most x − 1.
So, each of the 2 subtrees attatched to the root contain at most 2^{x−1} − 1 nodes.
But our tree contains 2^x − 1 nodes which is (2^{x−1} − 1) + (2^{x−1} − 1) + 1.
This means that each of the subtree contains exactly 2^x − 1 nodes.
This leaves the median node to be the only plausible choice for the root.

Now suppose we have a function f([1, 2, 3, ..., k]) which tells us the number of permutations
of [1, 2, ..., k] which form a balanced binary tree.
Then, we want to find out the value of f([1, 2, 3, ..., n]).
Now, under the condition that n is of the form 2^x − 1, our root is fixed. Which means that
the first number of all the valid permutations are fixed. Call this number as r.

The left subtree of r will have the numbers [1, 2, 3, ..., r − 1] while the right subtree will
have the numbers [r + 1, r + 2, r + 3, ..., n].
Since these are independent sub problems, we can solve them separately by calling f([1, 2, 3, ..., r− 1]) and f([r + 1, r + 2, r + 3, ..., n]).

Now notice that since the actual values on the nodes do not matter and only the relative
ordering between nodes matter, any increasing sequence of n numbers is essentially same as
the sequence [1, 2, 3, ..., n]. So, we can replace the entire sequence with a single number n.
So the answer for both subtrees will be f(n/2). (Notice here that n/2 will also be of the
form of 2^x − 1.)

Now, we need to use this result to build a valid permutation for the original problem.
In the first position of any valid permutation, we have r. In the rest n − 1 places, n/2 places
are for the numbers which go in the left sub-tree and n/2 places for the numbers which go
in the right sub-tree.

There ^{n−1}C_{n/2} ways of choosing these positions.
Hence,

f(n) = f(n/2)^2 \times ^{n−1}C_{n/2}

Now, when n is of the form 2^x − 2 we essentially have 2 choices for the root node.
Pick any of them in 2 ways. This leaves one of the subtree with n/2 elements and one of the
subtree with n/2 − 1 elements.
Notice that n/2 here is of the form 2^x − 1 and n/2 − 1 is of the form 2^x − 2.
So, if the answer in this case is given by a function g(n), we have:

g(n) = 2 \times f(n/2) \times g(n/2 − 1) × ^{n−1}C_{n/2}

It should be clear that a simple recursive implementation for f will return the answer for n
in O(logn) time.
And g(n) will, in each level, invoke f once and g once with the parameter value roughly
halved.
Since f will take O(logn) time and there will be at most O(logn) invocations, overall complexity
of a simple recursive implementation will be just O(log^2n).

Setter’s Code
Tester’s Code

1 Like

Also we can notice that the answer for 2x - 1 and 2x - 2 is same.

Author Solution : C++

Author Solution : Python

Tester Solution : C++