We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Sherlock's Array Merging Algorithm
  5. Discussions

Sherlock's Array Merging Algorithm

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 14 Discussions, By:

votes

Please Login in order to post a comment

  • Muhammad_Tariq
    4 years ago+ 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.

    6|
    Permalink
  • dzchoi
    4 years ago+ 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.)

    1|
    Permalink
  • Stoyan_Malinin
    5 years ago+ 2 comments

    Do the arrays in the collections have to be sorted?

    1|
    Permalink
  • naganjan931
    6 months ago+ 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|
    Permalink
  • rizwan_b170829cs
    1 year ago+ 0 comments

    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

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature