Codeforces Round 1095 Solution | ABCDE

Ajouté : 2026-04-29

[00:00:23]I'm live now and confirm So overall in the contest I was able to solve a b c and e was a bit tricky. The editorial is out. So I went ahead and editorial of the how to solve. I think able to e as for a bit more discuss I have enjoyed it video would be available as a v on my channel also consider So this area let's wait for a couple of minutes for more folks to like people in the chat like how many guys problems were you guys able to solve that will give fair set of idea of where most people are where we can move a bit faster.

[00:02:21]Hey, hi.

[00:02:33]Let's get started now.

[00:02:43]So the first problem says you are given an array a a1 up to a n. You wish to make array empty by performing the following operations as many number of times. Select any sequence of indexes.

[00:02:56]The element should be in increasing order.

[00:03:00]remove the elements from the array and the cost of this operation is equal to the product of all the numbers you have chosen the minimum total cost required to remove all the elements from the array A note that total cost is equal to sum of cost for all the operation actually it also says that as the answer can be very large reported modulus 76 some given number so this is where we are let's first try to analy Let's try to explore some of the elements. What are the causes?

[00:04:09]or actually like samples can actually be a good hint as well.

[00:04:13]So like we have let's say we have few numbers like let's analyze what is the cost if you choose all of the elements right now cost would be 2 into 3 into 1 into 4 which is around 24 like one initive idea is like what's the other way to look at it? Can we just keep all the elements separately and try to count cost for them?

[00:04:51]Like let's say if you choose this in the first operation, this in the second operation.

[00:05:02]For example, let's just choose only two in the first operation, only three in the next operation, only one in the operation after it, and only four in the operation after.

[00:05:16]Then our cost would be like it's around 10.

[00:05:21]So this gives us an intuitive idea like maybe it's always better to choose as much small segments as possible and overall in general actually it will hold true if for any two numbers x and y if both of them are greater than equal to 1 greater than one x is greater than 1 and y is greater than 1 then x * y would be more than = x + y.

[00:06:00]The idea over here is like let's say m is the maximum of both of these elements.

[00:06:13]Then x + y would be less than equal to m + m.

[00:06:20]and x into y would be greater than equal to 2 into x like let's say or let's keep it a bit simple we have two numbers x and y then let's try to see what x + y is and which is also greater than equal to 2 If there are two numbers both of them greater than equal to 2 then x + y would be greater than equal to y + 1 and this should be less than equal to 2 into y and because we have this equation 2 * x this will also be equal to x * y.

[00:07:11]Any questions over here? Like if you have two numbers both of them greater than equal to two then sum of that would be less than equal to product of those numbers and like once you have this condition the solution becomes as follows.

[00:07:44]Try to group one with other numbers because like if you have 1 and x some number x then if you take them individually their cost would be 1 + x.

[00:08:04]But if you take both of them together 1 * x is equal to x. Essentially you kind of got one free over here.

[00:08:13]So like in an ideal world our answer would be let's say we have two three 1 4 5 1 here and something. In an ideal world we can kind of assume that we can combine all the ones with one of the numbers and all we have to do is we have to just print the numbers that are not equal to 1. 2 + 3 + 4 + 5 is equal to around 14. Like the idea is like you can keep pairing all the ones with the number next number over here.

[00:08:49]Like for example, if your array looks like 1 1 2 1 1 3 4 11 1 5 1 6 something like that. Then what you can do is you can start from the first element two three things like this. Okay.

[00:09:11]Is my screen not visible?

[00:09:32]Okay.

[00:09:36]Sorry. Did not realize that screen is not visible.

[00:09:42]Thanks Chris.

[00:09:48]So I think let's go over the problem once again.

[00:09:56]So the main idea over here was we were trying to figure out like when like like because if you have to multiply some number the product will always keep on increasing.

[00:10:11]So the idea was like try to keep segments as small as possible and then we were trying to analyze when the product of two numbers would be more than their sum and when sum of the numbers would be more than their product. And our main claim was if there are two numbers both of them greater than one then their product would be more than their sum.

[00:10:34]The reasoning here was let's assume that x is less than y less than equal to y and since both of them are greater than equal to 2 is less than equal to x is less than equal to y. Now if you have x + y then we can make it like that x + y would definitely be more than y + y because y is the bigger number which makes it equal to 2 y.

[00:10:55]And now because x is greater than equal to 2, if you put a larger number or here, then you will again get x multiplied by y. So overall sum of two numbers is less than product of two numbers. If both of them numbers are greater than two and if any of the number is one then it's better you take their product and combine them into one segment rather than taking them individually because taking them individually the sum would be 1 + x but if you take them together you kind of got one for free.

[00:11:30]Now with this the idea we have came up was like let's say this is how our array looks like. Then what we can try to do is we can start our segment and we can choose it unless we get one element which is not equal to zero. So we can keep this as our first segment.

[00:11:49]We can keep this as our second segment.

[00:11:53]Now we start taking one. We have one. So let's go to the next element. Let's keep all of the segments with one. Let's also take this one. Let's also take this one.

[00:12:00]Now we have gotten two. So let's just take this segment.

[00:12:04]So the cost here would again be two.

[00:12:07]Here we have one. So let's take next segment as next element as well. One.

[00:12:11]Let's take next element as three. Let's take this.

[00:12:17]Now we have four. Let's just keep it. We have again one. Let's take the next segment as well. One. Let's take the next element as well. And this is what we will end up with.

[00:12:30]Now we can have again one. Then let's take next element as we have one again.

