Codeforces Round 1097 (Div 2) | Video Solutions - A to D | by Devansh Khandelwal | TLE Eliminators

Añadido: 2026-05-09

[00:00:02]So yo folks this is Dvanch here and today we are going to discuss the first four problems of the today's good forces contest 1097.

[00:00:11]Yeah the problems are super beautiful.

[00:00:15]We'll start with A and we'll see B C and D.

[00:00:21]Yeah. Let's start with the very first problem. Hope this contest went good for everyone.

[00:00:29]The zillian array operating.

[00:00:34]You are given an array A of n integers.

[00:00:36]You can perform the following operation any number of times. Choose an index i and assign a i a i + a i + 1. Okay. Each index can be chosen at most once. Let's see it.

[00:00:53]So this is a problem a right.

[00:00:59]So what we are given?

[00:01:02]We are given that we have an array of n inteious.

[00:01:12]Right? So what is this array called?

[00:01:17]Array A of n inteious. And then we are given that we can perform some number of operations.

[00:01:23]Right? And the operation is B for any index I. We can assign that index I by A I plus A I +. Okay.

[00:01:35]The second thing that we are given some operation.

[00:01:39]What is that operation? We have to choose some index I and then for AI.

[00:01:47]AI is by the way our array that we are given. This would be equal to ai plus a i + 1. So basically the next the very this element plus the very next element.

[00:02:09]Okay. Got it. This is operation that we have we are given. Okay. Great. What is the third thing that we are given?

[00:02:19]An index can be chosen at most once.

[00:02:22]That means this I this I index can only be chosen at most once. That is for every index either we can choose it either we cannot choose it. Okay, great.

[00:02:33]This is it. Good uh statement actually which is going to help us. So this only once only or at most once right so let's change it at most once. Okay. What is the third thing we are given here which is what we need to find out actually which is to find the maximum number of positive integers in the array after all the operations. Got that? So this is what we need to find out which is maximum number of positive elements in the array.

[00:03:30]Positive elements After performing this operation after performing the operation some number of times. So this is there are three parts of the problem. First tells us that we have this array A whose size is N. Also see the let's see the constraints for the n. n is less than equal to 2 into 10^ 5. The typical constraints for a code forces problem.

[00:04:11]And we also given that the sum of n over all test cases does not exceed 2 into 10^ 5. Okay, got it. That means that here are our constraints that 4 n iss less than equal to 10 to^ 5 2 into 10^ 5 5 and each element in array a is less than uh basically greater than equal to - 10^ 9 to less than equal to 10^ 9.

[00:04:44]Okay.

[00:04:47]10^ 9 greater than equal to a I which is the element here less than equal to 10^ 9.

[00:04:57]So we are given these four statements and then we have what we need to find out maximum positive elements we can apply after performing this operation.

[00:05:08]Right? Let's see this with an example.

[00:05:12]Let's take example from the official example itself.

[00:05:18]Let's say if we are given this five which is the size of the array and then 0 - 1 3 - 3 0 - 1 3 - 3 and 0. Let's recheck it. Yeah, we have written it correctly.

[00:05:40]Okay, great. Now what we need to find out? We need to find out maximum positive elements that we could make positive elements. Okay.

[00:05:51]What are current number of positive elements? Only one, right? Currently we have one. We need to make it maximum as maximum as possible elements. Okay. What operation we have in one operation? What we could do? We could do update any element by its uh we could update the sum of any elements by its successor.

[00:06:17]Right?

[00:06:19]I + 1. This is an operation. What an operation can do. But uh one thing that we have to note or we have to take care of is that I must be unique.

[00:06:34]Right? That means we cannot do two operation to any one index. Right? So what could be the best way that we could make all elements positive? First thing first, we cannot do anything to make this positive. Right? Because the only operation we have which updates the current element with its sum of the current elements with its successor. But we don't have a successor here. So we cannot do anything. What else can we do?

[00:07:02]Okay. Can we do an operation here? Uh but one thing uh we must have noticed we can do an operation here. After doing the operation here this element would become min -1 + 3. The successor is three. The successor would remain same or the all the elements in the suffix or prefix remain same. Only this element will change after performing this operation. This would become two which is positive number. Now we have two elements this and this which are positive. Can we change it further or improvise it the number of positive elements further? Yeah, we can perform an operation here. Now after performing this operation, this would become 0 + 2 and this two would come here or the suffix of the prefix or the rest of elements will remain the same. Only the element where the operation we have performed will change. First operation we performed here and then second operation we performed here. What are the total number of positive elements? Now this is greater than zero. This is greater than zero. This is greater than zero. Total number of positive elements are now three.

[00:08:09]So this would be our answer. Right? We cannot make this positive and we cannot make this positive. This is suff this is the last element. Right? We cannot update it with it successor because it's it has no successor. And similarly this it does not have any positive element.

[00:08:24]Yeah. The final answer would be three.

[00:08:26]Let's check if we are correct. Yeah. The final answer for this test case is three. So how can we solve this chat?

