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

Añadido: 2026-05-23

[00:00:00]Hello everyone, welcome back. So, today we would be discussing the recent Codeforces contest as an educational round round. And I was able to solve ABC till now, so I was making the video right now. Struggling with D's, I would be I'm trying to solve the D. If I would be able to I would add in the solutions part as well.

[00:00:18]So, let's start with the A problem.

[00:00:20]So, A problem was very easy. So, it was given that you are given some an individual key and a group key, and your cost is B dollars.

[00:00:27]Okay, and you need to access the three Okay.

[00:00:30]So, if I explain you the problem statement, the problem statement is saying that you are given with a key uh and keys are A and B. For A, it would be like working as a single unit. It would be working as a single unit and it would be serving as three uh like at most uh three number of students, okay?

[00:00:47]So, what you have to find is you have to find the minimum cost to actually tell that what is the what would be the minimum cost, okay? So, minimum amount you need to provide the online courses for all the N students, okay?

[00:01:01]So, it would be quite easy. So, if Okay, so what if I say you might be thinking that if it's serving three particular students then obviously then I should go for B, but that's not the case. So, you have to take care of a case that if three times of A is less than B. Okay, if we talk about the three students, okay? A, B, and like these are the three students we talk about. So, if we take the keys for them individually, so it would be A plus A plus A. That would have been 3A or there could be a possibility that it could all be combinedly served by B, right? So, if your 3A is already less than B, then can you say that it would be better to choose that A key for each of the students, so it would simply be NA.

[00:01:45]Right? Else, else it would be less than equal to condition. Else, if your B is greater than 3A, then there would be a possibility, then what you would be doing is you would be uh doing B by 3 into Sorry, not B by 3.

[00:02:02]It would be N by 3.

[00:02:05]Like you would be taking the all the possible groups of triplets.

[00:02:09]Right? N plus which would have been minimum of either A into N modulo 3.

[00:02:17]Like let's suppose you are left with two children or one children.

[00:02:20]And then you have to check whether I need to give A keys to that particular students or a single B key to that particular student.

[00:02:28]So this would simply be our simply be our answer if I show you the code as well.

[00:02:34]Let me load the code.

[00:02:37]In the meanwhile the code is loading, let's discuss the next problems as well.

[00:02:48]Yeah, so if we see the code, it's been simply written in the similar fashion.

[00:02:53]If N modulo 3 is then would simply be B.

[00:02:56]And like there I've made up a simple check over here. If it's divisible then it would simply be here. Else it would have been this. And this could be easily omitted because here it would simply be zero. So it would simply be B only.

[00:03:10]So like this is how we actually write this code of this problem.

[00:03:15]Now let's jump to the B problem.

[00:03:17]Okay, so the B problem was quite tricky in terms of understanding the problem statement. So let me first give you the idea of what the problem statement I was saying. Then we'll discuss. Okay.

[00:03:28]So if we talk about B, so what B was telling is that you are given with this particular string. Right? So you are given with the string. And what you have to do is that you need to remove some characters.

[00:03:39]You need to remove some characters.

[00:03:43]Such that remaining string that remaining string is not divisible by four. Right?

[00:03:51]It's not divisible by four.

[00:03:53]And that particular string is known as a beautiful string, right?

[00:03:57]If a string It's already written in the question also. The string is beautiful if it's impossible to select some of the elements and write them out to form a number that is a multiple of four. For example, this is a beautiful because these all are not multiple uh >> [snorts] >> like not divisible by four. And these are not beautiful because if I remove one and three, then four this would easily be divisible by four. For 3 1 2 3, you I would have taken 12 and it would have been divisible by four. So, you need to tell minimum number of elements you need to remove, right?

[00:04:29]Yeah. So, this was actually also an easy problem. Just you need to make cases and you need to take care of few and here and there steps.

[00:04:36]So, if I tell you here in the string you're given with only four type of characters, either 1 2 3 and 4.

[00:04:42]Now, remember the divisibility test of four, right? If I tell you the divisibility test of four, what it says is last two characters should be divisible by four.

[00:04:52]Uh it should simply be 0 0 or last should be divisible by four, right? So, 0 0 cannot be possible because our characters are only 1 2 3 4.

[00:05:01]So, in what case can I say my last characters would be divisible by four?

[00:05:05]If it's a 12 or if it's a 32 or if it's something like 24, right? So, this would all be the possible cases. Or it could simply be the four as well. Like if any if at any moment my uh string could land up to four, then also my string would be divisible by by four.

[00:05:24]So, first thing and foremost, first we have to you would be able to think that let's remove all of the fours, right?

[00:05:29]This is the bare minimum we have to reduce, right?

[00:05:32]Because if any four is left in the string, I could delete all of the characters and this particular string would only be divisible by four, right?

[00:05:41]So, first we'll remove all the fours.