[00:12:35]Let's take next element as if we choose segments like this. Our cost should essentially be equal to all the number sum of numbers which are not equal to one. 3 2 3 4 5 6 and that is the overall idea. Like the only catch is like if your last element is also one then you cannot pair this one with any number after it. So in this case you will have some segment where the cost would be one. For example the numbers may end like this one one one one. In that case you have to we'll have to take this segment as well because like notice that we will have to choose the numbers in an increasing order.

[00:13:28]So if you choose any number more than one before this then you won't be able to choose it. So that's the overall idea.

[00:13:40]Sum of elements greater than one and add one if last element is one.

[00:13:53]Any questions anyone?

[00:13:58]So like the overall idea comes from the fact that if you have two numbers both of them greater than two and product of those numbers should be always be more than sum of those two numbers.

[00:14:30]on all the numbers and if the number is greater than equal to two insert plus and if the last element is one then you do answer plus+ the overall idea for the problem.

[00:14:43]Any questions anyone?

[00:14:53]It looks like system testing is going on.

[00:14:58]We cannot submit it.

[00:15:02]Okay, let's wait for a minute or two then we will move on to problems.

[00:15:49]So let's move to the next problem.

[00:15:53]An array is called good if the difference between maximum and minimum in the array is equal to the greatest common divisor of all the numbers in the note that an empty array is considered to be good. More formly an array is good if maximum minus minimum is equal to the gcd of the element.

[00:16:10]You are given a permutation p of length n.

[00:16:14]Determine the number of good arrays in the given permutation.

[00:16:19]So what we need over here is we are given an array.

[00:16:39]You have to count number of goods sub arrays.

[00:16:43]For example, it can and so on.

[00:16:51]And we can have a few more arrays here like these are some of the examples.

[00:16:59]And definition of good is maximum minus minimum is equal to the GCD of the sub array.

[00:17:14]Like in problems like this one problem that often helps is you try to solve for first GCD equal to 1 and then try to generalize it.

[00:17:27]If let's say we have GCD equal to 1 then how does our problem looks like?

[00:17:34]we would have x - mean = 1 which essentially translates to x = 1 + m.

[00:17:46]So if the GCD of all the numbers is one then like you can have only two elements in the array some X and some X + 1.

[00:18:00]If GCD is one because the moment you take X + 2 then your maximum minus minimum would be more than one.

[00:18:17]Does that makes any sense?

[00:18:23]So like the only possible way when we can have GCD equal to one is like when we take two consecutive numbers like the element set should be two consecutive numbers. That's what I'm saying. Now if we have to take let's say GCD equal to 10 then the one all the numbers would be multiples of 10 right so we can write it as 10 * I 10 * J 10 * K and so on like that's how the numbers would look like there there would be multiples of 10.

[00:19:09]Let's say this is our maximum and this is our minimum.

[00:19:18]So then the order of elements we have would be 10 * k less than equal to 10 * j less than equal to 10 * i.

[00:19:31]Again this gives us k less than j less than i.

[00:19:39]And if I have to look at the equation, this was my maximum.

[00:19:44]This was my minimum.

[00:19:48]And this was my GCD.

[00:19:51]If I divide everything by 10, it again becomes I minus K = 1.

[00:19:59]So like again it becomes like one of the element would be X I equ= to K + 1.

[00:20:11]So this gives us the set again like the difference between this and this should be 10 in this case or something like that like difference between K and I should be one. So that when you have JCD the difference becomes 10 or if I have to look at it on a broader picture what I can make a bold claim is I can only have two distinct elements if this equation needs to be satisfied.

[00:20:54]If the array can be good, I'm not saying every pair of two distinct elements will give you a good array. But what I am saying is if you have more than if you have three different elements in your array then your array cannot be good.

[00:21:17]And the claim is like this like if you have the GCD of array G then one of your number would be G * I another number would be G * A and another number would be G * K.

[00:21:31]And whatever maximum minus minimum you have. If this is your maximum and if this is our minimum then g * k - * i = g maximum minus and which gives us k - i = 1.

[00:21:55]Any questions so far?

[00:22:20]So like now if this is our claim then one thing you can notice is that in the input array we are given the permutation.

[00:22:30]Permutation means all the elements are different.

[00:22:42]So like we are given a permutation and this implies every element is different because permutation means all the numbers from 1 to n appears at least once.

[00:23:09]So what we can do is we can check every pair of consecutive element and call it a day. We can check A1, A2. We can check A2, A3. We can check A3, A4. And what are good pairs we find? We will do it.

[00:23:22]Okay. And oh wow, this is proof is good way. I thought of this question is maximum minus minimum is a non-dereasing function. Why?

[00:23:34]over and error keeps gd keeps on decreasing and maximum minus minimum keeps on decreasing. So yeah like in the contest I did not really try to prove anything. I just ran two for loop and validated it. This proof is actually from the editorial not something that I invented.

[00:23:55]So this is where we are in context. I was like the answer must be something small as long as you find good pair you keep it otherwise you want.

[00:24:07]So like overall our problem becomes like this. We need to check all the pairs all the consecutive pairs.

[00:24:26]If maximum of pairs minus minimum of pairs is equal to GCD of pairs then we do answer plus and essentially that this ends up being the solution for the second.

[00:24:42]Any questions?

[00:25:24]So like so in context I knew like this is problem B. So you need to just check couple of answers left and right and call it a day. I would have tried proving it like if I have to prove it.