[00:08:41]To solve this there is only one observation that we have to notice that we can make from here by seeing this example itself. For every element for every element we could either keep it same or updated by it successor. Right? And to update it by successor, we would need this successor to be as maximum as possible.

[00:09:04]Right? To make this maximum, we can either update it by it successor. Again, we will have a choice. Right?

[00:09:12]Let's understand this. Let's say we have four elements C and D. We want this element to be positive. For example, let's say currently this is a negative.

[00:09:24]That means we have to perform the operation where we we would add the successor right the successor to it. To add this we would want this to be maximum right to want this to be maximum we would have to update it by e if e is positive right and similarly the cycle would go again and again. Right? So basically we want all elements maximum all elements maximum as possible.

[00:09:54]All elements maximum starting from the suffix starting from the suffix suffix or the end right again let's See we would want for example this element was negative initially right we would want this to be greater than zero then we would have to change this right to make this element positive to make this element positive we have only one option to perform an operation here to perform an operation when this D is as maximum as possible to make D maximum again we have to rely on E we have to ensure that we perform when E is as maximum as possible Right? And E is greater than zero and E is as maximum as possible. And again to make E as maximum as possible, we have to make F as maximum as possible. And this chain would go. So simply the last element would matter. So what we would do is we would start iterating from the very last element and we would try to make this as maximum as possible.

[00:11:16]So this would be our algo.

[00:11:19]Our algo would be Start from the end.

[00:11:33]Start from the end and make this element or make that element maximum as possible.

[00:11:41]Max. And when could we make max? by performing operation.

[00:11:52]By performing operation and why we did it again because to make any element greater than zero, we would want this element as uh we would we would we can do it by applying an operation. To apply this operation, we would want this element as maximum as possible or some number that would make this greater than zero. Our best case would be when this is as maximum as possible. To make this as maximum as possible again we would want this as maximum as possible and the chain would go. So from the end we would try to make that element as maximum as possible by performing operations. Right? So basically we'll perform operation. We'll see if the current element's value is increasing or decreasing. If it's increasing then we would apply the operation otherwise we won't be apply operation. Let's see with an example.

[00:12:43]Let's see with an uh example from the official example itself. So let's see from this for this we have n equal to this and we have 0 - 1 3 - 3 and 0. Let's from start from the list. Can we make it more or can we increase it value? No. Because this is last element. We cannot apply an operation. So this would become as it is. Now comes this can we update its value? Yes, we can perform an operation but that would result in minus 3 itself.

[00:13:15]So yeah this is as maximum a value as there could be in the index three based on zero base indexing by the way. Now this can we increase it further? No. If you perform an operation this would become zero. Right? So here we won't perform an operation. But let's take for this should we perform the operation? We have two choices right? With or without operation. Now with operation this would become minus1 + 3. This would become two. But without operation this would remain minus one. So we would always choose the maximum element. We would always want this number to go maximum.

[00:13:51]Why? Because now this we want this greater than zero. So now as we know we can make the this element as maximum as possible and that value would be two. We could use this two here and we could apply the operation again and we would we could make this true. Right? So this is the entire algo what we are doing we are starting from the x and we are making this element as max possible. How by performing operation or by deciding when to perform deciding deciding performing the operation. This is the entire logo that we need to follow.

[00:14:36]Right?

[00:14:39]Let's see the final code and understand it once more by the code.

[00:14:46]Ignore the template. Just focus on this part.

[00:14:52]Okay. Let's see this. Here we are taking the input. Again we are taking the input. And then here I'm calculating the suffix sum.

[00:15:03]This is actually what I am doing here.

[00:15:06]I'm updating it by sum. Sum is our suffix sum. Right? Sum holds the value of that element, zero. If for example here, one second. If for example here we come across some negative value. Uh let's say for here the suffix sum is minus3. So we would the maximum suffix sum actually right. For example for here the suffix sum would be three not zero because the suffix sum is zero. But the maximum suffix or sorry or the maximum uh subarray starting from the very next element is three. Right? How can we com uh how can we calculate it? We'll keep this sum and we'll update it by the current element again and again. And whenever this sum is less than zero, we'll update it by zero. In this way, this would never hold a negative value.

[00:16:08]Right? So this is what we are going to do and we are going to start from the last and we are going to iterate till the very beginning. So this is what we are doing and if any value is greater than zero we are going to increment our answer and this sum again is equal to that element itself or by zero the maximum of both. So we ensure that that the some ele some variable never holds the number zero and then we are finally printing our answer.

[00:16:37]I hope this is crystal clear.

[00:16:46]Yeah, let's start with the problem B. Again the the same approach we are going to do against all the problems. First we are going to understand the problem itself and then we are going to see it and understand it more using some examples and finally we will see the observations the intuitions of the problem that we could make from these from understanding the problem itself and finally we'll code the solution by compiling or combining all the observations and intuitions we'll derive the final solution. This same approach we'll use in for the all the problems that we are going to discuss in this BCD right let's start with the second problem now so yeah Zill max and max X and max basically you are given an array or a of non negative inteious you can rearrange it arbitrarily. Okay.