[00:05:43]All fours, right?

[00:05:45]Now, what we have to deal with one three and three two. So from this we actually came to know that if we talk about some I index some I index and which A of I is equals to two where A of I equal to two then if there is any one or three before this two I have to remove that. Right?

[00:06:06]I am don't care about this one and three before after two but if there is before two then I have to actually delete them.

[00:06:13]Right? So if we talk about that some I index if I if I talk about some I index of an array if I talk about some I index of an array where A of I equal to two then can I say after removing like removing all of the fours can I say before this would all be twos only, right? And after this there could be one threes one threes one threes or three ones.

[00:06:39]Right? It was something like this and before this it would something be something like this.

[00:06:44]So this is what you have to actually compute for each I point for each I point you just need to check for the count of what is the count of one three one or three and what is the count of two?

[00:06:58]Whichever is your minimum you'll take that as an answer.

[00:07:03]So let me show you the code as well.

[00:07:06]What I'm trying to say is So this is simply let's count the if I what I've done is I've simply counted how many number of fours are there and how many number of twos are there.

[00:07:17]And my answer would be either what I've done is the answer simply would be either I remove all of the one threes before two or remove all of the twos.

[00:07:26]Whichever would be the minimum I would do that.

[00:07:30]But there would be some cases some cases where this would fail is where you have only one two two one like it's something like this there are no threes. So in that case you have to uh like this would be some kind of an edge case. So, that's why I've come up with this particular logic where for every ith index you need to check that before that there should be no one or three.

[00:07:50]And after that there could be one or three possible.

[00:07:54]So, this is what we have done. For each I what we are checking is what is the count of 1 3s and what is the count of two. Right?

[00:08:02]If your count of 1 3 plus your count after that, like the count of 1 3 over here and the count of remaining twos, that the remaining twos you have is less than your current answer. Current answer could be remove all of the twos. If it's less than that, then just simply update your answer.

[00:08:23]And then the final what you have done is answer plus count of fours.

[00:08:27]So, this is how you would be solving the problem B.

[00:08:32]This was actually an easy problem. Just you need to take care of this particular induction that this could fail at something at this point as well. So, or some of the edge cases here. So, you just need to deal with that.

[00:08:45]So, okay. So, let's discuss the C problem as well. So, C problem was actually also a good problem.

[00:08:50]Uh let's discuss this part.

[00:08:53]So, what the C problem is saying is So, C problem was saying that for some C of I Okay. That C of I is the of CI is the number of cards of type one, C2 of type two, and till CN of type N.

[00:09:08]What you have to do is you have to arrange them in a circular order, like in a circular fashion, such that three consecutive cards, if I take about this particular three consecutive cards, two of them should be same. Any two of them should have been the same value. Right? Let's discuss with the test case as well. So, if we talk about this particular test case, 1 1 1 3.

[00:09:29]So, if I talk about 1 1 1 and 3. So, this is one, this is the value two, this is three, and there is four, four, and four.

[00:09:38]So, what it actually means is what they want to say is so, if you arrange so, what they are saying is if you arrange this particular into some circular permutation, let's suppose we have made this particular permutation. So, if we talk about any set of three three values, right? This, this, or the circular one.

[00:09:57]All have at least two values are same.

[00:10:01]So, this could be other possible length of the Like this could be a one possible pair, right? So, you need to find the maximum number of cards that you can arrange.

[00:10:10]Right? You need to find the count.

[00:10:15]Okay. So, now let's discuss how do we actually solve this problem. Okay.

[00:10:22]Now, if you would have solved this like or give some time on this problem, you would have come up with a simple idea of that if if your count of distinct values like whose value whose it's not one is zero.

[00:10:47]Then, means all are ones kind of I would say. So, in this particular case your answer would simply be zero because you cannot arrange them in such a fashion that it would become a like it would satisfy this particular scenario, right? This particular condition would be failing.

[00:11:06]Right?

[00:11:07]Now, let's see how do we actually like let's now delve deeper into this intuition part of this.

[00:11:15]Okay.

[00:11:17]Let me give you a name. Let me define a weak card and a strong card, okay?

[00:11:22]The weak card is the count whose frequency or count is one. Like whose count is one and here the strong card is whose count is greater than two.

[00:11:30]Like greater than or equal to two. So, like it's greater than equal to two.

[00:11:35]Okay. So, now what we'll be doing is if if I want to place a weak card, if I want to place a weak card, then I would be at least be have been placing a strong card here and a strong card here to make this particular pair as a safe pair. Like this particular triplet as safe. Then only I would be able to say that this particular triplet is safe.

[00:11:59]But, if you zoom it a bit, like if you if you say this is a weak card and here is a strong card. If I talk about this particular triplet, here is a question mark and or this particular triplet here is a question mark. So, here also to make this triplet also safe, do I need a strong card here as well?