[00:25:37]This is how I would have proved it. I would have assumed that the GCD of the numbers is G. Then maximum is some multiple of G and minimum is some multiple of G and then I would have tried to played around it. So actually this is what I would have tried doing it if I was trying to prove it in the box for me like it was just be so one WA was worth it. So I just end up implementing something because in the problems like this if you have an array of elements with GCD then it makes sense to convert the array into G into some multiple and then try to work on that remaining part.

[00:26:17]So like essentially whenever you have something with respect to GCD of an array let's just try to convert the GCD equal to one by dividing all the elements by GCD and see what nice properties you can get there.

[00:26:37]So this was problem B.

[00:26:42]Any questions anyone before jump on to problem Yeah. So let's move to problem C and mountain easy version. So this is an easy version and E is the hard version of it.

[00:27:21]And most of my contacts did when trying to solve E.

[00:27:28]It says this is an easy version. The difference is we have to only find the value of f of a. Now we have defined some f of a.

[00:27:36]We are given an we are given some array c1 up to cm. We have to choose an array of inteious b1 into bm and take mod of each element with the corresponding other element and then we have to find the maximum possible max of the resulting array.

[00:27:57]So to put it this way we are given some array A1 A2 A3 A4 and so on.

[00:28:28]Now we have to take mod of each element with whatever numbers you choose.

[00:28:43]We are free to choose whatever number we want. Take mod.

[00:28:49]You will get some new array.

[00:28:52]Let's call it D1, D2, D3, D4. And we have to find the max of this.

[00:29:01]And this max should be maximum possible.

[00:29:11]We can make maximum we can make the flexibility we have is we decide what number to take mod with and what we have to ensure is that max is maximum possible and max is also defined as max of an array A is defined as smallest number not present smallest positive number present in the any questions anyone on the problem statement.

[00:30:38]So now the idea is as follows.

[00:30:46]Let's say if we want to make max= to 5 then we need to insert like in our new array all the elements from 0 to 4 are present.

[00:31:13]Similarly, if we want to make x greater than equal to 10, some number more than that, then we must have all the numbers from 0 to 9 present in this array.

[00:31:34]like max equal to 10 means 0 to 9 are present 10 is missing. What I am saying is if we can somehow insert that all the numbers from 0 to 9 are present then our answer is at least 10. Any questions so far?

[00:31:55]So with this idea what I can claim is my answer is would be kind of or if I ask you this question can we make all the can we insert Or is it possible to have all the numbers from 0 to 10 at least once?

[00:32:42]If you say the answer is yes, then I can also say that the question answer to this question.

[00:32:57]Is it possible to have 0 to 9 at least once?

[00:33:07]If I say that you can definitely have all the numbers from 0 to 10 by doing some by choosing the given operation in some way then what would be the answer to this question? Is it possible to have numbers 0 to 9 at least once after doing the operation?

[00:33:30]This would also be yes, right?

[00:33:39]this will also be yes.

[00:33:44]Similarly, I if I ask you this question, is it possible to have all the numbers from 0 to 20 at least once?

[00:34:01]And if you say the answer to this is no, then what would be the answer to this question.

[00:34:10]Is it possible to have all the numbers from 0 to 21 at least once?

[00:34:24]What would be the answer to this question?

[00:34:35]like this would be no because if can you cannot have 0 to 20 all the numbers together then for 0 to 21 also you have to make 0 to 20 together and some additional elements. So if you cannot have some small set of numbers together then if you add more numbers to it the answer will remain wrong.

[00:34:57]Similarly here if we say that we can make all the numbers from 0 to 10 together in the array then if you remove for example 10 also then the same would hold true for 0 to 9 as well.

[00:35:10]Now whenever you have problem like this for example if you have some function which says for some question for x if it is true yes for x it is yes this means for x - one also is yes like this problem has this property if you know the answer is yes for some larger number then you know that any number smaller than that will also give you yes and for some number y if the answer is no then if you choose some number more than that also the answer is no then like the problem here would look like this you will have some yes and then you will start having no like your array from The numbers from zero to all the numbers would look like this.

[00:36:17]All like is it fair to say like this that you will have some number X some number up to which the answer to this question will always be yes and after that you will start receiving no.

[00:36:39]And now because 0 to 5 is the largest element where the answer is yes then this is the best we can choose and the max here would be six.

[00:36:51]Any questions anyone?

[00:37:00]Now how do we find answer to that question? We are yet to go over there.

[00:37:21]So now if we can sum off and one more idea over here is like now we can always bind the search for this array for point where yes changes to So now if we can somehow solve our original problem which says can you somehow make all the elements from zero to 10 in the array and if we can somehow return that yes and no then we can binary search on the complete array to figure out our required answer.

[00:38:05]Yes. Now we will binary search on what is the max we can get. Essentially we are trying to binary search this point where the answer for this question changes from yes to no.

[00:38:15]And that point will also give us what is the maximum number from zero up to what you can make. And the max is usually plus one of that.

[00:38:25]Because if you have an array where you say you can make all the elements from 0 to 5 then your max would be more than six at least. And because you cannot make 0 to six together so you will end up in a situation where your answer cannot be Like for example, if we can make all the elements from 0 to 5 together, but if we cannot make 0 to six together, then this is the best answer we should make.

[00:38:55]And in this case, the max of whatever more elements is there, that would be your max because you will have all the numbers from 0 to 5. Six would not be there. And then you will have numbers more than six. And our definition of max is the smallest positive number that is not present in the array. We have every number from 0 to 5. Six is not there.

[00:39:15]And we care less about the elements more than six now because we have found six.

[00:39:22]So now probably first I will try to jump on board for this.

