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.
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/python3importmathimportosimportrandomimportreimportsys## 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()foriinrange(5,1001):P.append(P[i-1]+P[i-2]+P[i-3]+P[i-4])deflegoBlocks(n,m):UPPER=1000000007# Total number of layouts is P^n,# number of good layouts is ST=[0,1]S=[0,1]ifm==1:return1ifn==1:ifm<5:return1else:return0start=2ifninallS:S=allS[n]iflen(S)>m:returnS[m]start=len(S)T=allT[n]foriinrange(start,m+1):T.append(pow(P[i],n,UPPER))allT[n]=Tforiinrange(start,m+1):S.append(T[i])forjinrange(i):S[i]-=S[j]*T[i-j]S[i]=int(S[i]%UPPER)allS[n]=Sreturnint(S[m]%UPPER)if__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')t=int(input().strip())fort_itrinrange(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()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lego Blocks
You are viewing a single comment's thread. Return to all 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.