Sorting on TRIE | Codeforces Round 1111 | Video Editorial | ABCD1D2

[00:00:04]Okay, I think I'm live now.

[00:00:07]Can anyone confirm if audio video etc looks good and then we will get started.

[00:00:24]Hello Okay, by the just let me just put one port.

[00:00:36]How many problems did you solve?

[00:00:46]And let's see what the problem destination is.

[00:01:03]Okay. Yes.

[00:01:08]Do Okay. Yeah.

[00:01:11]Do last contest everything. Hello.

[00:01:14]Hello. Hello. So I think Okay. I forgot we have seven problems. So like the options are a 1 2 3 I am counting D1 as four and five six as the at least one of the remaining parts.

[00:01:39]By the way, like do install my code forces Chrome extension like you can find all of my editorial easily there and do join in my telegram channel like where I post early updates on when I'm going live.

[00:02:05]So and like can anyone confirm if audio video set looks good and then we will get started. So this is where we are. So tips to increase rating after 1200 like you can join the discord server and there you can check road map to red in 2 minutes channel there I have addresses for all the levels actually.

[00:02:25]So let's just wait for a couple of more minutes and then we will get started.

[00:02:32]Yeah.

[00:03:01]Okay, let's go.

[00:03:04]Like I did write E but did not try solving it because I spent most of my time on D2N and still could not manage it. My solution was around N login also.

[00:03:14]But yeah, so the goal is we will definitely discuss A B C D1. I will also check what are the other people's solution for D2 and then there we are let's get started so it says you are given an array of length and consists of minus one and one you can perform following operation on a any number of time choose an index i and satisfying i between 1 and n minus one multiply a i and a i + 1 by minus one determine whether it's possible to make sum of elements equal to zero And it's like all the elements are between one and minus one.

[00:03:54]So actually it's a bit tricky one.

[00:03:58]But the problem statement is as follows.

[00:04:03]If we have numbers a a1 up to a n.

[00:04:10]We can take any two neighboring elements and multiply them by minus one.

[00:04:18]and can we make sum zero?

[00:04:23]So like the crux of the problem is since we know that each ai is one or minus one we can try to analyze cases of ai and a i + one.

[00:04:34]Both of them can be minus one. One of them can be minus one.

[00:04:43]This is how the numbers in starting will look like.

[00:04:47]And after you multiply by minus one, the numbers change to this.

[00:05:00]Here the sum of these two numbers is minus2.

[00:05:04]And here the sum is two.

[00:05:07]Here the sum is zero.

[00:05:10]Here the sum is also zero.

[00:05:14]Sum is zero. Here also sum remains zero.

[00:05:20]Here the sum was two. Here the sum becomes minus2.

[00:05:25]So you can see like overall the numbers sum changes from -2 to 2, 0 to 0 or 2 to -2 and if I have to put it in the form of delta here I would say like the sum increases by +4 here sum changes by zero and here sum changes by minus4.

[00:05:53]So on each operation either you can increase the sum by four keep the sum same or decrease sum by min.

[00:06:01]So this means like we can and what we need is all element zero or or actually we need sum zero right sorry then this can happen only if sum is a multiple of four and pretty That's the solution. Okay, sum is a multiple of four. If it's a positive number, you can keep subtracting 4 4 to reach zero. Or if the sum was negative, you keep adding 44 and it will give you zero.

[00:06:49]And this is would be the overall solution for probleming.

[00:06:54]Take sum of all the elements and if some it's some divides four we are good otherwise we can leave and yeah like it was the first problems.

[00:07:36]And this is actually the first problem for us.

[00:07:43]Any questions? Anyone on the first problem?

[00:08:08]So this was the first problem actually.

[00:08:13]I will move in order A, B, C, D. Like I am directly not jumping over here like be mindful that even if you were able to solve A B C like many people were still stuck on the remaining problems.

[00:08:33]So this was problem A. Any questions anyone on problem A?

[00:08:40]like one last call otherwise we will move on to the next problem.

[00:08:48]Okay, then let's move on to the second problem.

[00:08:52]It says you are given three inteious n, k and m. We call an array a of length n consisting of positive integers good. If the minimum length of non- empty subarray of a whose sum is divisible by m equals k. Formally an array is good if the following condition holds true.

[00:09:07]There exists integer l and r such that r minus l + 1 this is the length of elements from l to r and sum is divisible by m and there does not exist any l to r such that the length is less than k and sum is divisible by m.

[00:09:24]Find any good ar or determine that no such array exists.

[00:09:29]Okay.

[00:09:31]And so essentially the problem statement says we have to construct an array A such that we find at least k consecutive numbers such that their sum is divisible by m and if I look at all the sub areas which are which has length less than k then their sum should not be divisible by m.

[00:09:52]So like any ideas of how we can do over here.

[00:10:13]So like the crutch of the idea is like whenever you have to deal with subarray sums the first thing that's helpful is look at prefix sums.

[00:10:36]Whenever you hear this word, you should immediately strike prefix sums.

[00:10:46]For those who don't know what prefix sum is, the idea is like let's say if we have numbers 2 3 4 1 3. Let's say this is your array. Then we call prefix sum such that pi is sum of first i numbers.