[00:18:01]Find the maximum value of sum of max and the maximum value of all prefixes.

[00:18:07]Formally you need to maximize the following expression. This basically which is the maximum the max of the prefix plus max of the prefix. Okay, let's see it. So this is problem number B.

[00:18:24]Okay.

[00:18:25]So the first point we are given is we are given this array A which consists of all elements greater than equal to zero and let it we have n inteious and the second point we are given as for all the elements we need to find the maximum of for all prefixes basically right here I is = 1 to N the max M E X starting from the very first element element till the IT element plus max starting from the very first element comma also comma a2 comma a i dot dot dot dot this is our last element we need to find this value for all prefixes Let's also see the constraints for the problem. Here the size of n is less than equal to 2 into 10^ 5 for sum of all such n typical constraints n is less than equal to 2 into 10^ 5.

[00:19:49]So basically we will have to update this prefix again and again. By the way, by the way what is max and what is max? Max give us the maximum value.

[00:20:02]Maximum prefix value.

[00:20:04]Max prefix and max m x means minimum excluded value. Right? Minimum excluded value as the name suggests this gives us the minimum excluded value. For example, for the series of numbers 0 1 3 5 and 7 the minimum excluded value the value which is not here which is greater than equal to 0 and not here.

[00:20:38]Not here.

[00:20:41]This value greater than equal to 0 and which is not in the array. The very first value which comes very first is called our max or the minimum excluded value. The minimum excluded value here is two because two is not here in the array. Right? And it's the first element which is greater than equal to zero and not in the array.

[00:21:02]That's why the max is equal to two. And for our answer we would require to find max and max of the entire prefix. And we would want this as maximum as possible.

[00:21:13]Okay. Let's understand it more using some example. Let's see as some official example itself. Let's take this example text and then 114 514 and = 6 and 4 514.

[00:21:39]Now the thing here is which is very important actually which we didn't added to our question point this this is was our question right which is third point we can rearrange the array as we want we can rearrange this array we can rearrange as we want also one more thing we want the value of this as maximum as possible. Right? This value, this entire value, we want the maximum possible value for it.

[00:22:21]Right? Let's jump back again to was the example. What would be the max plus max value here for all prefix? For this prefix the max is equal to zero and max is equal to 1. The maximum element which is greater which is the the sum of both elements one. For this and this again this would be equal to 0 and max would be equal to 1. So again it's one for this it would become max is again zero. Max is always zero cuz we don't have the number zero. Right? uh that means in any subarray or any prefix array the number zero would not occur. That means that means that the max would always be equal to zero but the maximum element changes the maximum element here is four here is five and here it's again five because five is in the prefix right and here is again it's five right so what would be the sum here four five and five and we would want the sum of all of these first sum 21, right? So, yeah, but we know we can rearrange them, right? So, what can we rearrange for the maximum possible answer? Let's see. We know the max is always zero. So, that means here we would want the max or the maximum element to be greater. What if we arrange it like this five? Then we arranged all the elements as it is 1 4 1 4 right let's see what's what's the max and the max here again the max and the max the max here is five and for all the prefixes that has it would be five and the max is zero for all the prefixes as we have discussed earlier that means the final sum would be equal to 5 * 5 25 which is as maximum as possible possible sum we could get. So this is our answer.

[00:24:38]So what we what we can see or what we can see from this this case let's see we have for each element we are calculating for all profics right for all prefixes for all prefixes we have this max and we have this max.

[00:25:07]These both value is what we want to basically take care of, right? We want these as maximized as as possible for all elements.

[00:25:19]For all elements.

[00:25:22]Okay, great. But which one we should basically value more? Let's say we have an element like this. We have an array like this two and then we have seven.

[00:25:35]What should be the possible best possible arrangement we could do? Now let's take we have we have taken this max more seriously. Then the uh array would be again would be like this right 0 1 2 4 and then 7. But we know the max of this entire array is three. So after three after three we could we would want that are maximum as maximum as possible.

[00:26:03]Right? This is max plus max. If we value max first then this would be like this and then it would be like this 74. The final element would be this. Why?

[00:26:13]Because after this the max would remain same right for both the elements. That means we would want the maximum value here. We would want this to be maximum.

[00:26:23]We will see here with an example but with the max and max of this array. The max here is one. The max here is two.

[00:26:30]The max here is three. And now we know the max would be three always because we don't have the element three. And the max the max here is zero. The max here is one. Max here is two. And the max here is seven. And here would be again seven. That's why we have chosen seven here. That's because we got two suffixes as two prefix arrays their maxes as their seven. Right? And we want the maximum value here. Again what would be the final value? 1 3 5 10 and 10. So the final value here is 29. Right?

[00:27:07]This is the maximum number we could get by ensuring by our by placing max first.