[00:39:34]Now this is my checker function. I'm not going into the details yet but what it says is can I make all the numbers from 0 to m minus one in this array and it will return me a true and false.

[00:39:47]So I start with zero like left end point can be zero and your max is more you if you n numbers then you cannot have zero to n plus one all the numbers together. I look at mid. If the mid is true, if I can make all the numbers from 0 to m minus one in the array, then I change my left hand point to mid. Otherwise, I change my right right hand point to mid and whatever maximum number I could find. Now here the constraint would be for L the answer would be true. For R the answer would be false. So I have to print L here. So like you see how like the original problem of max divisor and all we have changed into one simple question.

[00:40:26]If I give you a number 10, can you give me a yes and no answer? If you can make all the numbers from 0 to 9 in your answer.

[00:40:43]Now let's try to observe how we try to answer this question.

[00:40:50]Like let's say we have 10.

[00:40:55]If we take mod x, what are the possible values we can get?

[00:41:01]10 mod 10 is 0 or let me put it this way.

[00:41:14]10 mod 1 is 0.

[00:41:17]10 mod 2 is 2 is again zero. 10 mod 3 is 1.

[00:41:24]10 4 is 2.

[00:41:28]10 mod 5 is 0.

[00:41:35]10 mod 6 is 10 mod 7 is 3.

[00:41:45]10 mod 8 is 2.

[00:41:47]10 mod 9 is 1. 10 mod 10 is 0.

[00:41:52]10 mod 11 is 10 mod 12 is 10 so on and if I look at all of these values the possible values I could get was 0 1 2 3 4 and 10 these are the only possible values I can get by taking more because everything else would become start becoming similarly if I try to inspect more for example if I try to look at 19.

[00:42:24]What you will notice is you can get all the numbers from 0 up to 9 and you can get 19.

[00:42:31]These are the only values you would be able to get by taking some number as you want.

[00:42:39]This you can try to write down numbers and you will see if I have to prove it then I can prove it like this.

[00:42:48]If I have to take 19 mod m, if m is less than equal to 9 and so a mod b is always less than equal to b is always less than b assuming b is not zero because the remainder when you divide something if you divide a number by five then the remainder is always between 0 and four.

[00:43:20]So this number is less than 9 less than equal to less than 9.

[00:43:27]If my m is less than equal to and if my m is less than equal to 10 and less than 19 then I can notice is 19 mod m 19 would look something like this.

[00:43:49]m + r because when you divide that number by 19 the quotient would be one only.

[00:43:56]So this gives me my r would be 19 - 1.

[00:43:59]And because m is between 10 and 19, this value if my m is between 10 and 10 10 and less than 19.

[00:44:21]10 - 19.

[00:44:26]less thanus. If I add 19 here, this greater than m greater than and if my m is 19 then 19 mod.

[00:44:46]This is problem C. So what I'm trying to prove is if I take 19 mod m this value is always less than equal to 9. I cannot have it more than the proof is if this value is less than 10 then anything mod it would always be less than 9 and if this value is greater than 10 then my m would be like this. The remainder would be one and the question would be one and there would be a remainder and the equation would like this like usually it would be like this and for this case Q would be one.

[00:45:35]So what I have end up proving is or in general if I try to do it for odd numbers odd numbers the value is n / 2 always less than equal to n / for 19 it was 9. Similarly, you can try to prove for even numbers as well and the value would be n / 2.

[00:46:07]Like for example, if you take 20 like for 0 up to 9, the remainder would be less than= to for 1 up to 10 the remainder would be less than equal to 9.

[00:46:22]And from 11 up to 20 again like this would here the term would be 20 - 11 20 - 12 and this would also be less than I proved it for odd you can try to similarly prove it for even.

[00:46:38]So for any number we have two choices.

[00:46:44]If you have a number x, we can either keep it x or I can map it to the number x / 2, x / anything between x and x / 0 to x / you need to take care of plus - 1 here based on order.

[00:47:09]So this is the overall idea. So for every number what you know is you can either keep it as it is by choosing a larger number for division or if you have to divide it then you can you will always have number which is less than the half of the original.

[00:47:27]Now if I have to answer question like can I make all the numbers from zero up to 10.

[00:47:34]What I should do is all the numbers which are between 0 to 10.

[00:47:51]So for example if my array looks like this 2 19 4 25 let's say this is the array and the question is can I have all the numbers from 0 to 10 in that case I should keep this two and four as it is and all the remaining elements I should try to make them closer to as possible so I can try to make this 19 equal to zero.

[00:48:22]is 25 = 1, 30 = 2 and so on.

[00:48:27]Or alternatively, if I have to put it in a different That's If this is our array and the question is can I make all the numbers from 0 up to three.

[00:49:08]I should keep one copy of two as it is.

[00:49:10]This is free. I am free to make anything. I should keep one copy of three as it is.

[00:49:17]And in the remaining array I should try to pick the smallest element and I should try to make it equal to zero which is possible. You can take two mod 2.

[00:49:29]Then I should look at the second smallest element. I should try to make it equal to one.

[00:49:36]And you cannot make okay you can actually take 3 mod 2 and make it one.

[00:49:41]So 0 1 2 3 is possible. Now I should try to look at if I can make four over here or four I would possibly able to make but that gives me the idea.

[00:49:55]No like I simply choose like now I am binary searching on the answer. So my question is can I make element from 0 to three if the answer is yes then I will now binary search with my L as three and move further. So the answer for 0 to 3 is yes. So now I will try to binary search a bit more like right now I'm choosing like if I have a question can I make all the numbers from 0 to x how I'm going to find an yes or no to it once I have an algorithm for it I will go ahead and use my binary search for the answer now if someone asked me can I make all the numbers from 0 to five with this given array what I will do is I will keep one copy of one copy of three. Then I will choose the smallest element like that zero is not yet here. So I will try to make it zero.

