Hi, the solution of the problem are is clearly defined.

I have following confusions,

Why the solution {[1,2],[3]} is not included in first sample case as a solution ? Why the solution {[1],[2]} is not included in second sample case as a solution ?

I would request the author of the problem to include 2 more samples to better understand the solution.

The dynamic programming comes in for computing the next count for each additional item (i.e., m_i) from previous count. However, besides the addtional item, computing needs to distinguish whether it is greater than the last item (m_i-1) or not, and needs to memorize some state to do the proper next computation.

I have used map (std::map of (int, int) pair into int) to trace such states, and I could pass all cases except the case 35. To pass it finally, I have changed map to 2-dimensional array (std::vector of std::vector of int).

For a hint, I focused on how to divide the sequence M = m₀ m₁ m₂ ... into sub-sequences.

For example, when M = 1 2 5 3 4,

1 --> 1 way

1 2 --> 1 way, 1 / 2 --> 1 way

1 2 5 --> 1 way, 1 2 / 5 --> 2 ways, 1 / 2 / 5 --> 1 way

1 2 5 / 3 --> 3 ways, 1 2 / 5 / 3 --> 2 ways, 1 / 2 / 5 / 3 --> 1 way

1 2 5 / 3 4 --> 6 ways, 1 2 5 / 3 / 4 --> 3 ways, 1 2 / 5 / 3 / 4 --> 2 ways, 1 / 2 / 5 / 3 / 4 --> 1 way

So, 6+3+2+1=12 ways in total.

Note also, to compute the number of ways for a divided sequence, I could just think '/' symbol induces a multiplication of permutation.

1 2 5 / 3 4 --> ₃P₂ = 6 (one '/' here, the counts of its left items = 3, and the counts of its right items = 2.)

1 2 5 / 3 / 4 --> ₃P₁ * ₁P₁ (₃P₁ because left items of first '/' count to 3 and right items do 1. ₁P₁ because left items of second '/' count to 1 and right items do 1.)

Do the arrays in the collections have to be sorted?

python3

def arrayMerging(data): # Write your code here n = len(data) M = 10**9+7 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:
    return 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
return cmp

I think the solution given is wrong .

For the input n = 4
1 3 2 4

The possible V are

A. 1 2 4
3

B, 1 2
3 4

Hence there are 2 solutions . But the algo mentioned gives 5 as op