[00:27:14]Let's place max first. Now the beautiful thing here is for this sub array what we did we choose max max over max first right and we made the best possible array. How to make the best possible array? First put all the elements from 0 to dot dot dot max minus one. This max is actually the max dash is the max of entire array and then paste the maximum possible element then all the elements because now after this the max would remain same and after this the max would remain same and they both will be as maximum as possible right but we let's choose max first here then what we have to do we have to place the maximum element max dash is the maximum element we have in the array Okay. And then we could place 0 1 2 this this this and all elements.

[00:28:09]Again notice that we are all prioritizing max second. Why? Because this max has to be maximum for all the subarray. Now for all the prefix array the maximum would be the as maximum as possible max dash. What would be answer?

[00:28:23]Let's take this example. 0 1 2 4 7.

[00:28:28]We have 0 1 2 4 7. What if we choose max first in the rearrangement?

[00:28:40]If we choose it, we would have zero, then 0, 7, then 0, 1, 2, and 4. Why?

[00:28:46]Because we are then again prioritizing max. What would is max plus max here?

[00:28:55]So this max would here would be zero then it would be 1 then 2 then 3 and then then three. The max would be seven for all the elements.

[00:29:06]The final sum would be equal to 7 5 Z is 35. The total sum for this and then the total sum for this is equal to 9 I think is yeah so this would be equal to 44.

[00:29:21]And you can see this 44 is marginally greater than 29 which came as our previous answer. So this is the final and the most destructive answer we could get. That means that if we make this array again and again where we choose max first. If we choose max first that means only one thing that the first element would be max and then we are making all the elements 0 to max minus one and then rest of the elements. Why?

[00:29:52]Because for rest of the elements the max dash and max both will have as greater value as they could have right. So we have to just take care of this part when why this works because this maximum would is a greater number right as a really large number. This maximum is the as maximum or as large number we could get right and we would have slow increments in max right initially max would be one then two then three but instead if we choose the very last number in the very first we would always get this maximum right in the maximum column on the maximum row we would always have all numbers maximum Always always and as we are after putting the maximum element we are greedily pushing from 0 to 1 0 to maxus one we are going to next cover give second priority to our max. So we are basically using greedy here right. So our final go is we use greedy first we'll place the maximum element then we'll start from 0 to maxus one then all the other elements and for this array we are going to find the answer again how we came up with this using the max we know is always beneficial because for this entire array will keep a max and max array. Again let's say if we had only one we have to take for the only one element or the prefix one then this max would be significantly greater than putting zero right instead of zero any element we put will give zero as their max right but if we put zero this would give one as their max but the maximum element would be zero instead putting max really helps a lot right so I use this observation right that we can choose the maximum element first. That means that would always mean that this row is always as greater as possible and then for max we can gradually see it from here to here. Initially it would become one and it would go as large as max and for all the elements we would have max here and again this increases incrementally right so it wouldn't matter that we put this first rather than max right so this is the final algo this is exactly what I did in my code let's see it here so let's see step by step taking the input this part here I'm putting the maximum element right and which is the maximum element I'm taking an ordered map and I'm pushing all this is actually a MP is basically a frequency map here this rest is our result or our final answer I'm pushing the maximum possible element here right and also decreasing the maximum possible elements frequency here then from zero to our max I'm pushing the element Right? You can see the code here. I'm pushing 0 1 2 3 until we reach our max or minimum excluded element. And then here what I'm doing I'm pushing all the other elements. In this way we will get our final array. Right?

[00:33:35]Now for this array we would have this answer that we are going to find out.

[00:33:42]And here we are finding out for this p trading from starting to ending. This max id keeps the maximum possible element that we are having. And this max uh is basically calculating the current max current minimum excluded element.

[00:33:59]Right? You can see what algo we are using here. Here to calculate the minimum excluded element. Let me actually show you. Basically, let's say we are at whatever. Let's say we are at zero. This is our max. What I'm doing is while the frequency of the current max is greater than zero, increase the max.

[00:34:27]This is a very effective strategy when we need to calculate max and max is again between 0 to 10^ 5 after calculating for the entire array. Right?

[00:34:38]So this is what algorithm we are using.

[00:34:40]We are checking if we have that many maxes available. If we have that means our max would increase. Right? This is what we I'm doing it here.

[00:34:51]So yeah this is all about the problem.

[00:34:56]Hope you guys like this problem too. And now let's jump towards the third problem.

[00:35:04]Brazilian bracket swapping. By the way, this during the contest really confused me. I tried all sort of pro like approaches and all but yeah this was a really really simple problem and this problem was not meant to overthink rather than just giving a basic and general answer for it. Let's actually discuss the problem itself. A regular bracket sequence is is a sequence consisting of both brackets which can be turned into valid math expression by inserting one and plus one any number of times in the sequence. For example, this sequence is a regular bracket sequence while this are not the regular bracket sequence. Let's understand the both lines if you couldn't understand it. So basically for a this is our problem C right for any sequence let's say this this is a regular bracket sequence if we can use these operators and turn this sequence into any valid sequence for example this could be 1 + 1 right if this is a valid expression that means yeah this is a valid regular expression But what about this?

