Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Roy has taken a liking to the Binary Search Trees(BST). He is interested in knowing the number of ways an array A of N 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 N 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 0 ( 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 10**9 + 9 output the answer % 10**9 + 9
(If the answer is less than 0, keep adding 10**9 + 9 until the value turns non negative.)
Input Format
The first line of input file contains an integer, T, denoting the number of test cases to follow.
Each testcase comprises of 3 ines.
The first line contains N, the number of integers.
The second line contains two space separated integers, alpha and beta.
The third line contains space separated N integers_, denoting the i**th integer in array A[i]
Output Format
Output T lines. Each line contains the answer to its respective test case.
Constraints
1 <= T <= 10
1 <= N <= 150
1 <= A[i] <= 10**9
1 <= alpha,beta <= 10**9
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
Code Examples
#1 Code Example with C Programming
Code -
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;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <vector>
#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;
}
#3 Code Example with Java Programming
Code -
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();
}
}
#4 Code Example with Python Programming
Code -
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)