Codeforces Round 1100 (Div 2) | Video Solutions - A to D | by Anish | TLE Eliminators

追加: 2026-05-24

[00:00:00]Hello everyone. So today we will discussing uh the problems of this round spectral cup 26 round two code first round 1100 which was a div one plus d2 round. So let's start. The first question here is slimes on a line. So let's read out that there are n slimes on a line where slime i is at position ai and you will perform the following operations some number of times. uh you can also choose to uh not do the operation.

[00:00:32]So what is the operation here? So select we have to select an integer x then for each j uh 1 to between 1 to n. If aj is less than x then we will do a equal to aj + 1 and if aj is greater than x then we will do a equal to a minus 1 and if a equal to x then we will do nothing.

[00:00:56]So actually what we have given here we have a given here uh we have given here a vector a of length n and these these are the positions of slime positions of slime.

[00:01:16]So here what is the question here that let's say the positions of slime let's say here if we to take take this test case 5 6 7 1 2 3 then our five 6 7 1 2 3 So if we position uh slimes on a number line let's say from 1 2 3 4 5 6 7 and uh here 1 2 3 5 6 7. Here the slimes are uh uh positioned and we can select we can select an integer x which is uh then for each j uh between 1 to n and if uh a is less than x then a equal to a + 1. So what we can do we can select any uh we can select any of the position here x here and if the a is less than x for example this one all these three if a is less than x then a equal to a + 1 that means all these slimes will uh come closer to this x one step closer one step closer and if a is greater than x here if a is greater than x then a equal to a minus 1 that means the uh position the slimes whose a is greater than x it will come again one step closer a minus one that means the position will be decreased by minus one so it will come closer to x one step closer closer and what we have to find out we have to find out determine the minimum number of operations to make all slimes occupy same position. So what we have to do that we find we have to find a minimum number of operations to make to make the position of all the slimes equal.

[00:03:33]So what we have to do that we have we can choose any of these X let's say if our X is here then all of these slimes will go a one step closer to this X that means it will be two then three then four it will be six 7 and 8. So how can we minimize the number operation to make all these slimes uh at one position. So, so obviously intuitively we can say that the we can we have to choose any x between uh these between the numbers only. We cannot choose x on the extremes like here or here here or here. So if uh like for example if the uh if I choose any x between the between these numbers then and uh let's say let's say we take one and six here. So if we choose any x between 1 and six then in one in one operation in one operation distance between them distance between 1 and six will decrease by two decrease by two decrease by two. So here the positions after one operation the position of one will be two and uh six will be five. So initially the distance was five and now the distance is three.

[00:05:10]So the distance is decreased by two.

[00:05:13]Here distance is decreased by two.

[00:05:17]So what is the minimum number of operations? So mean so what uh what numbers are the uh will take the most operation to become at the same position. So we have to say what number we have to basically check the upper bound here. What numbers will take maximum operations to present at same position.

[00:06:02]So obviously the numbers would be the maximum and minimum of the array. For example, here in this question the minimum is one and the maximum is seven.

[00:06:13]So one and seven is the is the farthest number. So the it will take maximum number of operations. So we have to just calculate the uh number of operations to uh bring both of these on the same position. It will take maximum number of operations.

[00:06:33]So how many operations will it take? So it will take it will take uh like in one operation uh the distance is decreased by two.

[00:06:50]So how many operations will it take? So it will just take the we will make the difference 7 - 1 and uh uh we will check the distance between them. So set the distance between them will be 7 - 1 + 1.

[00:07:03]Uh we will check the distance like in one operations currently distance is six. In current distance is six. In one operation it will be two and six. So the distance will be four. Then third second operation it will be three and four uh three and five distance will be two and the third operation it will be four and four distance is equal. So it will just take - 1 by 2 equal to three operations.

[00:07:35]Uh what if the we have minimum maximum as 1 and 8. So in one operations it will be 2 7 then uh 3 6 then four five here it it already took uh uh four or three op three operations but here the distance is four uh again one so it will take one more operations uh to make it uh like if we will have to put here we Take x = 4. If x = 4 then the four will be at the position four only and five will go closer. So it will be four and four then plus one operations. So here if the difference is odd then we have to uh plus one the uh number of operations.

[00:08:31]So just for that question uh I will make the uh the farthest the rightmost element right maximum element minus minum element + 1 by 2.

[00:08:45]This will cover up all the cases. So let's uh go to the code here.

