Codeforces Round 1101 (Div 2) | Video Solutions - A to D | by Vikas Soni | TLE Eliminators

[00:00:00]Yes. So hello everyone. My name is Vikas Sunni and uh I welcome you all in this uh post contest discussion of the code forces round 1101 due to. So let's start our discussion.

[00:00:18]So let's see the first question which is convergence.

[00:00:21]So in this question all is inviting her friends to a party to eat cake and each friend may not be at the same place. So so the eyes friend has at position AI and to make everyone at the same place allies has to make a multiple group calls and unfortunately the signal is weak and allies can only call two people at a time and allies doesn't want to her friends to walk too far. So if the uh let's say if C is calling the I friend and the J friend so they both will meet at some integer location between the minimum of this position and maximum of this position inclusive and uh yeah so we have to output the minimum number of group calls she need to make so that every friend of her is at the same position. Uh so let's analyze this question.

[00:01:22]The name of the question is convergence.

[00:01:28]So like first of all we have to see how the operation is happening. So let's assume that uh her friends are like at this position. One friend is like at position one and 2 3 4 sorry 3 4 6 7. Let's say if if one friend is at this position and one friend is at this position.

[00:01:53]Oh now if you are calling two and six you can uh they can move to only like minimum of two and six. Yeah. Which is just two and minimum of sorry maximum of two and six which is six. So, so it means that they both can come to any position within this range 2 to six, right? So, like they can stay here and like he will come here, they both can come to this point, they both can come to this point or but the only thing is like they cannot come outside right outside this range. So, yeah, this is our operation. So now let's assume that like if if there is some position X and everyone has to come at this X how how they are going to come. So assume that the friends are like this.

[00:02:44]Let's say the positions are one. So this is position of her friend 1 2 4 6 8 and 10. And now like they have decided to come at this position position four.

[00:03:02]Okay.

[00:03:04]So now they are how they are going to come. So just see here that like if we choose this both friends six and eight.

[00:03:12]So now you know that like they cannot come to this four. Right? Because if this is six and this is eight they can only go to six, seven or eight position right? So yeah you cannot take the friends which are both have bigger position than the four. This is our target and you cannot similarly not choose the value such that both positions are less than x right you cannot choose this both because like for this two they can only come to one or two they cannot reach four only case is when you take one from the left side and you take someone from the right side right because you take two and eight now they both can come to eight uh four in one operation only yeah so that's what we will do we will choose one person from this side we will choose one person from this side and they will come to this position. We will choose some person from this side and some from this side and they will come to this position. We will choose some person this is same but like there is someone to choose. So we will choose this and let's say someone to this and both will come at this position. So yeah that's it. Only case is like how many operation it will take. So you can say like there were two people here and there are three people here. So this three is bigger value. So there will be at least three operations you have to do right. So yeah in the three operation it will uh yeah everyone will come at the same position because in three operation and from there there are only two people. So like you can choose this two you can choose this two and you can choose these two. So yeah the like whichever side the people are bigger that will be our answer. That's it. So like this side there are three people this side there are two people. So my answer will be three and that's it. Now the only problem is when the like position are same I mean let's say the position are like this.

[00:05:11]Oh and let's say you are here. Okay. Now maybe you can mistakenly you can like think that in left there are five people but there are not five people. This three doesn't need any operation right? This is already at three. So what you can do here is just uh uh I mean you can just have unique uh positions and have the frequency of them. So like what you can do here is you can make the position and their frequency let's say the position is equal to one and its frequency is equal to two. Position is equal to two and it frequency is two. Position is three it frequency is four and yeah like something like this. Right now it is easy to calculate the answer. Okay. So what you will do? you will just iterate on each element. So let's say you are at this position.

[00:05:59]Now you will count how many values are lesser than it and how many values are bigger than it. So in less there are zero value and in bigger there are eight. So answer will be eight. If they all want to come at the position one for this one there are two value and this is this side six. So answer will be six. If they everyone wants to come at this position too and yeah that's how you can iterate at each position and we'll calculate the answer what is the minimum number of operation it takes if they all want to come at this position and that's it and the minimum among them will be our answer. Yeah. So that's it. And like also iteratively you can just count how many values there are in left. Like if you are counting the position here, here the left will be zero. Right? Because there is no value which is less than one. Now when you come at this position, the left will become two. Right? Because this is in its left. You come to this.

[00:06:58]So in the left you will add two, right?

[00:07:00]So now in the left there is four. And when you come at here in the left you will add this four. and we will see this in the code. So that's what you have to do here. Uh let's see the code and you will understand this more. Okay. So first of all we take the input of N and take the array. Now I have make the map. So map will just give me so just here map of I will give me the frequency of I frequency of I. So yeah I will just it on map and like so yeah the data structure we are talking about here like the position and it is position is combined with its frequency that that is done by map that's it initially the answer is let's say pretty some big value and this is less how many values there are less than the current position that's it I iterate on the map uh the frequency of the current element like this is I do second now like there this much less people and now I have to count how many people there are big so like see here let's say I'm at this position okay let me draw this I am at this position in the less there are four people right and the current one at the current position there are four people and the total people are 10 so now how will I just count how many people which have the position strictly greater than four easy I will do total minus less values minus equal values that's it yeah so that's what you have to do here so the number of big values this is n which is total minus less minus current and answer is just a minimum of answer and like maximum of this thing right so like you can have like sorry yeah so the answer is like this partition so I mean answer for this case will be this much and the answer is just minimum among among all position or possible scenarios and yeah after this uh iteration the less uh I have to add the current one in the list right that's it and I just print the answer I hope that was like very easy now let's move to the next question which is problem Yeah, sorry.

[00:09:36]Okay, this is question B.

[00:09:39]So, Alice is preparing cake for her party. However, she is in rush. So, the frosting on the cake is uneven. To quickly solve this issue, Alli will put her knife at some integer height and then sweep the frosting from left to right uh to make the frosting equal.

[00:09:57]And formally like AI is the height of the frosting at the E position. And suppose that allies put her knife at some integer h. So like he will start sweeping the knife from left to right and with having the knife at integer height h. So like if there is at position I the height is greater than h.

[00:10:21]So the excess frosting will be pushed to the next position and from the last last position the excess frosting will be just go out of the cake and now like we we have to answer that if let's allize was only serving the prefix of the cake then what is the maximum height of frosting C can make while keeping the frosting level of all positions same yeah that's so yeah this is kind of confusing to like understand first but we will discuss it no worry and the input uh the number of position till 2 e5 so yeah the length of k is 2 e5 so we have to think something in o of n time complexity or of n login time complexity so Yes.

[00:11:22]Now the name of the question is I guess level frosting cake leveling.

[00:11:30]Sorry it is cake leveling like what does it is trying to say? So let's assume that my take is something like this. So okay, my cake is something like this.

