Algorithm

 Problem Statement for ConstructBST

Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=6714&rd=9999

Problem Statement
     This statement contains images which must be viewed in the applet.

A Binary Search Tree (BST) is a tree data structure which obeys the following properties:

  • Each node has at most 2 children.
  • Each node except the root has exactly 1 parent.
  • There is exactly 1 root node. The root node does not have any parents.
  • If a node has a left child, all values in the left subtree are less than or equal to the value of the node itself.
  • If a node has a right child, all values in the right subtree are strictly greater than the value of the node itself.

 

A BST is constructed from a string of characters in the following way: The root node of the tree is assigned the value of the first character in the string. All subsequent characters are added as children of existing nodes subject to the above rules. Note that the tree is never altered in any other manner. In this problem, nodes are identified starting from the root node as 1, and following in order with nodes at the next level, etc. See the figure below for clarification.

You will be given the shape of a particular BST by specifying the identities of the nodes which constitute the tree, according to the above scheme. Note that you do not know the exact input string used to construct the given BST. You do know, however, that the first N uppercase letters were used to construct the given BST with N nodes. See the examples below for further clarification.

Create a class ConstructBST that contains a method numInputs. The method takes an int[] tree with a list of node numbers present in the tree and returns a long corresponding to the number of strings composed of the characters from 'A' to 'Z' that could have been used to produce the particular BST. Note that tree will always contain a root node numbered 1. Note also, that tree will represent a connected tree, that is, all nodes present in the tree will be reachable from the root node.
 

Definition
    
Class: ConstructBST
Method: numInputs
Parameters: int[]
Returns: long
Method signature: long numInputs(int[] tree)
(be sure your method is public)
    
 
 

Constraints
- tree will contain between 1 and 26 elements, inclusive.
- Each element of tree will be between 1 and 226-1, inclusive.
- Each element of tree will be distinct.
- tree will represent a connected tree.
- tree will contain a root node numbered 1.
 

Examples
0)  
     
{1, 2}
 
Returns: 1

This input represents a BST of the following shape:

Using the characters {'A','B'}, only the string "BA" can generate a tree with the given shape.
1)  
     
{1, 3, 6}
 
Returns: 1

This input represents a BST of the following shape:

Using the characters {'A','B','C'}, only the string "ACB" can generate a tree with the given shape.
2)  
     
{1, 2, 5, 3, 4}
 
Returns: 8
Using the characters {'A','B','C','D','E'} the following 8 strings generate a tree with the given shape: "DBACE", "DBAEC", "DBEAC", "DEBAC", "DBCAE", "DBCEA", "DBECA", "DEBCA".
3)  
     
{1, 2, 4, 6, 3}
 
Returns: 6
 
4)  
     
{2, 4, 3, 62, 7, 15, 1, 31, 5, 14, 28, 57, 56, 114}
 
Returns: 96096

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

class ConstructBST {
  void paskal() {
    nCk[0][0] = 1;
    nCk[1][0] = 1;
    nCk[1][1] = 1;
    for(int i = 2; i < 30; ++i)
      for(int j = 0; j <= i; ++j)
        if(j == 0 || j == i)
          nCk[i][j] = 1;
        else
          nCk[i][j] = nCk[i - 1][j] + nCk[i - 1][j - 1];
  }

  int DFS(int u) {
    vis.insert(u);

    cnt[u] = 1;
    for(int i = 0; i < g[u].size(); ++i) {
      if(vis.count(g[u][i]))
        continue;
      cnt[u] += DFS(g[u][i]);
    }

    if(cnt[u] == 1)
      leaf.insert(u);

    return cnt[u];
  }

  long long count(int u, int p) {
    if(leaf.count(u))
      return 1;

    long long ret = 1;
    int all = 0, child;
    for(int i = 0; i < g[u].size(); ++i)
      if(g[u][i] != p) {
        ret *= count(g[u][i], u);
        all += cnt[g[u][i]];
        child = i;
      }

    return ret * nCk[all][cnt[g[u][child]]];
  }

public:
  static long long nCk[30][30];
  static set<int> vis, leaf;
  static map<int, int> cnt;
  static map<int, vector<int>> g;

  long long numInputs(vector<int> tree) {
    sort(tree.begin(), tree.end());
    for(int i = 1, a, b; i < tree.size(); ++i) {
      a = tree[i];
      b = a / 2;
      g[a].push_back(b);
      swap(a, b);
      g[a].push_back(b);
    }

    paskal();
    DFS(1);
    return count(1, -1);
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
{1, 2}

Output

x
–
+
cmd
1
Advertisements

Demonstration

TopCoder Solution SRM319-D1-500  Problem Statement for ConstructBST C,C++, Java, Js and Python ,SRM319-D1-500,TopCoder Solution