[00:50:54]Then I will try to choose second smallest copy.

[00:50:58]One is not here and I can actually make one here. Then I will try to choose third smallest number. 0 1 2 3 is there.

[00:51:07]Can I make four using six? The answer is no.

[00:51:12]Can I make four using this?

[00:51:15]Again the answer would be no. Can I make four using this? The answer is again no.

[00:51:21]So for 0 to 5 the answer overall answer would become no.

[00:51:26]So this is what I try to do.

[00:51:30]If I to check if I can make all the numbers from zero up to m, I keep one one copy of all the numbers that are already there. And for remaining element I try to match it with one larger element.

[00:51:57]I checked on all the numbers here. I'm checking If my current element is less than M and if I have not yet taken then I will take it otherwise I keep in Now I start for all the J from 0 to M.

[00:52:39]If I have already taken one element for this, I skip it.

[00:52:44]Otherwise I try to find one element which is my given answer.

[00:53:00]What we know is for odd numbers the answer is simply divid by two. For even numbers the answer is vidide by two.

[00:53:19]As long as I cannot make I from the current element, I will skip it.

[00:53:26]Now if I have reached the end of the B, then I cannot definitely make J.

[00:53:41]So I keep it and I skip further. And if I was able to make all the numbers from zero up to m minus one then I will return.

[00:53:49]So this was the overall idea for this problem.

[00:53:54]Any questions ideas? Any the crucial idea was okay problem totally destroyed my model.

[00:54:12]I try to just it x through 0 to n since n is the greatest max you can get and try to make any element in the array equal to x by doing lower bound or x itself. If not possible then I print X as an answer. Could not think of one.

[00:54:28]Actually for this there is a very good article on top.

[00:54:34]this I would strongly recommend you to go over there like these were the article I actually read probably 5 years ago or so and that's where the intention of binary search came for me. I very strongly recommend you guys to go ahead and read this out.

[00:55:05]a binary guide. I don't know if I remember it or not.

[00:55:10]I very strongly recommend everyone to go ahead and read this article.

[00:55:16]Like this will completely change how you think about binary search and it would not be possible for you to forget this binary search idea. Like if you have some number x then x - 1 is also true. You have y then y - 1 is also known then you can binary search on that.

[00:55:33]You will simply never be able to forget this if you just go ahead and read this article and this is actually the article I read probably like you can try to solve it but the problem here is like top coder is no longer there so I don't I really doubt you would be able to submit these problems and try to probably search for code forces problem or USAS SEO guide for binary search like you cannot submit problems on top is m assumed is m assumed based on nx2 logic like I'm not sure if I understood it so like I the I took the left most range for the binary search as minus not zero like if you read article you will get a sense of why I took minus one not zero one or something and my right end point is n plus one because max of n numbers cannot be more than n so I just choose one number more than what max we can get and minus one because max is at least zero so I simply choose minus one so for l it's guaranteed to be positive for r it's guaranteed to be no and then a binary search based on yes I either change my lower bound or I change my upper and this is simply the mid for the bin.

[00:57:15]So this was the idea for the problem.

[00:57:19]And like you just read this probably it won't take more than 5 10 minutes but the moment you do it will this idea you will always get in the problem.

[00:57:36]So this was our problem C. Any questions anyone on problem C we will move to problem D and problem is harder version of this problem. So we will have to do a things bit differently there without a binary Okay. Like whether what is the feedback for Twitch? Should I stream both on Twitch or YouTube or mostly YouTube?

[00:58:35]Any feedback? I do see a couple of folks who have created an account just before this stream. So, thanks a lot for that.

[00:58:48]Yeah, like I was mostly experimenting with different platforms and that's why right now I'm mostly streaming on Twitch.

[00:59:13]So in the context after doing problem C I directly went to problem E because that was the harder version. Here the difference is now we have to find this maximum for every possible prefix of the answer and like this needs to be done a bit differently but let's go ahead and body I mostly read the editorial because I did not think about it in the content and editorial was already so it says you are given an array a cons string of n positive integers For any segment of the array starting at position L and ending at position R that small M L R denotes the minimum value in the segment and large M R denotes maximum value in the segment. We can perform following operation any number of times. If the sum of minimum and maximum is odd.

[01:00:10]This means they have different parity.

[01:00:12]One of them is odd, one of them is even then we can reverse that segment.

[01:00:21]Now we have to determine if we can make the original area non-dereasing by performing a some set of operation.

[01:00:33]So this is where we are.

[01:00:48]So our problem statement is like this.

[01:01:02]You have an array.

[01:01:09]and so on.

[01:01:12]If we have a sub array where minimum plus maximum all then we can reverse it. So this becomes a6 becomes a5 this becomes a4 this becomes minimum means some odd means this is either even plus odd or this is odd plus.

[01:01:43]Now can we sort the complete array?

[01:01:45]That's the question to me.

[01:02:06]So this is where we are and we have to print an yes or no and an array is here.

[01:02:14]So for few observations if we have two numbers we have this array then we have an odd number then we have an even number and then we have few more elements then we can choose these two elements and apply a reverse operation on it it will become even this will become odd so is it so what I'm saying is I then two nearby odd and even number if the nearby combination is odd and now editorial boldly claims if you look at all the odd numbers if we can somehow sort them and if you look at all the even numbers we can somehow sort them then the answer would be yes. So with this claim what I'm trying to do is I will first move all odd numbers in starting stop and move all odd numbers at even at n I'm not changing the order of the element like for example If my array is like this 2 4 1 3 6 I can first move this one before here and then one over and I can choose this three move it before and move it before and I can do the same for move it before move it before move it before. My array would become like this. 1 5 2 4.

