This talk is the best, because you spend most of the time on the math. For so many of us, coding is easy and combinatorics is hard, yet this is the only talk I found that explains the math. Thank you so much.
To those who are wondering: We counted (1, 3) combo as 4 but (3, 1) as 1 cuz if we break 3 in (3, 1) it will break into (1, 2, 1) and (2, 1, 1) which can already be covered by previous considerations from (2, 2) and (1, 3) so to avoid overlapping it has been done so.
Imo your comment is misleading from the pattern of thought in the video. When making 4, it is true that: 2,2 breaks to 112, 211, 1111 (which would be 4 possibilites) and 3,1 breaks to 211, 121, 1111 (which would also be 4 possibilities) but in the explanation she didn't go through all the possible breaks, since she said we keep the first block in tact, and only look for possibilites with the rest of the blocks. You can see she marks the part that needs to be broken down with small diagonal lines. if the first block is a 1, we have 3, 21, 21 and 111, which is 4 possibilities if the first block is a 3, we only have 1 option left for the second block: 1. Thats why it is only 1 there.
Thanks for the solution, Lulu! Could you please explain why is the total of ways to have a split in the wall is a multiplication of number of ways to build left-i and right-i?
In the first step when calculating the number of ways you can build a single wall layer of length 6, why do we add the four previous ones? I don't understnad that part
28:11 total = 0,1,8,32(should be 64)
Thanks for the correction.
Finally someone who describes the algorithm behind the solution. This is very well done.
This talk is the best, because you spend most of the time on the math. For so many of us, coding is easy and combinatorics is hard, yet this is the only talk I found that explains the math. Thank you so much.
Thank you. May you be blessed. I wanted logical help and it was the best resource. Rest of the internet had code.
Glad it helped!
感谢分享，很清晰易懂的解释！
Great explanation: well-structured, concise, with a practical walkthrough.
Many thanks!
You're very welcome!
Very gorgeous and lucid! Thanks for saving time!
Awesome solution and eloborated explanation, thanks for clarifying this problem!
To those who are wondering: We counted (1, 3) combo as 4 but (3, 1) as 1 cuz if we break 3 in (3, 1) it will break into (1, 2, 1) and (2, 1, 1) which can already be covered by previous considerations from (2, 2) and (1, 3) so to avoid overlapping it has been done so.
Imo your comment is misleading from the pattern of thought in the video.
When making 4, it is true that:
2,2 breaks to 112, 211, 1111 (which would be 4 possibilites)
and
3,1 breaks to 211, 121, 1111 (which would also be 4 possibilities)
but in the explanation she didn't go through all the possible breaks, since she said we keep the first block in tact, and only look for possibilites with the rest of the blocks. You can see she marks the part that needs to be broken down with small diagonal lines.
if the first block is a 1, we have 3, 21, 21 and 111, which is 4 possibilities
if the first block is a 3, we only have 1 option left for the second block: 1. Thats why it is only 1 there.
Great explanation, helped me understand this difficult problem. Thanks for the effort you put into this video.
great explanation. Thanks a lot. This is a harder question.
I am trying to solve this problem right now. Your video came in the right moment. Thank you so much.
Glad it helped
Thank you so much for this explanation. It really helped.
Thank you
This was good explanation
f[0] is 1 which means there is only one way to build fp[0]: "no block". Thus you can just manually caculate f[0]~f[3] and f[4]=f[0]+f[1]+f[2]+f[3]=8
many thanks for your video
You did a great job explaining the intuition on this one thank you!
Glad you enjoyed it!
Hey Lulu, thanks for the explain.
I didnt get why we are recursing the *width - the width* of each blocks in minute 7:36
omg you actually taught me😂, thanks a lot
Happy to help!
Thank you very much, I was stucked
Thanks for the solution, Lulu! Could you please explain why is the total of ways to have a split in the wall is a multiplication of number of ways to build left-i and right-i?
You can draw on a paper with hight = 1 and width of 4. When the i == 2, left side has 2 ways and right side also 2 ways, so the total is 2 *2.
Lulu did you come up with this solution independently? Such a genius
No, I did reference to the official solution in Hackerrank. Yet, still needs lots of effort from my side to really understand the solution.
In the first step when calculating the number of ways you can build a single wall layer of length 6, why do we add the four previous ones? I don't understnad that part