Codeforces slowrun (1300 Rated) : Episode 1

本站添加: 2026-05-16

[00:00:01]If you have been solving problems on code forces for a while, you must have realized that for some people it is very easy to level up while others keep on learning new stuff but they underperform in contests.

[00:00:16]So what is the difference between people who are able to increase their rating very rapidly by absolving in a particular fashion versus the people who try a lot solve a lot of problem but aren't able to make any progress.

[00:00:37]So one of the reasons behind that which I believe is true is that most people hate ad hoc problems.

[00:00:49]Not just the ad hoc problem but also the constructive problems. Whenever a constructive problem arrives on a code forces round you will see a lot of downwards on the announcement and the editorial blog. But I will not jump into the debate of whether constructive problems are good or bad to solve. But let's talk about these ad hoc problems.

[00:01:12]So for ad hoc problems, most people have this reasoning that uh this problem had so many observations required that uh there is no way that a similar problem can arrive in future.

[00:01:30]So then they decide to skip this ad hoc problem altogether under the assumption that there is nothing to learn from it. And they are right in a sense because ad hoc problems they usually have a setting which will usually never be repeated in your feature contests.

[00:01:50]So that's why they try to solve via tags.

[00:01:55]Now trying to solve via tags is good if you are focusing on the broader tags. So for example, if you are solving problems related to DP and you have applied the DP tag, there is no harm in it because sure sometimes you might not be able to understand when to apply DP and when to apply greedy. But DP is one of the concepts where you have to practice by tax. And even if you do practice by tax once you read the problem it is actually not a big spoiler because even in a contest when you see a problem for the first time you can just assume that it can be solved via DP and if it doesn't lead anywhere then that's all right you tried and that's what matters similarly for trees and for graphs and for bit manipulations. So these are standard topics and of course they need to be practiced topic wise but in an actual setting in an actual contest setting you will see that when D when you have to solve a DP related problem the reduction so if you look at the reduction from the ad hoc problem to DP that is an area which very few people focus on.

[00:03:29]But if you look at the top competitive programmers and not just the top right even if you look at uh intermediate level competitive programmer they have solved a lot of ad hoc problems. And by the way let's not be con let's not confuse ad hoc problem with the ad hoc problem does doesn't just mean that the entire problem is ad hoc. It means that you have a problem and there are certain observations required like let's say this is observation one this is observation two this is observation three and after doing all of these observations you will reach a known state wherein you can apply DP or bit manipulation or graphs so that's why I believe that ad hoc problems are very important to solve And one of the reasons being is that whatever topic wise things that you are trying to learn that we you can only apply those if you try to reduce the problem from the ad hoc tag to a known tag that you have practiced.

[00:04:46]That is one of the reason. And the second reason is like why you should solve more ad hoc problems. And by ad hoc I means problems without tags.

[00:04:57]is that in a contest setting suppose you are attempting problem C or problem D in a diff round let's say in a contest setting you actually do not know what kind of technique you have to apply to it so in that case it becomes very crucial that you understand the premises of the problem and then try to come up with some observations yourself like I said that you need a lot of observations to actually excel in competitive programming and I don't know maybe this might be a controversial opinion but I believe that if you are good at observation related problems you will grow very fast on code forces code chef at coder any competitive programming problem now at first it might look like the ad hoc problems there is no way to improve upon the skills for ad hoc problems because like I said that this setting of a particular problem might never be repeated in the next contest.

[00:06:09]So that's why a lot of beginners find it very confusing on what to practice, what to what not to practice. But my opinion is that for ad hoc problems it is actually possible to improve upon ad hoc problems and improve your observation skills.

[00:06:29]By that I mean that sure the first 100 or or the first 200 problems that you solve in those 200 problems you might not be able to infer that observation that is hidden in the problem which the editorial talks about. So editorial might say something like it is clear that you have to do XYZ or it is clear that we should pick a certain subset.