[01:04:16]This is one simplification that I am doing first because I know that I can swap two nearby equal elements.

[01:04:30]Now my idea is let's try to sort these elements.

[01:04:37]In this case it's already sorted and let's try to sort these elements also separately with some jugard or something.

[01:04:51]And let's say after sorting I end up being 1 3 5 2 4 6 like in this case it happened to be the sorted one but if it was not then I can again move all the even elements to its required place and I would end up with 1 2 3 5 4 3 4 5 6 because if this is sorted I can first try to move it to its correct this then I can choose to then exit because you don't have to cross two and four again.

[01:05:32]So this is what actually the editorial is also trying to do.

[01:05:44]Now it says like this. If I'm only focus on the even elements.

[01:05:52]If I have some alternative pair for example looks like this.

[01:06:00]6 then I should try to make this a sorted array using inserts and sort of or things like this. So first I can keep this two as it is.

[01:06:29]Then I look at the next number. Six here is at the right position. So I keep it as it is. Then I look at the next element. 8 is also right. So I keep it as it is. Now I have a zero here.

[01:06:43]So I should figure out some magic using which I can move the zero here to here.

[01:06:49]So my current pair become 0 six.

[01:06:54]Then I have four here. I should try to sub four with eight and four with 8 zero.

[01:07:03]I should try to get array like this.

[01:07:08]And is there a way I can make an array like this? For example, here I was 2 6 8 were already sorted. Now I somehow ended up with a zero.

[01:07:23]Now I have to move this zero over here.

[01:07:29]Can I somehow do it?

[01:07:34]And I have to try bracket always like this.

[01:07:38]The only time when I can try to do it like this is for example if I have a line here and then some more elements. I am right now not trying to look at it but if I have a nine here then what I can try to do is I'm not saying half But let's say if I bring this 9 magically over here then my array would become 9 to 6 8.

[01:08:24]I can first apply reverse operation on my array would become 0 8 6 9.

[01:08:38]Then I can also apply a reverse operation again here.

[01:08:44]It will become zero 9 to 6.

[01:08:48]And then I can again move 9 over here and then again to a seven. Here I can remove nine anywhere between this because all the other numbers are odd.

[01:09:00]So minimum maximum if you can somehow have it between that.

[01:09:07]So this is what editorial is trying to prove. So now you maintain a sorted list of even numbers. You try to add more elements to the back of it.

[01:09:17]And if the sorted array is not maintained, can you somehow make it sorted by choosing some element from the or part and I believe we possibly need the maximum and minimum of the odd even elements.

[01:09:43]But let me just 41 are the minimum maximum.

[01:10:02]So now if I have to I have some sorted element of even numbers then what I can choose it either I can choose maximum odd from here and use it to move the numbers around or minimum odd because what I really need is or another way to put at it is Like let's if you have 2 6 8 0.

[01:10:35]Let's try to first move this zero before 8.

[01:10:40]You will end up with 2608.

[01:10:43]Then try to move this zero before six.

[01:10:47]You will get two 08.

[01:10:51]Then try to move this zero with two here. You will get 0 to 6 here. Like one at a time. looks like some bubble sort or something. So now I have two nearby elements. Let's say 8 and zero. Then I swap them using some another element some more numbers.

[01:11:21]If I can do it then we are good. So the way I would do is like I have some set of even numbers then 8 then 10 then zero and then few more numbers.

[01:11:34]I will first move some odd number from here. We can freely move it among the even numbers.

[01:11:46]So I now have odd 8 0.

[01:11:52]If I can apply an operation on this then I can make it zero 8 odd and then I can take odd back to its original position.

[01:12:09]So for me to apply this operation here we have odd 8 and zero. If my minimum is odd you remember like Minimum plus max equal to odd means either my minimum is odd and maximum is even or my minimum is even maximum is odd.

[01:12:39]If this is the case then maximum should be eight and the minimum odd should be less than zero. Or if this is the case then this is zero and my odd should be greater than it.

[01:12:53]So I should have one odd number either less than zero or odd number greater than only I can swap odd zero and it array has elements like this then I'm good.

[01:13:16]And if I'm trying to satisfy this condition then I can just choose odd equal to minimum odd element.

[01:13:25]And if I'm trying to satisfy this condition I can choose odd equal to maximum odd element.

[01:13:36]And this is where and I believe this also.

[01:13:56]Essentially, this was the idea for this work and I mostly looked at the editorial and editorial simply says this ing I believe a thousand people solved it in the contest but I doubt more than 500 would be able to solve this. I will probably rate it around 1,800 1900 very high.

[01:14:58]Now let's try to find simply making it as two separate array because odd can mean there something even can And you don't have to do it.

[01:17:36]Please.

[01:18:13]or menu as both of these elements.

[01:18:27]then it's possible to sort it because the maximum would be both of them otherwise x is more than both of these elements and also we can say we cannot shimly I check All right.

[01:19:17]This was actually the problem of Mostly the idea I implemented whatever was in the editorial mostly right now. Any questions otherwise we will move on to problem E and then wrap up.

[01:20:36]Wait one second.

[01:21:01]simplif one.

