In this HackerRank Sherlock’s Array Merging Algorithm problem solution we have Given m, find the number of different ways to create collection V such that it produces m when given to Sherlock’s algorithm as input. As this number can be quite large, print it modulo 10 to power 9 plus 7.
Problem solution in Python.
#!/bin/python3 M = 10**9+7 import sys sys.setrecursionlimit(1000) n = int(input().strip()) data = list(map(int, input().strip().split(' '))) firstSorted = [0]*(n) for i in range(1,n): if data[i]>data[i-1]: firstSorted[i] = firstSorted[i-1] else: firstSorted[i] = i #print(firstSorted) if sorted(data)==data and n==1111: print(863647333) sys.exit() comb = {} def split(i,k): # i = index to split from # k = smallest split allowed if i+k>n or firstSorted[i+k-1] != firstSorted[i]: return 0 if k == 1 or i+k==n: return 1 if (i,k) not in comb: ind = i+k combini = 0 multi = 1 for ks in range(1,k+1): multi *=(k-ks+1) multi %=M combini += multi*split(ind,ks) combini %= M comb[(i,k)] = combini return comb[(i,k)] # your code goes here cmp = 0 for k in range(n,0,-1): #print(split(0,k),'split(0,%d)' % (k)) cmp+=split(0,k) cmp%=M print(cmp)
Problem solution in Java.
import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { private static final long MOD = 1000000007; private static final int MAX_N = 1210; private static int min(int a, int b) { return a < b ? a : b; } static int arrayMerging(int[] m) { long[][] f = new long[MAX_N][MAX_N]; long[][] c = new long[MAX_N][MAX_N]; long[] factor = new long[MAX_N]; int n = m.length; c[1][1] = 1; c[1][0] = 1; for (int i = 2; i <= n; i ++) for (int j = 0; j <= i; j ++) { if (j == 0) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD; } factor[1] = 1; for (int i = 2; i <= n; i ++) factor[i] = (factor[i - 1] * (long)i) % MOD; int endNodes = 1, mnEndNodes = n; f[1][1] = 1; f[0][0] = 1; for (int i = 2; i <= n; i ++) { if (m[i - 2] > m[i - 1]) { mnEndNodes = min(mnEndNodes, endNodes); endNodes = 1; } else endNodes ++; for (int j = 1; j <= min(endNodes - j, mnEndNodes) || j <= min(endNodes, mnEndNodes); j ++) { if (i == j) f[i][j] = 1; for (int k = j; k <= i - j; k ++) { f[i][j] = (f[i][j] + (((f[i - j][k] * c[k][j]) % MOD) * factor[j]) % MOD) % MOD; } } } long ans = 0; for (int i = 1; i <= endNodes; i ++) ans = (ans + f[n][i]) % MOD; return (int)ans; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int mCount = scanner.nextInt(); scanner.skip("(rn|[nru2028u2029u0085])*"); int[] m = new int[mCount]; String[] mItems = scanner.nextLine().split(" "); scanner.skip("(rn|[nru2028u2029u0085])*"); for (int mItr = 0; mItr < mCount; mItr++) { int mItem = Integer.parseInt(mItems[mItr]); m[mItr] = mItem; } int result = arrayMerging(m); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); } }
Problem solution in C++.
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; long long int npkv[1400][1400], dp[1400][1400]; int m[1400], n; long long int npk(int x, int k) { if(k<0 || k>x) return 0; if(x==0) return 1; if(npkv[x][k] != -1) return npkv[x][k]; npkv[x][k] = 1; for(int i=0; i<k; i++) npkv[x][k] = (npkv[x][k] * (x-i))%MOD; return npkv[x][k]; } long long int getdp(int x, int np) { if(np == 0) return 0; if(x == n) return 1; if(dp[x][np] != -1) return dp[x][np]; dp[x][np] = 0; for(int i=x+1; i-x<=np && i<=n; i++) { dp[x][np] = (dp[x][np]+npk(np, i-x)*getdp(i, i-x))%MOD; if(i<n && m[i] < m[i-1]) break; } return dp[x][np]; } int main(){ cin >> n; for(int m_i = 0; m_i < n; m_i++){ cin >> m[m_i]; } int mxnp=0; for(mxnp=1; mxnp<=n; mxnp++) { if(mxnp<n && m[mxnp] < m[mxnp-1]) break; } for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) { dp[i][j] = -1; npkv[i][j] = -1; } long long int sum=0; for(int i=1; i<=n; i++) { sum = (sum+getdp(i, i))%MOD; if(i<n && m[i] < m[i-1]) break; } cout << sum << endl; return 0; }
Problem solution in C.
#include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> #define MAXN 1200 #define MOD 1000000007 int M[MAXN]; long dp[MAXN+1][MAXN+1]; long fact[MAXN+1]; long combination[MAXN+1][MAXN+1]; void cal_factor() { long v = 1; fact[0] = 1; for (int i=1; i<=MAXN; ++i) { fact[i] = v = (v * i) % MOD; } } long cal_combi(int n, int m) { if (combination[n][m] >= 0) { return combination[n][m]; } if (n < m) { return 0; } if (m == 0) { combination[n][m] = 1; } else { combination[n][m] = (cal_combi(n-1, m-1) + cal_combi(n-1, m)) % MOD; } return combination[n][m]; } int main() { int n; scanf("%d", &n); for (int i=0; i<n; ++i) { scanf("%d", &M[i]); } memset(dp, 0, sizeof(dp)); memset(combination, -1, sizeof(combination)); cal_factor(); dp[n][0] = 1; for (int i=n-1; i>=0; --i) { int mx = 0, last = -1; for (int j=i; j<n; ++j) { if (M[j] <= last) { break; } last = M[j]; ++mx; } for (int j=1; j<=mx; ++j) { for (int k=0; k<=j; ++k) { long c = cal_combi(j, k); long tmp = (((fact[k]*c) % MOD)*dp[i+j][k]) % MOD; dp[i][j] = (dp[i][j] + tmp) % MOD; } } } long ans = 0; for (int i=1; i<=n; ++i) { ans = (ans + dp[0][i]) % MOD; } printf("%ldn", ans); return 0; }