[00:08:51]This is this is the code for that question. We will find out the minimum maximum of that array. Take the input and uh update the values of minimum and maximum and the output will be max minus min + one by two and uh what is the time complexity here? Time complexity is just uh O of N as we are iterating the loop only once and space complexity of one because we are not storing anything.

[00:09:18]Yeah, we are storing here like vector just made vector so it will be off and okay.

[00:09:27]Okay. So this is the first question. Now let's go to the second question here.

[00:09:35]Yes.

[00:09:37]So the second question is absolute cinema. So you find yourself with the two arrays of positive integers a and b both of length n and you have to perform the following operation any number of times.

[00:09:50]So what is the operations we have to we can select an integer i and just swap a a i and b i and then find the maximum value of maximum of a and summation of all the elements in bi.

[00:10:06]So what we are given here?

[00:10:10]We are given here and in array A and array B.

[00:10:15]And what we can do in one position one operation in one operation we can swap array and AI and BI. We can choose I then swap AI and BI.

[00:10:35]And what you have to find what is what the value I have to find maximum of A.

[00:10:40]So maximum element of array A plus summation of all the elements in B summation of B. So this is I have to maximize maximum element of this. So what can we do like we can swap any number of times.

[00:11:03]So we can swap any number of times. For example, uh let's take this an example here.

[00:11:10]What example here uh if we take this or this example let's say this example we have 1 2 3 and 4 5 6 4 5 6.

[00:11:30]So here what uh first thing which comes to uh mind in our mind that let's make a the absolute maximum absolute maximum of all 2 into n elements. So here uh from that this one if we make for example uh let's take another example in a shorter example that uh the a is 10 and uh 2 uh a is 10 2 and b is uh 8 uh uh 10 and 2 and uh b let's say is uh 8 and 20.

[00:12:16]So from this one like if we make the a the absolute maximum then we will swap uh 20 to 2 and uh 10 to 8 and uh after making like if we take a and also we have to maximize B for the rest of this uh element. So if we uh so here the absolute maximum 20 so we swap the 20 by two and uh to make the max make the rest of the b maximum we will swap 10 and 8.

[00:12:50]So here we will have we will be having 8 and 20 and b as 10 and 2. So what will this sum here?

[00:13:01]Maximum of a will be 20 plus summation of b 10 + 2 which will be 32.

[00:13:12]But here is this thing that this is not the actual maximum value which we are have to which we are supposed to find.

[00:13:20]So what here we can do is like if we swap if we swap this 10 only like uh if we swap for example if we take uh this sum from this uh directly then here maximum of a is 10 plus uh here summation of b is 8 + 20 it will be 38. So this is the this is greater than 32. So that will not work here. So what we can actually do is so let's take an another example.

[00:14:04]Let's take another example here.

[00:14:15]Let's see what will work here. So let's say we have a1 a2 a3 and so on and b1 b2 b3 and so on. So we have to we can swap any of the any of the pairs and we have to maximize uh we have to take we have to maximize the is max of a plus uh summation of b. So we we uh we do should not focus on just max of a. We should focus on here the summation of b.

[00:14:54]We have to maximize the whole this sum the whole sum. So we can do that is summation of B. We have here B is the larger entity which we can make the sum more greater. So what we can do is the make the uh uh put all the greater elements in these pairs in B only. We can do that we we put all the greater pairs in B only. We greater elements in these pairs in B only.

[00:15:27]And then we will uh just take the maximum of all a is here. So let's uh check that out. The maximum of all a is here. That means the maximum of the maximum of all minimum of those pairs.

[00:15:48]all minimum of those pairs.

[00:15:57]So we what we are doing here we we are putting the maximum of these pairs in B only and we like if B2 is greater than A2 then we will put B2 in the B only and then take the maximum of these A's which will automatically the maximum of all minimums of those these pairs A1 B1 A2 and B2. So let's uh go through the code here.

[00:16:27]uh B. So what we are doing here? We are taking A and B inputs and we are taking two values X and Y. So the X is here the absolute the sum of all the maximum of those pairs. So while iterating we are taking we are increasing X by maximum of A and B the sum of all maximum of these pairs. And what is Y? Y is the minimum of those maximum of minimum of those pairs. We are uh we are finding the minimum of of each pair and taking the y the maximum value of those minimums and the answer will be simply x + y. Here the time complexity is just of we are iterating one time and the space complexity is uh also of like we are not taking any extra space though but uh we are uh storing the array.

