UVa 10821

From Algorithmist
Jump to navigation Jump to search

10821 - Constructing BST[edit]

Summary[edit]

Greedy works here. Solve each problem by greedily divide into sets of smaller subproblems.

Explanation[edit]

Notice that the first node we insert will be the root. Subsequentially, nodes will be on the left if it's smaller, and will be on the right if it's bigger.

Since we want to go for the smallest sequence, we should try to pick the smallest number that will still have the target height. We create the smallest root (and thus, the earliest number in this subproblem) by creating a full right subtree. Since this tree is binary, the right subtree will contain nodes for some values of . Initially, we'll choose to be - because the root takes one level away. Given a sequence of numbers, with nodes on the right, the root would simply be . Then, we can recurse on the left subtree as a subproblem of and .

All we have to do now is to handle the special cases.

Input[edit]

4 4
4 3
4 2
4 1
6 3
0 0

Output[edit]

Case 1: 1 2 3 4
Case 2: 1 3 2 4
Case 3: Impossible.
Case 4: Impossible.
Case 5: 3 1 2 5 4 6