[00:11:57]Now let's assume that if I put my knife at this level. Okay. So I will just keep swipe uh sweeping from the left to right and just see here I come at this point and there is one level of extra cake right. So this extra cake will just come here. So now it is like there is no cake here and the cake is now at this position. Okay I keep sweeping I come here. Uh yeah there is no access kick. I come here. There is no access kick. I come here. Still there is one level of access kick. So that will be pushed here. Right. So now this will be like let me make this more clearly.

[00:12:42]So now this cake will be just pushed here and again I keep shipping. So this cake this one piece of cake will just go out of the cake. So like in the last my cake will become like this.

[00:13:02]That's it. So yeah let's understand this uh with uh the area of position it will be more better. So assume that the height of each kick yeah it is height.

[00:13:17]So let's say height of each kick is something like this two then four 2 5 then 7 and 1. Okay. So assume that you put your knife at height three.

[00:13:36]So first of all you will come at you will come at this position. You will see that hey is there any excess kick?

[00:13:45]There is nothing because the knife is at level three. So nothing will happen. You will come at this place. So there is one level of excess kick. Right? Because I want only height is equal to three.

[00:13:58]Currently height is equal to four. So the extra cake will get pushed to this position. So this thing will become now three and this thing will become two sorry three. Right? So one uh one layer of extra kick is now at this position.

[00:14:13]Then you will come at this position. You will see what is the height of this cake. The height is three right? So yeah nothing will happen. You will come to this position. Height is five. So two levels of extra kick will come here. So now it will be three and this height will be nine. This is again bigger. So how much? Uh 9. So 9 - 3 which is six. Six levels of cake will come here.

[00:14:42]So this will be three now. And this will be how much it seven now. And again extra cake will just go out of the cake.

[00:14:53]So extra layer and uh this will become three. So like in the end my cake is like 2 3 3.

[00:15:02]Yeah, I hope you can just understand what I was trying to say in this example. Right? If there is some extra cake then it will be just move to the next position. That's it. Now what is the actual question? So actual question is like for each prefix you have to think like if this was only the my cake then what is the maximum leveling I can make. So let's take an example and you will understand this properly.

[00:15:27]Assume that uh this is my cake initially uh 4 3 1 and 2. Okay. So now let's so the first thing you will check for i is equal to 1. So this is just like prefix of length one. Prefix of length one.

[00:15:48]So now like you see the prefix of one uh length one. What is the cake? Cake is this right? So now you can see that like this four is like every height is even right because there is only one ele. So for this the maximum frosting height you can make. So the answer will be four. Let's say you want to see the prefix of length two.

[00:16:11]the prefix of length two. So now you will just see this much kick it is four and two. So now you have to think what is the maximum height that you can make and also like each uh such that at each position the height is equal to that much right I mean let's say you want the frosting is equal to four so now my array will be keep same that was before right nothing will happen let's say if you want to make the knife at four right nothing will happen because like they both are not same right I want every element of the array same let's say I put a knife on height three knife on height three so now like this was four two so this will become three and one will be added here and this will become three so yeah you can see that for three uh this is the maximum value and each value is equal right like if I make the knife at a position two again uh this this both will be two two. So yeah you can see that now they are equal for this position also. So yeah you can see that for some smaller values everything will be same and and after some uh height of knife they will not be same right like see here they are not same and we I want the maximum height I can make that's it.

[00:17:47]So how we are going to do that?

[00:17:50]This is our question right?

[00:17:54]So let's analyze this by let's try to solve this question by just like by our hand and then see if we can get any observation here.

[00:18:06]So again let's assume that position is uh 4 3 2 and 5.

[00:18:15]So now like for prefix is equal to one the answer is clear it will be four. Now for this much four and three uh what I can see here is that like okay initially the answer was four. Okay. So like for the prefix this is prefix of length like for this the answer was four. Now for the two a prefix of length two what I can think of?

[00:18:44]So I mean uh I can the first thing I can say for sure that my answer cannot be greater than four right because like even for the lesser position I cannot get the answer greater than four so for this bigger gate the answer cannot be four uh that's that is our first obser first observation that uh that is not going to be so much useful but yeah then it's observation and that's how you should solve the question so like answer for height I will be like nothing just answer for prefix is equal to I prefix is equal to i will always be a greater than or equal to answer is equal to prefix of length i + 1 that's So this is our observation. Okay. But this can be reduced right because now you see here at this point this is only three. So for this cake I mean you have to put the knife at position three. So from this there will be uh cake will come to here and from this also one piece of cake will go outside. So there is I mean you can see here that the answer is equal to three but the excess kick excess kick which is equal to one right the excess cake is of height one so now let's say you come at three you see this array now only right like assume that this we are solving the question from height n is equal to three only so now you will see here like you come here and now You check like can you make the answer for can you make the height for this thing is equal to three and now you will check here that this thing is only two right so how you are going to do that so yeah you can see the excess cake is equal to one right so that's it so like the extra cake which is at this position will sweep and come to this position and you can make the answer is equal to three okay so now like how you can see so Let's assume that like the this is the thing. Okay. So for this one you can make the answer is equal to four and for this position this is one only.

[00:21:13]So now you have to uh you will just like have this uh extra kick from this point to this this position right? How you are going to do this? The thing is that you will do minus one from this thing and this at this position it will be plus4 right?

[00:21:32]I mean the thing is if you try to make let's say the answer is equal to three. So like from this it will become three right? So from this + one will come from this also + one will come. From this also + one will come from this also plus one will come and so this one will become 1 + 4. So this will become five. Right? So that is the thing and like that is the observation. So easily you can just do the binary sets to see like uh like can I make the answer is equal to x you will just do the loop uh and you will find that else what you can do is uh what you can do is like let's say there are n elements right there are n elements and you want to and you have the total sum is equal to let's have it as x let's say like the sum is the variable okay you have this much sum so you know that the maximum value you can make is sum / n right this is the maximum answer you can get like even if you just divide all the position the cake equally then this will be our answer but from the last point and you will see the answer of I minus one I minus one and yeah that's that was just it in this question whatever is the minimum you will just take that point that was just like intuition based question like and that's how I just solve this like yeah and uh let's see the code and you will understand this thing. This is cake level is nothing. I just take the input.

[00:23:31]I just find the I just take the input of the array. The what is the current sum?

[00:23:37]It is I take it here and initially the answer is equal to infinity. It is just pretty big value. I iterate on each element. So like yeah this will just give me the prefix. So now I add the current value and my answer is just minimum of the previous answer or sum divid by so uh this much values are sorry there are this much elements okay so let's say I go on one based indexing I write this and uh before because R is in zero based indexing you have to do this okay so now this much is sum and there are total I elements or I levels sorry I position So yeah this is the maximum answer you can get and from the uh this is the previous answer whichever is minimum it will be our answer and that was it in the question.