[00:17:25]So yeah uh we can walk through a example here also like for 2 3 6 and 1 58. So let's say here is an example 2 3 6 7 and 1 4 5 8. So what we will do? We will put all the maximums in B. So here 1 2 3 4 and 5 6 and 7 8.

[00:17:58]So here the sum will be the sum of all these numbers plus the sum of all minimums of those pair that is seven. It says 7 + uh 2 + 4 + 6 + 8. So it will be 27.

[00:18:16]Here the answer is 27.

[00:18:20]So now the let's go to the C1 question.

[00:18:24]See in C1 question we will be flipping.

[00:18:27]So this is the easy version of this C1.

[00:18:29]Let we have C2 also. So in this question we have given an array of length n which consist of non zero but positively negative integer. So in the array a we can have negative inteious also. You will perform the following operations at most n times.

[00:18:47]We can also choose to uh not uh perform the operation.

[00:18:52]Then what in what we can do in the operation? Select an index i such that the i's a i must be positive.

[00:19:01]Then for each j which is less than i, we will do we will flip the sign of that element and we have to then uh output a valid sequence of operations of length at most 10 which minimizes the sum of a at n. So we have to minimize the sum of a and uh for that uh we have to perform some operations on some indexes.

[00:19:30]So we have to output the num the indexes also. So what we have given here we are given an a with positive and negative integers and negative integers can also be present and we can ch we can choose i uh during an operation such that ai must be greater than zero and uh for in that operation we can say We have for J less than equal to Y the A will be minus A. So we are we will flipping the sign of that uh element and after some of the operations we have to minimize or minimize sum of a.

[00:20:31]So how can we approach this question? So let's say an example here. Let's start with an example. Let's say we have a three element 2, minus 3 and uh 1.

[00:20:45]So let's say we choose this. We have to minimize the operation. So we have to make make sure to uh put maximum number of positive elements to negative. So what we can do here like if we choose one to choose to perform an operation at index one so we will be have minus2 then minus 3 and then one then if we choose to have perform an operation at minus 3 then it will make the two and three positive.

[00:21:18]So we can we can't do that. So let's uh go to uh choose uh perform operation at index three then it will make 2 3 - 1 but performing the operation at one the third index it made the indexes at one and two positive. So we'll again have to make the uh some operations to make these negative or minimize these. So this is very uh confusing here. We can't do operations from here left to right.

[00:21:55]Why?

[00:21:56]Because doing an operation at any index I we uh we are we can we are uh affecting the integers on its left side but the on the right side will be the same right will be the same here. It will not affect the right right one. So instead of uh performing the operation from left to right, we must try to perform the operation on the uh from right to left from right to left.

[00:22:32]So what we can do here for example in the same question write 2 uh - 3 and uh 1.

[00:22:42]So if uh the if the question if the in this question let's say at we come at the third position so it is positive so we will make so we will choose uh the to perform operation at index one so it will be then minus2 then 3 then minus one then it is non negative here. Now for this uh this is also positive. So we will again choose two operation here.

[00:23:10]Then it will be 2 then minus 3 then minus one. Then again here 2 is positive. So we will uh choose index = 1. Here index = 2 2 and index = 3. So it will be minus2 -3 and minus one. So we can here you can see that we can always make all the elements negative.

[00:23:34]No matter what are the uh elements in that original array, we can always make the all elements negative. Here let's say uh check an example from here. For example, here 1 - 1 - 2 3 - 5 4 -1 - 2 3 - 5 and 4.

[00:23:58]Here going from right to left going from right to left we will choose minus4 here then five then -3 then 2 then 1.

[00:24:13]Now it it is positive here. So we will again choose the operation -4 then -5 then 3 then -2 then -1.

[00:24:23]It is uh it is now again positive. Then we will again do the operation minus 3 uh here it is 2 it is 1 - 5 - 4 again it is positive here.

[00:24:38]So we'll again do the operation here uh -1 - 2 -3 - 5 and -4. How many times do we did the operation? 1 2 3 and 4. So the answer is here is four.

[00:24:58]So and what are the uh sorry here the answer is four. And what are the positions where we did the operations? 3 5 42. Here what are the positions here? The positions are five then four then three and then two. Yeah.

[00:25:18]So the this will match the answer here.

[00:25:22]So how can we approach that? So what what should we do to make this because at if we if in code uh if at each step we will try to update the whole whole array then it will take much longer time. So what we are doing in what we will do in code here uh let's walk through the code directly.

