Tiling dominoes | Dynamic programming
Вставка
- Опубліковано 15 лип 2024
- Walkthrough of dynamic programming on how to tile dominoes on a grid.
Problem:
open.kattis.com/problems/trit...
Source code:
github.com/williamfiset/Algor...
Video slides:
github.com/williamfiset/algor...
Website:
www.williamfiset.com
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 ua-cam.com/video/1A6OYsKmL1U/v-deo.html
It always helps to to see some sort of visualization instead of understanding it in the abstract :), great video.
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.
amazing. Please keep doing this. Good DP videos are lacking on youtube.
Would love more on DP . Great explanation.
What a cool question and cool DP solution.
Well this was a bitmask dp problem with the best explanation.
Possibly best tiling video ever
certainly
I always wait for ur videos WillamFiset
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.
Wow! Superbly derived solution. Thankyou.
Most intuitive approach for this problem 🔥💖
need more videos on DP. Amazing explanations. more, more, more....
This blew my mind! Thank you so much
Awesome explanation!
what can be more better than this wow...
Most underrated channel tbh
the best possible solution! thanks
Your videos are great! You should consider making one about Push-Relabel. Keep up the good work!
You're a great tutor! Let me know if you're starting any mentorship programs.
Great video ! thanks a lot :D
Wow great explanation thanks
Excelleny video ! Thanks?
What if there are more than 3 columns? How would the state transition work?
this is brilliant
what softwares do you use to create these videos?
Please upload videos on Convex Hull Algorithms.
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
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.
AWESOME!!!!!!!!!!
awesome
love from ghaziabad💕💕💕💕
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!
Thanks my brain said 🤯
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.
I did it much more simply, but thank you for showing me this question nonetheless!
Can you please give a brief on your approach?
great
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?
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].
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.
I came to find the explanation for sin and cos in the kasteleyn domino-tiling formula - yuk
Why is dp[0][7] = 1 ?
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
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
2:00
2:20
it turns into a neural net!
2:39
Ok, I completely understand this, this is a great video, but how do I think of this in front of the interviewer??? 😖😖😔
would you say this could appear in a interview?
Variations of this problem could definitely appear