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 ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-1A6OYsKmL1U.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.
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
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.
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?
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.
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