[00:25:46]Uh here it's C1. So what is uh what are we doing here that uh uh take the input here uh array and this is this sensor will store the indices where we have to make the changes. Now we will just count the number count the number of operations like number of licks flips we are doing.

[00:26:08]For example, if uh if I did the uh flip here here only then after iterating uh after going to the left of this array we we will the real element is not uh we will check if after the flip it is the sign is flipped or not. Like for example uh here uh when uh when we performed the operation at four we are we have flipped the count equal to one. So we not have to just we will not have to update this array here. We will just check if the count is odd or not. If it the count is odd then we will take the opposite sign of this element and then we will check if this uh this opposites. For example, if there is count equal to 1, then we will take min -5 to 5 and then check if it is positive or not. If it is positive, then again do the operation and then uh increase the counter by + 1.

[00:27:10]Counter equal to two and then check for three. So as the counter is two that means it is flipped twice that means the sign will not change. The sign of three will not change. And so here again it is positive. Here again it is positive.

[00:27:28]Then uh we will do again uh operation the at this position and we increase the counter equal to three. It is odd here.

[00:27:38]So we will again flip the sign of minus2 here and it will be two. Then uh again the two is positive. Then again we will increase the counter equal to four.

[00:27:50]So it will again uh uh then counter equal to counter is even then the sign of minus one will not change. So minus one again here is less than zero. So we will uh stop that stop here not stop here but we will skip this index and go to the next index. So here this we are actually doing here.

[00:28:14]Here we are iterating from right to left and then uh we will uh we are storing that uh element in x and we are checking that if count is counter is odd or odd or even. So if if the counter is odd then we will flip the sign of this element and if the flipped element is positive then we will perform the operation and increase the counter and store the position of that uh store the position in the our answer vector and then uh just output the answer result. So here the time complexity is of n as we are just iterating once and the space complexity is also of n because we are storing the answer in this uh vector. So hope you understood this question clearly.

[00:29:15]Yeah.

[00:29:18]So now let's go to the next part here.

[00:29:25]So in this question this is the same question as C1 but here instead of minimizing we have to maximize this sum.

[00:29:36]So what we can do here uh we are what we are given here this same array A of length n and uh we have to perform uh we we have to choose any i and for a and uh for any j less than equal to i and less than equal to 1 we have to flip a = minus a we have to flip this sign here.

[00:30:05]So and yeah this is the catch here that this ai must be greater than zero.

[00:30:13]So if ai is less than zero we cannot choose negative integer and flip the flip the left elements. If we can we could choose then the same uh the c1 will be the our answer but we are not we don't have we can't do that. So what can we do that here?

[00:30:36]So uh here let's say an example first here for example let's say this one - 3 2 - 1 and 10 1 - 3 2 - 1 and 10. So uh let's say the u let's say the highest number of highest index let's say uh the highest index let's say the answer is here the high let's say high let's again highest index to choose is uh four Here let's say the highest index to choose is four. For example, what this means is this means that in the answer in the answer the num the uh indices which we have to choose uh there are many indices which can we can choose here. But let's say the highest index is four. We can choose here. So the index for example this one four 1 2 3 4 four let's say this one is here which we can choose the highest index.

[00:31:56]So if we choose this index this highest index then we can always make all these uh elements as positive.

[00:32:06]How? Let's say we ch we have to uh in the previous question we we have already seen that we can always make all the elements negative here to minimize the sum we we have already seen that we can make all the elements here and we can make all the elements negative. So before choosing K we can always make before choosing K we can always make all the elements before 1 to K minus one. So before choosing K we can always make always make some we can always make all elements.

[00:33:02]ends from 1 to k minus one all negative we can always say that so let's say if uh if here we we can make here all these negative only so after making all these negative -1 -3 -2 2 - 3 - 2 then -1 then 1 and then 10.

[00:33:39]So now uh after this let's uh uh we have already made all these elements negative here.

[00:33:47]So now we can now if we apply the if we perform the operation at this k position this k position then all the elements before which were all negative will become all positive this will maximize the uh uh the sum which we have to actually find out we have to actually uh get. So now here it will be 1 3 2 then 1 and then 1 and then 10.

[00:34:21]So here what we can see that this if we if the maximum maximum ele index which is to be chosen is k then we can make all the one elements from 1 to k minus one as positive here as negative here and then choose the kth position to make all the positive all the all the elements before it positive.

[00:34:48]Okay.

