HackerRank Roy and alpha-beta trees problem solution YASH PAL, 31 July 2024 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; 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("%dn", m); } return 0; } coding problems data structure