[00:06:57]But then you might wonder how did they even arrive at this conclusion.

[00:07:03]So to to improve upon that part of that competitive programming wherein you can see any random problem and you still have the confidence to at least try something with it.

[00:07:18]So that is why we need to solve a lot of problems with a lot of ideas that might or might not work. But even if it doesn't work, we will look at the editorial. We will look at other people's solution. We will look at some hints and then we'll see what are the observations that we have missed.

[00:07:42]But in order to really really benefit from this, you have to stop being afraid or if you have to stop hating on ad hoc problems or problems that require a lot of observations.

[00:07:58]So once you have made peace with the fact that you have to get good at observation related related problem then I am pretty sure that on diff two round you can easily solve problem A to D and not sure what rating range it would put you in but it should still be a decent rating range if that's what matters to you but the main idea is that you have to get out of your comfort zone and start solving problems without tags and start with the easy ones. I'm not telling you to start with the harder ones.

[00:08:38]So, it's if you think about it, it's just like going to the gym. So, if you're going to the gym and you are working out, but at the end of the day, if you do not feel tired or if your muscles are not actually sore, in that case, you aren't actually putting in that much effort. you are not pushing yourself, you are not stepping out of the comfort zone and if that is the case then of course the next time you see a problem on a code forces round you will not be able to solve it.

[00:09:10]So that's why I'm I am trying to add some videos on my channel. Now I cannot promise that I'll be consistent with it but this is just an experimental series that I'm trying out on my channel. the previous series that I tried that was the brain gym series. Uh unfortunately that did not get a lot of traction maybe maybe we don't have the correct audience at this stage.

[00:09:37]So I might continue that series. I'm not discontinuing it as of now. But in the meanwhile I'm also trying to start a new series on my channel which is the code forces slow run. Now in this series I will pick any problem depending upon which edition of the slow run we are uh watching.

[00:10:01]So the in this video the slow run edition is for the 1300 rated problems.

[00:10:08]So I just pick a random 1300 rated problem and I have not seen this problem before nor I have seen the editorial or the solution for it. uh not even the problem statement. So I will try to walk you through my thought process and just a fair warning that since I have not solved this problem before recording the video, it is possible that I might end up taking a lot of time to solve it or end up taking a lot of time to debug it.

[00:10:42]But uh even in that case even if I'm not able to solve I will at least try to read the editorial in this video only so that you can see how to read the how to read the editorial how to read other people's submission but uh yes so just a disclaimer that I'm not very good at competitive programming in fact I can hardly solve B as you might have seen in my previous videos But uh still I'm just creating these videos just for fun. I am not claiming that uh uh watching me quote through these code forces problem might help you. But if it helps you well and good and if you have any suggestions do let me know in the comment section and I might try to incorporate them in future videos. So right now the first episode is for the 1300 series 1300 rated problem. So in this problem, let's look at this problem which is for a diff to round and it appeared at position C.

[00:11:48]It is rated 1300 on code forces.

[00:11:52]So this is the problem statement.

[00:11:54]Let us read the problem statement together. So it says that you have n coins with these denominations a1 up to a n and you also have a natural number k. Okay. So, and then you also have a bag which is initially empty where you can place coins. You need to perform exactly K operations.

[00:12:21]Let's keep this in mind. And in each action, you can take one coin from those you have left and put it in your bag.

[00:12:31]After that, you can no longer take that coin. So, okay. It is saying that you have an array and it contains several coins even up till n and you have to do n rounds of a certain game where you have a bag and in every round you can pick one element from here and insert it into this bag and you have to do it exactly k times.

[00:13:05]Okay, fair enough.

[00:13:07]Then at the same time, you have a cat that loves even numbers. Okay, so we are dealing with even numbers.

[00:13:16]So every time the sum of the denominations of the coins in your bag, so sum of the denomination of the coins in your bag becomes even, your cat empties the bag. Okay, so this means that all the coins vanish if the sum is zero. sum if the sum is even. So let's write that down. If the sum is even meaning it takes all the coins to a place known only to it and the bag is empty again. Note that the bag is emptied every time the sum becomes even during the process of adding the coins and not just the very last moment. Okay.