[01:21:15]The order is already then you don't need Any questions? Anyone on problem D? We will move on to problem A and that would be last problem Okay. So, problem is same as problem C where we tried to do binary search and all the fancy stuff. Now, here it ask us to find the answer for all the prefixes of the answer, not just the whole level.

[01:22:48]This changes dynamics a bit.

[01:22:52]The key takeaway that we need to remember from the previous problem is the observation that either you keep the numbers same or you decrease it by at least half and you can get every number from half to the remaining element.

[01:23:17]The thing that we need to remember from the previous time is for example if we have 19 then we can make it any number from 0 to 9 or 19 or if we have 30 then we can make it any number from 0 to 14 or 30.

[01:23:33]Overall idea would be as follows.

[01:23:38]I will try to form some pairs already.

[01:23:40]Some numbers would remain fixed just like the last time where I keep them same and some number would be divided into half.

[01:23:47]I will maintain these two arrays fixed that remains same small number that become half the idea would be as follows I would let's say I have a1 up to a and let's say the answer for this is the max for this is M.

[01:24:22]Then I will try to put AJ + one in my matching set and then try to check if I can get M + one or not. X has M + one. Basically, can I get numbers from 1 to N? If it's there, then I will do M++. Then I will check again. Can I increase answer by one more? If yes, then I will do M++ again and I will keep doing this.

[01:24:52]So that's the overall idea.

[01:24:54]Now what can we do over here?

[01:25:01]Let's say we are checking. We know that the answer up to 1 to m minus one is possible.

[01:25:12]And the question is can you make it zero up to n or let's say we have this or let's try to take some running example uh let's say from the fix I got this from two four and I got zero from six.

[01:25:51]I got one from 10.

[01:25:55]I got five from let's say 90 and then there is no way I can make seven or something like that.

[01:26:07]Like the crucial ideas if I have unmatched number let's say two my max is seven so far so 2 4 and six are my fixed numbers that I have kept them as it is and all the numbers other than seven are like this I have kept one copy of the numbers less than seven and let's say the remaining number which I want to change That was my B array earlier or this.

[01:26:46]So what I can try to do is I can try to make this smallest number a zero. Second smallest number a one.

[01:26:59]Third smallest number two is there.

[01:27:00]Three.

[01:27:02]Four is already there. Fourth smallest number of five. six is there and if I have 12 then I cannot make seven or something like that. So in my sorted order I will try to fill my numbers as it is and if I let's say I had let's say my unfixed numbers were like this 10 8 12 10 and 12 and these are my again fixed numbers.

[01:27:43]I can get zero from two. Eight from one.

[01:27:46]0 is there. One is there. Two is there.

[01:27:49]Three I can get again from 8. Four is there. I cannot get five. So this is a waste. No use at all.

[01:27:57]I cannot get five from 10. So this is also a waste. I can get five from 12.

[01:28:03]I have six over here.

[01:28:06]And let's say the remaining numbers are 13.

[01:28:11]So six is there. I cannot get seven. So this number is also a waste.

[01:28:17]So what I will try to do is I will maintain a list of fixed numbers.

[01:28:30]Like if I have to make numbers from 0 to m then they will contain one copy of the numbers from 0 to m.

[01:28:39]And for the remaining elements I will try to fill them in as small as possible.

[01:28:46]And here my set count is 2 8 8 8 10 12 13 1 2 3 total seven numbers among them. If I can somehow figure out what numbers were a waste, for example, in this case 8, 10 and 13 were waste, then I would say I can make four four smallest numbers from the missing s.

[01:29:12]If three numbers have been wasted, this means I can make smallest four numbers.

[01:29:36]and how do I try to match numbers like this? So the idea is I will have a number line.

[01:30:09]This is my number line.

[01:30:13]All the numbers that I already matched.

[01:30:17]I will put a zero there which are 2 4 6 from the original part and I will try to put one on all the remaining elements.

[01:30:52]and we thank like not sure you are getting what I'm doing or not. But this is some magical stuff I'm trying to do. My overall idea was I tried to I'm trying to find the numbers that I cannot match with everyone and then my remaining elements are like this using two. If I have to make it smaller then I can only make a zero.

[01:31:39]I cannot make one using it.

[01:31:44]So I will put a minus one here for two for eight. I can make numbers from 0 up to three if I have to make it smaller.

[01:31:58]So I will put a minus one for that eight. And I actually have 38.

[01:32:05]So I will add three minus ones here.

[01:32:13]Then I add 10. Using 10 I can make numbers up to 0 to four.

[01:32:19]So I will put 1 - 1 here.

[01:32:25]From two I can make numbers up to 0 to 5.

[01:32:30]So I will put 1 minus one here.

[01:32:34]And 13 also I can make numbers up to 1 to 5. Then I can make one more minus one.

[01:32:41]The numbers that are already fixed, I place zero on their behalf.

[01:32:46]Numbers that I could not get from the fixed area, I kept one one everywhere.

[01:32:52]And for all the numbers that I have to now decrease by half. So like this zero denotes if my array had numbers, my array had these numbers 2 4 6 2 8 8 8 10 12 13. These were the original numbers from my array. What I knew was I can make max between 0 to 6 or basically I can make all the numbers from 0 to 5 and I'm trying to see if I can make number equal to six or not using that binary search property as well because if you add more numbers into the array your max can only increase.

[01:33:32]Now the idea here was We have to now somehow pair all the numbers. The earliest one with the earliest minus one.

[01:33:51]Then the next one with the earliest minus one you can get.

[01:33:55]Then the next one with the earliest minus one you can get.