[00:24:34]uh now like this was based on the intuition and in case you don't get this intuition you can just easily do the binary search and get the answer that was easy to make the logic but quite hard to implement it for the B uh I suggest you you try the binary search method also okay like I hope that you understand this question and uh from now uh the some good questions will come. Okay. So let's uh see our question C2. Uh the C1 and C2 both are just the same question and uh there is uh no change in the approach.

[00:25:18]So we will just directly solve the C2 question and this was a really nice question. I mean there are so many ways you can solve this question by the binary search or by the 3D way.

[00:25:31]So let's read the question. So Alli's friend have come to the party and now they are lining up to enter the party.

[00:25:39]There are X tables and each table have S seats and each seat can hold one person.

[00:25:46]So introverts so there are three types of personalities. So there are introverts. So introverts will only sit at the empty table. Right? So if they see a table which is non empty they will not sit on that table. Then there are extrovert who have to sit at non- empty table only. So I mean they come in the party and they see if this table is empty they will not sit there. They will find that non empty table and there are ambvers who can sit at any table. They have no choice. I mean they they are the nice person. They can sit anywhere.

[00:26:23]Okay. So initially each sheet is empty and allies was eating cakes and so her friends has formed a line. Okay. So now we cannot change the order of the friend of their coming. So for each person in the line I can choose to assign them a table or just take them out of the party and each person is seated before the next person is assigned a table. So I mean you have to sit the uh you have to select for each person like either you want to assign that seat or you want to kick them then only you will see the next person and yeah you will just see every person in a order that is given and we want to find what is the maximum number of uh friend that can be seated and this is the n number of friend this is number of tables and number of seats.

[00:27:18]everything is still 25. So yeah, you have to again find something in O of N or O of N login and like you you will learn so much from this question because this question is it it's kind of tough to make the greedy strategy. So the name of the question is sitting arrangement is C1 and C2 both the name is sitting arrangement.

[00:27:57]Okay. So let's take some example and uh let's assume that uh in our party we have three tables and each table have three seats. So these are our table.

[00:28:10]These are our table. Okay. Now let's say uh the people come in this order. So let's say the order is like this.

[00:28:22]This is our order.

[00:28:25]Let's say this extrovert will come then introvert will come. Then uh ambro will come then two introverts will come then extrovert will come then one introvert will come. Okay. Yeah. Uh so now first of all the extra word will come.

[00:28:42]Now he will see that is there any non- empty table? Unfortunately every table is empty right? Every table is empty. So there is no way you can assign a seat uh seat to this person. So what you will do is uh you will just keep this person. So for this person you will just keep him.

[00:29:04]Okay. Uh now the introvert will come. Oh sorry this what is you will take this person.

[00:29:15]Now this person will come. Uh there are three tables and everything is empty. So yeah you can just have any table you want. So let's say this introvert is sitting at this table. Right. Also uh in the question it was written that uh okay once the friend is seated they are not allowed to move even if they are not seated according to their personality. What does that mean? So I mean like we have assigned this introvert a position right now uh initially uh its condition was satisfied right he he wanted a empty table and we gave him an empty table.

[00:29:55]Now we can assign uh here the extra words or anything right now he cannot resist uh the thing.

[00:30:04]So yeah that this was the thing. Okay so now uh okay so we are at this position.

[00:30:11]Okay this MB will come. Now this is the main problem of the question because this MB what uh so you can give him a empty table right you can just sit him here or you can just uh put him in the non- empty table like at this position. Now you have to choose between them because like for the introvert it was clear if they have empty table they will just sit elseh you have to kick them out. For the extrovert also it is clear right? If just give me a moment what is the thing like if uh okay just a second.

[00:31:41]Okay. Sorry for the delay. Yeah.

[00:31:48]>> Oh yeah. So I was talking that for the introverts it was clear that if there is an empty table I will just give him empty table else I will kick him out.

[00:31:59]uh then for the extrovert also it it is again clear if there is some empty seat then I will on the non- empty table I will just give him that seat that's it but for the MB words this is the main problem right should you give him a like give him a empty empty table but maybe then like it can be possible that uh then the introvert will come and there are enough tables for the introvert, right?

[00:32:32]Or the another thing that can happen is like uh this thing right let's say here it was introvert and here is that let's say this type of arrangement is there so assume that first introvert come you you sit him here the MB come and you choose to uh have it here at this but now extravert will come and there is no non- empty table right this is fully empty yeah you cannot sit here like here and this is fully fooled so I mean this is full so yeah again there is no seat for the extrovert but if you if you have assigned the uh this non-MP table to the MOT now extrovert has position right he has seat or what what is another case another case is like if here it was introvert right now let's say you give this position now introvert doesn't have any position so at each point you should choose for the MB word right and this is the main core of the problem like for the MB word for the MB word you have two two uh options give him a new table and another opt is uh just assign a seat in some non- empty table in some non- empty table.

[00:34:13]Okay. So like before uh solving this thing let's make this clear right now you have to prove by the like the exchange argument. So this is a very nice topic exchange argument. In case you don't know uh you can search on YouTube there is a I guess one or two hour a very nice video on this I mean like uh how you have to prove is let's say like I write this observation okay that if introvert come if introvert come then there will be only thing if there is a table empty table empty then always assign him that table. Always give him always give him else take him.

[00:35:04]Now like we have to prove this thing right. Why is it every time beneficial that you give him that empty table like maybe there can be some way right that you don't assign him that table and in the next position you get more benefit. So this is the part of exchange arguments. The thing was it you just take some examples and just try that.

[00:35:27]Let's say at this point you just kick him. You don't give him that table. Now is there any way that uh there is a better uh better answer by just kicking him and you will find that it this is true. So there is no better answer you get. So if there is table empty you will always give in. And also the another point was if extravert is there.

[00:35:54]So now if uh if there is a what if there is a non- empty uh if there is if seat at non- empty table non-MP table you will give him that seat always give him you will always give him else you will keep him that's it because there is nothing you can do so yeah this was our observation one right and Now comes the case for the MB word for the MB word and okay so for this thing there are many ways to solve this question.

[00:36:34]Uh one thing is you do the binary search and yeah this was the like binary search approach was the approach that many people solved. Many of my friends also use this approach but there is a better approach which is like very easy to code. It is called the I guess it is called regret greedy approach. Okay. I mean this is regret greedy.

[00:37:01]Maybe the name was something like this.