[00:34:50]Ah wait, we cannot choose here. We I made a mistake here.

[00:34:56]We cannot choose this one because we cannot choose an index where AI is less than zero. So here let's we have just let here we didn't mean to um uh derive answer for this. We just let so this let's say this is five.

[00:35:16]Let's say this is five. We have to we can we can choose this one here.

[00:35:23]The answer what was this question minus one and then 10 then 10. So we can let's say this is five here. Maximum position which we can choose here is five. Then we can make all the before elements as negative.

[00:35:40]So we can make all the elements before as negative here. and then choose 10 to make all the elements before it as positive. So it will be 1 3 2 1 and 10.

[00:35:52]So uh this is was not to solve this question. We uh this uh example with this one not to solve this this we have we just wanted to understand what we can do here. So we just have to find the optimal K for which the answer is will be maximum. So how can we find that optimal k? So we will just iterate from left to right and at each position we will find for example for index for uh last index to be k what can be the maximum sum we can get? What can be the maximum sum we can get? So for each index I from 1 to K minus one we have to sum index sum uh in index AI with positive mod of the AI because we are we will eventually get all the elements from 1 to k minus one as summation of as positive as we can see here we will get some from 1 to k minus one as positive. So we have to make a summation of a i mod of a i plus a k the element a k sorry not plus it is minus because we are choosing the k index so it it sign will be flipped so we will minus a k plus as it is the large highest index we can choose the index from uh let's say it is a which is K which will be greater than K and less than equal to N. We will just sum AJ because the if we choose the maximum index we can choose is K then it will not affect the right elements at the right. So we will just sum the original array. So we have to maximize this one this sum.

[00:37:58]So how can we maximize this? So let's uh we have to just choose the find the maximum k find the optimal k for which this is maximum and then apply the previous c1 question here only because we have to make 1 to k minus one uh negative and then add one element extra uh where we can perform the operation.

[00:38:22]So let's go to the code here let's see two.

[00:38:29]So here we can choosing uh we are taking the input here and we are taking two sum here.

[00:38:37]So what are these sums? Uh the s1 is just uh uh the sum of elements sum of uh original array original array and uh this sum is uh what is s_2?

[00:38:56]S2 is what here is actually is S2. This is this one.

[00:39:03]This one here this is S2 and this is S1. This will be S1.

[00:39:13]So here uh we added the sum. This is the original sum of the array and uh we will take the maximum as someone because if we don't do any operation then the this will be the maximum uh uh then int k equal to minus one this is we initialize the k index to be minus one and we will just we will then iterate this array. So here uh during iterating we decreased the original sum by vi by the current index. So what we did here for example if uh if we take an example here uh let's say uh let's say let's say this one only 1 - 3 2 - 1 and 10 1 - 3 2 -1 and 10 so what is the S1 here s1 is sum of elements -2 + 2 0 then 9 s1 is 9 and uh so uh while iterating let's say we came at this this position here first position then we will decrease the sum s1 minus one uh then it will be 8 because we are choosing kth position here so we will take this sum we will take this one we will while finding the value of this one we will take absolute values of the elements at the left and the original sum from the right and decrease and take the flipped sign of this a1. this one that is uh um we will check we will do uh minus a not for example this s1 minus a z is a1 because this first element will be at minus a1 minus a1 because we will we will flip this uh element here here like here we we did minus ak and then plus we will do the absolute sum of the uh elements at the left. So here we are have no elements at the left. So we it will be zero here. So this at first step at first iteration we will get s1 minus a + 0. What will be this? S1 is 8 s1 is 8 and minus a1 is 1. So 81 - 1 equal to 7.

[00:41:57]Now uh we will do go to second position.

[00:42:01]Then s1 s1 what what what is the s1? s1 is the uh sum of the left right uh elements original elements. So we will decrease we have already decreased the we have already decreased the first element from s1. So we will not decrease the second element. S1 - 3 uh uh actually minus of minus in of minus 3 it will be S1 was 8 so it will be 11 and uh then we will this 11 is the sum of this one and then minus the current element.

[00:42:45]Okay. So we can't choose the negative number. So we will we will just skip that. We will skip that. But uh we will just increase the s2.

[00:42:57]We will just increase the s2 by the absolute values of these these uh elements.

[00:43:05]So here it will be four 1 and then s2 plus equal to 3.

