Python3 solution

# https://www.hackerrank.com/contests/w4/challenges/roy-and-alpha-beta-trees
import sys

MOD = 10 ** 9 + 9
MAX_N = 150
dp = [[None] * MAX_N for _ in range(MAX_N)]

def read_numbers():
    return [int(d) for d in sys.stdin.readline().split()]

def subtree(numbers, start, end):
    """Calculates result for all trees from start to end, inclusive."""
    if start == end:
        return 1, 0, 0
    if dp[start][end] is not None:
        return dp[start][end]
    tree_count = 0
    even_sum = 0
    odd_sum = 0
    for i in range(start, end):
        left_count, left_even_sum, left_odd_sum = subtree(numbers, start, i)
        right_count, right_even_sum, right_odd_sum = subtree(numbers, i + 1, end)
        tree_count = (tree_count + left_count * right_count) % MOD
        even_sum = (even_sum + numbers[i] * left_count * right_count + left_odd_sum * right_count + right_odd_sum * left_count) % MOD
        odd_sum = (odd_sum + left_even_sum * right_count + right_even_sum * left_count) % MOD
    dp[start][end] = (tree_count, even_sum, odd_sum)
    return tree_count, even_sum, odd_sum

def solve(numbers, alpha, beta):
    global dp
    dp = [[None] * MAX_N for _ in range(MAX_N)]
    numbers.sort()
    tree_count, even_sum, odd_sum = subtree(numbers, 0, len(numbers))
    return (alpha * even_sum - beta * odd_sum) % MOD

if __name__ == '__main__':
    T = int(sys.stdin.readline())
    for t in range(T):
        n = int(sys.stdin.readline())
        alpha, beta = read_numbers()
        numbers = read_numbers()
        print(solve(numbers, alpha, beta))

for complete solution in python java c++ and c programming search for programs.programmingoneonone.com on google

You don't actually need to compute all the different BSTs. The trick is to sort the array first.

Then, you iterate through each element in the array and make it the root of a BST.

Then to create the left child and its subtree, you take a subset of the array consisting of everything before the root element. They will all be less than or equal to the root since the array was initially sorted. Recurse on this left subtree.

Same thing for the right child and its subtree, just use everything after the root element in the array to create it.

Your function should have a flag determining whether it's an odd or even row. When you recursively call your function, just toggle this flag. Then, when you add to your total, you'll know based on this flag whether to multiply it by alpha or by beta and -1.

sol:

include

include

using namespace std;

typedef long long ll;

define FOR(i, a, b) for (int i = (a); i < (b); i++)

define REP(i, n) for (int i = 0; i < (n); i++)

define ROF(i, a, b) for (int i = (b); --i >= (a); )

int ri() { int x; scanf("%d", &x); return x; }

const int N = 150, MOD = 1000000009; ll catalan[N]; int a[N], f[N][N], g[N][N];

int inv(int x) { int r = 1; for (; x > 1; x = MOD%x) r = ll(MOD/x) * -r % MOD; return r; }

int main() { catalan[0] = 1; FOR(i, 1, N) catalan[i] = catalan[i-1] * (4*i-2) % MOD * inv(i+1) % MOD; for (int cc = ri(); cc--; ) { int n = ri(), alpha = ri(), beta = ri(); REP(i, n) a[i] = ri(); sort(a, a+n); ROF(i, 0, n) FOR(j, i, n) { int ff = 0, gg = 0; FOR(k, i, j+1) { ff = (ff + catalan[j-k] * catalan[k-i] % MOD * a[k] + catalan[j-k] * (k ? g[i][k-1] : 0) + catalan[k-i] * (k+1 < n ? g[k+1][j] : 0)) % MOD; gg = (gg + catalan[j-k] * (k ? f[i][k-1] : 0) + catalan[k-i] * (k+1 < n ? f[k+1][j] : 0)) % MOD; } f[i][j] = ff; g[i][j] = gg; } printf("%lld\n", ((ll(f[0][n-1]) * alpha - ll(g[0][n-1]) * beta) % MOD + MOD) % MOD); } }

How to compute all the different BST's required for this problem.?? I am trying to find a solution simillar to optimal binary search tree(OBST) , can anyone guide me if I am going in the right direction.