[00:37:06]The thing was like you if if there are two options right if there are two option A and B and now you have to choose. So you will just greedily give him the option A. Okay. So you choose this option A and like after some time let's say you know that oh I chose the wrong option so you will do regret and like you will come come back here and now you will choose this thing you will cancel out this you choose this that was kind of approach you can uh think in this question right let's say for the MB word maybe you can think like Uh let's say always you give him a uh you give him a non- empty seat. Okay, non- empty seat right and now and uh like after some point okay this this is a brilliant observation just see here let's say this is our table okay uh let's say this is our introvert and so the string is like this now comes the main observation The the question you have to ask yourself is that when when you have to put this MB on the new table if like after that if some extra will come and he don't have position right if that is the case then you will assign the MB here and now there are many seats available right this is the case so you you find this observation and Now what you can do is by default you just give him this position. You can just give him a non- empty position.

[00:39:03]Okay. If if there is no non- empty position then definitely you you have to give him a a new table. But you will definitely give this uh non- empty position.

[00:39:16]And now you come here and now you see that oh there is no empty seat non seat at the non empty table for the extrovert. You do your regret but you see that in the past in the past there was one amb guy and he can sit it to this position right he can get a new table so just get him a new table. So this this was the case. So now you do the regret and you just uh you just undo your move. So now the MB word guy is here and also there is some seat empty right. So one seat empty uh will empty because of this MB guy and the the new table will be unlocked right for the extra.

[00:40:05]So that was our observ that was just our logic and yeah just see this was a pretty easy and you can just solve this question in 5 minutes if you know the this regret greedy kind of technique so okay so what we'll do is let like our logic for MB it will like let's say MB come okay I will just call him MB so you will see is there a non-MP table.

[00:40:35]If there is a non- empty table, if there is some seat at the non- empty table, you will just assign him.

[00:40:44]You will just assign him that. And now you will you will remember, okay, you will remember that at there was a MB word guy. Let's say you will call the MB. Okay? and you will just count how many MB words there are that you can change that uh you can change that seat okay so somewhere you just remember that there was one amb guy that can change the position okay and now let's say at some point okay that's the thing and at some point extrovert came and extrovert came and now he has no seat okay he has no seat seat.

[00:41:28]So then you will call this MB guy. You will call this MB guy that hey you have to change your seat. You have to change your seat. So now that MB guy will get a new table and yeah and then that extrovert this extrovert will also get the seat. So that was the just the logic and yeah this this is just of an approach and this video technique can be useful in many like many harder like questions also.

[00:41:57]Uh and yeah these two these two are the main topics that are used here that one one is the exchange arguments and they are not used that much but to prove the thing right to prove the observation that like if there is a empty table you will always assign the introvert that is always beneficial that can be proved by this exchange argument trick and another thing is the regret DP In case you don't know, you can learn about them in YouTube or the code forces blogs. Regret grey.

[00:42:36]Yeah. So, okay. When you see the code, this thing will be very clear to you.

[00:42:45]So, I just directly wrote the code for the C2 because this also works for C1.

[00:42:51]So, uh let me change this thing.

[00:42:54]So I just take the input of n then this is tables and this much are seed and I take the string str. So this is just the order of the people right now initially the answer is equal to zero. Okay. And now see here how I'm doing the what are the variables showing this should be MB but by mistake in the speed I wrote it as omni what forgive me for this okay so just see here uh how should be the variable speed so I mean what I'm doing is let's say these are the tables I just store how many tables are there and how Any empty seats are there where the extrovert can sit? Okay, where the extrovert can sit? What does that mean? So I mean let's say there is one introvert here. So now these both sheets can be used, right?

[00:43:55]So therefore the empty sheet uh sorry uh this empty seat will be equal to two because there are two seats where the extrovert can come to sit at like this position there should be someone at this right already. So yeah that's it.

[00:44:13]So the tables will give me the number of tables for this introvert. So like initially there are two tables right one is this one and one is this one. And after this introvert sit here the empty seat will become two. This one and this one right. So yeah that's it.

[00:44:31]And this omni just uh is giving me that how many ambate people there there are that can change their decision. That's it. Okay. So I just iterate in the order. Let's see the thing for the introvert first. Okay. So if there is one tab uh table available the t table is greater than zero. So I will assign that table to that interval. So I do tab minus minus the number of empty seat will increase by seat minus one. Why? So like the thing is if the table has three seats the one seat will the introvert will take. So there are three minus one seats available only. Yeah that's it. So I will do empty plus equal to seat minus one and one person is seated. So I will do answer plus. Okay. Now just see what if the MB word guy let's see here. Okay.

[00:45:28]So uh if if what if there are no empty seats for the MB guide to came. Okay. So just see like if the thing is like this uh this table is full and so now we know that for the MB word guy compulsorily he have to come at this position right he have to take a new table he don't have choice so now my mword guy is just like the introvert guy right he have to take a new table so if empty is equal to zero and table is available I take that table MT plus is equal to C minus 1 and I do answer ++ same as what we do in the introvert right assign it a new table else what I will do else I will just do the omni++ which means that there is amb guy who can change it its position okay and I will do the empty minus minus because I am assigning him the empty position right and I do the answer plus so see here what is h happening in this way so assume that assume that there is introvert here and there is ambrovert and there is ambvert here this is something like this and this is i a a n and t okay so uh let's have all of the variable and dry run our code so this is our table then the another variable is empty and another variable is answer okay and yeah also the m word in my case it is only.

[00:47:09]So initially table is equal to there is no empty seat answer is equal to Z and there are no empty word person. Okay.

[00:47:16]Now let me remove this thing.

[00:47:22]So now the introvert person came we check that is there any empty table? Yes there is empty table. So I will give him that empty table. So now the tables I have is only one. I will give this I. So there are also 3 - 1 which is equal to two seats. Right? So these are the two extra seats. So my empty will become two. Now my answer will become one now because this is one person which has seated now. And yeah MD is equal to still zero. Now this my MD person will now check uh can it sit to the empty position? Yes, there is empty position.

[00:48:02]So I will just assume that it is my extrovert guy and I will just assign him this position. Okay. So the MB will just sit here and yeah just like uh the extrovert guy I will just do the empty minus minus because now there is only one seat available. Uh sorry for this and uh answer will become answer plus+ answer will become two right and yeah I will write that there is a 1 mb person that can change the location if you want right yeah that is it now let's say another MB person came I will do the same thing I do the empty is equal to zero answer plus and MB is equal to So after this there is only one table available and no non no seats available at any non- empty table right so no no seats where extrovert can come and answer is equal to three and there are two ambbert people that can change their position if they want to yeah that's it now my extrovert come now is the main point okay so the extrovert people come and he see that oh my god there is no empty seat for it. So what to do? So now allies will do the regret and she will see oh initially there was one MB guy that can change its position. So what I will do just see this I will like I will go to the past I will cancel it from here. I will uh give a seat at this position.

[00:49:47]Now see what happens. So the one thing uh what will happen on the number of tables? So you can see that table will be reduced by one right. So I will do table minus minus.

