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?.

HackerRank Roy and alpha-beta trees problem solution


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


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 *read_int_array(int n)
{
    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;
}