Codeforces Round 1099 (Div. 2) | A B C Full Solutions | C++ with Explanation

本站收录: 2026-05-21

[00:00:00]Hello everyone, welcome back to the channel. So, today we would be discussing the next Codeforces contest, which is the Codeforces round 199.

[00:00:08]Uh in this I was able to solve ABC, so let's discuss the problem one by one.

[00:00:14]And guys, uh like there is a small question and surprise at the end of this video. So, please stick till the last of this video.

[00:00:23]Yeah.

[00:00:23]So, let's start. So, if we see the first problem, so the first problem was very easy. Like in this contest, A and B were the very easy problem. C was quite a tough and a challenging problem.

[00:00:33]Uh I was also like taking a lot of time to solve this problem. So, let's discuss with the A. So, A is saying that uh every A of I is between 1 and 2n, and for every element you need to find okay.

[00:00:43]Yeah, it was very easy problem. So, if we discuss it, so what what the problem statement is saying is that what we have is we are having with the given with an array.

[00:00:51]Like we have to make an array, like okay.

[00:00:54]And we are given with the value n.

[00:00:56]Right?

[00:00:57]What we have to do is we have to choose the elements A of I.

[00:01:00]Uh A of 1, uh A of 2, till A of n. We need to output an array such that every pair, which is A of 1, A of 2, uh A of 3, till A of n.

[00:01:14]And A of then we have uh add the adjacent elements. These all kind of pairs should be distinct from each other, right? So, let me give you an example. So, let's suppose n is equals to four. And if we have taken the array as 1, 2, 3, and 4.

[00:01:29]Right? So, if I start making the pairs, it would be 1, 2, 3, 4. Till here it would be distinct. But when I add 1 and 2, it would become 3. So, this 3 is actually matching here. So, like this cannot be the possible combination of the array. So, we need to return some of the combination of an array such that uh this particular question this particular satisfy the condition.

[00:01:48]So, it was very easy. So, in terms of logic if I say, try to think that A of I, if we put A of I as even or odd any of it numbers it if I put a of i as an odd number then adding two odd numbers a of i plus a of i plus one two adding two odd numbers would actually eventually give me an even number right and if they both are distinct then the sum would also even would also be distinct so this is what we would be doing we would be printing all of the elements in one to two n all of the odd elements are taken as an element so if we talk about this particular here so these all would be odd which would be distinct from each other and these all would be even and they would all be distinct from each other and they would all be distinct from themselves as well so this is how you'll be solving this problem so if I show you the code so what I've done is I've taken from one to two n if it's element is odd I'll just print it and so that's the answer so that's how the problem is quite an easy and I would say very easy in terms of >> [snorts] >> okay so now let's jump to the problem b so what the problem b is saying so you are given choose a positive integer k and there's a subsequence okay and we need to do this and we need to make it a non-decreasing okay so problem b was actually was also easy like it was kind of a very greedy kind of a problem so if we say what the problem statement is saying that we are given with an array we are given with this array and from this array we need to choose a subsequence b let's a subsequence is actually you know about the subsequence right we it is a sequence where the elements are being picked in a random order then right not in a contiguous manner that would actually be a substring or a so in this the elements are being picked in a non-contiguous manner so let's suppose we pick this this and this element example of an array and we need to add all of them by k so that we make this particular array as non-decreasing.

[00:03:55]Non-decreasing is that A of I + 1 should be greater than equal to A of I.

[00:04:00]Like this is the case for non-decreasing, okay?

[00:04:04]And uh there is a case that this operation can only be performed once.

[00:04:09]Right?

[00:04:10]So, this could only be performed once.

[00:04:13]So, if we jump to the logic part of it, like how do we actually approach this problem?

[00:04:20]Okay. So, if we see the logic of this logic.

[00:04:25]So, in this problem uh if we have an array right? If we have this particular array and let's suppose uh this particular A of I, if we talk about any A of I, let's suppose this.

