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.

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()

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

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

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]