[00:11:16]So if you don't have anything sum is zero. If you just take two the sum would be two. If you look at three the sum would then element would be 2 + 3 5.

[00:11:26]If you have to go for the next element the sum would be nine. Sum of these three elements.

[00:11:32]Next element sum would be sum of all four numbers which is 10. Sum of all these numbers 20. Sum of all these numbers 23.

[00:11:42]And the idea is if you want to know the sum of elements from let's say L to R what you can do is you can take sum of elements from first to R and then subtract sum of elements from L to L minus one.

[00:12:06]essentially sum L up to R is equal to sum 1 up to R minus sum 1 up to L minus one like you can see why this holds true right you have to take numbers from L to R you first took numbers from like for the elements which are between 1 to L minus one you took them and you remove them so only L2 R remains straight so this gives us an idea okay we can keep numbers like and which in turn becomes prefix of first R number minus one prefix of L minus one.

[00:13:21]Can anyone see like can can everyone see like why sum of numbers from L to R will be equal to sum of first R numbers which is R element in the prefix sum minus sum of L minus one which is L minus one up to L minus one element in prefix sum like can anyone see like why this equation holds true like this is would be one of the most important equation for Okay, what I'm saying is let's first whenever you hear something like subarray sum or something always think of prefix sum first. The way we define prefix sum is I element is sum of first I elements and when you have this then sum of elements from L to R becomes sum of first R elements minus sum of first L minus one element.

[00:14:22]So any questions anyone so far here? If not then we will pick up the next piece on the problem.

[00:14:39]So now if you have some L up to R mod M if you take then it becomes P R - P L - 1 mod M right and if this is zero Then the overall equation actually becomes P L minus one equal to P R model like essentially the remainder you have for L minus one is equal to the remainder you have for R.

[00:15:32]So this is where we are. Now what I will do is I will first generate PI mod M these values.

[00:15:54]Then based on these values I will try to figure out pis and based on pis we will try to figure out a and like essentially we will fix what are the different values of pi minus pi mod m for the prefix array. Then based on that we can fill this array in some way such that those equations holds true. And then based on pi we will also fill in a and what I am claiming is this value will always be between 0 to m minus one right because like anything mod m is always between 0 to mus.

[00:16:49]Now let's try to fill in the unique values here.

[00:16:55]First I am claiming is whatever array we choose.

[00:17:11]We cannot have k greater than m.

[00:17:16]The idea is as follows.

[00:17:21]Let's look at AM over here. Sorry, PM over here.

[00:17:31]And all the values here P 0 up to PM minus one.

[00:17:43]If all of these values are equal, these values are unique, then all the numbers from 0 up to m minus one appears here.

[00:17:58]And whatever we have over here will actually match with one of these.

[00:18:08]Or if the values here are not unique then you know that you have found two same divisor over here.

[00:18:15]Or another way to look at is like if you look at zero up to PM we have m + one numbers and all the values are between 0 up to n minus one.

[00:18:39]And these are m distinct values.

[00:18:47]You have n + one numbers but only n possible different values.

[00:18:59]So you must have two numbers equal.

[00:19:08]have two equal numbers.

[00:19:13]And whatever would be the subarray for those two numbers that will have some divisible by m between those two numbers.

[00:19:34]Some would be divisible by any.

[00:19:43]And this is how you should look at it like can anyone see like why we cannot have K more than M.

[00:20:03]If we choose m different numbers, if we choose m numbers, then we must have one sub array among them such that their sum is divisible by m.

[00:20:14]The reason for that is they will have m + one different values for pm and you cannot have and if you have only m distinct values then one of the value must repeat over there.

[00:20:33]Like actually this is the important part over here like should I repeat once again or like did everyone understood that if you have m different numbers then you must have some subarray in among that such that sum is divisible by m.

[00:20:55]We cannot have an m different number s with us and none of the subar that has some divisible by m.

[00:21:13]Okay. If it repeats how it's divisible by let's go over the previous part again. I said sum of numbers from L to R would be if I look at the prefix sum then that would be difference of number at R and difference of number at L minus one.

[00:21:37]And if sum is divisible by M then the number if I take everything mod M then the number at L minus one will be equal to number at R.

[00:21:54]If I look at prefix sum, if I divide everything by m then the if the sum of numbers from L to R is zero when divided by M that means L L minus 1 and R will be equal element at L minus 1 and R will be equal.

[00:22:16]So with this I can confirm that whenever I have two equal numbers in the prefix sum then whatever subarray those two numbers correspond to their sum would be divisible by m like can you see why like this comes from the equation of how those prefix sums are divisible by m and now I say like I will first work on all the prefix sums mod m only and then I will populate all are the remaining numbers. First I will try to fix the values mod M and yeah okay first I will try to fix values mod M then I will fix PI and then from that I will also find here.

[00:23:02]Now I am saying if I have M different numbers then I would have M plus one different values in the prefix sum. P 0 is always zero and what I'm saying is if all the these M plus values and if all of them are between 0 to M minus one because that's the value of the remainder then we must have two equal values. It's also known as pigeon hole principle.

[00:23:30]Pigeon hole principle.