[00:36:24]Now we cannot do one or plus and make this a valid expression. Right? We can make one here and we can add plus here and then again one here. But this is again breaking. This is not a valid expression. That means this is not a valid sequence. So this is what our first point tells us about about a valid parenthesis or valid sequence. The second part, you are given two bracket sequence A and B of even length N. You are given the following operation to perform any number of times. Choose and position I and swap A I and B I. Okay?

[00:37:03]So what we need to do we are given two strings string A and string B and we are given this operation again. Now what we have to do in this operation we can swap AI and BI.

[00:37:27]You can swap those both.

[00:37:30]Right? This is what we can do in one operation. And what is our final goal?

[00:37:35]Determine where you can turn both A and B into regular bracket sequence. That is both A and B we have to return. We have to turn it, this is our goal by the way, into regular bracket sequence, right? This is our final goal. Let's understand it first. See the constraint and understand it even deeper. The constraints are again n is even. By definition, you would know that we would never have odd number of elements in a regular bracket sequence, right? Because every close end uh starting tag would have a closing tag if this expression is valid, right? So yeah, we cannot have any negative or sorry uh any odd number of length for any good regular bracket sequence. So yeah, let's now understand it using this example. This one or let's take a good example. This this is actually a really beautiful example.

[00:38:48]Let's see if everything is working.

[00:39:04]Okay.

[00:39:18]Yeah, let's start it.

[00:39:33]Yeah, let's see the example now.

[00:39:42]So first the example example is here n is = 6 and we have these strings. The A is equal to 1 2 3 4 and then we have 1 and 2 and here B is equal to this string.

[00:40:18]Right? Now is this a regular packet sequence? No. Right? You can always see right in a regular bracket sequence every starting tag would have a closing tag right like this and this have this but these two both don't have any closing tag similarly here this has a closing tag this has a closing tag but these two don't right so basic definition of a regular packer sequence is for every starting tag let's mark it as observation number In regular bracket sequence RBs every starting every this has a ending tag and every ending tag would have a starting tag.

[00:41:09]Right?

[00:41:12]And this would always occur before.

[00:41:18]Right? because this wouldn't make sense, right? This is wrong.

[00:41:22]The starting tag should be before the ending tag. So, this is a point one and point 2 of observation one, right? Okay.

[00:41:32]Great. So, yeah, this is definitely not a regular bracket sequence. Now, also let me tell you some trick about our visualizing this. Whenever this occur, we could say this that every starting tag would contribute + one in our sum if you are calculating a sum uh while doing a sliding window operation or something like that. And every ending would give us minus one. Why this? This tells us two things about the regular bracket sequence. Regular bracket sequence. The first thing is the sum. The final sum, the final sum would be zero.

[00:42:15]Right? And the second thing is sum can never equal to less than zero. This could never happen. That sum is less than zero. Why? If sum is less than zero, that means the closing tags the number of closing tags are greater than number of opening tags. And that's a false. Right? Again as you told here this sequence there would be something like this which is not good right for example let's see this here what's the sum the sum would be equal to one then zero then minus one but why is this minus one because the number of closing tags are greater than number of opening tags right and this would never be a regular bracket sequence That means if we place + one instead of a starting bracket and minus one instead of closing bracket, we would have this algo right that the final sum is equal uh to zero and sum should never be less than zero. Okay, great.

[00:43:24]Let's see now.

[00:43:36]So okay great how can we make it we know the final sum here is equal to uh + 2 and the final sum here is equal to minus2 right + two because we have two extra tags here and two extra tags of positive here right otherwise you can always make a sliding window starting from the very first element and ending and you can calculate for the prefix what would be the Right? What I thought of that I didn't thought initially for this problem is you can always rearrange this element.

[00:44:15]Right? You could always choose for any element that if you want to swap it or not, right? You can swap both A and B as well. Right? A could be equal to B and B could be equal to A. Why I'm telling this, right? Why I'm telling this is because you could basically apply a very brute force and naive approach to this what I have just told you the sum theory. Let's assume we have a a which stores the sum for the first string and then we have BB which stores the sum for the first string the second string. Now while iterating from first to last, first to last we would have some op like for every index I we would have an option to swipe or not swipe.

[00:45:11]Right? And what would this option mean?

[00:45:13]Let's study it more.

[00:45:17]There could be a operation where a and b this is for a and this is for both are equal to this that means both are going to contribute + one right we cannot do anything here similarly if both are this then both could uh contribute minus1 but what if this is like this is going to contribute + one this is going to contribute minus1 and if this is like this and this this is going to contribute minus one this is going to contribute + one for this And this we have no choice right we have to mark it as it is but for this we have a choice and let's make it we would mark the closing tag or the minus one where which has greater value greater value right because always in the later we could cover it the number with the greater value would get this minus one and number with lesser value would get this + one or the opening tag.