[00:14:02]So this means that every time the sum becomes even the all the coins inside the box will vanish.

[00:14:14]Now what do they want us to find? So let your score be the sum of the denominations of the coins in the bag.

[00:14:22]Your task is to perform k actions such that your final score is maximized.

[00:14:30]So this means that when we are plucking things from this array and inserting it into this bag, we have to make sure that the final sum is maximized. And if any intermediate step achieves an even number of coins then all the coins that you have placed into the box so far that will vanish and the constraints are up to 10 ^ 9 for the AI values and 10 ^ 5 for n. So this means that they expect an O of N login solution.

[00:15:16]So how do we approach this? So first of all, let's make sure that we understand the the problem without looking at the problem statement anymore.

[00:15:27]So you have to make sure that this problem statement gets embedded in your brain so that uh you can freely think about how to approach it.

[00:15:39]So you have this array and the problem is basically saying you every round you pick one element and you place it over here and you have to ensure that this sum is maximized at the end. So you have to maximize But if if the sum is even then it vanishes.

[00:16:26]Entire thing vanishes.

[00:16:34]Now what all can we infer? So even before doing any brainstorming first of all you can say that all the AIS are up till 10 ^ 9 but then their ordering does not matter. So then if that is the case we can actually sort all the elements and maybe this sorted order might help us visualize things better.

[00:16:57]So let's write the first observation.

[00:17:00]Ordering does not matter.

[00:17:04]Sort all the elements. This might or might not help us but doesn't hurt to sort all the elements. What is the second observation that we can make?

[00:17:16]So if so you can see that since you are transferring some coins from here to here.

[00:17:25]You are transferring some coin but you want your final result to be as big as possible. Right? You have to maximize the sum.

[00:17:40]Right?

[00:17:41]So this means that if you're putting in all the effort of smartly selecting all the coins and placing it over here then you would not want your efforts to go in vain. So you don't want to waste your efforts. So this means that you have to avoid this condition anyhow because if you don't avoid this condition then what would happen is that you did a lot of efforts over here and then things vanished. So basically you said that these were my best candidates but then you removed it altogether. They didn't really contribute anything.

[00:18:24]So basis on that we can write another observation.

[00:18:38]So the second observation is that try not to lose coins.

[00:18:45]But how can this be possible like how can we ensure that uh the coins are not lost?

[00:18:53]So this means let's start let's start with a small case.

[00:19:08]So if you want to put anything over here let's assume that the first element is X.

[00:19:16]Now what can you say about the parity of X? If this first element itself is even, if the first element is even, then as soon as you place it over here, it will vanish. So this means that you just lost X. So why would you want to lose something?

[00:19:40]Because you have to maximize the sum at the end. So one thing is clear that at the start you have to place an odd element. So that is another observation that we have come up with.

[00:19:54]So we say start with an odd element.

[00:20:07]Okay, that's fair. Now suppose you have placed an odd element inside this box.

[00:20:16]What about the second element?

[00:20:19]Now you can see that if you place a second element which is odd then this sum would become odd plus odd which is even means all of your work would be wasted and entire thing would be lost. So this gives us the hint that you have to place an odd element first and the second element should be even in order for you to not waste your efforts that you did.

[00:20:51]What about the third element?

[00:20:54]Should it be odd or should it be even?

[00:20:57]So you can see if you place odd over here then again odd plus odd will give you even and even plus even will give you even. So all your effort in vain.

[00:21:12]So now a pattern emerges just by doing these observations that your ideal split should be something like odd, even even and so on.

[00:21:33]Because there cannot be two odd elements.

[00:21:38]Because if there are two odd elements then suppose the first odd element entered here second odd element entered over here. So by the time the second odd element entered all this entire thing would be deleted.