[00:43:13]Okay. Now we will go to the third position only. So S what will be S1 here? S1 equal to the elements here this which was which will be 9. Yeah 9 here 11 - 2 = 9 11 - 2 = 9 and uh then we will do the find the maximum find this sum for this k = 3.

[00:43:44]So it will be 9 minus here 2 2 then uh the absolute sum of these these two it will be uh s2 is 4 so + 4 9 13 - 2 11 so 11 so like this we will just iterate from 1 to n and for and we will see that for for what k this uh for what k this sum is maximum and that will be our optimal k. So that this we are seeing here the s1 which is the original array we are decreasing it at as the iteration is going on and uh we are checking if it is pos if the current element is positive or not. If it is positive then we will just then we can only try the operation. Then we can uh we will check this sum and uh for this sum what we are doing this is the absolute values the absolute sum values which we are updating at each iteration by absolute value of u pi that means absolute value of that current element and then we are decreasing it by the current element because we are flipping the sign of that current element. So here that's why it is minus and then uh plus then adding it by the uh elements the original sum of the elements at the right.

[00:45:21]So and then we we check if the sum is greater than max. So we we initialize this by max and if it is greater than max then we will in update this variable max by sum and the k element by i. So yeah so if k now we will get get the optimal value of k from here. If we didn't gain any k values that means k is still minus one that will initialize here k. So we will just output k equal uh we will output zero and continue.

[00:46:00]And now if we get any K here K from that we will just uh apply the previous code of C1 here. The same here you can see the same is written here. the same code.

[00:46:16]We will just find the num find the indices on which uh we have to perform operation to make it uh all the indices from 1 to k minus one as negative and then uh we will just uh push back the k + one index as uh after the making those negative we will just choose the element k and uh choose we will have to ch also choose the element k to perform the operation which will make the uh elements at the left all positive to maximize the sum. So we will just push back this k + 1 into the our answer vector and then we will just output that. So what is our time complexity for this time complexity is uh obviously often because we are just iterating uh we are not making we are just making one loop for iterating here and uh this space complexity is also of we are just storing the answer here answer vector so yeah this is all for uh the question C2 now let's go to the next question Hey uh let's say let's read this question.

[00:47:45]So what is D here?

[00:47:48]Uh you are given two arrays of positive inteious A and B both of length N. You will perform the following operation exactly n minus one times. So what is the operation? Let m be the current length of a and b. Then length will always equal. So what we are given? We are given two arrays a and b both of both of length n.

[00:48:18]So we can select an integer i which will be uh between uh 1 and m and uh let s with the multis set a i i i + 1 b i and b i + 1. So what we are we are actually doing is let's say a1 a2 a3 a4 and so on. Similarly B1, B2, B3, B4 and so on. So what we can do is we can choose any adjacent pairs here. We can choose any adjent pair like this or like this. And we we have to sort the elements of S such that S_sub_1, S2, S3, S4. Now replace a i ai + 1 with s2 and v i b i + 1 with s3 and more replace a with a1 to a i - 1 and s2 then a i + 2 to a m and replace b with this one. After performing all operations there will be exactly one element remaining in both a and b. Determine the maximum value of a minimum of a1 b1 at any. So what we have to do is here let's say we choose uh this uh for these four elements a2 b2 and a3 b3. So we will uh a2 b2 a3 and b3.

[00:49:54]So what we can do here is we will just sort them in uh sort them and put the uh elements in the middle and replace it by these four elements. For example, if these element if the elements in middle are a2 and b2 let's say a2 and b3 then the uh this uh arrays these arrays will now become a1 b1 then a2 and then b3 then a4 then b4 and so on. So here you can see that uh the number of elements are decreased by one in both the arrays.

[00:50:39]So similarly we can perform these operations. We have to perform this operation n minus one times and after that only one element will be remain remaining in a k in a and b it can be any element let's say k and bp and we have to what we have to do is we have to minimize uh what we have to do is here is we have to maximize the minimum of a1 So we have to maximize the minimum of AK and BP.

[00:51:27]So let let's take an example here. So shorter example for example here it is 2 1 4 3 5 6 2 1 4 3 and 5 6 let's say we choose this one it we choose this one then 1 2 3 4 these are these are these are the on the middle here so it will replaced by 2 3 5 6 then if we choose this one then uh uh after sorting it 2 3 5 6 it will be three and five.

[00:52:06]So here the minimum value is three uh here.

[00:52:19]So here you can see this is the three.

[00:52:23]So now uh so and that's how we have to perform the operation here.