[00:04:38]If this A of I if this A of I is actually less than A of I + 1, then do we need to do anything? No, right?

[00:04:47]We don't need to do anything because it would be then following this particular principle and it's already in increasing order. So, we won't be doing anything.

[00:04:55]But if the cases are different, if A of I is actually greater than A of I + 1 then what we would have actually done to make it non make it increasing is sorry, make it non-decreasing or we could say increasing is that we could make this A of I could be minimum equal to A of I + 1, sorry, A of I - 1. Like this could be the minimum least possible value for this to actually reach.

[00:05:20]Right? So, what we would actually be doing is we would be going and find a value K for which A of I - A of I + 1 for which A of I is uh great less than A of I + 1.

[00:05:35]Sorry, A of I is greater than A of I + 1.

[00:05:40]Let me write this. Yeah.

[00:05:42]So, we need will be find for each K and we need go and find for the maximum of this, right? So, we'll go and find for the maximum K which would be possible.

[00:05:54]Right? And out of those all maximum possible case that we have actually reached, what we will be doing is we will be then finding and checking whether the particular K is like working or like fulfilling our conditions or not. So, let me give you the logic as well. So, what we'll actually doing is so we would be uh what we'll be finding is so K would something be like K would something be like max of uh all A of I greater than A of I plus one.

[00:06:32]Right?

[00:06:34]And it would be this.

[00:06:38]Okay. Now, once we have got this the reason to take max is actually uh to uh that that they what if it's a maximum possible gap between two numbers, right?

[00:06:49]If I'm talking about this and this and this is the maximum possible gap, then I need at least this much of K to fill this particular gap, right? To make it non-decreasing, I need at least this much of K. So, that's why I'm taking max over here. Now, we would be using this particular K, right? So, what we'll be using is that if we need at least this K, right? So, we would be checking if the answer could be possible with this K or not. So, what we would actually be checking is that if A of I if A of I is greater than equal to your pre current right?

[00:07:25]If it's already greater than equal to your current, then you will simply update your current. Your current is actually defined as your previous element.

[00:07:34]Current is equals to A of I. Like the maximum previous element that you have achieved right now. If it's less, if it's less, what we will be doing is with the a condition.

[00:07:43]Right? Else if it would be like A of I plus K is greater than equal to the current, then update your current, which is equals to A of I plus K.

[00:07:56]Else, else we would be saying that the case would not be like the possible flag or you take in a flag value would be false instead and you can simply break from here.

[00:08:08]I I hope you would be able you're able to see what I'm trying to tell. That go and find the value of K, the maximum possible value of K, and try to use this particular value and see whether the condition, whether the array that we want to achieve is possible or not. So, let me show you the code as well.

[00:08:26]So, here what I've done is I've gone and check for each of I A of I is greater than A of I plus one and I find the maximum K.

[00:08:33]And for that if K is equals equal to zero, I would know that it would be a already increasing array. So, it would simply be yes.

[00:08:40]Else, what I'm doing is I'm going and checking if current if this particular element is already greater than the current element, then it's actually increasing condition. So, I'll simply update my current.

[00:08:50]Else, what I'll be doing I'll try to update this value with the current with the K value. And if I'll say whether it's fulfilling the condition. If it's fulfilling, then I'll update my current.

[00:09:00]Else, if it's not fulfilling, then I know that my flag should be false and it would simply break from here.

[00:09:06]So, this is how the B problem can solve.

[00:09:09]Now, let's jump to the C problem. So, this is actually a good problem, I would say.

[00:09:15]A much more difficult problem to solve.

[00:09:17]But yeah, sure we would be seeing how we can actually optimize it.

[00:09:23]Like this problem was not a tough in terms of logical part, but in terms of coding part it was bit challenging because I've also faced a runtime error and a TLE as well. And this and actually this TLE actually took me the time to reduce it.

[00:09:39]Right, so uh let's see what the problem is saying.