[00:21:54]So there cannot be more than one odd element. Why can't there be three odd elements? Because you can argue that sum of three odd elements is also odd.

[00:22:05]So why is this true? It is true because the problem statement clearly mentioned that you have to make sure that the bag is empty every time the sum becomes even not just at the last. So one thing is for sure that you can only have a single odd elements and then multiple even elements.

[00:22:27]Now which odd element should you pick from the array? So of course you want to pick the biggest element.

[00:22:36]So this is also another observations that we have made. So let's write that down.

[00:22:42]Place the biggest odd element at the start.

[00:22:50]But then you also have to place k minus one even elements.

[00:23:00]Which k minus one elements would you pick? of course the maximum because there is no other restriction. So the first element should be as big as possible. Second element should also be as big as possible and so on. So this is another observation that we had made.

[00:23:18]You say place k minus one even elements k minus one large largest elements on the even side.

[00:23:33]So these are some of the observation.

[00:23:37]But now at this point most of the people would start coding this implementation right because the strategy looks clear.

[00:23:44]But this is the point where you have to stop and ask yourself are we missing any corner cases?

[00:23:52]Because one of the corner cases that people usually miss is the duplicates.

[00:23:58]So we have to see are we missing any corner case.

[00:24:09]Now if you have this pattern, if you have this pattern then if you have at least one odd element then you are good.

[00:24:25]So if you have at least one odd elements you can place it over there.

[00:24:35]So odd count number of odd elements if it is at least one right and number of even elements if it is at least k minus one then you are good this formula applies but then there could be a scenario where there is no odd element in the array at odd.

[00:25:05]So if there is no odd element in the array then it means that all the elements are even.

[00:25:14]But if all of them are even now you can see that as soon as you add one element it will vanish. As soon as you add the second element it will vanish. Add the third element it will vanish and so on.

[00:25:29]So then you can see that you have made another observation which is place uh which is if if all elements if no odd element exists exists answer is zero.

[00:25:57]Okay. So now we can assume that once we say this statement that if there are no odd element answer is zero. Then after this statement you can assume that there will be at least one element and at least one element is the only thing that we need over here.

[00:26:18]But then what if there are not enough even elements? So what if the count of even elements count of even elements is strictly less than k minus one.

[00:26:36]So if this is the case then you will realize that it is not possible to place all of these even elements over here.

[00:26:50]Now of course you cannot place less than k elements right you have to place exactly k elements that is what the problem said so let's wonder about how to hand so we have already handled this case that if there is an odd or not so if there is an odd element if there are no odd elements then you are good and if there is at least one element then you have to worry about whether the count of even is greater than k minus one or less than k minus 1. If it is greater then this strategy that we have just discussed this should work even though this is a greedy strategy but the proof looks optimal.

[00:27:37]So now suppose that you have at least one odd element. This is the odd element and this time you don't have enough even elements on the right hand side to cover up for the k minus one. So ideally these should have been k minus one in count and that is your ideal scenario that you want. But it is possible that the number of even elements is less than k minus one. But somebody has to fill this k minus one slots because one slot is filled by this odd element. So the remaining slot should be filled by other elements be it even or be it odd. So let's compute how much the red elements are how much the even elements are missing. So let's define delta as. So we want ideally to be k minus one but then we only got this many even elements and remember that we always want to want to take as many even elements as possible because these are the ones that contribute to the answer.

[00:28:48]So this means that this delta this is basically saying that there was this delta gap that is missed. So somebody has to fill it. Now of course you won't fill it with an odd element because as soon as you insert one odd element over here everything will collapse everything will vanish. So it's no point in adding an odd element there. So of course we will add odd elements to the left hand side.

[00:29:17]Now you can see that on the left hand side if you add odd elements in pair like let's say x or let's say odd comma odd then you see that these pairs collapses right and if these pairs collapse then this entire thing would be your answer and we had already concluded that the answer can only be of the form odd followed by a series of events.