[00:52:29]So what can we do here? Like what approach should we follow here? Because if we um iterate over all the possible ways to merge uh two pairs then we can uh get T or just uh just be in the loop.

[00:52:53]So what can we do actually here? So we what we have to do is maximize this minimum of uh final pair.

[00:53:03]So let's say if we get maximum so let's say if we get maximum value as K.

[00:53:10]If we get maximum value as k then we can always get k minus one because if we get maximum value is k then we can get maximum value is k minus 1 and maximum value is k - 2 k minus 3 because this is the maximum we can get.

[00:53:28]So we can always get this uh numbers lower than that here.

[00:53:40]And if we and similarly if we can't get if we can't get uh an element k if we can't get an element k then we also cannot get k + 1 also cannot get k + 2 and also cannot get k + 3.

[00:54:02]So this u we I have also explained this this type of question in previous one of my previous videos on t that if we are we are having a sometime some type of uh the similar type of problem that uh we have to find maximum value of something and if we can get if we can get the k then we can get k - 1 then k - 2 then k - 3 if we can't get k then we can't get k + 1 also can't get K + 2 also and can't get K + 3 also.

[00:54:35]So for these type of question we generally apply binary search.

[00:54:41]For these type of question we generally apply binary search.

[00:54:48]Now the question is how can we apply binary search here? So let's say uh for binary search let's say we uh put any uh put we check uh we are checking on K here. Let's say for banish we are checking on K. So now for all elements for all pairs here actually we are we are not we will not treat we will not be treating every elements as pairs only.

[00:55:14]Uh so uh for any binary search for checking on K let's say answer is K then how can we check that if K is possible or not? So we can divide the uh we can divide all pairs all pairs as follows pala well first uh let's say the pair have one element both elements greater than equal to k Second uh both elements less than K.

[00:56:03]Third uh one element greater than K, one greater than equal to K and second element less than K. Uh only three types of pairs we will get. Yeah. So let's say this uh this is the larger pair, this is the smaller pair and this is neutral pair. Okay. So what uh what will happen if we choose to mix up these these type of types of pair. So first type of mixing the first type of mixing will be L + L. So what if we mix two pairs whose both elements are greater than equal to K. Then what will we get that if we uh if we sort the those four elements we will always get the medium middle of those elements as both greater than equal to K. So if we mix up two L then we will get an L only if we similarly if we mix up two S then we will get uh S only.

[00:57:09]Third if we get if we mix of L + N.

[00:57:14]So what we will get like greater than equal to K, greater than equal to K plus greater than equal to K and less than K.

[00:57:27]If we sort it we will get less than K.

[00:57:30]Then third all three elements greater than equal to K. So the medium of middle of two elements will be greater than equal to K. So l + n will always get l.

[00:57:42]Similarly s + n will we get s and what if n + n we will get n only.

[00:57:56]Okay. So from here these five types of combinations we can have. So we can from we can see from here that if we combine neutral uh neutral pair into any larger pair we get larger pair only and if we combine neutral pair into a smaller pair we will get smaller pair only and combine neutral plus neutral will we get neutral only. So we can say that the neutral pairs will not affect any of our answer because uh it it is just neutralizing everything.

[00:58:33]And also uh one type of I missed that l + s.

[00:58:41]So what is l + s? less than greater than equal to k greater than equal to k plus less than k and less than k. So if we sort it we will get less than K then less than K greater than equal to K and then greater than equal to K. And if we check the middle elements we will get N.

[00:59:02]So it is also N. So these are six type of combinations here.

[00:59:08]So here you can see that the the mixture of one larger and one smaller pair will we will get a neutral pair and uh the combining neutral pair with any of these uh any of the pairs we will get the same. So neutral pair is not making any difference. So differences difference we will be make uh we will get is from the larger pair and smaller pairs.

[00:59:37]So you can you can also see that the the mixture of larger and smaller will get neutral only.

[00:59:45]So after for example let's say so there are three types of pairs we can divide L S N. Let's say number of uh larger pairs are L number of smaller pairs are S and the number of neutral pairs are N. So uh these these neutral pairs will not affect our answer.

[01:00:10]And uh we can say that the mixture of we can make the minimum number of here we can make minimum number of L comma S as new neutral pairs and add uh and at the end at the end we will be left with whatever the uh maximum of L and S is so if L greater than equal to S uh so if we get L greater than S so like we have to just we have to maximize the uh K we have to maximize the K. So if we get L greater than S that means we have more we have more larger pairs and fine and at final we will get greater than equal to K and greater than equal to K. So both are greater than equal to K. That means we can uh we can increase K. We can increase K and binary search.

