For those of you looking for a challenge, check out this tiling problem: open.kattis.com/problems/tray The problem is very similar except that it adds two elements of complexity: 1) 1x1 tiles are introduced 2) Some cells are banned
Hey for this problem, I am following the similar idea. Here there will be more possible combinations for a particular dp state(a column). I have eliminated the banned cells(set it to INT_MIN) by using a hashmap and checking if a state(out of those 8 as stated in video) is possible or not. I am stuck from this point on. Could you give a hint or something on this problem? Thank you:)
The problem just blew my mind! Then solution blew my mind even more! I was like speechless when I saw that each columns tiling pattern could be mapped to 0 to 7 in a binary fashioned way! Thanks a lot. This problem definitely opens mind about how a problem can be approached.
@WilliamFiset I think another channel is uploading your videos. Is it your channel or have you provided it with the permission czcams.com/video/1A6OYsKmL1U/video.html
was stuck for a long time, very very informative,really the best possible explanation, instant share with my friends practicing dp. Thank you keep making these videos.
Variations of this problem: 1. There field is N x M. 2. There are two domino types: 2x1 and 1x1. 3. There is limited number of dominos: A dominos of type 2x1, B dominos of type 1x1. 4. There are dominos of weird shapes like “r” or 2x2 square.
Well instead of determining states, a simple solution is to just sum up prev states and then F(n)=3*F(n-2)+2*sum int numTilings(int n) { vector arr(n+1,0); arr[0]=1; int sum=0; for (int i=2;i
I solved it quite differently but my submissions always failed because I forgot to output 1 for width 0 >.> I did a recursion on the width: x = 3*f(n-2) for (i = 2; i < width - 2; i += 2) x += 2 * f(i) x += 2 The thing is that the whole rectangle is always filled by two types of blocks: - 2*3 blocks of which there are 3 possible types - 2*(2x) blocks of which there are 2 possible types for every x always arranged like this: 11 55 88 2 33 66 9 2 44 77 9 or the same thing upside down where the middle parts can be repeated to add 2 to the width. This is even fast enough to work without DP. Oh and if width % 2 == 1 i.e. the width is odd I just output 0 immediately.
Excellent video, however there is one case which is not expanded on. Theoretically, state 1 can come from state 0, by placing 1 vertical and 1 horizontal domino. How come this is not accounted for?
I guess that the arrangements of Dominos I described above is already counted when state 6 is considered in the creation of state 1. So considering state 0 would be overcounting states. Correct me If I'm wrong
I also struggled a little with it, but if you apply the algorithm you will see that the only state that is affected by 0 state is 7. The line is ´´dp[i][7] += dp[i-1][0];´´. He is simply extending this logic. Another way to do this is to instead let the code do this for you. Increase the size of the array by one (so it is now n+2), and instead of dp[0][7]=1, you can do dp[0][0]=1, if that makes more sense to you. PS: I got AC with this solution.
Why did the initialisation of dp[0][7] became one. As there is no row behind it it should not be possible ? only dp[0][3] and dp[0][6] should have been initialised to 1 right and all rest 0.
Great question! This might have merited more of an explanation, so let me write it out here. If you have a look at 12:12 when we go from state 2 in column 0 to state 5 in column 1, you will notice that state 2 in column 0 is an impossible state with 1 tile. Similarly, state 5 in column 0 is an impossible state. Both of these impossible states dp[0][2] and dp[0][5] will have an initial value of 0, so dp[1][2] and dp[1][5] will also have a value of 0, and so will dp[i][2] and dp[i][5]. It's safe to remove state 2 and 5 since: 1) no other states depend on states 2 and 5 for their number of tilings 2) states 2 and 5 only depend on each other 3) dp[i][2] and dp[i][5] are always 0
Can't dp[i][7] be constructed from dp[i-1][0] in 3 different ways? Clearly, one of them as pointed out in this video is to tile three of them horizontally. The two remaining was are : Tile two of them vertically and another one horizontally underneath them and following symmetry, the opposite. Someone please help me out regarding this!
No, the area difference between dp[i-2][0] and dp[i][7] is 3x3 if you notice carefully. However, one problem lies in the fact that dp[i][7] can be constructed from dp[i-1][0] in 3 different ways. Why do we not account for that?
Actually State 7 cannot be generated by state 1 because adding 2*1 tile to state 1 will create dp[i-1][7] and not dp[i][7] and similar is the case of state 4
For those of you looking for a challenge, check out this tiling problem:
open.kattis.com/problems/tray
The problem is very similar except that it adds two elements of complexity:
1) 1x1 tiles are introduced
2) Some cells are banned
Hey for this problem, I am following the similar idea. Here there will be more possible combinations for a particular dp state(a column). I have eliminated the banned cells(set it to INT_MIN) by using a hashmap and checking if a state(out of those 8 as stated in video) is possible or not. I am stuck from this point on.
Could you give a hint or something on this problem?
Thank you:)
The problem just blew my mind! Then solution blew my mind even more! I was like speechless when I saw that each columns tiling pattern could be mapped to 0 to 7 in a binary fashioned way! Thanks a lot.
This problem definitely opens mind about how a problem can be approached.
@WilliamFiset I think another channel is uploading your videos. Is it your channel or have you provided it with the permission czcams.com/video/1A6OYsKmL1U/video.html
It always helps to to see some sort of visualization instead of understanding it in the abstract :), great video.
Possibly best tiling video ever
certainly
Well this was a bitmask dp problem with the best explanation.
was stuck for a long time, very very informative,really the best possible explanation,
instant share with my friends practicing dp. Thank you keep making these videos.
Variations of this problem:
1. There field is N x M.
2. There are two domino types: 2x1 and 1x1.
3. There is limited number of dominos: A dominos of type 2x1, B dominos of type 1x1.
4. There are dominos of weird shapes like “r” or 2x2 square.
amazing. Please keep doing this. Good DP videos are lacking on youtube.
need more videos on DP. Amazing explanations. more, more, more....
what can be more better than this wow...
Most intuitive approach for this problem 🔥💖
Would love more on DP . Great explanation.
Most underrated channel tbh
Wow! Superbly derived solution. Thankyou.
I always wait for ur videos WillamFiset
Well instead of determining states, a simple solution is to just sum up prev states and then F(n)=3*F(n-2)+2*sum
int numTilings(int n)
{
vector arr(n+1,0);
arr[0]=1;
int sum=0;
for (int i=2;i
it's not right, ig
What a cool question and cool DP solution.
the best possible solution! thanks
love from ghaziabad💕💕💕💕
This blew my mind! Thank you so much
I solved it quite differently but my submissions always failed because I forgot to output 1 for width 0 >.>
I did a recursion on the width:
x = 3*f(n-2)
for (i = 2; i < width - 2; i += 2) x += 2 * f(i)
x += 2
The thing is that the whole rectangle is always filled by two types of blocks:
- 2*3 blocks of which there are 3 possible types
- 2*(2x) blocks of which there are 2 possible types for every x always arranged like this:
11 55 88
2 33 66 9
2 44 77 9
or the same thing upside down where the middle parts can be repeated to add 2 to the width.
This is even fast enough to work without DP.
Oh and if width % 2 == 1 i.e. the width is odd I just output 0 immediately.
Fun fact: you can do this in log (n) with matrix exponentation (and I think there is a formula to calculate domino tiling as well)
He did show the formula at the start!
You're a great tutor! Let me know if you're starting any mentorship programs.
Excellent video, however there is one case which is not expanded on. Theoretically, state 1 can come from state 0, by placing 1 vertical and 1 horizontal domino. How come this is not accounted for?
I guess that the arrangements of Dominos I described above is already counted when state 6 is considered in the creation of state 1. So considering state 0 would be overcounting states. Correct me If I'm wrong
Please upload videos on Convex Hull Algorithms.
What if there are more than 3 columns? How would the state transition work?
this is brilliant
Your videos are great! You should consider making one about Push-Relabel. Keep up the good work!
Awesome explanation!
I have difficulty understand why is only dp[0][7] set to be 1 as the initial value. Could someone explain? Thnaks a lot
how many ways is it possible to make an empty grid?
I also struggled a little with it, but if you apply the algorithm you will see that the only state that is affected by 0 state is 7.
The line is ´´dp[i][7] += dp[i-1][0];´´.
He is simply extending this logic.
Another way to do this is to instead let the code do this for you. Increase the size of the array by one (so it is now n+2), and instead of dp[0][7]=1, you can do dp[0][0]=1, if that makes more sense to you. PS: I got AC with this solution.
Wow great explanation thanks
Great video ! thanks a lot :D
Why did the initialisation of dp[0][7] became one. As there is no row behind it it should not be possible ? only dp[0][3] and dp[0][6] should have been initialised to 1 right and all rest 0.
Nice Explaination. Thank you. However i couldn't understand how states 2 and 5 are not possible, but 3 and 7 are possible.
Great question! This might have merited more of an explanation, so let me write it out here.
If you have a look at 12:12 when we go from state 2 in column 0 to state 5 in column 1, you will notice that state 2 in column 0 is an impossible state with 1 tile. Similarly, state 5 in column 0 is an impossible state. Both of these impossible states dp[0][2] and dp[0][5] will have an initial value of 0, so dp[1][2] and dp[1][5] will also have a value of 0, and so will dp[i][2] and dp[i][5]. It's safe to remove state 2 and 5 since: 1) no other states depend on states 2 and 5 for their number of tilings 2) states 2 and 5 only depend on each other 3) dp[i][2] and dp[i][5] are always 0
@@WilliamFiset-videos i guess picture is worth thousand words and your explanation was on target. Thanks for making such beautiful video
Can't dp[i][7] be constructed from dp[i-1][0] in 3 different ways? Clearly, one of them as pointed out in this video is to tile three of them horizontally. The two remaining was are : Tile two of them vertically and another one horizontally underneath them and following symmetry, the opposite. Someone please help me out regarding this!
That case is already being considered when transitioning from say dp[i-1][6].
When we are calculating state 7 from state 0, it should be dp[i][7] += dp[i-2][0] instead of dp[i][7] += dp[i-1][0] or am I. missing something?
No, the area difference between dp[i-2][0] and dp[i][7] is 3x3 if you notice carefully.
However, one problem lies in the fact that dp[i][7] can be constructed from dp[i-1][0] in 3 different ways. Why do we not account for that?
Why is dp[0][7] = 1 ?
Thanks my brain said 🤯
I came to find the explanation for sin and cos in the kasteleyn domino-tiling formula - yuk
I did it much more simply, but thank you for showing me this question nonetheless!
Can you please give a brief on your approach?
Excelleny video ! Thanks?
what softwares do you use to create these videos?
AWESOME!!!!!!!!!!
Can't state 7 be generated from state 1? Or have I misunderstood something?
Actually State 7 cannot be generated by state 1 because adding 2*1 tile to state 1 will create dp[i-1][7] and not dp[i][7] and similar is the case of state 4
would you say this could appear in a interview?
Variations of this problem could definitely appear
awesome
Ok, I completely understand this, this is a great video, but how do I think of this in front of the interviewer??? 😖😖😔
2:00
great
it turns into a neural net!
2:20
2:39