hi everyone welcome back to the channel in this video we're going to be discussing this problem counting tars from the CSS problem [Music] site and before we do that let me remind you that this video is a part of a dynamic programming series that is going on this channel and in case this is the very first video that you're watching from the playlist I would highly recommend you to start the playlist right from the very first video so let's give this problem statement a read it is written that your task is to build a tower whose width is two and the height is n you have an unlimited supply of blocks whose width and height are integers so basically you have been given you know a tower of height n whose width is two and now every single cell of this Tower should be occupied how do you want to occupy it by filling it with rectangular cells right for example if you look at this fourth example they've you know filled this entire grid like this that they have this huge block then they have these one cross one one cross one one cross one block right similarly here it's like a different configuration Al together and so on right so you just need to find out what are the different number of ways that you can construct this Tower of height n and width two right and it is also written that mirrored and rotated towers are counted separately so let's try to understand what do they really mean by the statement that mirrored and rotated Towers have to be counted differently let's suppose this is one of the tower now let's suppose we have the same Tower but mirrored okay this is how it's going to look like when it's mirrored so what they're saying is that you know this is one and this is two they have to be counted differently okay they cannot be counted as the same Tower right that is the main thing that is given in this problem statement okay let's further read this problem statement now it's written that uh you are also going to have test cases here right so you're going to be given T Test cases and in every single test case you're going to be given an integer n right you need to find out what is the number of different ways you can construct a tower of height n and width two for every single test case so these are the constraints let's make some observations out of this okay and this is also going to be a general way of approaching DP Problems by looking at the constraints okay so firstly you know that 10 ^ 8 operations are allowed in 1 second yes we clearly know that n is going up to 10 the^ 6 T is going up till 100 so you cannot have a solution which looks something like order of n square or maybe order of n logn into T right so essentially how would you like to solve this problem so how would you like to solve this problem one case is that for every single test case is you are going to be solving the problem for that given n right so your time complexity overall will be something like T into maybe n or n log n right so if you have something like this order of T * n log n do you think this will work no this will also not work because this will go till 100 this will go till 10 the^ 6 and this another log Factor will go to 20 so this is again not going to work what if you have a solution like order of T * n is this going to work yes this might work but this is barely going to pass why because this is going till 100 and this is going till 10^ 6 so whenever you're writing a solution in competitive programming you don't really you know make use of exact number of operations right basically your time complexity comes out to be something like maybe 3 * T into n right or maybe let's say 5 * T into n so there is this constant which is involved in every single problem even though we write our time complexity as order of n or order of n Square there is always a constant factor involved this constant Factor cannot be something like 10 into T * that will not pass correct all right so let's try to draw some grids and let's see how is this really working out okay let's look at this first five cross two grid here what you could do is that uh something like this you could fill let's suppose the bottom two rows completely like this this is one block okay one block I have filled here next let's suppose you fill another block like this okay next let's suppose you fill another block like this now look at this point when you're standing here on this Green Dot now standing here try to understand can you fill a horizontal cell here no because the right side of the grid is already occupied so you can only put a vertical cell here right similarly let's suppose you know we were at this point let's suppose you fill this grid like this now look at this Orange Point can I fill a horizontal cell here like can I fill it something like this that I mark it like this yes that is completely allowed right but why is this allowed here and why wasn't it allowed when we were doing something like this it wasn't allowed at this green point because the right side of the grid was already occupied right so for a given cell if you're looking at a particular cell if the right side or if the left side of it is already occupied you cannot put a horizontal cell you only have to put a vertical cell right that's very obvious and before we go beyond this let me also tell you that when I was solving this problem for the very first time I was not able to do it on my own okay I think I solved this problem almost 2 years ago and I was not able to do it on my own okay so it is absolutely fine if you're not able to solve this problem on your own and if you have to watch this video completely to understand the solution it is absolutely fine so let's suppose this is the you know grid that we want to build okay now look at the a through okay look at this point like look at this a through now when you look at this I throw what could happen right one of the things that we have already seen is that okay this the cells below it are all completely occupied and you know they they completely filled like you know there is a block let's suppose like this here and below it also some blocks are present something like this this is one way in which the I throw could look like that okay the cell below it is already closed right all the cells below it are already closed one of the other ways to look at the I throw could have been something like this that okay now um this is the I throw here let's Suppose there were two cells like this they were both closed there were two cells like this they were both closed okay two vertical cells just below the I throw both are closed and let's suppose these are the other cells this could have been another possibility right and if you look at these two possibilities here you could come up with a lot of different possibilities which have the same criteria that okay in the first criteria what I'm saying that there is a horizontal cell just below the I row which is closed there could be multiple different ways in which this could have been done like the same grid that we have constructed in the first case could have been different let's suppose this was a complete block here right let's suppose this orange block was there this white block was there and then this green block was there right but what we drew on the first time was something like this this is also one of the possibilities so if you look at the a row you would see that there are so many repetitions like so many different ways in which the same thing could happen that the IUS one row is completely filled with a horizontal block similarly this was the second case that we looked at that okay below the ith Row the IUS one row is filled with two vertical blocks now these vertical blocks could have different lengths like this could have a length of two this could have a length of four or let's suppose the first one had a length of five the second one had a length of one all of these are possibilities right now if you try to understand it here in both of these cases we are closing the blocks right we are closing the blocks just below the I row now it could happen that there are certain blocks which are extending from the IUS throw and going Beyond right for example if let's suppose this is the same grid and let's suppose this is the I throw here you could have a condition that you know there is a block extending like this that okay something like this is going here and let's Suppose there is another block which started from let's suppose here which is going forward forward if you look at the ius1 row here like this is the IUS one row you would realize that the blocks on the I minus row they were not closed on the I row they were just both extended forward right what you could have done instead is that let's suppose you know you could have maybe closed the block here maybe let's suppose you could have closed this block here and you could have allowed the other block to extend forward right this could have been a possibility right that you closed the left block which was coming from the I minus one at row and you allowed the block on the right side to extend forward in this case what would happen in this case the left side of the grid you would have to start another vertical block can I say this yes you would have to start another vertical block from here why will I have to start another vertical block because I have closed the vertical block on the left side that was coming from the IUS one atow and I'm allowing the right side of the grid to extend forward so the left side cannot have a horizontal block it also has to have a vertical block right so now are you able to understand where are we going right let's now try to understand what are the different cases that could you know uh come up from this right so this is the first case that I'm constructing let's suppose this is the entire grid this is the I row on the I minus one row what you have is two cells which are vertical which are trying to extend okay these are two vertical cells which are trying to extend now remember we don't care about where did these blocks start like this left side of the block could have started here and let's suppose the right side of the block could have just started here that is completely fine we don't care about where did they start we are just concerned about that okay they're trying to extend okay so there are two vertical blocks that are trying to extend what can I do with these vertical blocks one of the possibilities is that okay I just close one of them and allow the other one to extend can I do this yes let's try to look at what will happen in this case if I close one of them right let's suppose without loss of generality I close the uh left side of the grid so if I close the left side of the grid this is how it's going to look like I don't care about where it started I have just closed it but the right side of the grid is just going to extend forward now if the right side of the grid is extending forward can I say on the left side of the grid I will have to start a new vertical block to fill this row yes so I will start a new vertical block here right now do one thing and look at the I plus one row here this one isn't this the same type of problem that we're trying to solve that for the I we said that from the I minus one there are two blocks that are trying to extend now for the I plus one we are saying that okay there are two blocks that are trying to extend same thing that happened here right another thing that you could have done in the same case is that instead of closing the left side and extending the right side you could have closed the right side and extended the left side that okay in this case I have allowed the left side of the grid to extend but I have closed the right side of the grid right and similarly if I close the right side of the grid I will have to put another new block which is going to be a vertical block on the right side but now look at the i+ one row here again in both of these cases the i+ vth row looks very similar in both of these cases the I plus oneth row is just concerned about what is trying to extend from the row below it and in both of these cases there are two cells which are trying tot end forward right so what we've seen so far we said that we'll close one of them and we'll extend the other one what we could do instead is that we could either close both of them or extend both of them let's see if we extend both of them this is how it's going to look like that okay both these cells are just extended forward so same for the i+ 1 row they're again going to look very similar see in the first example I said that okay close the left side extend the right side when you do something like this our small block has to be inserted on the left side so for the I plus v row see if you are standing here and if you look below you like just on the I throw you will see that okay there are two cells trying to extend forward in this case also you saw that okay there are two cells trying to extend forward in this case also you saw that there are two cells trying trying to extend forward yes now what happens when you close both of them when you close both of them there are two possibilities that are going to arise from this see one of the possibilities is this that okay I closed both of these two cells here and I inserted two new blocks something like this in this case also if you look at the I plus 1 at row both these cases are going to look alike like the first case and the second case standing on the I plus one row both of them are going to look alike yes can I say this correct so another case that you could do after closing both of them is that now you can insert a horizontal cell remember when can we insert a horizontal cell on the ithow when it is completely closed on the IUS 1ow even if one of the cells is extending forward you cannot put a horizontal cell right so if you close it and you put a horizontal cell this is how it's going to look like so you closed both of them and then you put a vertical cell here yes you put a vertical cell which is allowed to extend forward right so what can I say in this case I allowed extension extension of both in this case in both of these two cases I closed both of them right I closed both of them and I said that now there are two choices either I can put two uh you know vertical cells which are going to extend forward or I can put a horizontal cell which is going to extend forward correct so for this particular case where you have two cells trying to extend from the I minus one row there are five cases that come out of it right so we've seen the case where you know two vertical cells are trying to extend from the I minus1 let's see what happens if a horizontal cell is trying to extend below the iow right look at the cell below it this is how it's going to look like there is going to be a horizontal cell trying to extend forward now again guys it doesn't matter where did they start this horizontal cell could have started here or this horizontal cell could have started here it doesn't matter where is it starting all we care about is that what is trying to extend from the ius1 in this case a horizontal cell is trying to extend from the IUS one right what could you do with this cell you could either close it or extend it right what happens if you close it let's suppose we try to close it here okay let's consider this case when we close it like this is the I thr again you closed this cell so it doesn't matter where it started you closed it now there are two things that you could do here either you could start a new horizontal cell here why because the IUS 1 is completely filled or you could start two vertical cells right so one case is where you start to Vertical Cate suppose like this from the I row another case is where you just close this entire thing and start a horizontal C so this is going to look something like this that you closed this here and then you started a horizontal cell again from here right this is one of the other cases this is now this happened when we closed this horizontal cell which was coming from the I minus one another case is if we just allow this cell to extend right let's suppose this is the I row another case which is very simple is that you just allowed the cell to extend we don't care about where it started we just said that okay we're allowing it to extend okay now understand one thing here guys when you reach the end when you reach the top of the grid that is the place where it doesn't matter how the cells are extending you just going to put a bar here you're just going to close the cells right if you have two vertical cells you will close them if you have a horizontal cell you will again close them right right so let's try to look at the cases in a more compact Manner and let's try to compare both these cases all right so just summarizing this entire thing uh this is how it looks like in the first case this one what I'm saying is that there are two cells two vertical cells which are trying to extend from the IUS one at what are the various possibilities that can happen here first case is where you close the right side of the grid and you extend the left side of the grid okay second case is where you close the left side of the grid and allow the right side of the grid to be extended forward third case is where you extend both of them fourth case is where you close both of them and start another two vertical cells right fifth case is where you close both of them and now start a horizontal cell correct similarly if you look at the second case where we were saying that there's a horizontal cell trying to extend forward there are three cases which come out of it one is where you close the cell and start another horizontal cell second is where you close the cell and start two vertical cells third is where you just extend this horizontal cell right so now if you were to look at this entire thing right we can now think of certain DP States right we could say that okay looking at the I throw we are just concerned about what are the two cases are we having two vertical cells trying to extend forward or do we have just one horizontal cell trying to extend forward so we could say that okay DP of I comma 0 is equal to number of ways to fill the grid from I row to n minus 1th row such that there is a horizontal block trying to extend from the IUS 1th row correct this is what you could say and now think about it what are the various possibilities into which this breaks down two see this is the case that I'm talking about DP of I comma 0 that from the IUS one in row there is a horizontal s trying to extend forward this goes into this particular case this is case one where you say that okay I'm going to close this horizontal cell and I'm going to start another horizontal cell doesn't this look something like DP of I + 1 comma 0 right because on the i+ 1 row now this is going to be the same problem that from the ith row there is a horizontal cell trying to come forward right now similarly you could Define the other state DP of I comma 1 which just means the number number of ways to fill the grid from the ith row to the N minus 1 row such that there is a there are two vertical cells trying to extend from the I minus one right so I'm not going to write it again here you could just you know uh replicate the same thing here and just assume that instead of a horizontal cell trying to extend forward there are two vertical cells trying to extend forward right so this is going to be the entire State what are the transitions how are the transition going to look like we clearly know that okay from the I Row for DP of I comma Z there are three possib ities so what you would do if you want to find out the number of is you would just add up all these possibilities right similarly for I comma 1 there are five possibilities so you would just add up all these five possibilities so let's first of all try to see what happens for this case you know DP of I comma 0 so DP of I comma 0 has three cases right one of them is I + 1 comma 0 another one is I + 1 comma 1 and another one is I + 1 comma uh 0 again because see in 2.1 what is happening in 2.1 we are saying that we closing the horizontal cell we another horizontal cell so for the i+ one row it would just mean that there is a horizontal cell trying to extend forward right for 2.2 look at it we said that we closed it we started two vertical cells so for I plus one at row it would just mean that there are two vertical cells trying to extend forward correct similarly for 2.3 we saw that we just extended the horizontal cell so for the I plus1 it would just mean that there is one horizontal cell trying to extend forward correct so what I can say now is that for transition DP of I comma 0 is nothing but DP of I + 1 comma 0 this is the case I + 1 comma 0 where we just said that close the cell bring another horizontal cell another case is where we said DP of I + 1 comma 1 the second one what is happening here we closed the cell we started two vertical cells another case is again DP of I + 1 comma 0 because we again said that don't close this horizontal cell just extend it Forward got it so this is how it's going to look like for DP of I comma 0 similarly if you were to look at DP of I comma 1 there are these five cases right and four of them are nothing but DP of I + 1A 1 this is DP of I + 1A 1 this is DP of I + 1A 1 same same but this is a different case where you say DP of I + 1a0 right okay so this is going to look something like this that okay you have four times DP of I + 1A 1 plus DP of I + 1A 0 okay this is how the transitions are going to look like all right so these are the transitions now if you look at this equation it looks like a very easy thing to solve right you have the state you have the transitions now it's pretty easy but coming up with this transition was so damn difficult like we had to consider so many different cases right now you will have to look at the base case where is this thing eventually going to end we know for fact that you know if this is the grid When You Reach here when you reach the end what does this mean it could have two cases either there is two vertical cells trying to extend forward and you will say that okay I'm not going to extend you forward I'm just going to close both of you here similarly is the case where you said that there is a horizontal cell trying to extend forward and you would say that okay I will not extend you forward I will just close you here so these are just one possibilities now right so what you would say is that something like DP of n comma 0 is equal to 1 it means that I have reached the end of the grid there are there is a horizontal cell trying to extend forward and similarly DP of n comma 1 is going to be one it means that I've reached the end there are two vertical cells trying to extend forward okay so these are the base cases all right now comes the point how do you decide the final sub problem right where do you really start this problem from so let's look at your state first your state clearly means DP of I comma 0 is the number of ways to fill the grid from the ith row to the N minus oneth row such that there is a horizontal cell trying to extend from below correct but look at the zero throw where you start filling the entire grid is there any cell trying to extend forward no see when you look at this grid here and when you look at the zero throw this one there is nothing trying to extend from here right so you you will have to try out both these possibilities one is the case where you will say that okay I will put a horizontal cell right if you put a horizontal cell what would this mean this would mean that starting from the first row you would have all these possibilities another case that you would consider is this that okay instead of filling the zero throw with a horizontal cell I will fill it with vertical cells Yes again if you look at the first row here there are going to be various possibilities that would arise out of it so can I say on the Zero row I will have to try out both these possibilities right but the actual various possibilities that would come out are going to start from the first row yes because if you look at the state how did we Define the state we said that DP of I comma 0 is the number of ways you can fill the rows from I row to the N minus one row such that there's a horizontal cell trying to extend forward but when you look at the zero row is there anything trying to extend from minus one row no so you will have to try out both these cases starting from the zero row yes so your actual transition will start from the first row so can I say my final sub problem will be DP of 1A 0 which means that starting from the first row here it is not really the first row it is like saying that okay on the Zero row we have put something now start your transitions from the first row right plus DP of 1 comma 1 this is the case where you are on the first row when I say first row it is zero based right so just assume it is actually the second row okay the first case is where you are on the second row and you're saying that there is a horizontal cell trying to extend forward and this second case is where you're saying that there is there are two vertical cells trying to extend forward okay so you would just add up both of these cases and that would be your final sub problem all right now I understand that this is a very difficult problem even if you haven't understood what has been taught so far just watch this recording again you will be able to make sense of every single thing right it might be the case that in the very first go you might not be able to understand but that's expected okay it's not expected from you to come up with the solution on your own or even understand what has been taught in this video in just one as far as the time complexity is concerned the formula is very simple number of states times average transition time right how many states are here we are saying DP of I comma 0 and DP of I comma 1 so I goes from 0 to n and those this the second dimension only has 0 and one yes so I will say the number of states are just 2 into n or order of n right and the average transition time it's very simple this is just a very small equation that we're writing to calculate DP I comma 0 we have two values that need to be added for calculating DP I comma 1 we have another two values that need to be added yes so I can just simply say that okay this is nothing but uh order of one transition time so overall time complexity comes out to be order of n now remember guys this is for a single test case Okay this entire thing that we're doing is for a single test case and remember in the problem statement it was written that we have T Test cases which is going from 1 to 100 so your actual time complexity is not going to be n it it is going to be order of like let me write it here actual time complexity is going to be order of T * n okay that you must understand this is not just order of n it is T * n okay similarly what is going to be the space complexity it is simply going to be number of states number of states are order of yes so let me write it here why am I not writing order of T into n for space complexity why am I not multiplying it with the number of test cases because the space that you would have used in the first test case you don't need it in the second test case you can discard it right and uh similarly uh if you were to look at the space complexity it can still be optimized see the transition equation DP of I comma 0 depends on DP of I + 1a0 and I + 1A 1 so your current rows answer only depend on the answers for the next row correct so do I really need the answers for rows above that no so I can do space optimization here as well in case you don't understand what is space optimization I would highly recommend you to check out our lecture on Space optimization right and you would be able to understand all of this pretty easily all right so let's look at the code for this problem it's a pretty easy code very very small but overall coming up with the idea coming up with all the observations that was actually very difficult right okay so T is the number of test cases that I've taken in the input n is the integer that is given to us for every single test case the you want to construct a grid of n cross2 right like a tower of height n now one thing that I've done here is that you know I've defined my DP table outside like I've have taken it as a global variable if I would have defined it here let's suppose inside every single test case that would have just resulted in me creating the same memory again and again right but what we could do is that we could just create a DP table of 10 to the^ 6 and then use that same table for every single test case right because see if your n is equal to 100 you're only going to need 100 rows out of it if your n is equal to 10^ 5 you're going to need 10 the^ 5 rows out of it why should we create the memory again we can just create it once and then use it for every single test case right because see when you need it for n is equal to 100 you're only going to fill up the 100 rows you're going to get your answer when you're going to need the answer for n is equal to 10 the^ 5 you're going to fill up the 10 the^ 5 rows again so those 100 rows are going to get overwritten with your new test case right so that is why I have defined the DP table outside itself and that will also help you you know save on time every single time if you create some memory location that is going to take more time right right so this these are the states that I had already told you DP of I comma 0 is the number of ways to fill up the grid from I row to the top such that there is a horizontal cell trying to extend forward similarly for DPF I comma 1 number of ways to fill from I thr to the top such that there is there are two vertical cells trying to extend forward these were the base cases we said that okay if you've reached the end if you've crossed the Grid in that case what does it mean it just means that okay whatever Sals trying to extend you will have to close them so DP of n Comm 0 is 1 DP of n comma 1 is one all right so then what do we do we just you know find out the answer for every single DP of I comma 0 and I comma 1 how do we do that we have the transition equation DP of I comma 0 is nothing but 2 * DP of I + 1 comma 0 and 1 times DP of I + 1 comma 1 we take the mod because that is required in the problem statement and similarly we do it for I comma 1 right this transition equation we've already seen correct and the Order of the for Loop should also be very clear that if if DP of I comma 0 depends on DP of I + 1A 0 and I + 1A 1 then the further States need to be calculated first so n is equal to 100 should be calculated before n is equal to 80 probably right so that's what we're doing here and then finally this was the you know final sub problem that we talked about right so if you look at the time complexity it is going to be order of n into T for every single test case we are doing an order of n work right but like I said if you could somehow think of a new DP state where you know you could uh let's suppose pre-compute this outside like this entire for Loop if you could put here and find out the answer for every single n from 0 to 10^ 6 and then every single time a test case is given to you you can find out the answer in order of one by looking at that particular Row's answer right in that case you will have to define a DP State differently so that is going to be a homework for you how do you convert the time complexity from T into n to just t plus n all right that is doable and even this will pass okay even this code that we've written here will pass but if you do it n plus T that is that is going to be much better and let me tell you it is possible so that was it for this video guys uh I hope you all enjoyed this lecture I know there was a lot to learn here there was a lot to grasp in case you have any doubts feel free to mention them in the comment section in case you've understood everything that was taught don't forget to comment understood and yeah I'll see you in the next video where we solve even more challenging [Music] problems