[00:49:59]What happens to the number of empty seats? So you can see that uh there are s minus one seat added from here and one seat added from here. So total s seat will be added. So s is equal to three here. So now my empty will be three and answer there is no change in answer.

[00:50:16]Okay. So extrovert let's say he has still yet to come and now amb people is now reduced by one. So there is only one ambbert people now he can change its position. This one cannot change its position now because if it change then this extrovert cannot sit here. So yeah only this can change the position now.

[00:50:37]So now this is my okay and now the extrovert come and extrovert will happily sit at any non- empty seat.

[00:50:45]Okay. And yeah then I do the same thing what I do. So that's it in the code.

[00:50:52]So this is so if it is empty compulsorily I have to give him table and that's it. Else I will just remember that there is a one empty but guy that can change its position. I do the empty minus minus because he is seated on the empty seat and I do answer plus. And now comes the main part. Okay. If uh the position is uh the person is extrovert now if if uh there is some empty seat available I will do nothing I will just assign him that empty seat so I do empty minus minus and answer plus that's it else if there is no empty seat left so I will check that hey is there any amb guy that can change its position and I will check that is there any table right because I I also have to check the table right the table should be empty and then I do the so this process is for the omni word guy okay so I do the omni minus minus which mean the mword guy that can change its position is now reduced by one I take the table minus minus and mp plus is equal to se then this is for the extrovert guy okay so this is for the extrovert guy So extrovert guy will just cheat on its sheet. So empty minus minus and I do answer plus close plus close plus close plus close plus close plus close plus close plus close plus close plus close plus that's it. After okay after all this iteration okay this is just yeah after the this thing answer will just give me the maximum people that can sit and that that is the thing I just print here right. So I just do see out answer and yeah just ignore my snippet and the macros.

[00:52:40]So that's it in this C1 and C2 both are the same thing. Also try to like uh solve this thing in a different methods that will be more better for you. I mean try to solve it with the binary research and also like think that like for the 1 MB guy you see how many people coming next and from that already you can currently decide that either to give him a empty table or give him a seat. Yeah try this thing also. Okay. If you have any doubts you can write it in the comment box.

[00:53:16]Else let's move to the B question.

[00:53:21]This was just like a modified version of the of the Hanoi tower thing.

[00:53:29]Okay, so let's just don't read this question. Okay, this was very confusing to see here. Okay, so name is magical tear cake and let's just analyze it here.

[00:53:48]So the name of the question is magical teard cake. I I forgot the spelling of teard.

[00:54:00]Okay. So the thing is that I have a cake. Okay.

[00:54:06]It has nothing. Let's say this is just like the hano tower. We have the three rods. You can assume uh let's use that Hanra tower example.

[00:54:19]Okay. So I have some plates right? I have some plates like this.

[00:54:25]H you know the Hano tower thing. Okay.

[00:54:26]So in case you don't know Honey tower so this is just I have some plates. So also like this plate is smaller than this one. This is smaller than this one. This plate is smaller than this one. So they are put on put in the increasing order of their size. The rules are simple. In one move I can take any plate at the top position and I can move it to any anywhere.

[00:54:52]And the only case is like if let's say there was a very small cake here. Okay. And now this is a bigger one. So I cannot make the bigger plate on a small smaller plate. That is just the rule of Hanoi tower and after some after doing so many operation I just want to move this thing to here right so like I want this this plates to be here and yeah they also should be in the increasing order that's it but now this is slightly modified version so what does it say initially I have the cake like this cake or plates you can say anything Now each uh each plate has a number on it. Let's say the number is like this.

[00:55:41]It is zero. This is zero. This is one.

[00:55:44]And this is three. So what does this mean? So uh just see here. So like in the Hano tower you just can always just move the upper plate, right?

[00:56:00]Always. But in this one you can move any plate. The only rule is that like if you want to move this plate if you want to move this plate then on the top of it on the top of it that should be exactly one uh one plate only. Yeah that's it. So you can see that currently there are two plates right so you cannot move this one but uh for this this plate you can see on the top there are three uh plates here. So you can move this thing to anywhere and all of this thing will be stay here and this will go at anywhere.

[00:56:38]So I mean after this it will become like uh this is one this is zero this is zero and now this plate of size three is come here. Yeah that's that is the thing. So you just take this and put it here. Now you can see that now you cannot change the three because on top of it there are not exactly three plates right? there are zero plates on top of top of it.

[00:57:03]Okay. So yeah and that's how after some operation uh you want all of this cake to be here like this and I just have to print any sequence of operation that do this thing and yeah I have to do like this this is the first plate. Okay I have to output something like this. I have to output yes there will be it will take seven moves and I have to output like this number of plate and I will move it from first to third rod then after that like I will take the second plate I will move it from first to the second rod and uh let's take this see this uh video like so what are the rules so for all of the case all of the plates the rule is there should be only zero plates on top of it right so initially I take this one I take top and okay this is quite fast okay just try to see that and understand this I just one move here and yeah after that I move three to here okay let's write it in our so let's assume that uh initially the test case is like this and for this it is 0 1 and two now I want to move everything. So what I can do like I can just take this I can take this uh plate and I can just move to this one directly right. So after that it will become like uh they all will be removed there is only now it is one and it is zero and the three sorry this third plate is come here. Now also you can see here this need to move this plate this need exactly one plate on above and that is the case. So you will just take this plate and move it here.

[00:58:59]Yeah. So now it will like this. There is one. Remove this thing. And for this plate it needs only zero plates on top of it. That is the case. So you will move this thing. And in only three operation you can do your work. Right?

[00:59:13]Now what if the plates are like this? Let's say there is 0 1 and two. Sorry 0 0 and 0. Now comes a nice question. Right? Because you cannot move this plate. Why? Because it needs only uh on above above of it. There should be only zero plates which is not the case.

[00:59:35]You can also not move this plate. You can actually move this plate. So what we will do is we will move this plate to here.

[00:59:44]So let just remove this plate. And uh now this first plate which is the smallest one is come here. Now uh now this plate can also move right. So this both plates can also move. So I we will just move this plate to here.

[01:00:01]So uh this one will come here. We will take this to here. So this one will come here. So after this the thing will become like this.

[01:00:16]Yeah. It will become like there is a bigger one and there is a smaller one.

[01:00:20]Now I can move this one to this one. I can move the smaller one to here. I can make the bigger one to here and smaller.

[01:00:26]That's it.

[01:00:28]Okay. So this was just like the Hanoi tower thing.

[01:00:32]And right uh you can also see this is the test case both test case we talked about.

[01:00:39]Now uh in case you don't know how we solve the Hanoi tower. First of all this thing is necessary to learn for you to solve this question. So let's see what is the tower.

[01:00:52]So the observation is very simple. What do you or what do you do?

[01:00:57]You just assume that the tower is of length n minus one. Okay.

