# HackerRank Roy and alpha-beta trees problem solution

In this HackerRank Roy and alpha-beta trees problem solution, 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 N integers?.

## Problem solution in Python programming.

```MOD = 10**9 + 9
def compute_catalan(N):
global MOD
catalan = [0]*(N+1)
catalan[0] = 1
for i in range(1, N):
for j in range(i):
catalan[i] += catalan[j]*catalan[i-j-1]
catalan[i] %= MOD
return catalan
def generate_counts(catalan, N):
counts = [[[0]*2 for j in range(N)] for i in range(N+1)]
for i in range(1,N+1):
for j in range(i):
counts[i][j][0] += catalan[j]*catalan[i-j-1]
counts[i][j][0] %= MOD
for k in range(j):
counts[i][k][0] += counts[j][k][1]*catalan[i-j-1]
counts[i][k][1] += counts[j][k][0]*catalan[i-j-1]
counts[i][k][0] %= MOD
counts[i][k][1] %= MOD
for k in range(j+1,i):
counts[i][k][0] += counts[i-j-1][i-k-1][1]*catalan[j]
counts[i][k][1] += counts[i-j-1][i-k-1][0]*catalan[j]
counts[i][k][0] %= MOD
counts[i][k][1] %= MOD
return counts
catalan = compute_catalan(150)
T = int(input())
for test_case in range(T):
N = int(input())
alpha, beta = (int(x) for x in input().split())
arr = [int(x) for x in input().split()]
arr = sorted(arr)
res = generate_counts(catalan,N)
s = 0
for i in range(N):
s += (alpha*res[N][i][0] - beta*res[N][i][1])*arr[i]
s %= MOD
print(s)```

## Problem solution in Java Programming.

```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;
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();
}
}```

## Problem solution in C++ programming.

```#include <vector> // headers {{{
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <fstream>
#include <ctime>
#include <cassert>
#include <cstring>

#define DEBUG(x) cout << #x << ": " << x << "\n"
using namespace std; // }}}

const int Z = 1000000009;
typedef long long lint;
unordered_map<int, pair<int, int> > MEMO;
vector<lint> C;

pair<int, int> doit(const vector<int>& A, int l, int r)
{
pair<int, int> res;
if (l == r)
return res;

int p = l * 1000 + r;
if (MEMO.count(p))
return MEMO[p];

for (int i = l; i < r; ++i) {
res.first = (res.first + ((A[i] * C[i - l]) % Z) * C[r - 1 - i]) % Z;

pair<int, int> left = doit(A, l, i);
res.second = (res.second + left.first * C[r - 1 - i]) % Z;
res.first = (res.first + left.second * C[r - 1 - i]) % Z;

pair<int, int> right = doit(A, i + 1, r);
res.second = (res.second + right.first * C[i - l]) % Z;
res.first = (res.first + right.second * C[i - l]) % Z;
}

return MEMO[p] = res;
}

int main()
{
//time_t start, end;
//time(&start);

//ifstream cin("test.in");
//ofstream cout("test.out");
//fcout.precision(6);
//fcout.setf(ios::fixed,ios::floatfield);
ios::sync_with_stdio(false);
const int M = 151;
C.resize(M);
C[0] = C[1] = 1;
for (int i = 2; i < M; ++i) {
lint& cur = C[i];
for (int j = 0; j < i; ++j) {
cur = (cur + C[j] * C[i - 1 - j]) % Z;
}
}

int T;
cin >> T;
for (int i = 0; i < T; ++i) {
int N;
cin >> N;
lint a, b;
cin >> a >> b;
vector<int> A(N);
for (int j = 0; j < N; ++j) {
cin >> A[j];
}
MEMO.clear();
sort(A.begin(), A.end());
pair<int, int> p = doit(A, 0, N);
lint res = p.first * a - p.second * b;
cout << (res % Z + Z) % Z << endl;
}

//time(&end);
//cout << difftime(end, start) << endl;

return 0;
}```

## Problem solution in C programming.

```#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MOD 1000000009
{
int *ret = malloc(n * sizeof(int));
for( int i = 0 ; i < n ; ++i )
{
scanf("%d", ret + i);
}
return ret;
}
static int intcomp(const void *v1, const void *v2)
{
return *(const int *)v1 - *(const int *)v2;
}
struct node
{
long long odd;
long long even;
long long count;
};
int solve(int *array, int size, int alpha, int beta)
{
qsort(array, size, sizeof(int), intcomp);
struct node **data = malloc(size * sizeof(struct node *));
for( int i = 0 ; i < size ; ++i )
{
data[i] = calloc(size, sizeof(struct node));
}
for( int s = 0 ; s <= size ; ++s )
{
for( int i = 0 ; i < size - s ; ++i )
{
for( int j = i ; j <= i + s ; ++j )
{
long long left_count = 1, right_count = 1, left_part_even = 0, right_part_even = 0, left_part_odd = 0, right_part_odd = 0;
if( j != i )
{
left_part_even = data[i][j - 1].odd;
left_part_odd  = data[i][j - 1].even;
left_count = data[i][j - 1].count;
}
if( j != i + s )
{
right_part_even = data[j + 1][i + s].odd;
right_part_odd  = data[j + 1][i + s].even;
right_count = data[j + 1][i + s].count;
}
long long count = left_count * right_count;
count %= MOD;
data[i][i + s].count += count;
data[i][i + s].count %= MOD;
long long root = count * array[j];
root %= MOD;
data[i][i + s].even += root;
data[i][i + s].even %= MOD;
right_part_even *= left_count;
right_part_even %= MOD;
right_part_odd  *= left_count;
right_part_odd  %= MOD;
left_part_even  *= right_count;
left_part_even  %= MOD;
left_part_odd   *= right_count;
left_part_odd   %= MOD;
data[i][i + s].even += ( right_part_even + left_part_even );
data[i][i + s].even %= MOD;
data[i][i + s].odd += ( right_part_odd + left_part_odd );
data[i][i + s].odd %= MOD;
}
}
}
long long even = data[0][size - 1].even, odd  = data[0][size - 1].odd, val = 0;
val += even * alpha;
val %= MOD;
val -= odd * beta;
val %= MOD;
for( int i = 0 ; i < size ; ++i )
{
free(data[i]);
}
free(data);
return ( val + MOD ) % MOD;
}
int main()
{
int t, n, m, alpha, beta;
scanf("%d", &t);
for( int i = 0 ; i < t ; ++i )
{
scanf("%d", &n);
scanf("%d %d", &alpha, &beta);
int *array = read_int_array(n);
m = solve(array, n, alpha, beta);
printf("%d\n", m);
}
return 0;
}```