[00:23:37]Like the idea is if you have m different containers and if you have m plus one pigeons then numerous keep at least two pigeons in the same container then only you would be able to put everyone somewhere.

[00:23:52]And when the moment you found two equal numbers in the prefix sum, you know that sub array that correspond to those two numbers will have sum divisible by m.

[00:24:02]So this gives us an impossible case that k cannot be one.

[00:24:07]Like k cannot be more than m.

[00:24:12]Now how do we solve for the how do we find a first? If k greater than m this means answer is minus one.

[00:24:29]Now my idea is as follows.

[00:24:32]Let's first put pi mod m values.

[00:24:38]We can fill in those values like this. 0 1 2 3 4 up to k minus one.

[00:24:48]All of these are unique here. and then again fill zero 1 2 up to k minus one and so on.

[00:24:58]If you fill it like this, then if you choose any two elements at a difference of K like sum will be divisible by M.

[00:25:21]I'm saying like this is how we keep prefix sums.

[00:25:26]If this is my remainder for the prefix sums, then whenever I choose any two elements that are at a distance of K, those two values would be same.

[00:25:36]So like overall sum would also be divisible by and if you choose any two numbers that are at a difference less than K, they cannot be equal in this way and their sum will not all will not be equal either.

[00:25:52]First we fix prefix sum like this.

[00:25:56]Then what we can do is let's call this RA.

[00:26:06]Then we can put P I simply like this I into M plus RA.

[00:26:16]So if you take this value mod M you will get RA and all of these values would be increasing.

[00:26:32]And once you have all the pi, you can find all a which would be equal to pi minus pi minus 1. Like essentially the sum of i number is equal to a.

[00:26:49]And this was actually the solution. And this is how you should actually be looking at it.

[00:27:01]So this was actually the proof for this.

[00:27:03]Any questions anyone?

[00:27:15]First if k is greater than m the answer is directly zero.

[00:28:09]Let's take an array of length.

[00:28:40]This way you can find here and then you can print all the values of here.

[00:29:02]Any questions? Anyone?

[00:29:29]Like Yeah. So like now people have recognized that they can also print 111 musk + 1 111 m k minus one. Yeah that will actually this solution can also give you that as well.

[00:29:45]So this was problem B.

[00:29:49]Any questions? Anyone like do react something so that I can know okay we can move to the next problem.

[00:30:20]And yeah, I realized that someone had some question on problem A as well.

[00:30:25]Okay. Like why does sum four works actually.

[00:30:34]So like the idea is first even though you have operation that a i and a minus one should be changed we can translate it to you can change any a and a r by minus one.

[00:30:53]The way this operation can work is as follows. You have a l a + 1 a + 2 a r - 1 a r.

[00:31:07]So in the first operation change these two numbers.

[00:31:11]In the next operation change these two numbers. In the next operation change these two numbers. Keep you keep going like this.

[00:31:21]Then you will change numbers here.

[00:31:26]And you will change here. And what you can notice is a l and a r are multiplied by minus one.

[00:31:36]All the numbers in between are multiplied by minus1 and then minus one.

[00:31:40]So they remain same.

[00:31:43]So this way you can change any two numbers and once you realize this you can see that if you have to decrease some by four keep changing 2 1 into minus one and keep going or if you have to change add four to it just pick any to minus one and keep multiplying them by one.

[00:32:02]So that is how you can construct the array which the piece that I missed in the problem A. Any questions anyone on problem A and B? If not, we will move on to the next problem. Just give me 2 minutes. I will be back. And let me know if you have any questions on A and B.

[00:33:29]like any questions anyone on A and B? If not then we will start the problem. So let's go.

[00:33:45]Hello. Hello.

[00:33:49]Hello. Hello. Hello.

[00:34:00]Hello. Hello.

[00:34:03]Am I audible?

[00:34:09]Hello. Hello.

[00:34:11]Okay. Let's go to problem C then.

[00:34:16]inversion of a subsequence. Yeah. So it says we are given two arrays A and B of length and consist of zeros and ones.

[00:34:23]You can perform following operation of A any number of times.

[00:34:27]We choose all the indexes.

[00:34:32]We choose K indexes such that sum of those K indexes is odd and then we change all of them by minus one. Like essentially we change 0 to 1 1 to zero and we have to find minimum number of operations required to change a into b or we have to say that it's impossible.

[00:34:55]So the problem is like this.

[00:34:58]We have been given an array which consist of zeros and ones.

[00:35:03]We have been given an b which consist of zeros and ones. We have to change a into b.

[00:35:10]All we can choose is we can choose a subsequence with odd sum and invert them.

[00:35:30]Essentially 0 becomes one, one becomes zero. Any questions anyone on the problem statement itself?

[00:35:40]Like the hint I have is answer is less than equal to two if it's possible otherwise it's impossible.

[00:35:52]And how do we solve this?

[00:35:54]Like this is actually few of the cases only and each of the case you will try to figure out.

[00:36:04]When can the answer let me ask you this when can the answer become be zero if a is equal to equal to b.

[00:36:22]There is no other way to have zero operations and make everything one.

[00:36:29]Now the next question is when can the answer be one?

[00:36:45]The answer can be one if we can fix all the incorrect numbers in one operations.