[00:29:46]because you cannot have two odds. So this means you have to start your sequence at odd and collapse everything in between. So this means that if delta is even if this delta is even then all the odd elements can be paired.

[00:30:06]Odd elements can be paired.

[00:30:18]But what about the case when delta is odd? This means that you have one odd element over here.

[00:30:28]You have this many even elements over here.

[00:30:34]And you need delta is equal to k minus one minus number of even.

[00:30:43]Now you can see that you can only place the odd elements on the left hand side.

[00:30:48]Why? Because you don't even have even elements. Otherwise you would have placed it on the right hand side and even if you did place an even element it wouldn't have mattered because uh it will vanish because if the overall parity is even then adding even doesn't really change anything. So it will just vanish. So this means that delta is odd.

[00:31:12]Right? This case is very bad for us.

[00:31:15]Delta is odd. We have to avoid this case.

[00:31:19]So how can we avoid it? So we know that if delta is even then we are good. All we have to do is place all the odd elements in pairs and then they will cancel out once they reach over here and then you only have odd and all the even elements. But in order for you to make the delta as odd you what you have to do is you will have to sacrifice one of these even elements. So suppose this is the even element first even element you sacrifice it.

[00:31:52]So once you sacrifice the smallest even element then you see that delta denoted the gap to reach K. Right? So this means this delta has increased to delta + one meaning it has become even meaning you can now pair up all the odd elements together.

[00:32:13]But then you also have to keep in mind that if you are sacrificing this even if you're sacrificing this even element then you should have enough odd elements to pair it again. So what I mean is so this is the odd element these are the even elements and these everything in here will be odd so that they will cancel out. But you see that you have already utilized one odd element. So this is the total number of odd elements that you had.

[00:32:58]You utilized this and you also utilized so delta was odd.

[00:33:06]So delta is odd.

[00:33:09]This means that you have placed in this manner odd comma odd and up till delta* right delta by two times. So basically you have sacri you have already used up delta minus one odd elements right and that is why only one slot is remaining over here and if you insert an odd element then the entire answer would become zero. So if you can create another slot over here something like this. If you can create another slot then you can see that you can pair up the last remaining odd element with another odd element and then it would become zero. So how many odd elements have we already used? This much we have already used on the left hand. So this is the total. This is what we used on the left hand side. This is what we used in the middle for this central element.

[00:34:05]So this is the remaining odd elements.

[00:34:08]So this remaining element this has to be at least two, right? It has to be greater than or equal to two.

[00:34:18]Why? Because if you are sacrificing this even element over here, if you're sacrificing this, then it means that this element should have a odd partner, right? But what if this was the last element standing? This means that what if you are dealing with this case? This is the odd and there are exactly delta odd elements in the array. Delta odd elements in the array. In that case, the answer would be no because even after in that case the answer would be zero because even after your sacrifice of the smallest even element, this element cannot be paired. This means that since there are odd elements, so you have and you have to take all the elements in your array. In that case you have to make the sum will go to zero. There is nothing that you can do about it.

[00:35:09]So now we have our final final algorithm. So uh let's quick let's quickly discuss what all we have observed so far. Right? So the first thing that we discussed is that in problems like these the ordering does not matter. So we are free to sort all the elements and then of course we'll do a greedy strategy and we try not to lose any of the coins.

[00:35:34]Then we saw that there is no point in starting with an even element because that that is a waste of time. And then you always place the biggest odd element at the start so that uh you can have a series of even elements. So after that you place k minus one largest even elements and if there is no odd element then of course the answer is zero and if there is no even element if there is no even element then the answer would depend upon the parity of k. So now you can assume that there is at least one odd element then you follow that same strategy. You place big biggest odd over here and you place all the k minus one smallest even over here. If they fit good otherwise if they don't fit this is the delta right k minus one minus the count of events that you have placed. So k means total thing that you want to total length but one is for this odd element and number of even is for the even elements that you have placed. So this delta needs to come from the left hand side and who can fill this delta the odd elements. So if the delta is even then you are good. you place all the odd elements and uh if your delta is odd then you try to make this delta as even. How? By sacrificing one even element from here creating another slot on the left hand side and letting it be paired with an odd element. So now now that we have our algorithm let's try to implement it.