[01:01:03]So this is like a the amazing fundamental question of the recursion.

[01:01:08]So like what you have to do is in the tower thing. Okay. Now we are talking about Hanoi tower. Uh let's say this is the thing.

[01:01:16]So what I will do is I will assume uh like I have to move this one right. So first of all I will try to move this plate to this one.

[01:01:29]For that I have to remove all of this plates right I have to remove all of this plates. So like I just assume that uh the initially the size plates are only n minus one. So I call some recursive algorithm to move this all plates to here. All plates will move from here. Right? So they will move here. Then I I I take this last piece and come move here.

[01:01:53]Now I have to choose this piece and like okay so what like in the end what the thing is that the biggest one is here now and there are three ones that are here.

[01:02:07]So what happens is that now again like I have to move this one to here. So I just assume that like this is the my initial Hanoi and I have to move it here because after they move here then only I can take this one and move it to here right let's say they are here okay I don't move them so then I cannot I cannot move this smaller this bigger one right also if someone is here then they are the smaller one right so I cannot make the bigger one on the smaller one so they both should compulsory go to here then only I move to Okay. So yeah, this is just my approach. Uh this is just the 100 tower thing. So like I try to move this both here and now I will take this one and move this here. Right now I will just assume that this is only my Hanoi equation. Okay. The Hanoi tower of size two. That's it. So now I have to solve this thing. So I move here, take B here and yeah like I move A to here. I take B to here and then this this one to here.

[01:03:17]Okay. So in case you are not comfortable with the Hanoi tower, you cannot uh uh get the intuition of the this question because this question is kind of tough. So I suggest you that you see some video on the hano tower to get the intuition that why why this hard question can solved in only this three lines of code and this is the main question like that's it. So like uh what I do is I take the first n minus one rods.

[01:03:52]So I move them to the extra rod. This is the extra rod. Then I move the main disc main uh disc to the my target rod and then all of the n minus one rod that are at the extra position I will call the function to move them to the my target rod. That's it. So this like this is the tower of annoying.

[01:04:16]Yeah, I suggest you to see the YouTube video on this. And now let's analyze this over this question like how is this question is changed.

[01:04:26]So let's first uh see the case for when the answer is not possible. This is the thing. So let's try to make when the answer is possible.

[01:04:40]So let's assume that uh my cake is something like this and uh this is zero. This is two. This is two.

[01:04:56]This is three.

[01:04:58]Okay. Now you see this. Okay. Can you move this place? Can you move this cake?

[01:05:03]Yes, you can move this cake. Can you move this cake? You cannot move this cake. Why?

[01:05:10]The problem is here that this cake needs two plate on above it, right? Like to move this plate. There should be at least uh sorry, there should be exactly two plates on above him above it. But there is only one also the thing is you cannot move the bigger plate on top of it. Right? So there is only one smaller plate but it needs two plates.

[01:05:35]You can know you can never move this plate anywhere else. So like in case you can never move this plate. So how you want to like how you are going to make this thing right because for this plate should move this at this point but you cannot move this because it needs two plates but there on above it at maximum there can be only one plate because it is only the smaller one. So yeah this is the thing that on the top of one if there are lesser plates then the answer is not possible that was the thing okay so now what is the maximum value so for the first plate it's value should be exactly zero right because like if this is the smallest plate and if you cannot move it like if if it wants something on top of it Then we want that there should be some plate which is smaller than 8. That is not possible. So yeah this thing should be exactly zero. This thing can be like less than equal to one. Okay. So for this plate it can be either zero or either one. This thing can be either zero either one or either two. This cannot ask for three plates right because on top of it on top of it there are there can be at most two plates only. So yeah you cannot achieve this trip let's see so that this is our condition this is our necessary condition for the when the answer is not possible okay so now you have to okay this is our one observation so yeah let's call this observation one okay so now like you have to see is there any other way or other case when the answer is not possible uh we will see this later But yeah the spoiler the thing is this is our sufficient condition. Now let's try to solve our question.

[01:07:38]Let's assume that the plates are like this one. This is a bigger plate. This is a smaller plate and on above it there is smaller and there is also a smaller plate. This is zero. This is two. This is this let's call it one.

[01:07:56]This is also zero. This is also two and this is zero.

[01:08:01]So now the point is that if this is zero let's let's have it one so that it will be more clear.

[01:08:12]So if this thing is one and we will use the hano approach. So in the hano approach what we have to do we have to move this plate to this position. Right? This is the first thing we have to do to and to move this thing on above of it. There should be exactly one plate. But there are three plates.

[01:08:34]So we have to remove the two plates, right? We have to remove two plates.

[01:08:40]Yeah, that's it.

[01:08:42]Can you do that? Yeah, easily you you can. Okay, let let me in case you don't know Hanoi, let me just assume that there is a magical function. Okay, so there is a magical function Hanoi.

[01:08:56]This will uh this will just move any prefix. Okay, let's assume that you want to move three elements.

[01:09:05]You have to say from where what is the target? I mean where you have to move them and what is the extra thing? Okay, like which is extra ro.

[01:09:17]So this is the number of things to remove. This is just number and Hanoi will do it. Okay, I say you this thing and now you just have to call the Hanoi thing only. How you are going to do this? So first of all you will call the Hanoi to move this two plates here.

[01:09:32]Right? Hanoi will do that itself. You don't have to think about this. So I mean Han did its work and now and now this both two pieces. Oh sorry this both two pieces are at this position 0 and zero. Now you just move uh now you uh take our this last split and move it to the this place. Okay. So this plate is removed.

[01:10:07]Now there is only one plate remain and this is the three. Okay.

[01:10:17]Let's write it more clearly.

[01:10:21]Now what we have to see? So this is so the work for the biggest plate is done.

[01:10:28]Now we have to see for the second biggest plate. Right? But for this thing we need exactly two plates on top of it.

[01:10:37]But to move the three we we move that two plates to anywhere else right. So we have to take them back. We have to take them back.

[01:10:47]Okay. So we can do that and yeah from this you get your observation that why not why not you can do something like this just uh focus on this case. Now let's say make uh what I want to say is let's say this is zero one this is one and this is two what you can do is let's make this zero yeah what you can do there is so first of all you see how many things you have to remove how many things you have to remove so it needs zero and there are three plates so you remove all of these three plates Okay. So what you do is you just call your Hanoi and just tell him that hey these are the three plates. These are the three plates. Just make them just uh uh move them here. Okay. So these three plates are now here. Okay. Just imagine that these three plates are here. So this is the empty one. So you just move it. And now after that what you do is you just take all the uh plates to here.

[01:11:59]So now this plate has moved. Okay. So now uh there are only three plates remaining and there the biggest plate come came to here biggest plate. Now we we see about this plate. What is the case? So you say that he needs only one plate on above it. There are two plates. So you call the and move this one plate to here. So you will just remove this thing.

