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. Lego Blocks
  2. Discussions

Lego Blocks

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 32 Discussions, By:

votes

Please Login in order to post a comment

  • fadeevab_com
    8 months ago+ 2 comments

    Why is this "medium"? It's hard to understand and implement even with Editorial help (which I had to open for the first time on the hackerrank). Comparing to the "Simple Text Editor", which is actually easy but labeled as medium, this one is hard, in my opinion.

    57|
    Permalink
  • rdgpcampos
    2 months ago+ 2 comments

    Honestly, I found this problem pretty hard. The execution itself isn't that complicated, but figuring out the logic behind the solution took me a long time. The way I made sense of it was to think like this: Let P(m) be the number of possible layouts (good+bad) of a single row (n=1) of blocks. By inspection, we know that P(1) = 1, P(2) = 2, P(3) = 4, and P(4) = 8. For any m > 4, we can consider four different cases: 1. The last block has width 1, in which case the remainder of the row has width m-1 and thus P(m-1) possible layouts. 2. The last block has width 2, in which case the remainder of the row has width m-2 and thus P(m-2) possible layouts. 3. The last block has width 3, in which case the remainder of the row has width m-3 and thus P(m-3) possible layouts. 4. The last block has width 4, in which case the remainder of the row has width m-4 and thus P(m-4) possible layouts.

    Since there are no layouts that do not belong to any one of these cases, and no layout belongs to more than one of them, we can affirm that P(m) is the sum of the layouts in each case, i.e. P(m) = P(m-1) + P(m-2) + P(m-3) + P(m-4). Knowing the values of P(1), P(2), P(3), and P(4), we can determine P(m) for any possible value of m. Additionaly, since each row is independent from each other, we can affirm that the total number of layouts of a wall of height n and width m is P(m)^n.

    To find the number of good layouts for a wall of height n and width m, denoted by S(n,m), we still have to subtract from the number of bad layouts from P(m)^n. Let the number of bad layouts be denoted by D(n,m).

    Consider a wall of height n, width m, with a straight line running from top to bottom at the leftmost position (i.e. the blocks on the leftmost position of each row are all of length 1). The number of bad layouts that satisfy this condition is S(n,1) * P(m-1)^n, since to the left of the line there are S(n,1) good layouts (there are no bad layouts for m = 1), and to its right we have P(m-1)^n layouts (good + bad). We can move the line one step to the right and find the number of bad layouts that have a line at the second-to-last position to the left, while excluding the all the bad layouts we already counted. That is equal to S(n,2) * P(m-2)^n. This is because, to the left of the line, we count all the good layouts, to make sure that we are not recounting layouts from when the line was at the previous position. To the right of the line, we just count all the possible layouts. We continue then moving the line to the right and counting the bad layouts, which will yield at the end D(n,m) = sum_(i=1)^(m-1) S(n,i) * P(m-1)^n. Thus, S(n,m) = P(m)^n - sum_(i=1)^(m-1) S(n,i) * P(m-1)^n.

    Sorry for the poor explanation, I didn't take the time to draw images to make it easier to understand, but I hope this can clear out the problem for some people. I'll repeat, this is not intermediate in my opinion, unless I'm missing some obvious interpretation of the problem by some chance.

    The code I submitted is written below.

    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    #
    # Complete the 'legoBlocks' function below.
    #
    # The function is expected to return an INTEGER.
    # The function accepts following parameters:
    #  1. INTEGER n
    #  2. INTEGER m
    #
    P = [0,1,2,4,8]
    allS = dict()
    allT = dict()
    for i in range(5,1001):
        P.append(P[i-1] + P[i-2] + P[i-3] + P[i-4])
    
    def legoBlocks(n, m):
        UPPER = 1000000007
        # Total number of layouts is P^n,
        # number of good layouts is S
        T = [0,1]
        S = [0,1]
        if m == 1:
            return 1
        if n == 1:
            if m < 5:
                return 1
            else:
                return 0
    
        start = 2
        if n in allS:
            S = allS[n]
            if len(S) > m:
                return S[m]
            start = len(S)
            T = allT[n]
                
        for i in range(start,m+1):
            T.append(pow(P[i],n,UPPER))
        allT[n] = T
        for i in range(start,m+1):
            S.append(T[i])
            for j in range(i):
                S[i] -= S[j]*T[i-j]
            S[i]=int(S[i]%UPPER)
        allS[n] = S
        
        return int(S[m]%UPPER)
    
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        t = int(input().strip())
    
        for t_itr in range(t):
            first_multiple_input = input().rstrip().split()
    
            n = int(first_multiple_input[0])
    
            m = int(first_multiple_input[1])
    
            result = legoBlocks(n, m)
    
            fptr.write(str(result) + '\n')
    
        fptr.close()
    
    37|
    Permalink
  • lazarevzubov
    3 months ago+ 1 comment

    Height is "n" and width is "m". Very intuitive.

    20|
    Permalink
  • carlaustabile
    5 months ago+ 2 comments

    I honestly don't understand the problem, I've read it multiple times and I'm still puzzled ???

    15|
    Permalink
  • valentin27
    7 months ago+ 0 comments

    Python solution with comments:

    def legoBlocks(n, m):
        # Write your code here
        M = 1000000007
    
        a = [0,1,2,4,8] # a[i] is the number of all walls with width i 
        for j in range(5,m+1):  # this formula executes only when we have width 5 or more
            a.append((a[j-1]+a[j-2]+a[j-3]+a[j-4])%M)
        
        for i in range(m+1): # this will give us all the walls for height n 
            a[i] = pow(a[i],n,M)
    
        # let r[i] be the number of good layouts that have height n, and width i
        r = [a[i] for i in range(m+1)] # start with all of them 
        for i in range(1,m+1):
            for j in range(1,i):
                r[i] -= (r[j]*a[i-j]) # subtract the number of bad layouts, when the FIRST vertical break in the wall appears at index j 
            r[i] = r[i]%M # make the computations easier 
        return r[m]
    
    6|
    Permalink
Load more conversations

Need Help?


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