HackerRank Sherlock’s Array Merging Algorithm
In this post, we will solve HackerRank Sherlock’s Array Merging Algorithm Problem Solution.
Watson gave Sherlock a collection of arrays V. Here each V; is an array of variable length. It
is guaranteed that if you merge the arrays into one single array, you’ll get an array, M, of n
distinct integers in the range [1, n].
Watson asks Sherlock to merge V into a sorted array. Sherlock is new to coding, but he accepts the challenge and writes the following algorithm:
M] (an empty array).
knumber of arrays in the collection V.
- While there is at least one non-empty array in V
- T + [] (an empty array) and i + 1.
- While i <k:
If V; is not empty:
Remove the first element of V; and push it to T.
i+i+1. - While T is not empty:
Remove the minimum element of T and push it to M. - Return M as the output.
Let’s see an example. Let V be {[3, 5], [1], [2,4]}.
Sherlock isn’t sure if his algorithm is correct or not. He ran Watson’s input, V. through his pseudocode algorithm to produce an output. M. that contains an array of n integers. However, Watson forgot the contents of V and only has Sherlock’s M with him! Can you help Watson reverse-engineer M to get the original contents of V?
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 109 + 7.
Notes:
Two collections of arrays are different if one of the following is true:
- Their sizes are different.
- Their sizes are the same but at least one array is present in one collection but not in the other.
Two arrays, A and B. are different if one of the following is true: Their sizes are different.
Their sizes are the same, but there exists an index i such that a, #bi.
Input Format
The first line contains an integer, n. denoting the size of array M.
The second line contains n space-separated integers describing the respective values of
mo, m1,…, mn-1.
Sample Input 0
3 1 2 3
Sample Output 0
4
Sherlock’s Array Merging Algorithm C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ff(i,a,b) for(int i = (a); i <= (b); i++)
#define fr(i,a,b) for(int i = (a); i >= (b); i--)
#define REP( i , n ) for( int i = 0 ; i < n ; i++ )
#define REPI( n , i ) for( int i = n ; i >= 0 ; i-- )
#define sc( x ) scanf( "%d" , &x )
#define sc2( x , y ) scanf( "%d%d" , &x , &y )
#define scd( x ) scanf( "%.9f" , &x )
#define scl( x ) scanf( "%I64d" , &x )
#define pf( x ) printf( "%d\n" , x )
#define pfd( x ) printf( "%.9f\n" , x )
#define pfl( x ) printf( "%I64d\n" , x )
#define rrc( x ) return cout << x , 0 ;
#define all( v ) v.begin(),v.end()
#define all_r( v ) v.rbegin() , v.rend()
#define fi first
#define se second
#define endl '\n'
#define SZ(a) int(a.size())
#define pb push_back
#define cln( x , v ) memset( x , v , sizeof( x ) )
#define pi acos(-1.0)
#define e2( x ) ( 1LL*( x )*( x ) )
#define r2( x ) sqrt( 1.0*( x ) )
#define ones(x) __builtin_popcount(x)
#define MCM( a , b ) ( ( a*b )/( __gcd( a , b ) ) )
#define ddd cout << "despues" << endl ;
#define sss cout << "------------------" << endl ;
#define aaa cout << "antes" << endl ;
#define da( a , b ) ( (a)/(b) - ( (a) < 0 && (a)%(b) != 0 ) )
#define ceil_( a , b ) ( da( (a) , (b) ) + ((a)%(b) > 0) )
#define Mm greater<int>
#define nxtPerm next_permutation
#define L( n ) 2 * n
#define R( n ) 2 * n + 1
#define A 1 , 0 , n - 1
#define endl '\n'
typedef double db ;
typedef long double ld ;
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<vi> vvi ;
typedef vector<ll> vl ;
typedef vector<bool> vb ;
typedef pair<int,int> pii ;
typedef vector<pii> vpii ;
const ld EPS = 1e-8 ;
const int INF = (int)( INT_MAX - 100 ) ;
const ll mod = (int)( 1e+9 + 7 ) ;
const int N = (int)( 1200 ) ;
int days_month[ 12 ] = { 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 };
//inline ll modulo( ll num ){ ( ( num %= mod ) += mod ) %= mod ; return num ; }
//inline ll pot( int b , int e ){ ll p = 1 ; REP( i , e ) p = (p*b)%mod ; return p ; }
ll C[ N + 2 ][ N + 2 ] ;
ll F[ N + 2 ] ;
int lim[ N + 2 ] ;
int num[ N + 2 ] ;
int nxtL[ N + 2 ] ;
int n ;
void init() {
for( int i = 0 ; i <= N ; i ++ ) {
for( int j = 0 ; j <= i ; j ++ ){
if( i == j || j == 0 ) C[ i ][ j ] = 1 ;
else C[ i ][ j ] = ( C[ i - 1 ][ j - 1 ] + C[ i - 1 ][ j ] ) % mod ;
}
}
F[ 0 ] = 1 ;
for( int i = 1 ; i <= N ; i ++ ) {
F[ i ] = ( F[ i - 1 ]*i )%mod ;
}
for( int i = n ; i >= 1 ; i -- ) {
nxtL[ i ] = 1 ;
if( lim[ i ] == lim[ i + 1 ] ) {
nxtL[ i ] += nxtL[ i + 1 ] ;
}
}
}
bool used[ N + 2 ][ N + 2 ] ;
int memo[ N + 2 ][ N + 2 ] ;
int dp( int p , int last ) {
if( p > n ) return 1 ;
if( used[ p ][ last ] ) return memo[ p ][ last ] ;
used[ p ][ last ] = true ;
int &ans = memo[ p ][ last ] = 0 ;
int max_len = min( last , nxtL[ p ] ) ;
for( int len = max_len ; len >= 1 ; len -- ) {
ll perm = ( F[ len ]*C[ last ][ len ] ) % mod ;
if( p == 1 ) perm = 1 ;
ans += ( perm*dp( p + len , len ) ) % mod ;
if( ans >= mod ) ans -= mod ;
}
return ans ;
}
int main()
{
// ios_base::sync_with_stdio(0);
scanf( "%d" , &n ) ;
for( int i = 1 ; i <= n ; i ++ ) {
scanf( "%d" , &num[ i ] ) ;
}
for( int i = 1 ; i <= n ; i ++ ) {
lim[ i ] = lim[ i - 1 ] ;
if( num[ i - 1 ] > num[ i ] ) {
lim[ i ] ++ ;
}
}
init() ;
printf( "%d" , dp( 1 , n ) ) ;
return 0 ;
}
Sherlock’s Array Merging Algorithm C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
/// <summary>
/// Sherlock's Array Merging Algorithm
/// https://www.hackerrank.com/contests/university-codesprint-2/challenges/sherlocks-array-merging-algorithm
/// </summary>
class Solution5
{
// ---------------------------------------------------------------------
static int[][] FiF(int nmax, int modulus)
{
int[][] fif = new int[2][];
fif[0] = new int[nmax + 1];
fif[0][0] = 1;
for (int i = 1; i <= nmax; i++) fif[0][i] = (int)(((long)fif[0][i - 1] * i) % modulus);
long a = fif[0][nmax];
long b = modulus;
long p = 1;
long q = 0;
while (b > 0)
{
long c = a / b;
long d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
fif[1] = new int[nmax + 1];
fif[1][nmax] = (int)(p < 0 ? p + modulus : p);
for (int i = nmax - 1; i >= 0; i--) fif[1][i] = (int)(((long)fif[1][i + 1] * (i + 1)) % modulus);
return fif;
}
static long Choose(int n, int r, int[][] fif, int modulus)
{
if (n < 0 || r < 0 || r > n) return 0;
long factn = fif[0][n];
long invFactr = fif[1][r];
long invFactnr = fif[1][n - r];
long c1 = ((long)fif[0][n] * fif[1][r]) % modulus;
long c2 = (c1 * fif[1][n - r]) % modulus;
return ((((long)fif[0][n] * fif[1][r]) % modulus) * fif[1][n - r]) % modulus;
}
// ---------------------------------------------------------------------
const int R = 1000000007;
static int N = 0;
static int[] A = null;
static int[] B = null;
static int[][] FIF = null;
static int[][] DP = null;
static int[][] C = null;
static int wdp0()
{
long ways = 0;
int wxm = Math.Min(B[0], N);
for (int iwx = 1; iwx <= wxm; iwx++)
ways = (ways + wdp(iwx, iwx)) % R;
return (int)ways;
}
static int wdp(int ix, int wx)
{
if (ix == N || wx == 1) return 1;
if (DP[ix][wx] > -1) return DP[ix][wx];
long ways = 0;
int wxm = Math.Min(Math.Min(wx, B[ix]), N - ix);
for (int iwx = 1; iwx <= wxm; iwx++)
{
long c = C[wx][iwx];
if (c < 0)
{
c = (Choose(wx, iwx, FIF, R) * FIF[0][iwx]) % R;
C[wx][iwx] = (int)c;
}
//long c = (Choose(wx, iwx, FIF, R) * FIF[0][iwx]) % R;
ways = (ways + (c * wdp(ix + iwx, iwx)) % R) % R;
}
DP[ix][wx] = (int)ways;
return DP[ix][wx];
}
static void Main(String[] args)
{
TextReader tIn = Console.In;
TextWriter tOut = Console.Out;
N = int.Parse(tIn.ReadLine());
A = tIn.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(p => int.Parse(p)).ToArray();
B = new int[N];
int b = 1;
for (int i = N - 1; i >= 0; i--)
{
B[i] = b++;
if (i > 0 && A[i - 1] > A[i]) b = 1;
}
FIF = FiF(1200 + 1, R);
DP = new int[N][];
for (int i = 0; i < N; i++)
{
DP[i] = new int[N + 1];
for (int j = 0; j <= N; j++) DP[i][j] = -1;
}
C = new int[N + 1][];
for (int i = 0; i <= N; i++)
{
C[i] = new int[N + 1];
for (int j = 0; j <= N; j++) C[i][j] = -1;
}
tOut.WriteLine(wdp0());
}
}Sherlock’s Array Merging Algorithm Java Solution
import java.io.*;
import java.util.*;
import java.math.*;
public class Solution {
static class Reader
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do
{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
public static long inverseMOD( int a ){
if( a == 0 ) return 1L;
long t = 0L;
long r = MOD;
long newt = 1L;
long newr = (long)a;
long quotient;
while( newr != 0L ){
quotient = r / newr;
t -= quotient * newt;
r -= quotient * newr;
if( r != 0L ){
quotient = newr / r;
newt -= quotient * t;
newr -= quotient * r;
}else{
r = newr;
t = newt;
break;
}
}
if( r > 1L ){
return -1L;
}
if( t < 0L ) t += MOD;
return t;
}
static HashMap<Integer,Long> C;
static long I[];
static int F[];
static long FI[][];
static long MOD = 1000000007L;
static long MODLIMIT = Long.MAX_VALUE / MOD;
static long MODSUMLIMIT = Long.MAX_VALUE - MOD*10L;
static int S[];
static int M[];
static int mi;
static int N;
public static long solve( int blockindex, int funnellimit, int blocksize ){
//StringBuilder sb = new StringBuilder();
//sb.append( "Solve M["+blockindex+"]="+blocksize+"/"+(blockindex == mi ? 0 : M[blockindex] )+" with funnel limit "+funnellimit+" = ");
if( funnellimit == 1 ){
//System.out.println( sb.toString()+"1");
return 1L;
}
if( funnellimit > blocksize ){
//System.out.println( sb.toString()+"-1");
return -1L;
}
if( blocksize == funnellimit ){
if( blockindex == mi-1 ){
//System.out.println( sb.toString()+"1");
return 1L;
}
int key = funnellimit*N + (S[blockindex] + M[blockindex] - blocksize);
if( C.get(key) != null ){
return C.get(key);
}
long p = 0;
long t;
blocksize = M[++blockindex];
for( int f = (blocksize > funnellimit ? funnellimit : blocksize ); f != 0; f-- ){
t = solve( blockindex, f, blocksize );
if( t < 0L ) continue;
//t *= FI[funnellimit][funnellimit-f];
//if( t > MODLIMIT ) t%=MOD;
t *= (long)F[funnellimit];
if( t >= MODLIMIT ) t%=MOD;
t *= I[funnellimit-f];
if( t >= MODLIMIT ) t%=MOD;
p += t;
//if( p > MODSUMLIMIT ) p%=MOD;
}
if( p > MOD ) p%=MOD;
//System.out.println( sb.toString()+p);
C.put( key, p );
return p;
}
int key = funnellimit*N + (S[blockindex] + M[blockindex] - blocksize);
if( C.get(key) != null ){
return C.get(key);
}
long p = 0L;
long t;
blocksize -= funnellimit;
for( int f = (blocksize > funnellimit ? funnellimit : blocksize ); f != 0; f-- ){
t = solve( blockindex, f, blocksize );
if ( t < 0L ) continue;
t *= (long)F[funnellimit];
if( t >= MODLIMIT ) t%=MOD;
t *= I[funnellimit-f];
if( t >= MODLIMIT ) t%=MOD;
p += t;
//if( p > MODSUMLIMIT ) p%=MOD;
}
if( p >= MOD ) p%=MOD;
//System.out.println( sb.toString()+p);
C.put( key, p );
return p;
}
public static void main(String[] args) throws IOException {
// long start = System.nanoTime();
Reader in=new Reader();
N = in.nextInt();
int Np1 = N+1;
{
C = new HashMap<Integer,Long>(N);
}
M = new int[N];
S = new int[N+1];
mi = 0;
{
S[0] = 0;
int prev = in.nextInt();
int streak = 1;
int cur;
for( int i = 1; i < N; i++ ){
cur = in.nextInt();
if( cur < prev ){
S[mi+1] = S[mi]+streak;
M[mi++] = streak;
streak = 1;
prev = cur;
}else{
++streak;
prev = cur;
}
}
S[mi+1] = S[mi]+streak;
M[mi++] = streak;
F = new int[M[0]+1];
I = new long[M[0]+1];
long fac = 1L;
F[0] = 1;
I[0] = 1L;
for( int i = 1; i <= M[0]; i++ ){
fac *= (long)i;
if(fac >= MOD){
fac%=MOD;
}
F[i] = (int)fac;
I[i] = inverseMOD( (int)fac );
}
FI = new long[M[0]+1][M[0]+1];
for( int f = M[0]; f != 0; f-- ){
for( int i = f; i != -1; i-- ){
FI[f][i] = ((long)F[f]*I[i])%MOD;
}
}
}
long p = 1;
for( int f = 2; f < Np1; f++ ){
long t = solve(0,f,M[0]);
if( t < 0L ) continue;
p += t;
if( p > MODSUMLIMIT ) p%=MOD;
}
System.out.print( p%MOD );
in.close();
}
}Sherlock’s Array Merging Algorithm Python Solution
#!/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)