[01:01:24]binary search on a number greater than equal to K. Greater than K. That means we will just update the mid element by K and uh the the answer could be K. Answer could be K. And if if the smaller remains these smaller uh pairs uh if the number of small pairs are greater than equal to L then we will just uh uh we then we can't uh that means we will finally get less than K and less than K. That means we have to uh we have to search within that that we have to search in the lower values.

[01:02:10]Search for K in the lower values. So by this method we can always we can get the optimal value of K that the maximum value of K. So let's go to the code here for this question. So we are taking the inputs a and b and just running the binary search from 1 to 2n. uh uh by 2n here uh you can see that the elements are less than equal to 2 into n and that's why only we can also apply the binary search because we are we are we know the uh upper and lower limit here.

[01:02:54]So we will check between 1 and 2n and uh we will check uh update find the mid value then the low value here what are the low here low and high low is the number of small pairs and high is the number of uh I what I is the number of larger pairs and neutral is NT is number of neutral pairs.

[01:03:36]So now we are just iterating from it from left to right and we check that if both are greater than mid. If both the elements in the pair is greater than equal to mid then we will update increase the higher high by one and uh uh this ent is not number of neutral pair. It just denotes that uh if uh neutral pairs are present.

[01:04:14]So if both are greater than equal to mid then n equal to 1 and else if both are less than mid and n is not equal to minus one that means if n is not equal to minus one then we will put n is minus one as we processed just and we just processed a smaller pair. So here we initialize n equal to0 because uh the neutral pairs are present. So uh at at first the neutral pairs will be at present. So new and we'll update if update by the last pair we processed.

[01:05:08]So why we are doing that? Because uh we have to uh we have to merge two adjacent pairs. So we can so that's why we have to uh as we are iterating uh we have to check if uh the what we what the last pair was. So if if it was a larger pair then the ent equal to 1 and if it was a smaller pair and it is not equal to not minus one then it will be minus one.

[01:05:39]So uh and why why is that? Because uh why we are checking if it ent is not equal to minus one because if it was a minus one then it then it can uh then it will be automatically neutralized by the uh I uh so let's better understand it by the by code here. Let's say uh let's say let's say we have pairs like uh large then a smaller pair then a smaller pair then smaller pair then larger pair uh no again a smaller pair then a smaller pair and then larger pair and then larger pair. So if we directly count the number of S and L, if we directly count the number of S and L, then there we have 5 S and uh we have 3 L. So we will just uh put uh we we will just put K uh uh greater than. We will check for k less than sorry k less than uh check for k uh less than element like like uh the next element we check we will less than k.

[01:07:06]So here but let's say if merge these two we will get a neutral pair then again we will merge these two then we will get a smaller pair then again a smaller pair and then again a smaller pair then again a smaller pair then we will merge when we will when we we will merge these smaller pair into L then we will get neutral pair and then a smaller pair but so here we can say that we can see that the final pair is large not smaller So we can we can't just count all smalls and all largers because we have to we have to iterate we have to merge the adjacent pairs only.

[01:07:49]So what we will do that if while iterating if we get a smaller pair before then uh if we get a smaller pair then we'll check if the last pair we got was a smaller pair or not. If we get if the last pair was also smaller then we will skip that because the smaller with smaller when merge with smaller we will get smaller only. So we will skip that part. And uh if the last pair we checked was not smaller then we will just increase the count of smaller pair and uh then update this by the last element the n by minus one. uh to denote the checked pair is small.

[01:08:45]So now by this we will we can we get the count of uh the larger pair and smaller pair. And if the larger pair is greater than smaller pair then we will check for uh we will check for the mod we will check for more more larger key and update this uh l by mid + one and uh if the smaller pair is less greater than larger pair then we will dilute our search search position and we'll check for smaller Okay. And finally we will get the answer and output that we can check it here.

[01:09:30]So yeah this was the uh explanation of this question. This is this was a very good question.

[01:09:38]Hope you uh understood all these five questions here.

[01:09:43]So uh if you didn't if you have any doubt about these questions uh you can also comment down and uh if you can if you can tell that uh where I could improve my explanation you can also comment for that one also and uh if I I mist I made any mistake in the explanation and uh also subscribe to this daily channel and Also hit the like button if uh you liked my explanation. So thank you. Bye.