[01:12:26]And now this one is here. Okay, this one is here. So we take this uh plate and move it here. And after that whatever some uh like whatever thing we moved we take back again. We take them again.

[01:12:45]Right? This is same. So we just take them again.

[01:12:50]And after that we also see like how many I have to remove. I will remove them. I will move my plate and all of the extra stuff I will take them again. Yeah, that is that is the first approach I kind of think and this is like you can say our first observation but okay let's try to code this thing and it you will understand it.

[01:13:15]Let's try to copy this thing and let's try to paste this here. So what I'm trying to say is okay let's just uh ignore this thing the implement this try to implement this on your own okay so what we are doing just see here what we see okay so this is our Hanoi this is the number of plates we have to move okay so this is the number of plates this is the current plate let's write it the from plate from this is the two plate and this is our extra load So I mean like if we want to move this to this. So this this will be from rod.

[01:14:00]This will be our two rod and this is our extra load. Right? Like we can use this as a extras to put the extra stuff here.

[01:14:10]So what I will do I will calculate how many extra thing I have to move. Okay. I I will I will count how many extra uh extra rows I have to move I have to move okay then I what I will do I will call the Hanoi Hanoi I will I will let's say there are X to him okay there are X X plates I will call the Hanoi that hey here hanoi there are X plates there at at this from position and I want them at at this extra position. Okay, I want them to move at this extra rod. So move them to extra rod and and like in case you want something extra, you can use this two rod. Now this is the this is the amazing question. Okay, this like this may be confusing to you. That's why I just suggest you to see the Hanoi some YouTube video on this. Okay, so what is the thing like this is my from This is my two right I want to move them to this extra and this thing initially this is two right but I can use them to extra so let's assume that I want to move so okay let me be slowly assume that my question is I have to move this two rods from this to this and this is my extra so for that I have to move this smaller one. Okay. So let's give them name.

[01:15:53]Okay. Let's give them name. So this is my from, this is my extra and this is my two. Right. But now I will see that I have to move this smaller plate to here.

[01:16:10]Okay. So according to this thing, this will be from like for the smaller plate.

[01:16:16]Okay. this will be two and this will be extra right so yeah that's it so what I say that this is my from I have to move it to the extra right so for the this x pieces the two will be this uh like the target position is this extra position and I say that hey this is the extra stuff okay in case you want to use them you use them now I move the biggest one okay now I move the biggest Then what I do? I just reverse of this thing. Okay. I just take back our extra.

[01:16:52]Okay. So like take back our extra plates. Our extra plates.

[01:17:02]So then whatever I did, I call the reverse of it. I mean I tell the Hanoi that hey Hanoi there were the X plates that we moved. I don't like want them to extra. I want to come to the from position again. So like what is the thing? So there are the this x uh plates are now at this extra road right? I want them to the from road. So I call I uh I call it okay. So this is this is my from this is my to and this is my extra.

[01:17:36]I call the Hanoi that hey Hanoi uh there are some X plates that are at this extra position there are at the extra position I want them at the from position and you can use this two rod as extra rod. Okay. And now you can see that one plate is at its desired position. And now I have to call the hanoi for the n minus one or let's say okay x this was x. So now I have to call the hanoi for only x. No no yeah this is let's say number let's call it total.

[01:18:18]Okay let's call it n. So now there are only n minus one people and I want to move them to the from two extra.

[01:18:28]Sorry from this is two to two extra.

[01:18:31]Okay, like initially this may look very very confusing to you but try to like yeah because this question you have to pause the video and uh analyze this yourself and just see what is the recursive thing just doing okay and like the easiest way to think is like just don't try to think all of the solution okay just think that there is some function that can do any work you you just given and then like what work you have to do to that function Right? This is the thing.

[01:19:04]Okay. So this is the thing.

[01:19:06]This is my function.

[01:19:08]Try to implement this function. Right?

[01:19:12]The only change is this is the extra stuff because in the Hanoi what what happen is that like in the Hanoi thing like what happen is like you want to move them to here.

[01:19:36]Okay. So you take this two you you move it to here. You move this one to this one. Okay. And now you can see right this is like the exactly n minus 2 uh sorry n minus one which is of size two right. So now you call the function for this one. That's it. But now like for this case for our case the thing is we will move some prefix some number of things to here. Then I will move our main point to here.

[01:20:11]And now these are so some plates are at this point some plates are at this point. So I have to take back this plates to here. This is the thing.

[01:20:22]Okay. And this is the approach I used in the contest and there is a problem. There is a problem.

[01:20:34]What is the problem? Like by this approach just try to think and just remember this thing that for Hanoi to solve the n plates it takes like at most 2 to^ n operations right.

[01:20:52]So now also like in our question uh we want our answer to be like like this number of steps can be at most 2 to^ n only right okay I have to transport the cake within 2 to power n moves only but in this approach the moves can be greater than 2^ n that is the problem and now we have to solve this Okay like okay I also assume this like there are n plates okay so the thing is that like I have to solve something okay so thing is that for the hanoi like let's say I am changing n minus one plates okay I am changing n minus one plates then I take back I take back let's say n minus one plates right I mean in the middle I just move the bigger disc.

[01:21:51]Okay. So the thing is like I change the some let's say x plates I move the bigger disc I change the x plates again and now now my answer is of n minus one length of sorry now I have to see for n minus one length only that's it so this this can be of 2^ n this can be of also of 2 power n and this can add and make something like 2 to power 2 to n and this is not the same. Okay, this this can be much bigger than this because like at each thing it can take two steps. Yeah, this this thing is much bigger than thing than this. So we have to optimize this thing.

[01:22:41]And here the only little observation was that okay so only little observation is that like let's say okay also the thing is that uh like n is still 20 only right?

[01:23:01]So in the case of let's say 2 to power 19 and like n is equal to 19 and 2^ 20 when n is 20 2^ 20 like there is a very big difference in this number right so in case you want to optimize for something it will be amazing like because then is very smaller only observation was that was that this thing that if there are This is my disc. Okay.

[01:23:32]Now let's say let's have this bigger disc.

[01:23:37]Now let's say uh to move this bigger disc you only move this smaller two thing. Okay. You only move the smaller two things. So yeah that is okay. Like 2^2 is okay. It is a smaller number and you can also take back or you can also say 2^ n minus 2.

[01:23:58]Right.

[01:23:59]Yeah, this is this thing can be done easily. Okay. So, I mean what we do is we remove this two plates. We we uh move this bigger plate here and this there were the two plates we take back again.

[01:24:13]And now you can see here that we will have the like the ano tower of length three.

[01:24:21]Only case was when you have to move all of the three uh plates. Okay. Let's say uh for this thing it is zero. So now you have to move all of the three things right. So now what we do? We move this thing here. Okay. So let's let's analyze this some properly.