[00:46:24]This is what we are going to do. This is very naive and this really works, right?

[00:46:28]Because this was an easy problem actually.

[00:46:33]I hope you got it. For every index, we would get this option. Let's actually dry run it for this problem itself. For this problem we have a equal to opening bracket opening bracket then four closing brackets and b is equal to opening closing opening closing and then two opening I guess. Yeah. So the number of elements here are six. Let's see. A is initially equal to zero and bb is also initially equal to zero.

[00:47:07]Let's take for all elements 0 1 2 3 4 and 5 what would be the sum? Now the initial first both are equal to opening bracket that means both are going to contribute + one that means the both value of a and bb both would be equal to 1 here. Now here here we have a choice here one could be one and one could be minus one as both are equal let's choose arbitrary or let's keep it as they are right so this would be two and this would be equal to zero now again we have a choice and we will take it the greater element would reduce this would become one and this would become also one we would subtract minus 1 here and we would subtract + 1 here because both are different when both are different we have a choice otherwise we have to just apply it now We have closing tax again. Both are closing tax.

[00:48:00]Okay, great. Again, zero and zero. Now, uh we have this. I hope I'm doing some mistake. I think I haven't copied it. Oh yeah, I have not copied it correctly.

[00:48:17]Anyways, for this problem, both this we have opening. Let's see. Let's say we have an opening here as well and this is closing.

[00:48:28]If both are opening again we have don't have a choice and we'll add plus one here and plus one on the both sides. Now we have closing both sides. So again we are going to apply the same here.

[00:48:40]So this would become zero and zero. Now the final sum is zero and never it occurred minus one in any sum. Right? So both conditions satisfied. That means we are going to print yes.

[00:48:53]What are the both both conditions? Final answer or final sum should be equal to zero and any mediator sum s some dash let's say sum in between should never be less than zero and both satisfied our problem right so basically this is a simple problem where we are initially keeping a initial store and then we are deciding where to apply the operation when we have both different brackets let me show you with my example Yeah, this x and y's are a and bb. This is tells us if the answer is correct.

[00:49:36]For example, if x for any point or y for any point is less than zero, that means we have done something wrong or this arrangement cannot be turned into a regular bracket sequence. So yeah we are going to break it and then we are going to print if it's not yes no otherwise yes this again if both are equal A and BB either we are going to add both other either we going to subtract both if not we have to choose if X is less we are going to increment X otherwise we are going to decrement X if X is greater right so this is what we are doing and then we are finally printing our answer pretty easy right so yeah this is a beautiful problem but yeah pretty easy Even once you notice this, now comes the D part of the D question which is I think by far the best or the most interesting one.

[00:50:34]So yeah, let's discuss it.

[00:50:40]You can actually start from here itself, right?

[00:50:44]You are given two arrays A and B of n positive integers. Okay.

[00:50:50]What we are given here?

[00:50:52]A comma b two arrays with n positive inteious.

[00:50:57]n positive inteious.

[00:51:01]Let b dash be a permutation array be chosen uniformly at random among all n factorial possible permutations.

[00:51:12]Define CI equal to AI-B dash for all this. Find expected number of inversions in C. Okay, great.

[00:51:24]Let's see step by step.

[00:51:28]Yeah, what we are told is we are given this two arrays A and B. Now for all B for all permutations of B permutations of B right there would be some permutation where let's say it is B dash here right and now we have an two array B dash and A B dash is some permutation of B and we have array A we have to calculate this C array and C array for every element EI is equal to AI to BI.

[00:52:14]Right? This is what we need to do. Now, how can like this is how we will get the CRA and this in this CRA what we need to find is expected number of inversions.

[00:52:31]When does the inversion occur? When let's say we have this array, right? And here in B and D, D is less than B. D is less than B when but D occurs after B, right? Whenever this type of relationship happens, we tell it's an inversion.

[00:52:54]So yeah, let's calculate that. Let's see the constraints. Now the constraints of the problem are pretty relaxed. N is less than equal to 2 * 2.

[00:53:13]Now how how are we going to calculate it?

[00:53:17]Let's see some example first. Let's see this example. 3 to 5. They have already explained the example pretty well in the problem statement.

[00:53:29]Right? This is a B dash here. What's the example here? Here A I is equal to 3 to 5 and B I B array is equal to 3 to 5. So this B dash tells us what a likely permutation of B. Right? And this C how we are going to calculate it? This is equal to AI into PI. This 325 is again ai the corresponding value of AI for the position. And this B1 dash, B2 dash and B3 dash we haven't known yet. Now they what they did they calculate all possible value of B dash they have here and then we calculate all possible values of C here and then we calculate the final number of inversions. Now 9 is greater than four. This is this 94 is a one inversion. So total inversion is one. Here there are no inversions.