[00:37:09][snorts] So yeah, so this is the solution for this problem. uh I'm not uh doing a live coding for this. I I actually paused the video in between to implement the idea and submit it on code forces. But if for future problems you want me to write the code live do let me know uh whatever works for you and I'll follow the same.

[00:37:59]So here you can see first of all we take all the elements in the input and we segregate them based on whether they are even or odd.

[00:38:13]Then we sort all of these and we convert it to a prefix thumb because we want to get the subarray sum in O of one. Right? We we wanted a suffix thumb for the even elements. So that's why we sort it.

[00:38:32]Then you can see that.

[00:38:50]Yeah. Then then you can see that we have defined the prefix sum function to get the subar sum in O of one and then you have to do some case analysis. Now some of you might not like this case analysis but again like if you want to improve in competitive programming you have to become comfortable with these kind of problems as well. So you try to find the answer for each k.

[00:39:20]And of course if if the o if there are only even elements the answer would be zero. But if there are if there are only odd elements then depending upon the parity. If if you need odd number of elements then your answer would be the largest odd element otherwise it would be zero. Then you compute your delta.

[00:39:43]Delta meaning how much slots are remaining. So you wanted K slots. This is used by the odd element, largest odd element and this is used by all the even elements that you have placed. So if delta is less than or equal to zero, this signifies that you have more than enough even elements which is also good.

[00:40:02]You only care about having k minus one even elements, right? So then you get the suffix sum and once you get the suffix sum you add the largest odd element otherwise you can assume that the delta is greater than zero. So if the delta is greater than zero.

[00:40:34]Yeah. So you can see on the screen if the delta is even then we are good nothing to be done because all the odd elements can be paired up by themselves before the biggest uh odd element arrives.

[00:40:49]But if the delta is even now you want to make it if the delta is odd now you want to make it even. How do you do that? You sacrifice one element and then you check if the element that you just sacrificed and the lone odd element that is remaining can it be paired up. How can it be paired up? You see how many total odd elements that you had and then you see that you have already placed delta minus one. Why delta minus one? Because you have reserved one odd element to pair it with something else. Right? And why this minus one? This is because you have already used up one odd element as the maxima over here. So this is the remaining elements in the array. But if this remaining is not at least two then pairing cannot happen.

[00:41:40]Right? Because if you only have one odd element then no point in sacrificing that even value because the entire sum would be zero. So if this is not possible then answer is zero. But if you have at least two copy then you can see that that sacrifice was helpful. So you sacrificed that element and then you got your answer.

[00:42:01]So in this manner you you can see that with prefix sum we were able to solve it in O of N login sorry O of N per query which is good enough. Now one common complaint that I see in these kind of problems is people say that there are a lot of case work involved and so on. So I think uh it's not that much case work because you see that even though you see a lot of if else delta modulo 2 and whatn not but if you draw it on a whiteboard or your copy then you can realize that it's actually not that difficult like handling case work is not that difficult as long as you have clear cut picture of uh like what you are trying to achieve. So make sure that you have clear definition of what a delta is and what are the observations that you have made so far. So that's it for the video. Now if you have any feedback for me uh for this series and if you want me to continue the series do let me know in the comment section. I'll try my best to upload some video although I cannot guarantee anything. I'm just testing out this format. Let's see how it goes. And uh also regarding the coding aspect do let me know if you want me to do a live coding or uh do you want me to just walk you through the code just that I just did in this video. So the problem that we just discussed that is of course 1300 rated because this is the 1300 rated edition for code forces slow run and I will link this problem in the YouTube description. Do check it out. Thank you.