[00:36:54]If we can fix all the incorrect elements in one location.

[00:37:12]So the idea would be we take all the elements where a i is not equal to bi take their sum and if that sum is odd we are good and this is the only case when we can have one operation right okay the arrays were not equal. You looked at all the elements and if you can in one operation you can change all of them then only you can make the answer in one otherwise I will say that you can always fix in okay we can always fix in two operations or the answer is impossible.

[00:38:19]And the idea would be as follows.

[00:38:22]Let's for now first forget all the correct elements.

[00:38:37]Change this here you have to change either to 0 to 1 or 1 to zero and we now know that sum is even if the sum was odd you would be able to do it in one operations so my idea would be as follows let's say all operations we have to things.

[00:39:28]Let's say these are the changes you have to make and the pieces you have some numbers in between and everything is okay.

[00:39:44]Then what you can do is sum of these elements is even right.

[00:40:01]So let's just skip one number.

[00:40:12]If I skip this then the sum of remaining elements is odd.

[00:40:17]So you can fix that in one operation.

[00:40:20]Like in one operation you can change these and this first operation.

[00:40:33]and you do second operation for this.

[00:40:42]This way you can solve for this problem.

[00:40:44]Okay. If sum of changes is greater than equal to two then you can if it was odd you can do it in one operation. Now if it's even then I am saying leave one element apart and change everything because even minus one would be odd and then in one operation you also fix the even number.

[00:41:11]Now sum of the numbers cannot be zero.

[00:41:13]Some of the numbers cannot be one.

[00:41:16]So what it remains is only 0 to 1 changes are required.

[00:41:28]Like this is the only remaining case that we haven't solved so far.

[00:41:33]What all cases we have solved so far?

[00:41:45]First if a is equal to b we are simply done we don't have to do anything. So now we know that we have to handle for the cases then when you have to change something I am saying try to change all the in different elements in one operation that you can do if sum of the numbers is odd. So that's operation one. Now you are left with the cases when at all the places you have to change the sum is even.

[00:42:14]Then I am saying if sum is even then if sum is greater than equal to two then you can leave one element apart a you can leave leave one element aside and you can change everything else and in the next run second operation just change one element.

[00:42:33]So now you are done with the cases where you have sum odd is also gone. Sum even is also gone if the element sum is more than zero. So now you are left with sum equal to zero. Sum equal to0 happens when only type of operation you have is from 0 to 1.

[00:42:58]And here like I would say like the answer is impossible actually or let me see if we have cases here.

[00:43:18]Okay. Yeah. Like I believe this case will never arise.

[00:43:50]Okay, I do have this case as well.

[00:43:56]Okay, D odd is given some even is gone.

[00:44:04]Okay. Then I'm claiming key like now you have cases like this 0 to one.

[00:44:14]Now you cannot only get away with this as an operation like you need at least one.

[00:44:27]Every time we do an operation, sum is odd.

[00:44:40]This means we have at least one and that one changes to zero.

[00:44:47]Right? Every time we do an operation, we need to change at least one index where one changes to zero.

[00:44:57]because you have some odd and sum odd means there is at least one one in that array and when you invert it that one will become zero.

[00:45:09]So like your array is like this you have to change some zeros to one.

[00:45:21]These are the only things you have to change.

[00:45:26]you have numbers like this and so on.

[00:45:35]So my idea is let's use one of these one to one use this to change all the other elements.

[00:45:49]So what I'm saying is choose this subarray and change it first. So this change one will become zero.

[00:46:02]But how do we then change this one zero back to one?

[00:46:10]Because now if you choose this also for the operation then this will also be changed. So I'm saying don't just do this.

[00:46:20]Take one one to one and 0 to 1 pair. 0 to 0 pair.

[00:46:29]Invert these as well.

[00:46:37]So if I look at this array, let's take this as a sub area.

[00:46:50]This will become one. This will become one. This will become one. This will become one. This will become one. This will become zero. This will become one.

[00:47:02]And here then you take this and this again. This one will become again zero.

[00:47:10]This zero will become again one. And we are done with two operations again.

[00:47:18]And if you don't have a 0 to 1, a 0ero to0 and 1 to one pair then the answer is impossible and these are the enough and sufficient cases. I haven't yet proved the because if you only have zero to zero pairs, you can convert those zeros to ones and then one to zero again.

[00:47:49]But you also need like you why do you need both of these? You need a 1 to one like that's the only case remaining because you need sum as even sum as odd.

[00:48:01]So this becomes a must have condition and if you have only one to one then every time you do an operation you will change one one to zero and you cannot be in the final state where like every time when you change a one to zero then after you are doing done with some operations you will definitely have a zero somewhere in your array.

[00:48:25]So and you can match that zero only with the place where you need a zero in the B as well.

[00:48:32]Okay. If B does not have a zero then you can never get that error.

[00:48:43]Or another way to put is like this.

[00:48:47]Okay. A should have at least one one otherwise you cannot get you cannot even do an operation and B should have at least one zero and these are the only sufficient conditions for you. If you have these two then you can definitely make elements equal. If you don't have this then you cannot make elements equal and you would be able to do it in two operations. I have showed you the way out.

