Roy has taken a liking to the Binary Search Trees(BST). He is interested in knowing the number of ways an array of integers can be arranged to form a BST. Thus, he tries a few combinations, and notes down the numbers at the odd levels and the numbers at the even levels.
You're given two values, alpha and beta. Can you calculate the sum of Liking of all possible BST's that can be formed from an array of integers? Liking of each BST is defined as follows
(sum of numbers on even levels * alpha) - (sum of numbers on odd levels * beta)
Note
- The root element is at level ( Even )
- The elements smaller or equal to the parent element are present in the left subtree, elements greater than or equal to the parent element are present in the right subtree. Explained here
If the answer is no less than , output the answer % .
(If the answer is less than , keep adding until the value turns non negative.)
Input Format
The first line of input file contains an integer, , denoting the number of test cases to follow.
Each testcase comprises of lines.
The first line contains , the number of integers.
The second line contains two space separated integers, alpha and beta.
The third line contains space separated integers_, denoting the integer in array .
The first line of input file contains an integer, , denoting the number of test cases to follow.
Each testcase comprises of lines.
The first line contains , the number of integers.
The second line contains two space separated integers, alpha and beta.
The third line contains space separated integers_, denoting the integer in array .
Output Format
Output lines. Each line contains the answer to its respective test case.
Output lines. Each line contains the answer to its respective test case.
Constraints
Sample Input
4 1 1 1 1 2 1 1 1 2 3 1 1 1 2 3 5 1 1 1 2 3 4 5
Sample Output
1 0 6 54
Explanation
There are test cases in total.
- For the first test case, only BST can be formed with
1as the root node. Hence the Liking / sum is . - For the second test case, we get 2 BSTs of the form, the Liking of the first tree is and , this sums to , hence the answer.
1 2 \ / 2 1
- For the third test case, we get BSTs. The Liking of each of the BST from left to right are which sums to and hence the answer.
1 2 3 3 1
\ / \ / / \
2 1 3 1 2 3
\ \ / /
3 2 1 2
- Similarly, for the fourth test case, the answer is .
---------------------------------------------------------------------------------------------------
Roy and alpha-beta trees - Hacker Rank Solution
To solve this problem, firstly you need to understand the very basic structure of BSTs.
Any BST in inorder traversal produces a sorted list of its elements.
So, we can form the inorder taversal first and then try to make the trees that are in agreement to this.
Now, we can iterate over the sorted list and consider all BSTs that can be formed by choosing a particular a[i] as root.
Let us denote the answer for a subarray a[i...j] as ans[i][j].
Now, this problem can be broken into two smaller subproblems.
Suppose, that we are considering an element a[i] as root, then all elements a[0...i-1] shall form the left subtree and all elements a[i+1...n-1] shall form the right subtree.
Then,
ans[i][j] = ans[0][i - 1] * (number of right subtrees) + ans[j + 1][n - 1] * (number of left subtrees) + (contribution from root)
Try to make some samples and convince yourself of this relation. It is to be noted that the root is not considered in any of first 2 terms. This is where alpha, beta comes in.
The contribution of root = (total number of trees) * (alpha | beta) * a[i]
The choice between alpha and beta relies on odd and even levels.
Now, the number of right subtrees and left subtrees can be directly determined using Catalan number
So, we have a final dp state iterating over i as root index
dp[lo][hi][parity] = dp[lo][i-1][!parity] * right_subtree_count
+ dp[i+1][hi][!parity] * left_subtree_count
+(left_subtree_count * right_subtree_count * (alpha | beta) * a[i])
Take a look at the setter's solution for a sample implementation.
Set by Ankit Srivastava
Problem Setter's code :
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
class ANKBST02_solver {
long go(int lo, int hi, int odd) {
if (lo > hi) {
return 0;
}
if (dp[lo][hi][odd] == -1) {
long ans = 0;
for (int root = lo; root <= hi; root++) {
//consider all BST in left subtree of root
ans += (go(lo, root - 1, 1 -odd) * cnt[hi - root - 1 + 1]) % MOD;
if (ans >= MOD) ans -= MOD;
if (ans < 0) ans += MOD;
//consider all BST in right subtree
ans += (go(root + 1, hi, 1 -odd) * cnt[root - 1 - lo + 1]) % MOD;
if (ans >= MOD) ans -= MOD;
if (ans < 0) ans += MOD;
//totTrees is total number of trees considered
long totTrees = (cnt[hi - root] * cnt[root - lo]) % MOD;
//remember to add the root as many times for each tree
ans += (totTrees * ((mul[odd] * a[root]) % MOD)) % MOD;
if(ans >= MOD) ans -= MOD;
if (ans < 0) ans += MOD;
}
dp[lo][hi][odd] = ans;
}
return dp[lo][hi][odd];
}
public void solve() throws IOException {
cnt = generateCatalan(205, MOD);
cnt[0] = 1;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
int t = Integer.parseInt(br.readLine());
while (t --> 0) {
int n = Integer.parseInt(br.readLine());
assert(n <= 200);
a = new long[n] ;
mul = new long[2];
int i = 0;
for (StringTokenizer tokenizer = new StringTokenizer(br.readLine()); tokenizer.hasMoreTokens(); ) {
String s = tokenizer.nextToken();
mul[i ++] = Integer.parseInt(s);
}
mul[1] = -mul[1];
i = 0;
for (StringTokenizer tokenizer = new StringTokenizer(br.readLine()); tokenizer.hasMoreTokens(); ) {
String s = tokenizer.nextToken();
a[i ++] = Integer.parseInt(s);
}
assert(i == n);
Arrays.sort(a);
dp = new long[n][n][2];
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
for (int l = 0; l < 2; l++) {
dp[j][k][l] = -1;
}
}
}
pw.println(go(0, n - 1, 0));
}
pw.close();
}
long[] a;
long[][][] dp;
long[] cnt;
long MOD = (int) (1e9 + 9);
long[] mul;
public static long[] generateCatalan(int n, long module) {
long[] inv = generateReverse(n + 2, module);
long[] Catalan = new long[n];
Catalan[1] = 1;
for (int i = 1; i < n - 1; i++) {
Catalan[i + 1] = (((2 * (2 * i + 1) * inv[i + 2]) % module) * Catalan[i]) % module;
}
return Catalan;
}
public static long[] generateReverse(int upTo, long module) {
long[] result = new long[upTo];
if (upTo > 1)
result[1] = 1;
for (int i = 2; i < upTo; i++)
result[i] = (module - module / i * result[((int) (module % i))] % module) % module;
return result;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
new ANKBST02_solver().solve();
}
}
No comments:
Post a Comment