Sherlock's Array Merging Algorithm
Sherlock's Array Merging Algorithm
+ 2 comments 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.
+ 1 comment The dynamic programming comes in for computing the next count for each additional item (i.e., mi) from previous count. However, besides the addtional item, computing needs to distinguish whether it is greater than the last item (mi-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 = m0 m1 m2 ... 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 --> 3P2 = 6 (one '/' here, the counts of its left items = 3, and the counts of its right items = 2.)
1 2 5 / 3 / 4 --> 3P1 * 1P1 (3P1 because left items of first '/' count to 3 and right items do 1. 1P1 because left items of second '/' count to 1 and right items do 1.)
+ 2 comments Do the arrays in the collections have to be sorted?
+ 0 comments 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
+ 0 comments I think the solution given is wrong .
For the input n = 4
1 3 2 4The possible V are
A. 1 2 4
3B, 1 2
3 4Hence there are 2 solutions . But the algo mentioned gives 5 as op
Sort 14 Discussions, By:
Please Login in order to post a comment