[00:54:20]Similarly here this 15 is greater than six. Right? This is one inversion. Again 15 and 10 is the second inversion. In this problem 15 and 4 is one inversion, right? And then what we did finally added all we have to calculate expected number of inversions, right? That that means what like we have to calculate the probability basically. So this would be total number of inversions by total possible number of permutations we had.

[00:54:49]So this is 2a 3. And then again as we are using modulo I'm sure you guys are already aware of modulo inverse because this is a really a good topic really really important topic and everyone must know this you can see its resources in T channel or website right do this a prerequisite right without modulo you are not going to solve it so basically this for 2x3 for fractions we would use modulo inverse for three and then we are going to the output the final answer.

[00:55:29]So, so how are we how how are we going to solve this? So basically basically the problem here arises is the B factorial right we have to calculate for all possible variations of the B right after this variation we would have some B dash which is what is Bdash some permutation some permutation and then for B dash and A we would get our C dash Right? And using this C, we have to calculate the inversions.

[00:56:09]Am I right? Let's write it in more mathematical way.

[00:56:15]We would have some B dash and A dash.

[00:56:18]And then CI here is equal to what? AI by BI.

[00:56:29]Sorry.

[00:56:31]A I into BI right and what we need to do here what would be CJ here let's say G J is also some index J it would be equal to AJ into BJ let's take this that means we have to calculate all elements count CJ J or CI greater than CJ.

[00:57:11]This is what we need to count. Right?

[00:57:14]This is our final area and we have to calculate the inversions.

[00:57:19]Okay. Let's expand this. Let's expand this. Expanding this CI from here. This would become a into bi.

[00:57:34]Okay, interesting. A I into BI should be greater than AJ into BJ.

[00:57:44]Right? Again this is P ddash because this is some permutation of P because this is some permutation of V right let's actually verify like simplify it more that means AI divided by AJ should be greater n BJ divided by BI.

[00:58:23]Can I say this folks?

[00:58:27]Now can I say this?

[00:58:34]So this is a master equation.

[00:58:41]Now this is for some BJ B dash right but this equation can be used everywhere right?

[00:58:49]This equation can be generally used and for all permutations we would we would like to know for for some B dash by we can basically use this one second let's use this here this is one equation that we got how can we use this equation. Now we know that a i n aj this a is a constant array and this is not going to change right this is never going to change and we know this are also limited limited what are all possible like how many values of i and j can be here how many different values of this could be here.

[00:59:51]This would be equal to N into N minus one, right?

[00:59:56]How many different values of J and I could be here basically.

[01:00:08]So yeah, these are limited and there are n into n minus one.

[01:00:15]You can always apply the permutation here. This would be equal to n into n -1's factorial n into n -2 actually n -2's factorial divided by n -2's factorial np2 where we got this number basically right this np2 would be equal to this and we would cancel this we would get n into n minus one otherwise you can also take that if there are n elements If we are taking this element, we have n possible variations here. And let's say if we took took this, then we have n minus one possible variations, right? These are all possible numbers of permutation there could be here, right?

[01:01:03]This is a really important number. Why?

[01:01:06]Because we have to add final find expected number of expected number of inversions. That would be total number of inversions by total values right total values or total permutations here.

[01:01:28]Now this denominator here is n into n minus one. If we are calculating it at the element level at the element level right this would be equal to n into n minus one. And this total inversions we have to calculate. How are we going to calculate it? We have to notice something here. First this equation I and J we know this is constant. Why this is constant? This there are total possible again n into n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n minus one possible numbers for it and this is also constant right this is limited again right so what we could do here is for our this equation is our master equation so I'll write it again a divided by aj J.

[01:02:23]This should be greater than B I BJ sorry divided by BI.

[01:02:35]Yeah.

[01:02:37]Yep. Also the solution is here. Yeah.

[01:02:43]Oh yeah.

[01:02:46]Now what we could do here is first we could premp compute all the values premp compute and add it to a array.

[01:02:59]This would have all the values for it and and what we could do here then we would process all values. is process all pairs.

[01:03:10]Process all pairs and using binary search.

[01:03:20]Binary search find all values where this is greater.

[01:03:30]Right?

[01:03:35]Let's start from the very beginning.

[01:03:37]So it's super crystal clear because this part is this formula where we got the formulas would be crystal clear. What we did? We found there were two errors A and B and C I is calculated by AI into BI. Okay, great. We told okay if CI is equal to A I into BI let's say J is greater then if uh CI is greater than CJ then we will call this inversion.

[01:04:20]Yeah.

[01:04:22]So here again what we did CI is greater than CJ then it's an inversion if JJ is greater than I okay then we expanded CI and then we expanded CJ and then we derived this formula if AI is AI I divided by AJ is greater than B I uh BJ divided by B dash I and then here we have this formula and I'm saying this we can premputee this values and we could make this into an uh array for example.

[01:04:53]And then for all possible values for this process all pairs and then using binary search we could find all values all ratios all ratios which are less than ai divided by h a right this is our final algorithm that we are going to use.