[00:49:29]So these are your cases.

[00:49:32]If a and b are equal you simply divide it by zero.

[00:49:42]Now you look at the elements sum of the elements where you want to make a change.

[00:49:49]If that sum is odd, you can do one operation. Sorry for if sum is greater than equal to two, you can break it into two operations and you are done.

[00:50:13]A has one.

[00:50:20]We need to change check these two only.

[00:50:46]If both of these are true, then you would be able to make them equal in two operations adjint minus one. And this is all we have for problems here.

[00:51:02]Any questions anyone?

[00:51:09]The reason for these two is because you need whenever you are doing an operation you need some odd.

[00:51:16]So if you do not have any one in the array then you will never be able to even think of an operation and because you have a sum odd and that means you had at least one one in the array. So after you are done with the operation that one will become zero. So every time you do an operation you change one of the one to zero. So if B has all the ones then you can never reach that state either.

[00:51:41]So that's why these two are the suffic necessary conditions and then you can try to figure out on how you want to do these two conditions and this is actually problem C.

[00:51:53]Any questions anyone on problem C?

[00:52:07]Like guys do react something so that I know that we are done with this or if you don't want to even do this condition.

[00:52:28]If a and b are equal, you simply print zero. Otherwise, you know that you need at least one condition.

[00:52:36]So, if a does not have a zero, print minus one simply.

[00:52:49]If B does not have a zero, print minus one. Otherwise, see if you can do one operation or not.

[00:52:55]If you can't that if you can do one print one otherwise print zome this would be even more simplified way to do it.

[00:53:10]How to solve case word questions quickly without failing any test case edge cases like the only way is try to solve more problems which involve edge cases and here what we have done we have looked at the all the exhaustive cases we started with generic K and B then we said okay if there is a case like this then the answer will always be one then we removed that out from the world of problems we want to Look at then we checked if the operations we want to make has some more than equal to two.

[00:53:45]Then I was like in such cases also we can split it into two and we are done.

[00:53:52]Now when you throw that case out as well then all we are left with is some of the elements where we want to change become zero.

[00:54:00]And now you see like what are the other possible elements there like you need to definitely play with different cases try to make observations and you need to ensure that you all your cases cover all the possible cases you can have in input like that's the only way you can solve for all the edge cases.

[00:54:23]Any questions? Anyone on problem free?

[00:55:01]So this was problem C. Any questions anyone?

[00:55:05]If not then we will move on to problem D.

[00:55:21]Okay, it says this is an easy version of the problems.

[00:55:25]The only difference between the versions is that in this version Q equal to zero.

[00:55:30]Note that zero base indexing is used. We are given an array B. We define f of b like first f of b as we want to make array b sorted and we f of b as the smallest element k such that we can sort b. The condition is we can swap an index i and j only if their jaw is less than equal to k. And note that this applies on the indexes not the elements that we are swapping.

[00:56:12]So what the problem statement says is we have to find the smallest index k smallest element k such that if we are allowed to swap elements indexes i and j such that their jar is less than equal to k then we would be able to sort the array and like that's all we need for the problem d1 like there are no updates or anything we can ignore the remaining Essentially we are given an array B.

[00:56:53]We need to sort it and we can swap index i if there is less than k.

[00:57:06]Now we have to find smallest possible k Like the first possible idea is we only need to bother about K which is a power of two.

[00:57:39]That's the only case we have to bother about.

[00:57:43]For example, if you have k = 16 or k = 17, the set of elements we can swap will always be remain same.

[00:57:56]like how you can do it like let's say we have to swap I is dot Z which is 25 let's say I want to swap it I can say I can swap it using 16 only like if I look at in the largest power of two which is less than equal to 15 would be 16 so So I'm saying I can swap it using 16 only. For example, let's take these elements. We have to swap an index two and an index 27 would be let's say I have to select 2 and 29. 2 and 27. Let's z of 2 and 27.

[00:58:57]Two like looks like this and 27 looks like this. 16 + 8 + 2 + 1 and 2 is here.

[00:59:13]What I am saying is let's take the element 16 as well.

[00:59:21]Let's use this 16 to swap the elements.

[00:59:27]Let's say this is X, this is Y, this is J.

[00:59:33]If I first have 16 and 27 not 16 I would say let's pick 18 like the idea is like let's swap by ignoring the first bit itself the remaining part here is actually what do you have 11 right let's first swap A 27 and A1.

[01:00:16]You have this 2 11 27.

[01:00:21]Here you have A2. Now you have 8 27. A 11 over here.

[01:00:28]Then you swap you remove one more bit from here which is 8.

[01:00:42]You swap these two numbers again.

[01:00:51]The zor of 3 and 11 is eight only.

[01:00:54]Earlier the zor we took was 16.

[01:01:03]You have index 2 3 11.

[01:01:08]Elements you have is A2 A 27 A3 A1.

[01:01:17]Now you swap with two and three again.

[01:01:19]Here the Z is one.

[01:01:22]You'll end up with A27, A2, A3, A1. And then you can go in reverse again.

[01:01:31]Again 3 and 11 where the zor is eight. You will end up with a 27 a3 a2 a 11 and then you swap 11 and 27 again.