[01:24:46]Okay. So initially there are four plates.

[01:24:51]Now for this bigger plate to move this bigger plate I have to move all of this thing. Right? because on top of it there should be only zero plates. So I move this three plates. I call the Hanoi and Hanoi will work like he will just like ignore this thing. He will just assume that there are only three plates.

[01:25:10]So this is just like the Hanoi equation of three plates and he will just move them. So we just move them here and there is our bigger plate. Okay. So now I will move my bigger plate to here.

[01:25:25]Right. So now I this will be like this.

[01:25:29]There are three plates and that's it.

[01:25:33]Now the point is in my this this case in my this case I am changing the plates and then then I'm taking back again.

[01:25:44]So what we will do is that we will again move all of the three plates all of the three plates to here.

[01:25:52]Right? All of the three plates to here.

[01:25:55]But you can see that hey in this case we don't have to move them right it's like the ready annoying equation of length is equal to three right like if uh if my question was something like this right like if if it is something like this like for so now I have to take back them again but this position is like the readyment case of the tower why I am taking back again I'm moving my case. So that was the only optimization case here we have to apply and that's it in this question.

[01:26:34]This is this was just a smaller obser optimization that you don't take back your prefix uh if uh if you have moved all of the prefix here right I mean if the thing is like this uh you can just assume that this is our from plate And this is our extra plate, right? And this is our two.

[01:27:08]Yeah, that's it. That was just optimization. And like I tried that by intuition and like by that that thinking that uh like this was the case we took the maximum steps right to come back. So I just reduce the steps and that's why I just started this thing. This is very hard to prove the time complexity and why does it always give the I mean always gives the answer in 2 to power n steps but yeah I tried this by intuition let's see the code here so what is the case so initially like I have the answer vector which will just store me the answer the answer is something like this so this is like the first plate and I move it from first to third I mean like if I have to move like uh this plate from here to here so this is one two and three so I will in my answer I will add like this is the first plate I will move it from first to two yeah that's it and like this is our first plate second plate third plate and four fourth plate something like this also this is my cd by the way I I don't have cd Okay. Then I take the input of the n. I take the array.

[01:28:33]So this array just gives me how many number of element that should be above it to so that it can move right. So like initially first plate should have the zero plates above it to move the second plate should also have the zero plates and above it. Yeah. Same for third. I take the input. What is the thing right?

[01:28:58]So like if this is the first plate and like if the value is greater than I then the answer is not possible right as we saw as we discussed here like uh if if uh these are the plates this value can be zero this value can be zero or one which which this value should be less than equal to one right this value should be less than equal to two yeah so that's it I just check If the current value is greater than equal to I then I just print no and return from it. Answer is not possible.

[01:29:34]Else answer is always possible and what I call I call the Hano tower that hey there are n plates you have to move from the first plate you have to move them to the third plate and this is the extra. Okay. And I also give the array as the parameter. This is array. array just stores this thing. Now this is our main function.

[01:30:01]What is this function? So like the current is the number of plates I have to move from to extra. You know what that means? Okay.

[01:30:12]So now if I have to move the one plate, I just move it. So I just move one from and I move it to two. Right? And let this be done. Else I check I check that how many plates are above it. And remember this cur is one based indexing right. So yeah you can see here that the index is like 1, two and three. So for this two you can see that there is only one. For this three there are two plates above it. So for I there are I minus one plates above it.

[01:30:48]Right? Okay. So currently there are this much plates but how many plates I want? I want only this much plates. A of cur minus one.

[01:30:59]Okay. So like the thing is if I want to move the five plates I will try to move fifth plate currently and to move the fifth plate on top of it that should be this much plates. Currently there are this much. So I have to do the total minus the one. So I will get how many elements I plates I have to remove.

[01:31:24]That's it. Right?

[01:31:27]So this is RAM. So now if I don't have to remove anything I don't have to remove anything. What I do I just like I just move my this current plate right. I just move my current plate from end to rod. That's it. Then I I just say that hey find the answer for the car minus one. Else else this is the nice case.

[01:31:53]What I do? So these are the extra RAM.

[01:31:58]These are the extra RAM plates I have to move into I have to move into the extra load.

[01:32:10]Right? Extra load. So that's what I do.

[01:32:13]I call Hanoi that hey Hanoi I have this much plate and they are at this from road I want to have them on the extra road and you can take this two as extra and yeah so now Hanoi will do its work.

[01:32:27]Okay. So after that, so now there are so this this much plates are removed, right? So now I can move the biggest plate which is this current one to from to two. I move them and now I check now I check what now I check for the condition which is the condition. So yeah the condition was like as we discussed here that like if if it wanted zero plates on above it. So I know that I have moved all of the plate I have not taken some prefix right if if it there was some prefix I have to move them back but I have taken full plates. So this is like a ready honey question right? If it was not like if after moving it was something like this is a big plate and there are two smaller plates. So I have to call the function to take the two smaller plates again. Right? So that's what I do. I mean if uh it it did not want zero plates above it. So I just uh have back. So like at here I called Hanoi to move the RAM plates. Right. So I I tell Hanoi that hey Hanoi these are the RAM plates and they are at this extra position take them back to this from position and you can use this as extra right and after that this is like my question of hano of length minus one and all the plates are at from and I have to move it to two and now see here see here okay in case you are still confused see here what are we thinking Like this is like really confusing in the naming.

[01:34:16]For the last time I I'm again explaining this thing. This one zero. These are the two plates. This one zero. So now I move these two plates to here in the extra.

[01:34:28]So this is our from this is our extra and this is our two. So now I move let's write again. This is our from. This is our extra. And this is our two.

[01:34:42]I move this two plates to here.

[01:34:45]And after that I move this plate to here. Right? This is the biggest plate.

[01:34:50]Now I don't have to call back here because this plates are like already a readyment question of Hanoi of length two. So now like they are at this extra point right.

[01:35:02]So like call the Hanoi function and call him like Hanoi.

[01:35:08]There are the two plates or you can say more properly there are the current minus one plate which are at the extra position and I want to move them to two position and yeah you can use this from road the extra extra road right this one should be the from this should be the to I mean where you want where you want this is like where they are and this is just the extra rod. That's it.

[01:35:42]So yeah, that's that's the thing like you can see the code is a pretty smaller one. There are like some just some recursive call but to understand this thing it's kind of confusing. So in case still you have any doubts you can uh write it in the comment box and uh I will I will try to solve your doubts.

[01:36:04]And that what that was it in the question. Okay. So after solving this like I'm just push backing everything into the answer uh this answer vector.

[01:36:14]So after this I just print the size of the answer and I print the this answer array. So that's it in this question. I hope you understand this and uh this was it in the today's discussion. So that was it for now.

[01:36:34]Oh