[01:05:22]I hope you got it. First we are going to premp compute all values using this vector and then we are going to process it using uh process all values for this array A and then we are going to find all ratios in B which are less than equal to this and then after finding this we would uh this for all ratios this we would add it to our sum and then finally we would do sum divided by n into n minus one because we need to find expected number of expected number of inversions Right. So this would be equal to this. Again if you are aware of modulo inverse you can again convert it into modulo inverse by taking its power by modus 2. I'm not going to explain it in depth because it would unnecessarily stretch the video.

[01:06:14]So yeah this is how we do it. Right in my code what I did was my formula was a little different again the implementation all part is same it's just what I did was my formula became a j backpack yeah a j divided by a i is less than b i divided by bj Right? And if this occurs everything is same but again for this we have to calculate all pairs which are strictly greater. Right? Let me show you my code.

[01:06:59]This is what we did. And again for storing these values, right? What you could do is you could create a custom comparator function.

[01:07:10]Right?

[01:07:11]I also came came up with this custom comparator function postcontest, right? I was when I was like searching for uh beautiful suggestions, I came across this. Let me actually copy this and code shift compiler.

[01:07:35]Let me show you there.

[01:07:40]Right? Here what we are doing we are taking the input f is equal to 1. Right?

[01:07:48]That means there is only one number.

[01:07:50]Right? To ensure that we don't arise into some problems. Um ensuring if n is equal to 1 we are returning it there. Otherwise for all ratios this all stores all the ratios of BI divided by BJ instead of putting it all ratios like this we are using a custom comparator function if you folks are already aware of it that's super cool otherwise uh like I'll give you a brief about it so first I'm inserting all BI and BJ and for comparing this what I'm doing is I'm comparing it using the formula itself right for two numbers, right? We would have in our all array in our all array we would have all permutations of pi comma bj right or bj comma bi anyways right just note that I I am using a different formula but the core concept remains same right and then we what we are doing is we are using binary search here to find all the elements less than it right so basically What I'm doing here? Let's say we have two different ratios C, D.

[01:09:10]Now I want this all basically to store ratios of it. I could either use double here, long double here, right? But note that this long double always like it usually leads to some inconsistencies.

[01:09:28]try to avoid it to to avoid it what I did I created a custom comparator function if you guys are not aware of custom comparator I'm pretty sure you must have used it somewhere else right while sorting pair on basis of it second value or something like that uh otherwise you can actually look at up how comparative functions work but yeah using in this comparator function I'm what I'm doing instead of storing like this uh here you could see where I'm using comparator function to sort plot all the values. Why? Because later on we would require to find all values in the ratios which are greater than our target value AJ divided by AI. If I flip this, we would require all values which are less. Right? Similarly, to find all values which are for our use case uh all values which are less than our target otherwise it could be greater. uh for our use case to find it what we are doing we are using upper bound using this target and the comp custom comparator function this comparator function what it does it compares the two values A and B and C and D right let's say if C and D is greater how we how come we we would know this we could basically simplify it we could uh put D into its numerator. This would become A into D and C into D. This entire thing is what we are doing in a custom comparator function. Right? A dot first into B dot. A dot first would be this and B dot second would be this.

[01:11:09]Right? If this value is less than B dot first and A dot. Let's say if this was B, B dot first C A dot is B. Oh, this is B by the way, right? This right? This is what we are going to return on this basis. We are going to sort and this basis we are going to use our upper bound function.

[01:11:36]Right? There is some implementation part that I used in my code. You could I think you could use long double2, right?

[01:11:43]There are plenty of things you could use, right? But yeah, if you want the cleanest approach, this is this is actually I used it when I solved it uh like I was searching for the best possible approach to apply this and I really face some issues using double I think that that implementation was not that well thought but yeah you can always come up with some well thought implementation but the core logic is this you came up with this then you compute all the values this into an array then for all this values you could just do binary search here right and using binary searcher you could find all values which are less all the ratios which were less and you could add that to a sum and then after adding to that to a sum we could finally find it sum / n + n minus one again using the modulo function and modulo like mod multiplication and division we would find a final answer right but yeah this logic if you come up with this formula Now things comes pretty easy.

[01:12:48]This was all about the very beautiful problem. Problem number D.

[01:12:54]Overall contest was really good. This problems are really beautiful. Right.

[01:12:59]Hope you guys got the all the problems like if you folks have any doubt you can always ping me out right in the comment section or you can reach out to me right. Do subscribe this T channel right. Do subscribe if it helped you.

[01:13:20]Plus like right do subscribe and do like the channel always and also like do ping out how many questions you did in the contest or if you found any observation that I missed which could make it even easier. If you've like found something trivial or like some trivial solutions that passed, you can always ping it out in the comment section. And if you have guys have any doubt, you can always also ping that out in the comment section too. I'll be actively watching comments even after posting this video. So yeah, super cool.

[01:14:03]I think yeah, let's end the stream now.

[01:14:09]Okay, folks. See you. Wishing you all positive in the contest.