[01:01:50]You will end up with a 27 a3 a 11 a2.

[01:01:56]Now 3 and 11 are at the same position.

[01:01:58]You ended up shopping 2 and 21 A2 and A27 using Z 16 8 and one.

[01:02:17]So all I'm saying is like you just need the largest power of K that you would need a swap for and with 16 you would be able to do it and the way you figured out was if you have to swap 2 and 27 then there is 25 just pick the largest power which is get less than equal to 25 and that's all you need K for any questions anyone so And like this holds true for even for 17 like you don't need 17 like if whenever you need a swap for 17 first swap using 16 then one then again 16.

[01:03:04]So like this gives us an answer that k is a power of two.

[01:03:12]Like if you allow difference up to 16 then technically you would be able to swap all the jaws which are from which involves the bit at max 16.

[01:03:29]So you would be able to swap between 0 to 31 everything.

[01:03:34]Because when you have 16 available, you also have eight available as a zor, four available as a zor, two available as a zor, one available as a and you can look at any permutation.

[01:03:46]Okay, how can we swap 15 and 16 as the zor is 16? Good question actually.

[01:03:54]Let's say we want to swap a 15 and a 16.

[01:03:59]Then you know that we have numbers from a 0 up to 15 and 16. Right?

[01:04:04]In the first operation, swap a 16 with a z.

[01:04:12]You have a6 here.

[01:04:16]A5 here at the 16 index you have a z.

[01:04:19]These two will have z of 16.

[01:04:25]Then you can swap 0 and 15 in one go.

[01:04:28]You can go with 0 8 12 or things like that but I'm keeping things simple. 0 and 15 has a zor of 15.

[01:04:38]So you here you will have a 15. Here you have a 16. Here you have a z.

[01:04:46]And in next operation again you have zero and 16.

[01:04:52]You have a z again. A6 here a 16 here.

[01:04:57]So I would even go on to say like even if you don't want to look at the powers of two if you have 16 then first time you do an operation with Z 16 second time you do an operation with whatever the remaining pieces and then you do with 16 again. So see here you were able to change element at 15 and 16 using a zero.

[01:05:24]So how did you figure out that only power of two would be required? I did figure it out but it was just an obsession going through all the multiple values of K. So actually the idea is as follows. We have something known as Z basis which says like this.

[01:05:45]Okay. If you have a set of numbers B1, B2, B3, B4, let's say, then what are the possible Z?

[01:06:00]All possible Z using a subset of these numbers.

[01:06:16]like I am going a bit more general let's say rather than saying less than equal to K is allowed I have some fixed jaws only only those are allowed and I'm saying that B1 B2 B3 and B4 only these four possible Jaws swap is allowed okay if the zor is either B1 B2 B3 B4 then if I am allowed to swap then I am I would be able to swap all the differences where the zor can be we can obtain using some set subset from these numbers.

[01:06:57]only four types of operation where I is or J is either B1 or B2 or B3 or B4 because the operations are revertible then also I will be able to swap all possible solve that I can obtain by this by subset of those number they enabled by choosing some subset and that's all how I That's what I realized first and then I realized that choosing a power of two is the simplest and smallest possible set of elements I can get for all the possible source like now I can choose this B1 as powers of two those are the simplest number and using powers of two I can form all the numbers because you know how the binary works right so that's how I came up with an obser all I need some operations using a powers of two and I if even I am allowed to swap any two numbers such that they have zor which is a power of two then also I would be able to swap all the possible numbers and once you realize this then you can see the magic around we can swap all the numbers by using just powers of two and then you need all the powers of two like look at what all swap you need and pick the largest power of two.

[01:08:56]So this was the first level of observation here.

[01:09:01]Now what we can do is we have A with us. We also have B with us.

[01:09:10]So the idea would be sort A to find for each air which BJ8 lands to.

[01:09:32]Once you know all of this you know that after some series of operation you need a swap now we need to move I index to J by some sequence of operations and I am saying it would be possible if we are able to swap I and J at some point in able to swap I and J then we would be able to do it at some point in time. So look at I Z J find the largest power of two and we are done.

[01:10:31]So this was actually problem D1 where you we did not have any queries.

[01:11:01]So like essentially I'm trying to figure out what is the sorted order of the indexes.

[01:11:16]Now I figure out the maximum value.

[01:11:40]We know that I element is idxm.

[01:12:21]If I = to J then we don't even need a cell.

[01:12:43]This way we can find the largest power of two which is less than the Z and we can take the maximum power we have gotten to solve for D1.

[01:12:58]This way we are done with D1.

[01:13:06]Any questions? Anyone?

[01:13:11]Like I have around analog and solution for D2 but the time limit of 2 seconds was way too tight.

[01:13:23]Any questions? Anyone?

[01:13:43]I think we are done with D1. So, at least we are done with all the problems that I could solve in the contest.

[01:13:49]I will briefly see what people did for D2 and see if I can explain those ideas and my remaining content in optimizing D2 only.

[01:14:21]Where's Nothing.

[01:15:51]Not sure what Zeron did over here.

[01:15:58]What is this guy doing?

[01:16:12]I'm interesting.