[00:09:43]Okay. So, the problem is saying that we are choosing an element and we if the element is even, we can divide it by two. If the element is odd, we can increase it by one. Okay. So, what the question was saying that we are given with an array and for each element, if A of I is even, I'll simply do A of I by two.

[00:10:06]And if it's odd, I'll simply do A of I plus one.

[00:10:10]Right.

[00:10:11]And we need to boil down every element such that such that uh this particular uh every element boil down to a same element, right?

[00:10:23]Same element.

[00:10:26]Okay. So, the first thing that actually comes to our mind is DP, right? We could we were always we all thought of that we could use DP in this problem, but DP is not the good solution over here.

[00:10:40]Like in terms of what I thought because you don't know any start value or in don't you don't know any end value. Just you can What you can do is you can assume a start value and find how many steps you can reach a particular value, but that won't be sufficient enough to tell you that how would you be actually uh minimizing the number of operations to reach a particular value. Like how would you be knowing that whether they are reaching at a particular value or not.

[00:11:05]Okay.

[00:11:06]So, what the logic we would be using over here is So, the logic what I'm thinking of is I've taken a A of I, right? And I've tracked this particular path.

[00:11:16]Let's suppose A of I is even right now.

[00:11:18]Let's suppose it it would have been even. Then what I what it had gone to A of I by two.

[00:11:23]It would then it would have gone to A of I by four. Now, let's suppose this particular value becomes odd.

[00:11:29]Right? Then it would have gone to A of I by 4 + 1.

[00:11:34]Now, let's suppose this value is even, then it would still have done by 2.

[00:11:39]Right?

[00:11:40]So, eventually if you see, eventually if you see, this would all comes and boils down to a value either 1 or 2.

[00:11:47]Like it would either come at 1 or either come at 2. And once it has come to either 1 or 2, it would start repeating from here.

[00:11:55]It would start repeating. Like if I tell you, if for 1, it I would simply do + 1, I'll reach 2, and from 2 I'll 1, then it would start repeating over here. Same for 2, 2 to 1, then 1 to again 2, and 2 to 1. So, this would start repeating.

[00:12:09]So, what we can what we can say is that for every A of I, it would eventually reduce to either 1 or 2. Right? So, this is our safe safe case. Like this is actually the This is a safe case safe case in terms of that Here, though I can for sure say that they would be converged at either 1 or 2. Like I I could make them to converge at 1 or 2, and I could count the steps.

[00:12:31]Right? But now the question is a bit challenging in terms of We need to find some larger value some larger value greater than 1 or 2 where the steps are minimum and they all are coinciding at this particular step. Like this particular value. So, now with this you might have come up with the intuition or you got got an intuition what you'd be doing is for each A of I, we would be storing its path. Right? So, you would be storing its path out of out of which path this particular element is going through.

[00:13:03]Right?

[00:13:04]So, once we have actually got a path, so Okay, so what we would actually be doing is we would maintaining a score kind of a map, scoreboard you can say.

[00:13:16]Right? And scoreboard would be having maintaining two particular things.

[00:13:21]So, let me define that. So, first we will be defining a reached count.

[00:13:25]Reached count.

[00:13:27]What does this reach count means?

[00:13:29]That how many numbers how many numbers from array from array visited V.

[00:13:45]Visited a particular value V. Okay, let's suppose a particular value this particular value is defined as V.

[00:13:51]Like right and we will what will we defining is total steps.

[00:13:58]So and this would be telling us uh total operations.

[00:14:03]Not it's not we have. So it would be total operations, total ops to get at V.

[00:14:12]Right? So how many numbers to go for a to like to visit V would actually be we would be checking the count and here is the total number of operations, right?

[00:14:25]Okay, so if we start from a particular value now let's say now let's trace the path.

[00:14:31]Okay, so now let's trace the path.

[00:14:33]Now what we're doing is let's suppose we start at a particular value X.