[00:12:16]Yes or no? Like I would be needing a strong card here as well.

[00:12:20]Right? So, and this strong card should all should all be of same type. Right?

[00:12:25]Should all be of same type. Then only I would be able to make it a pair.

[00:12:31]Right?

[00:12:32]So, this is what the logic we would be using. So, if if this particular count, like if the count of if the count of strong is equals to zero, then your answer would simply be zero.

[00:12:45]If your count of strong is equals to one, that there is only one type of strong card exist, then your answer would have been simply be like you what you have done is what you would have done is like it would simply be the count by two because it would simply be the total number of possible pairs that you would have been taken.

[00:13:05]Right? Plus the minimum number of plus it uh and let's assume that this particular count uh let's uh there is a count of weak as well. Let me denote it by W. So, so there would have been CW, which would denote the count of weak.

[00:13:26]Right? And C by 2.

[00:13:29]Right? So, this is only we can say, right? So, this was the how many cards that you would be able to arrange. Okay, let's let's take an example as well. So, let's suppose uh Let's take this particular example only.

[00:13:41]Let's take this particular example only.

[00:13:43]Here your uh CW is one and your CS is actually three. Right?

[00:13:48]So, if we talk about how many cards that you can arrange is it would have simply be uh it would not be C only it would be C.

[00:13:58]Right?

[00:13:59]So, here how many cards you would have arrange is C plus the minimum of this particular thing.

[00:14:04]Right? So, here C is three plus the minimum of CW and C by 2. C by 2 is actually one and here also CW is also one so minimum is one and here four. So, this is the four four cards that you can easily arrange.

[00:14:21]I hope you would be able to like able to think what I'm trying to say over here.

[00:14:25]So, like for if you think it a bit like if you have a strong card strong card and a weak card over here then you have a strong so this is a particular I would say a pair or a what we call it as a bracket or something that uh that would exist. Okay?

[00:14:44]Now, let's delve the case when you have multiple multiple strong cards.

[00:14:53]Right? Example, let's suppose you have some fives and some eights.

[00:14:57]Example, let's suppose take this let's take this particular case.

[00:15:01]So, what I'm trying to say is so, let's consider this particular case we have six eights, right? Six eights.

[00:15:09]So, if you would have been you would have played something like this W1 8 8 W2 then 8 and 8. Right?

[00:15:18]And here you would have thought of placing some weak elements W3 and W4.

[00:15:22]But, you cannot place this W3 and W4 over here because before W4 and after W3, there would be some another pairs.

[00:15:30]Let's suppose five is five and five five would be starting. So, in this particular block, if you see or this particular triplet, if you see, or this particular triplet, if you see, that won't be a correct triplet or that the condition would be failing. So, in that case, that your count that you were actually dealing over here, like in when you were finding for this as well, so here your count is actually not giving you the exact picture. So, here your count should have been reduced to two.

[00:15:57]Like to count that how many number of pairs, like how many actually count is being used.

[00:16:02]To like how many cards are actually being used. So, here the count would actually be reduced. So, if I tell you the exact uh equation of how do this particular thing would look like, so if your count is if your S uh what we have defined in this particular thing is your count S. So, if your this particular count S is greater than equal to two, so what you have done is you heard have simply taken the sum.

[00:16:30]Like sum of all of the counts.

[00:16:32]Right?

[00:16:33]Plus the minimum of plus the minimum of uh count weak, comma count weak, comma C minus 2 by 2. Like the summation of all of this. Like it will be the summation of all of this.

[00:16:50]Like whichever would be the minimum, you would be taking that and you would be adding it to the sum. So, this is how your problem C would look like. If I show you the code as well, what I have written is So, here is the code as well. So, if you see, so what I've done is I've maintained a count one and a count two and sum and a capacity.

[00:17:11]So, here count one is the simply count one over here, else it's count two. And the capacity I'm maintaining as well.

[00:17:17]I'm maintaining the capacity as well and the sum is also I'm maintaining.

[00:17:20]So if your count two is simply zero, it would be zero. And if your count two is equal equal to one, it would simply be the sum that the that we have discussed over here.

[00:17:29]This particular C.

[00:17:31]This would simply work as a sum.

[00:17:33]And minimum of count one comma sum by two.

[00:17:37]Else, what would have been? It would be sum plus minimum of count one plus this particular sum. Like this particular with a new sum or you can term it as a capacity as well. So this would act as your new new sum. So that would have been uh used as a new sum over here.

[00:17:51]So this is how you would be solving the C problem.

[00:17:54]I'm sure uh you would be able to uh think about how do we actually solve the C problem.

[00:17:59]And yeah, so that's it. If you like the video, please do share, like, subscribe to the channel, and stay tuned for more such contest-related discussions. Thank you.