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

HackerRank Sherlock's Array Merging Algorithm Problem Solution — HackerRank Sherlock’s Array Merging Algorithm Problem Solution

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)