[00:14:37]So the what the rule actually says is if X is even X is even simply do X by 2 and if X is odd simply do X plus one.

[00:14:49]Right?

[00:14:50]And we would be update this particular operation into our uh hash map or scoreboard kind of a hash map you can maintain. What we will be doing is let's suppose we make a hash map and here we would be uh defining a some kind of a new number. Okay?

[00:15:05]The new number would be this would be actually working as a new number.

[00:15:09]dot count Okay, so this count is actually the frequency.

[00:15:15]That what is the frequency of this particular element. That there could be duplicate elements as well like this particular 10 10 10 10 10 10 and you if you need to compute for all of these 10s, then uh you you you should only calculate for a particular value rather than repeating it because if you start repeating the values, uh it would take a lot more time complexity. So, this why we are using this particular count to avoid the repetition part. So, here it would simply be a frequency, right? And a score of same new number {dot} steps. Like the total steps over here, so I've written the steps over here. It would simply be the frequency, like the total number into the current steps what X has taken.

[00:16:01]Current steps.

[00:16:05]Right? So, and after this after this, what all numbers when you will be iterating this final scoreboard, scoreboard.

[00:16:13]So, you would be only considering those numbers like whose count is actually score uh of like uh numbers.

[00:16:23]Number {dot} count.

[00:16:26]You would only be considering those number whose count is actually reached to N because then only we can say that these all N numbers converge to a particular point, right? If the scoreboard is actually equal to N, then you would uh go and find the minimum steps, like the So, the steps for this would have Let's suppose the steps for uh this particular value, this particular number is 10. And there could be uh more numbers as well which for which the steps could be two, for which the steps could be three. So, we'll take all of those values and we will find the minimum.

[00:16:59]So, this is how you would be uh solving this particular problem.

[00:17:03]So, I hope you able to think uh get the logic of what I'm uh trying to say.

[00:17:09]Uh let me explain you this with an example as well.

[00:17:12]So, let's take an example as 3, 6, and 10. Let's suppose this is an array and your n is equals to 3.

[00:17:23]Right.

[00:17:24]So, what we'll do is let's start with let's make the path for 3.

[00:17:29]So, for 3 it would be going to 4.

[00:17:32]For 4 it would be going to 2 and for 2 it would be going to 1.

[00:17:37]Okay?

[00:17:38]And for this I would have taken zero step.

[00:17:44]For here I've taken one step.

[00:17:46]Here I've taken two steps and here I've taken three steps. So, if we I'll make a scoreboard update scoreboard update kind of scoreboard kind of thing if I maintain a scoreboard over here, so what my scoreboard would look like?

[00:18:02]It would look like 3 4 2 1.

[00:18:08]We could all reach uh by all get count one, right? All get a count equal to one because these all are unique right now.

[00:18:17]Now, let's go for 6.

[00:18:19]Right? For 6 uh we have zero steps.

[00:18:23]For 6 to 3 we have one step. For 3 to 3 to 4 we will reach to from 3 to 4. We would be having two. For two again we would be having three.

[00:18:33]And for one we would be having four.

[00:18:36]Right? And now how would your scoreboard look like?

[00:18:41]Scoreboard would look something like 3 4 2 1.

[00:18:46]So, this all would get count as two because they are repeated and for 6 the count would have been one.

[00:18:54]Count is actually equal to one.

[00:18:56]Right? Now, same will process for 10.

[00:18:58]For 10 I'll go to 5.

[00:19:00]For 5 I'll go to 6, then 3, then 4, then 2, then 1.

[00:19:06]Right?

[00:19:07]So, if I update my scoreboard over here, for 10 and 5 my count would be one.

[00:19:15]Count equal to one.

[00:19:17]For six, the count would be two.

[00:19:20]Count would have been updated to two.

