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. Summing Pieces
  5. Discussions

Summing Pieces

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 29 Discussions, By:

votes

Please Login in order to post a comment

  • Gurupad
    6 years ago+ 7 comments

    This problem was featured in World Codesprint 7, I had commented the following in the discussion page there. Sharing the same here. :) Hope It'll help.

    Editorial is filled with fancy-pants math all over the place.

    TL;DR

    This is how I solved it. (I suppose editorial's approach is the same too).

    Looking for a pattern is the key thing to solve this problem.

    Let's take the test case 1 3 6 7 itself.

    Now 'Pieces' are:

    [(1),(3),(6),(7)]
    [(1,3),(6),(7)]
    [(1),(3,6),(7)]
    [(1),(3),(6,7)]
    [(1,3,6),(7)]
    [(1,3),(6,7)]
    [(1),(3,6,7)]
    [(1,3,6,7)]
    

    Now, count contributions of each number in the 'pieces'. For example, in pair (1,3), 1 and 3 contribute twice. in pair (1,3,6), 1,2and3 contribute thrice.

    We are calculating in this manner because we want to know how much amount of value is each number contributing to the final sum.

    So these are the final contribution count values for the above test case.

    1 - 15
    3 - 18
    6 - 18
    7 - 15
    

    Verfiy, final sum - (1*15)+(3*18)+(6*18)+(7*15) = 282

    Ah ha, there is some pattern visible now.

    ---------------------
    | 15 | 18 | 18 | 15 |
    --------------------- 
      ^     ^   ^     ^
      |     |___|     |
      |_______________|
    

    Also, 15 in binary - 1111 (pretty) 18 in binary - 10010 (not pretty)

    Try doing for n=5 on paper. These are the final count values.

    --------------------------
    | 31 | 38 | 40 | 38 | 31 |
    --------------------------
    

    Ah ha, the earlier pattern holds (a bit).

    31 in binary - 11111
    38 - 31+7 (hmmm, earlier case it was +3 now it's +7,I see something. But let's looks further)
    40 - 38+2 (Ugh, +2? sob sob, Let's look for n=6)
    

    Try doing for n=6 on paper (Don't !).

    Count values :

    -------------------------------
    | 63 | 78 | 84 | 84 | 78 | 63 |
    -------------------------------
    
    63 in binary - 111111
    
    78 - 63+15 (+3 , +7 , now + 15 ,prettay prettay)
    
    84 - 78+6 (+6? nooooo, umm, ok let's move on)
    

    Count values for n=7:

    -------------------------------------------
    | 127 | 158 | 172 | 176 | 172 | 158 | 127 |
    -------------------------------------------
    
    
    127 in binary - 1111111
    158 - 127+31
    172 - 158+14 
    176 - 172+4
    
    
    Let's look at binary representation of those additional numbers (i.e, 31,14 and 4)
    31 - 11111
    14 - 1110
    4 - 100
    
    Ummm, I feel something is getting subtracted from a nicer value. Let's see.
    
    31 = 2^5 - 1
    14 = 2^4 - 2
    4  = 2^3 - 4
    

    Evil racoon reaction

    Let's verify this pattern for n=6, where we had 63+15 and 78+6
    15 = 2^4 - 1
    6 = 2^3 - 2
    
    Let's look for n=5, where we had 31+7 and 38+2
    7 = 2^3 - 1
    2 = 2^2 - 2
    
    So, For n>1 in general, the count values are
    
    ----------------------------------------------------------------
    | 2^n-1 | p+2^(y) - 2^0 | p+2^(y-1) - 2^1 | p+2^(y-2) - 2^2|...
    ----------------------------------------------------------------
    where,
     p is previous box value
     y starts from n-2 and decremented by 1 afterwards
    

    When to stop calculating the count values? Well, Look at above examples and notice it stops in the middle and repeats itself. (as if, a mirror is kept at the center)

    Let's take n=10 and verify.
    
    2^10-1 = 1023
    p + 2^(y) - 2^0   = 1023 + 2^(n-2) - 1   = 1278
    p + 2^(y-1) - 2^1 = 1278 + 2^(n-2-1) - 2 = 1404
    p + 2^(y-2) - 2^2 = 1404 + 2^(n-2-2) - 4 = 1464
    p + 2^(y-4) - 2^3 = 1464 + 2^(n-2-3) - 8 = 1488
    
    Let's stop here it'll repeat in reverse order.
    

    After counting these values all one has to do is multiply each value with respective input array value.

    But, How the ** to implement this?. In python, it was easy, because, it has a function that takes cares of modular arithmetic.

    Pow(x,y,mod) = (x^y)%mod.

    One can store values into an array and multiply them or you can do both (i.e, calculating count values and multiply values with respective input array on the fly (that's DP).

    100|
    Permalink
    View more Comments..
  • mohitkumar20
    6 years ago+ 3 comments

    can someone explain me the solution. the solution i m giving its accepting till test case 3 but giving wrong answer from 4 onwards. is anything different logic wise between 3rd and 4th test case?

    3|
    Permalink
  • asbaghel
    2 years ago+ 1 comment

    Can we solve this question using Matrix Chain Multiplication.

    2|
    Permalink
  • sathiiii
    2 years ago+ 0 comments

    Optimized python Solution:

    from collections import defaultdict
    from operator import mul
    
    dp = defaultdict(list)
    
    
    def summingPieces(arr):
        global dp
        n = len(arr)
        mod = 10 ** 9 + 7
        if not dp[n]:
            contributions = [0] * (n // 2 + n % 2)
            contributions[0] = pow(2, n, mod) - 1
            for i in range(1, n // 2 + n % 2):
                contributions[i] = (contributions[i - 1] + pow(2, n -
                                                         1 - i, mod) - pow(2, i - 1, mod)) % mod
            dp[n] = contributions + contributions[:n // 2][::-1]
        return sum((dp[n][i] * arr[i]) % mod for i in range(n)) % mod
    
    2|
    Permalink
  • amaximov
    6 years ago+ 1 comment

    Sharing my O(n) time and O(1) space solution with an explanation.

    https://github.com/andreimaximov/algorithms/blob/master/algorithms/dynamic-programming/summing-pieces/solution.py

    1|
    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