[01:34:00]Now this the earliest number before it would be this and you will essentially have end up with three minus one which are not available anywhere and if you look at my original part as well I had three numbers that were not paired with anyone. So if my this array 1 2 3 four total there were seven numbers and I could not pair three numbers with some numbers then I know that I can have the smallest four numbers and the fifth number would be the missing number and one way to count pairing like this is we start looking at the prefix sums here if I put one and minus one over here the value here would be zero here the value would be one here the value would be zero.

[01:34:52]Here the value would be here it was 1 -1 -1 -1 it would be -2.

[01:34:59]Here the value is -1.

[01:35:02]Here the value is minus one.

[01:35:19]And now what we need is the minimum prefix sum over here. Like for example it's possible that here you will have zero.

[01:35:42]This is how each of the values are.

[01:35:47]And what we need to find is Minimum element in the prefix sum of this array like like overall idea would be like if I'm looking at movie look at the numbers that I have if I have unmatched pair I increment my counter by one.

[01:36:20]Whenever I receive the maximum number I can get, I decrease my counter by minus one and I keep moving it. And whenever I am decreasing my counter, if I cannot get a matching pair, then that one element was not matched with anyone and like finding the minimum sum prefix sum using a segment has appeared quite a few times.

[01:36:48]You can possibly use a lazy segment tree or a normal tree with maintaining some prefix subarray sum and minimum over there. So this is the part that I'm mostly skipping keeping it you as an homework access. Essentially you have to solve this problem.

[01:37:06]You have an error.

[01:37:14]You have updates of the following form.

[01:37:20]You are given I comm X.

[01:37:23]You do a plus = X. X can be positive and negative.

[01:37:30]Update query gives you find minimum prefect minimum element in prefect sum of this array.

[01:37:50]And my claim was if the minimum value is let's say minus 10 then I have 10 numbers which I could not pair with anyone like I haven't explicitly proved it but overall this was the idea any questions anyone so far like this 1 - 10 kind of looks a bit magical but it has appeared quite a few times.

[01:38:26]So I add a segment tree using which I'm trying to figure out the minimum prefix sum that's maintained in the first element on the second I have filled each of the element with one for initially because everything is one this is my update query if I have to add a value at a particular index Now I start with my max as the zero.

[01:39:01]I somehow push my number and then somehow increase max by one. If I was able to do it, I increment it by one and I keep doing it. And at last whatever value I could not increment, I put it into the answer. Kind of like you are doing two pointers. sometimes adding value from the array sometimes increasing a max and you have two different value. Now if I have to put the current element somewhere I have two variables here fixed number and the small number which numbers that I have to make smaller and I could not pay this is the limit up to which I can decrease. I have kept it n by two because n is my some number n by 5 because if your 10 ^ 6 also like you don't need to take anything if the current element is less than max and the current value is not in the fixed array I add it into my fixed array and I make that value zero every value was initially one so I decrement that particular value by minus one otherwise I put it in my smaller array and Whatever the maximum value I can get by division I have added a minus one for that. So for example for 10 this minus one would be at four and here I am changing that zero to one.

[01:40:19]Now if I have to expand it if my current max is cur if I have not made it from the fixed array like basically if there exist and then I'm checking does there exist any element equal to my current element like here I'm you can possibly use a multi Okay.

[01:41:08]Then I can make it in the fixed array. I again change it that value from 1 to zero.

[01:41:14]I erase the current element and I'm reverting the operation because earlier I was doing minus one. Now I have to remove it.

[01:41:26]Now I try to figure out the minimum prefix minimum element in the prefix sum of the elements that I had with my magical timeline. Negative of the that would be the maximum element that I would end up facing.

[01:41:41]So the size of small minus the element that were wasted is actually the number of elements I can get by decreasing and pair it with something. And the new elements I need would be like this. This is the total number of element. These were formed using the fixed.

[01:41:56]So this should technically be equal to also also. So if both of them are equal then I can get the requirements.

[01:42:13]Keeping it is fine because I'm taking product on all the elements not just zero.

[01:42:50]Any questions? Anyone on the problem?

[01:43:18]The idea of like counting minimum maximum you can probably try to solve the problems here. For example, how do you count the minimum segment?

[01:43:28]This is one more problem that you can try to solve for.

[01:43:54]I'm not sure if there are more problems over here, but that's the overall idea we have.

[01:44:01]Any questions anyone? Otherwise, I intend to wrap up this stream. I rushed a bit fast on the last problem. It's already almost 2 hours now.

[01:44:17]And thanks everyone who all are here so far.

[01:44:27]And if you have any questions related to this contest or anything else in general then feel free to ask it. I would try to take answers for 5 minutes and then well did get to learn a lot with stream.

[01:44:55]Thank you.

[01:45:06]Okay, currently I am 1100. How can I improve my actually the advices I have are quite generic or if you have your code forces username or something then I can try to take a look at that.

[01:45:25]And the most generic address is you can join in my discord server and you can look at this road map to add like my ideas are not going to change advice I'm going to give are pretty much but yeah like idea is like the current rating is around 1100 and you have solved 26 260 problems so the advice for you would be like participate in adoda beginner contests and try to absolve the problem for example you learn something new C today right and were you able to solve C in the contest or then yeah like I would strongly advise you to actually go back and try to code the idea for C at times when you listen someone's idea you do things like okay this is something that sounds fair but only when you go back and code you will remember it for the next time so that's the overall idea And yeah, thanks a lot for joining today.

[01:47:15]I definitely you should try to code at least one more problem from what you could solve into the content and that's how you improve. So thanks everyone and I will wrap up today's stream.