[00:19:22]And for three, four, two, and one, the count would have been updated to three. Now, what are the final checks? Now, here we have computed all of the possible counts, right? We have iterated all of the elements, right? So, what would be the final guess? Um what do you will be iterating over? We'll iterate over all of those elements. And we'll check whose count is equal to one. So, only three, four, two, one count is equal to one.

[00:19:47]So, we'll consider three, four, two, one.

[00:19:49]Right? And what we'll be checking is what is the minimum number of steps for each two reach at three, four, and two or one. Okay? So, at So, if we take at target three, at target if we assume that we want to reach three, so So, from three, like we would from three, what I'll be requiring is zero steps, right?

[00:20:13]From six, how many steps would I be requiring? Like the array was three, six, and 10, right? So, from three to three, how many steps I'll need? Zero.

[00:20:21]For six to three, how many are required?

[00:20:22]One.

[00:20:23]Right? And from 10, how many would I require? I would be requiring three steps. So, here in total there would be four steps.

[00:20:32]Right? So, here in total would be four steps I would be doing.

[00:20:35]Similarly, I will go and check for four.

[00:20:37]Right? For target four, so from three if I have to go, I would be requiring one step.

[00:20:44]From six, I would be requiring two steps. And from 10, I would be requiring four steps. So, here the answer would have been seven.

[00:20:55]Right? And I'll go and check for two as well. For two, I would be requiring two steps for this, three for this, and for 10 I would be needing five. So, there here would be 10 steps. And to reach one, what would be the steps? It would be three for this, four for this, six for this.

[00:21:14]Uh yeah, so and it would I'll add up to 13. So, out of all those steps, whichever is which is the minimum? Four. So, our target would be three. So, we could all reach three and the total minimum operations required would be four. So, if I show you the code as well of what code I've written, like here I face the time complexity because I was using a a normal hash map over the unordered hash map. So, unordered hash map is uh better to reduce the time complexity and so that's why we use that. And also I was using some kind of a set over here to find whether the particular number is being repeated or not. So, to avoid that uh because iterating the set was also taking a bit of a time, like a lot more of time. So, I'm using some kind of a I'll actually maintain the path over here because if you see to reduce 10 raised to power nine, 10 raised to power nine to actually by one using like the two by two by two by two, so it would actually take log in uh time.

[00:22:15]So, that won't like not log in time.

[00:22:20]This would actually reduce to like this would take up very less operations in terms of iterating over the set for each of those elements. So, that's why I've taken the path. So, it would actually roughly falls around 60 operations.

[00:22:35]So, that's why I've taken the path over here and and I'm checking for each of the path.

[00:22:41]And here the same thing I'm using, I'm updating my store as well for each of the value and current is also updating and finally I'm checking if the RC is equal equal to N.

[00:22:50]And for each of them, what is the total number of steps, minimum steps required.

[00:22:54]So, this is how I was able to solve one of those ABC problems.

[00:23:00]So, as I mentioned that there would be a surprise for which I've planned for the end of this video. So, the surprise is that what I'm thinking of is to start a playlist.

[00:23:11]Right? A playlist in terms of a DSA tricks or something which you would be helpful in terms of uh helpful in terms of I would say interview interviews and all of those that I'm being given giving the always much more today.

[00:23:26]So, I would be picking all of those question and in interviews questions so to help you that which questions are being asked, how to make them quickly a two to three minute video for each of the question. So, just let me know whether this would be helpful for you in the comment section and what all questions do you want me to add in that and what all things you want me to cover as well in this YouTube channel. So, I would be covering them uh completely. Like a kind of a playlist or a kind of a series you want from me.

[00:23:54]I would be covering all of this from interview point of view, from DSA point of view. I would be covering all of this. Just let me know in the comment section.

[00:24:00]Uh and also just start solving and do some solve more and more questions. Then only you will be able to solve ABCD.

[00:24:09]Yeah.

[00:24:09]Yeah. So, thank you. Thank you, guys.

[00:24:11]Thank you, everyone.