[01:16:19]Interesting. Any questions? Anyone on D1? Otherwise, we will go for D2.

[01:16:36]I was using std sort complexity was n login but sort was too slow.

[01:16:45]Can you please explain again how many different zor can come from a b c d. I think we have something known as zor basis.

[01:17:00]Like you can check here on how this works. It's kind of like linear algebra only.

[01:17:08]Like essentially I if I have a b c d then using these four numbers I can get all the possible zors I can get by taking some elements from it. If I need to to swap two indexes which are zor of a and c then I'm saying I would be able to do it by just using a and c like if I have a and c then I can swap indexes with different indexes with different c and that's also the reason why I can swap indexes which is also the zor of a and c as well. The idea would be first swap with difference one then difference C and then again with A.

[01:17:53]So this was actually D1. D1 D2 is actually a bit more interesting.

[01:18:16]Any questions? Anyone so far?

[01:18:24]The problem is you have D2 again, but this time you have an update here.

[01:18:33]And that's the only difference between D1 and D2.

[01:18:39]So when we did not add updates, what we simply did was we looked at what the sorted error would look like. We looked at all the possible swaps we need and we were done.

[01:18:56]How do we solve for D2?

[01:19:06]Like I would say shout out to Zaron the solution I just looked at.

[01:19:11]That's actually much easier to explain.

[01:19:19]So we we can solve this. Let's look at it this way.

[01:19:26]Can we sort using swap with k = 2 ^ 16?

[01:19:42]Let's try to answer this question and it will make things easier for us.

[01:19:50]We can swap with actually 2 ^ 4 let's say which is 16.

[01:19:57]This can happen only if all the S we need is either between zero to like let's bucket numbers that have the same Z less than 15 0 to 15 16 to 31 32 to 47 48 to 63 and so on.

[01:20:27]Let's look at all the elements all the which have pairs of Z less than 16 because I'm looking for can I sort elements between two with 2 ^ 4 or not.

[01:20:36]That's what I'm trying to if I have this restriction then I can swap independently between all the numbers from 0 to 15 because if you take any two p elements their Z would be less than 16. I can also swap between 6 to 16 to 31.

[01:20:54]I can also swap between 32 to 47. I can also swap between 48 to 63 and similar buckets here. But if I have to move something from 16 to 15, then the answer would be no.

[01:21:10]Like if I have to swap across these buckets, let's say from 47 to 1, I won't be able to do it using 16.

[01:21:23]Does this make sense for everyone? Like are they able to see you? Okay.

[01:21:30]If my K is 2 to the^ 4 which is 16 then I would be able to swap between all the numbers from zero like these would be the blocks. I can swap numbers arbitally in the same block but not outside those blocks.

[01:21:50]Like are you able to see like that's the only thing we can do over here.

[01:21:58]Now if you have this observation then what do you have? Another more question like if you look at maximum in this from 0 to 15 should be less than equal to minimum from 16 to n.

[01:22:25]That's the only case when no number after 16 will come to 15 or I would put it this way.

[01:22:39]Okay, if I look at this block then technically it means like this block is less than equal to this block, less than equal to that block and less than equal to that block.

[01:22:48]That's how this block should be finally placed in my sorted array.

[01:22:55]Like in my sorted array initially all the numbers should be consist of numbers from 0 to 15. Then the numbers should consist of 6 to 31. Then it should consist of numbers from 32 to 47. Then it should consist of numbers from 48 to 63 and so on.

[01:23:21]So and this can happen only if maximum in this range is less than minimum in this range.

[01:23:31]0 to 15 is less than equal to minimum of 16 to 31.

[01:23:38]Maximum of 16 to 31 is less than equal to minimum of 32 to 47.

[01:23:49]Maximum of 32 to 47 is less than equal to minimum of 48 to 63. These should be your condition right like these are the important conditions then only the numbers will not can you see like if I have this condition maximum of 0 to 15 less than minimum of 16 to 31 maximum of 16 to 31 less than minimum of 32 to 42 maximum of 32 to 47 less than minimum of 48 to 60 if these conditions hold true then I never need to move across the boundaries Any questions? Anyone?

[01:24:31]Can you see if these conditions hold true then only the elements will not move outside those blocks?

[01:24:39]And this is how your sorted array would also look like. Right?

[01:24:46]Here this would be the minimum. Once you sort it, this would be the maximum.

[01:24:52]This should be the minimum. This should be the maximum.

[01:24:57]This should be the minimum. This would be the maximum. This would be the minimum. This would be the maximum.

[01:25:04]So if the edge case holds here, we are good. If the edge case holds between these two, then we are good. If it holds between these two, then also we are good.

[01:25:18]Any questions anyone? Like can you see like because you we can swap arbitrary in this blocks. The minimum of this block will come here. Maximum will come here. Minimum will come here. Maximum will come here. Minimum will come here.

[01:25:30]Maximum will come here. Minimum of this block will come here. Maximum of this block will come here. And the whole array would be sorted. If these two are correct, these two are correct. These two are correct.

[01:25:44]Any questions anyone so far? Like this is the important idea and once we have this we would be able to solve the remaining pieces as well.

[01:26:08]Now let's add infinity to a to make length power of two.

[01:26:25]Then how will the segment array look like?

[01:26:31]First would be like let's say it will denote blocks from 0 to 127.

[01:26:40]Then the next element will denote blocks from 0 to 63 and 64 to 63. 64 to 127.

[01:26:56]Then you will have 0 to 31.

[01:27:02]32 to 63, 64 to 95, 96 to 127.

[01:27:22]Then you will again have 0 to 15.

[01:27:31]60 into 31.

[01:27:34]Here you will have 32 to whatever is the value 47 then you will have 48 to 63 and similar blocks here.

[01:27:54]So now if you are able to swap within here then when you go for this element the maximum of left part would be more than minimum of right part max like essentially for all of these elements maximum in left sub tree should be less than equal to minimum in right sub tree.

[01:28:44]This sounds accurate, right?

[01:28:46]Because if you are able to share between all the elements from 0 to 15 these parts then whenever you go up left part maximum and left part would always be more than minimum and right part and that should go up to all the numbers up to the root and this is a critical observation.

[01:29:12]So what you can maintain is in the segment total elements, minimum and maximum and the answer you have found by swapping these elements. Answer for this units.

[01:29:43]Then what you will do is if the left sub tree is less than equal to right sub tree only update minimum maximum and if we require swap update answer with the zor from these subarrays.

[01:30:25]with Zor with power of two for this one for this sub tree.

[01:30:39]And that's all you need to maintain for each segment for each child you need minimum maximum so that you know when you match it with the right sub tree what whether you need swaps between those sub trees or not and for each element denote what's the answer you have if you have to just look at that range. So now if you have to move some element from right sub tree to left sub tree update your answer with the power of two you have for the complete node otherwise you are done and this is all you need extra over Okay.

[01:31:48]Oh, I need a headquarter library.

[01:31:59]like rather than segment I would also say look at it as a trial like by making length as power of two like one thing I want to say Look this segment as a try.

[01:32:37]You have this node. If you have zero in starting, you go on left side. If you have one in the starting, you go to the right sub tree. Again, you add zero. You add one zero one.

[01:32:55]If you add zero in the bits, you go for the right side.

[01:33:07]Segment is also try if length is power of two.

[01:33:18]If length is 2 to the power k some k 2 to the power l for some l.

[01:33:28]Now you know if you have a sub tree of size 25 in the array 20 sub tree of length all the sub trees of 16 can keep your array sorted then that's your answer.

[01:33:43]We are using sub tree but technically we are maintaining a try here.

[01:34:30]We imported segment.

[01:34:51]minimum maximum length and answer.

[01:35:06]Minimum is well, maximum is well, length is one, answer is zero. You don't need to swap anything over here.

[01:35:22]Now the empty is like you can put minimum zero, maximum zero, length zero and power zero.

[01:35:33]How do you merge two elements?

[01:35:38]If length is empty, return right.

[01:35:45]If right is empty, return left.

[01:35:50]Otherwise, return.

[01:35:56]If left maximum is less than equal to right minimum.

[01:36:11]Then result dot answer is equal to maximum of L.

[01:36:17]R dot answer.

[01:36:22]is left length plus right total length Otherwise you need this much.

[01:37:06]We return a rest here.

[01:37:26]Huh? Headquarter segment.

[01:37:33]Yeah, this We update the value at index i and we again print the answer for all those.

[01:38:19]And this is actually problem data.

[01:38:24]Awesome.

[01:39:17]Not sure what is the issue here but let's say if left is empty then choose the right one.

[01:39:31]If right is empty choose the left one.

[01:39:43]And this is actually problem D2 like that segment is how we implement it. But look at it like a try.

[01:39:58]So this is problem D2. I haven't really spent time on problem E and F because most of my time was spent on problem D2 only. So this wraps up the stream for today.

[01:40:11]If anyone has any question do let me know. If not then I think we are done.

[01:40:19]So thanks a lot for everyone for joining today.

[01:40:33]Wait, this is also getting a T like honestly man I can't do much over here if N login is a T like this is also So analog and solution now if they are expecting me to optimize more on the segment then I think I won't spend more time on it like even in contest submission also like the solution was n login only but that okay I looks like I chose 32 bit let's try 64 bit as well but yeah like anal login solution is there and I cannot optimize more on this and forcing it with 2 seconds and numbers up to 1 six. I don't know why problem setters did this but yeah m contest solution was also and login something different from segment I discussed the segment way because I assumed like zeron got an AC so everyone will get an answer Okay, people say E was much easier than D2. It's possible that like I haven't really read the remaining problem. So let's wait for this to get an AC and yeah like do like share subscribe and if you have any questions or like do let me know in the comments as well.

[01:43:22]Let's see what folks have to say on the announcement for YouTube.

[01:43:30]Okay, this one actually got an AC in 1 2 3 4 seconds on even like I don't know what folks are expecting but yeah like I believe my cont solution in contrast was more implementation away from this one.

[01:44:37]It was again an login only but yeah not really So yeah this was all we have.

[01:44:53]So in the contest I was mostly optimizing my end login solution only and that never got any. So thanks everyone for joining in today and this wraps up our stream for today. Thanks a lot.