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

[00:00:03]Hello.

[00:00:06]So today we are going to discuss today's contest which was code forces round 1111 and div 2.

[00:00:19]That's div 2. So we can start now.

[00:00:28]Okay.

[00:00:29]So the first question is zero sum. You are given an array A of length N consisting only of minus one and one.

[00:00:37]You may perform the following operation.

[00:00:39]Choose an index I and satisfying one I should be one between 1 and N minus one and assign a I= to minus A I and A I + 1 equal to minus A I + 1. So we are given an array A and whatever index we will choose these two adjacent index will have we will get reverse sign.

[00:01:09]So and what we have to determine whether it is possible to make the sum of elements of a equal to zero. So let's say an array has uh a1, a2, a3, a4, a5. There are five elements in an array. And let's say we choose uh let's say we choose this element. So the a2 and a3 will have now opposite sign a1 then we will have minus a2 then we will have minus a3 then we will have minus a4 and sorry a4 not and then a5.

[00:01:49]Now what we have to do is uh determine whether it is possible to make the sum of elements a equal to zero. And this array consist of only one or minus one.

[00:02:04]So first we have to find out that if I reverse the sign of two elements two adjacent elements then what we this sum will how this sum will be a factor.

[00:02:16]So let's say we have 2 one. If I reverse the sign to minus1 and minus1, this sum will uh decrease by four.

[00:02:29]This sum will decrease by minus4.

[00:02:31]Decrease by four. Okay. First the sum was +2 then it will get minus2 + 2 to -2 it decreased by four. Now if I have 2 minus one and if the sign change to + one then here the sum increased by four.

[00:02:51]If we have one 1 and 1 minus one and if we change the sign then the sum remains zero. So the sum here the sum doesn't change.

[00:03:07]Now we can see that for any operation for one operation this sum s let's say sum is sum is sum s is either going +4 or minus4.

[00:03:26]So in num in in n operations in many number of operations the sum final sum will be s + 4k s + 4k like if I do it k * + 4 then it will s + 4k it will be something multiple of four sum will change by something multiple of four so and we have to make this zero So here we can see that s= to -4k.

[00:04:00]So if for sum to become zero we have to check that if s is divisible by four or not. So s also must be divisible by four.

[00:04:12]S also must be a multiple of four to make it zero. So we will just check that in this question.

[00:04:20]So coming to the coding part, we will just create an element s which will store the sum and uh ignore this one. This one this was for me and no and now we will just calculate the sum and if it is divisible by four then uh if it is not divisible by four that is remainder will not be zero then it is not possible to make the sum zero and if it divis then it is possible to make the sum zero. So this was the question talking about the time complexity and space complexity.

[00:04:59]The time complexity is O of N and we are not storing anything. So space complexity will be of one. This was the first question.

[00:05:15]Okay.

[00:05:19]Now this is the next question.

[00:05:21]Uh coming to question B.

[00:05:25]So this is next question. Yet another constructive.

[00:05:28]So here we are given three inteious n, k and m. We call an array of a of length n consisting of positive inteious good if the minimum length of an non empty subarray of a whose sum is divisible by m equals k.

[00:05:44]Formally an array A is good if the following conditions hold. Okay. So array is good.

[00:05:52]So an array A is called good if following condition follow. There exist in L and R such that it l between 1 and N and R - L + 1= to K and uh this sum is divisible by N.

[00:06:16]So there must be so when it is called good then if there exist any subarray subarray of length k length k which is whose sum is divisible by m. So this is the first concern for array A to be good. This any the subarray of length K at at any one subar of at least one subarray of length K whose sum is divided by M. So there exist some such subarrays in the array. And the second condition is there do not exist L and R such that R minus L + 1 less than K that this is the length of subarray and it is divisible by M. And there's one more condition subarray of length less than k. If the sub array of length less than k then it must not be divisible by n.

[00:07:34]So there are two conditions here that for array A to be good there are two conditions. There ex must exist some subarray whose length will be k and the sum will be divisible by m and also there should not exist any subarray of length less than k and the uh sum is divisible by m. Okay. So here let's understand this question using an example. Let's say we have k = 3 and m = 10.

[00:08:06]That means in the array we must have sub array whose sum will be sum will be divis divided by 10. So let's say we have 2 3 5.

[00:08:22]So if uh we add all these numbers then we will have get 10 and the 10 is divisible by 10. So it is uh it is satisfying the first condition. Now check for second condition. Sub of length less than K that means less than 3 that means 1 and 2. So let's say we add 2 + 3. 2 + 3 is 5. It is not divisible by 10. 3 + 5 is 8 8 it is also not divisible by 10. 2 + 5 is 7 it's not divisible by 10. And every uh distinct integer here is also not divisible by 10. So it is satisfying both conditions.

[00:08:59]So it is a valid array valid sub ararray. Now let's say now let's say we have 4 6 10.

[00:09:09]So here the sum is 20. The sum is 20 which is also divided by 10. So it is satisfying the first condition. The first condition is satisfied. But check this for the second condition.

[00:09:22]Here 4 + 6 is 10 which is also by 10. So here is this this is a subarray of length two which is also divisible by 10.

[00:09:39]So here it is not a valid array. It is not a good array.

[00:09:46]So this is the question. This is what is written here. Now what we have to find is find any good array A or determine that no such array exists. So we will we are given N k and M and we have to make n size array and which should uh satisfy these two conditions these two conditions which it should satisfy.

[00:10:15]So how to approach this question? So first thing like uh in this example we saw that if m is 10 and if we try to make this sum same as as least as possible because if we try to increase the sum that means if we try to make sum greater than m and divisible by m that is let's say 2 m or 3 m then we can have something uh uh then the sum of some sub arrays between that sub array can be sum up to uh less than uh can be sum up to some integer which is divisible by 10.

[00:11:01]That means here the m was 10 m was 10 and we try to make the sum 20. So here we can get this sum here less than uh the sum here equal to 10.

[00:11:18]Because let's say a b c we have three inteious and a + b + c equal to 2 m then we can have a + b equal to m. There is a possibility of that. We can have b + c equal to m. There is a possibility of that. So we can have something uh uh the sum of two uh sum of smaller subs which can result in divisible by m.

[00:11:46]So we what we will try to do that while choosing these three inteious we will try to make the sum as equal to m only. So then what happens if we try to uh get two inteious here less than of length less than k that means we will uh we will get this sum less than m only.

[00:12:11]So it will never be divisible by it will be never divisible by m. So that's what we will do here.

[00:12:22]Like uh for sum m we will try to make uh here k inteious such that this sum is equal to m.

[00:12:39]So now what uh how will we do that? We will try to make at least sum the least number the least sum. So what we will start with we will start putting one so that we have the sum of smaller such that the sum of a smaller subarrays smaller subarrays won't reach M.

[00:13:13]Some never reach M. So we will have to take care of this this thing. So we'll try to make let's say we have uh we have to make the sum m and we have k let's say we have to fill four inteious. Let's say k equal to 4. So what we will do? We will put three 1 and the last will be m minus uh 3. So here what we do what we did we put put 3 m here and m minus 3 here for the last integer. So the sum is now m here the sum is m which is divisible by m and if we take any two sub subarrays like 1 + 1 is 2 which is less than 2 which is less than m so it is never divisible by m. Here also 1 + 1 will be two it is never divisible by m.

[00:14:08]Now if we sum these three arrays maximum sub array sum will be m minus one m minus one which can never be divisible by m.

[00:14:20]So this is the way uh we will do we will split the array into. So we will take a block of let's say 1 1 1 this k*s and at last we will put m minus k + 1 uh m - k + 1 because we have k -1 into 1. So k - 1 is already there and we have to make the sum m. So we will do m minus k + 1 at the last and we will repeat this till we get uh the n ts.

[00:14:59]So that will be our result that will be our answer output uh for the question. Now there is a catch that what if uh what if m is less uh less than k here uh so what is if m is less than k m is less than k so we have to what is that that means that we have to make k inteious K integers.

[00:15:41]So let's take an example for this. Let's take an example for this. M is three and K= 4. M is 3 and K= 4. So now we have to make a four inteious A B C D such that A + B + C + D is divided by 3 is 3 uh 3K is divided by 3.

[00:16:09]So now we have to also figure out that we have so we have to also take care that sum of smaller subarrays sum of smaller subarrays smaller subarrays must not be equal to must not be divisible by three divisible by three so let's find out for this question this example. So we have four numbers a b c d. So let's say a uh when a will be divided by three then it will be some it will give some inteious uh so there it will give some remainder that while dividing by three we have we can have three remainders 0 1 and two there are three only three possible remainders. So when let's say we divide a by 3 then let's say we will divide a + b then let's say a + b + c a + b + c + d okay so we have three remainders only possible 0 1 and two. So there will be at least two uh integer here at least two uh a a + b a plus b plus c and a plus b plus c plus d. There are four inteious.

[00:17:40]So there must be at least two integer here which have same remainder because we have only 0 1 and two remainder possible. So we can have two we must have two remainders at least same here. So let's say we have this one this number and this number remainder same.

[00:18:03]So this is also three into let's say two.

[00:18:08]Uh okay. So remainder of both are same.

[00:18:10]So if we have two inteious let's say p and q have same remainder same remainder.

[00:18:19]So we can write p = 3k + r and q = 3k 3 uh 3 l + r let's say. So if we subtract these two we will subtract these two then we will get 3 into k minus l. So if two integers have same remainder then the difference will always be divisible by that uh quotient that means here it is three. So here also the difference of these two will be divide divided by three. So if we subtract these two we will get C + D. So here C + D will be divisible by 3. So now C + D is just sub here and the length of sub array is 2 which is less than four and it is divisible by three. So it is not satisfying the second condition.

[00:19:17]So whenever the m is uh whenever the m is less than k due to this thing that uh there will be only m minus one there will be only m minus one remainder possible m minus one remainders possible as for three sorry m remainders possible like here it was three and there are three remainders possible. Uh similarly if we have m then we have m limiters possible and if we k is greater than m then in that k inteious in that k inteious we will absolutely get at least two inteious uh which uh at least a a sub array whose sum will be divisible by m as we saw here because if we try to uh write the prefix sum of every uh big sum of the array then we will have k different prefix sum k different prefix sum and as m is less than k then we will have at least two prefix sum having same remainder and if we subtract this we will get a sub array which will be divisible by m.

[00:20:36]So if m is less than k then the answer will be no we can't create a good array and if uh m is greater than k then we will just do this thing we will replace uh we will do make a block using one and the last element will be m minus k + 1 and we'll repeat this till the nth element of that array. So this is the question uh we can go to the coding part here.

[00:21:09]Uh so we took the input n k and m. So if k is less than equal to m then yes we can we can build the array. We put the last element of the block as n minus k + 1 then we iterate it.

[00:21:25]So if i is divid by k that means uh it is part of a block.

[00:21:32]So we will put one. We will print one.

[00:21:36]And if it is not that means it is the last element of that block. So we will print x. And whenever it reaches the last element we will just uh print this space.

[00:21:52]Okay. And uh when this will end uh we will have there that array as here. And now else if the m is less than k then we can't make a good idea. So this was the question if we talk about the time complexity and space complexity. So here the time complexity is it the time complexity is what we did uh O of N only and the space complexity is uh of one because we are not storing anything. So the space complexity will be of one.

[00:22:35]I hope you all understood this second question.

[00:22:43]So we can move to the next question here.

[00:23:04]Now this is the third question of today's contest. inversion of a subsequence.

[00:23:13]Okay.

[00:23:16]So you are given two arrays a and b of n consisting of only 0 and one.

[00:23:23]So we are given two arrays uh a and b and both consist of 0 and one only. So you may perform the following operation on a any number of times. So we can choose K indices I1, I2, I till I K and uh such that and this sum of all the uh numbers chosen numbers must be odd. In other words, choose a non-impse of A with an odd sum.

[00:23:57]So for each j we can then for the chosen elements we can set a i as 1 minus a i that means we are reverting the sequence that means we are making 0 to 1 and 1 to zero. So we can choose any subsequence any subsequence of some odd.

[00:24:28]Okay.

[00:24:30]And what we have to do find the minimum number of operations needed to transform a into b or uh determine that it is impossible.

[00:24:39]So we have to find number of operations to per transform a into b. So first we will have to find out that what is the difference between a and b. That means if a is 1 1 0 and b is 1 0 0. So here we have to choose subsequence of a such that the sum is the sum is odd and we can reverse that. So here what we can do we can choose this one and uh the sum is one here sum is odd and uh so we can reverse it here we will get 1 0 0 1 0 0 so here we take only one operation so now what we will do so but how to solve this question so the first condition is that so The first condition is if first we will check first we will check uh how many numbers like how many indices are Hello.

[00:41:37]I was muted.

[00:41:55]Okay.

[00:42:08]So when I got disconnected like hello. Yes.

[00:42:39]Okay. So I can explain it one more time this case. I hope.

[00:42:49]Um, so in cases like I will explain I got muted around uh 10 minutes before.

[00:43:31]So I will just uh recap everything uh in fast maybe. So what is the question here? The question here is uh so the array has 0 and one. There are two arrays as uh of consisting 0 and one only. And the operation is what oper the operation is doing that we can we can choose a subsequence where sum is odd and uh then we can uh revert all of the 0 into one and one into zero. So here the main thing is this sum must be odd. So what we did what we did we counted some uh we counted some parts here like we counted that indices where x a is 1 and b is zero and we named it at x10 and we then we counted the indices where a is 0 and b is 1 and we named it x01 and also we had to count x0 and x11 also we will know why uh why we counted that.

[00:44:46]Now if x10 is uh x10 is what? It is uh it is the uh it is symbolizing that uh the one is in a and zero is in b. So we have to obviously change this x10 change this x10.

[00:45:11]So if x10 is odd, we can take all such all such indices and make a equal to b. a equal to b. Uh like here uh like here there are three uh 3 x10. Here the x10 is 3. x01 is 2. So we can uh here this is the x01. So we can take all five uh indices at once because the sum will be three and it is odd.

[00:45:48]It is odd. So we can put take all the five indices at once and uh apply that operation. So it will be one operation only. So the answer will be one. So if x10 is odd then the number of operation will be one. And if x10 is even if x10 is even then we have we will split it into two odds like if the x10 is two we will split it into one and one and do the operations on both separately. So it will take two operations.

[00:46:26]Now what if x10 is zero? What if x10 is zero and x01 is not zero. That means we have we have just x01 here. So we have to revert we have to make the uh both arrays equal. So we have to revert 0 to one. So now in order to revert 0 to one if we choose this array as subsequence only then this sum will be zero which is even the sum will be zero which is even. So we must have at least one uh one one one in this array.

[00:47:08]So what we will do we will destroy one matching array that we destroy one correct array such that in this uh in this array we will take this ind index uh and so we have to make one one one here in the a so let's say we have here it is 0 0 0 so we we will have to take one one here we will We have to make a one one here because in order to apply the operation we need at least one one.

[00:47:46]So we have to make one one here and how can we make one? We have to uh revert this 0 to one. So we have to put choose one zero here which is correct. And in order to apply operation on zero we have to choose one correct one also. Why?

[00:48:04]Because for this operation for this first operation we will need one also because to apply operation we will have to have this sum as odd. So we have to take this one also and this correct zero also. Then if we choose if we revert these two index what we will get? We will get this one. We will get this one.

[00:48:28]Now here we can see that x10 is 1 and x01 is three. So now we can just repeat this one. Repeat this. So here x10 is odd. So now it it can be converted to a equal to b in one operation only. So how many total operation it took? One operation here, one operation here. So now this is the final part that if x10 is greater than zero, then we'll check if it is odd or even. If it is even then it will take two operations. We will split the even into two odds and if it is odd it will take only one operation.

[00:49:08]And if it is zero then and the if x10 is 0 and x01 is greater than zero. So we have to convert this all zero to one. So what we will do?

[00:49:22]We have to check if the correct zero and correct one are how many they are correct zero and correct one. So both must be present in order to make the array equal. So if both are present here then it will take two operations. If any one of them is absent then it is not possible to make the arrays equal.

[00:49:48]And uh now the code here. So we made the variables the four required variables then uh updated the variables x we counted all these four things and checked if both are not present x10 and x01 that means the arrays are already equal so it will take zero operations. If it is odd then it will take one operation. If it is not odd that means it is even then it is take two operations. If it is neither or nor even that means it is zero and if both are present there correct zero and correct one are present then it will take two operations. If it is not present then it will take it can't be both arrays can't be equal so it will print minus one and here time is space complexity of n as we are iterating only one time and we are storing array of size n. So this was the C question of today's contest.

[00:50:55]Now we can move to D.

[00:51:08]So this is the last question of today's session. This is Z sorting the easy version.

[00:51:18]So here we have no queries.

[00:51:23]So the for an array B of consisting of M positive inteious define F of B as follows.

[00:51:30]For a non- negative integer K, we can say that B can be K sorted if it can be sorted in non decreasing order by performing the following operation any number of times.

[00:51:43]So we can choose two indices I and Z such that Z of I and Z will be less than equal to K. So we can choose two indices I and Z that the Z is less than equal to K. Not the condition apply to indices I not the elements. So the condition is in on the index and then if it if this condition satisfies we can swap the elements BI and BJ. So the value f of b is defined as smallest non negative integer k such that b can be k sorted.

[00:52:18]Okay. So dur using these swaps using these swaps we have to make the array sorted. We have to sort the array.

[00:52:29]We have to sort the array.

[00:52:33]So now we have to you are given an of the q + one states of a here q is zero though so we don't have to take care of the updates on it. So we just have to find the smallest k smallest k that the array can be sorted.

[00:52:55]So now what is the meaning of zord first? So what is zord? Let's say we have 1 0 0 1 1 0. So if we do the zord of these two integers then zord is so uh if both are the both set bits are same then the zord operation makes it zero. If both bits are different then it will make one. So here it is same zero it is one and it is zero.

[00:53:33]So the z uh this is the zord. So let's say if k= 1 if k equal to 1 that means the z a z or b a z or b is equal to 0001 a z or b is 001 that means the bits in a and b is different on the first place.

[00:54:00]the bits in A and B is different on the first place and same on the list other places. Okay. So here let's say A is 1 0 1 0 1 and then B can be 1 0 1 0 0 only. So here uh if we start from one then 0 0 0 uh 0 then 0 0 1 these will uh these two uh integers these two index will have z equal to 1.

[00:54:42]Now if uh we come later then 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 these two are different at the last uh the first place on first bit only. So it will also have a Z equal to one. So it is another set another block.

[00:55:01]Now we can change we can take any of any number here any set bits here any bits here just if the last if the first bit if the first bit is different only the first bit is different then the zord equal to one but that that is that's what the zord is here so if zord if k is one that means zord is 001 one and one. What does one means?

[00:55:33]One means that the a and b are different at first place and the same at other places.

[00:55:42]So it uh for this for for k = 1 we have blocks of size two.

[00:55:52]We have blocks of size two that means 1 2 here uh 1.12 is 0 comma 1. It uh uh it comes at uh it is first block then 2 three it is at first block 2 and three it is two and it is three then four five it is first the next block then 6 7 it is the next block so that's what uh we will do now uh if this As for k equal to 1. Now if let's say k= 2. k= 2. So a or b is what is two here? 0 1 0.

[00:56:54]So here if k equal to 2 the zord can be less than equal to k. That means the zord can be zero. These are can be 0 comma 1 comma 2 because here here it's not written k it's written less than equal to k. So if k is two then it can be the zord can be 0 1 2.

[00:57:20]So what does it mean? It means that it can be either 0 0 0 the z can be either 0 0 1 and it can be 0 1 0. So either all must be same, all bits will be same or only the first bit is different or only the second bit is different.

[00:57:41]So let's say we have 0 0 0 then if the first bit is only first bit is different only first bit is different then we will have 0 0 1.

[00:57:56]Then if we have only second bit different then we will have 0 1 0.

[00:58:01]Now if we apply this uh apply this uh z on this number on this number and if we uh if we take if we take only first with different then it will be 011.

[00:58:21]If we apply if we z this with this then only first bit is different then it here the zord will be one only so it is valid. Now if we apply first bit different on this uh on this number then also we will get okay if we apply the second bit different on this number then we will get 011.

[00:58:48]So it is also valid because the Z of these two the Z of these two will be two. So it is also valid.

[00:58:56]So here you can see if k= 2 if k = 2 whatever the previous bits are the first two bits 0 and one first two bits can be anything can be anything for k equal to 2 like 0 0 it can be 0 0 it can be 0 1 it can be 1 0 it can be 1 one there are four cases and the rest previous bits can be anything. Uh and this bits previous bits must be same and this next the last first two bits can be anything.

[00:59:38]So it makes a block of four numbers four consecutive numbers 0 0 0 1 1 0 and 1 1. So here in the previous k= 1 for k equal to 1 we had uh blocks in the form of 0 1 then 2 3 then 4 5 then 6 7. Now here we have blocks of 0 comma 1 comma 2 comma 3 as first block.

[01:00:05]Then the 1 comma 2 comma sorry four then five then six then seven as second block and here here what is the blocks here? What why am I creating these blocks?

[01:00:28]Because here the numbers in this block is interchangeable in is swipable.

[01:00:39]It's swappable.

[01:00:41]Why? Because we just saw that if I z is less than equal to k then we can swap b i and bj. That means if let's say we have 3 0 1 2 in this index uh let's say in the first index it is uh uh let's say the array starts with uh 9 7 uh 10 2 this array starts with and something later then this is the first zero index one index two index three index And now if k = 2 we can swap any of this because what are these these four index with this these four are 0 0 0 1 0 0 1 0 and 0 1 1. We can swap this with this because the zord of these two are one. The zord is one. We can swap this with this.

[01:01:52]because uh the here we we have 0 1 and here this Z is 011.

[01:02:02]Okay. So we can't swap this with this because here 0 1 1 is three. Okay. But we can swap this with this. Here the Z is here the Z is 0 1 0 that means two. And we can swap we can swap these two because here zord is here zord is 0 0 1 that means one here three is greater than two is that's why it's not allowed here. So if we cancel this with this, this with okay let me change the color. If we cancel this with this and this with this and this with this then we can also swap this with this with this indirectly. We can also swap this this with this indirectly and we can swap anything. We can arrange these four the numbers in these four indexes indices in any order.

[01:03:07]That's why we are making these blocks that we don't consider uh we we will always consider these blocks as sorted.

[01:03:17]We will always consider these blocks as sorted. The numbers in these blocks blocks are always sorted because we can always swap in all the inteious in this in each block. You can always swap all the inteious in this block. Similarly, we can always sort all inteious in this block also because this is nothing but uh whatever we were doing with here all zeros.

[01:03:44]We are just doing the same thing here for one 1.

[01:03:50]Here it is 0 0 then 0 1 then 1 0 then 1 one.

[01:03:55]So it the same thing will be applied here. So we can swap any of these numbers here also.

[01:04:02]Now similarly if we have k = 3.

[01:04:06]So for k = 1 we had blocks of two uh numbers. For k = 2 we had blocks of four. For k= 3 we will have blocks of 2 to the^ 3 that means 8.

[01:04:22]So in the first block we will have 0 to 7. Then second block we will have 8 to uh 15.

[01:04:31]and so on.

[01:04:35]So now what?

[01:04:38]So now what this actually says us uh what was the question?

[01:04:46]The question was to find such smallest k such that this array can be sorted. So what we will do and what is this constraints here? What are the constraints here?

[01:05:00]Uh the numbers can be till 10 ^ 9.

[01:05:06]The numbers can be till 10 to the^ 9.

[01:05:12]So what we will do the 10 ^ 9 the numbers are 10 to the till 10 to the^ 9 and the uh blocks like if k if we the if if the number k is given then we have blocks of size 2 ^ k 2 to the power k and uh the 10 ^ 9 it's is almost equal to like 2 ^ 18 or 2 ^ 19 the 10 ^ 9 is almost equal to 2 ^ 18 or 2 ^ 19 so at most the so if let's say if k is 18 then we have 2 ^ 18 uh we have 2 the^ for 18 elements in one block and we can always sort that. So the number can't be greater than can't be this K can't be very large. This K is maximum to maximum it will go till 18 or 19.

[01:06:27]The maximum K it will go till 18 or 19.

[01:06:31]So we will just for safer place we will take the max K as 20.

[01:06:38]So what we will do we will iterate from k = 1 to 20 and check that if the array is sorted or not. And how we will check now? Then if then what we will do?

[01:06:58]We will split the array into the 2 to the power k elements like this. We will split the array into the power k elements uh in the one block like this.

[01:07:10]And what we will do? We will find maximum and minimum in each. Let's uh uh let's draw this here.

[01:07:20]Let's say K is let's say K is three. Uh let's say K is 2. Then we will have 0 1 2 3. Then we will have 4 5 6 7 then we will have 8 9 10 11. So now these all these inteious in these blocks are already sorted. already sorted. We have to find out if we uh write the inteious in the same order it will be sorted or not. So what we will do? We will find min uh max of this array and minimum of this array. So if max is less than min then of course uh this is sorted. If max is less than equal to min then it will be sorted. And similarly we will find max and min max of this uh this block and minimum of this block minimum of this block. So then we will check if max is less than equal to main. If it is uh true then uh the array is already then these two blocks are already sorted. If it fails at any moment, what we will we will just increase the k and we will try with larger blocks.

[01:08:43]And at any k if we find that all are sorted all the max is less than equal to minimum of next block then we will uh output that k print that k. So that is the approach for this question.

[01:09:08]So let's go to the coding part. Here we have N and Q. Q is uh one here. Q is zero here. No updates.

[01:09:22]And we took the vector V.

[01:09:25]Then we have we have boolean uh to check if it is uh like uh if it is already sorted or not.

[01:09:35]So let's say if we while taking the input of the array we are checking if it is already sorted or not. If it is already sorted then there are no we will just k equal to0 is we will output zero. We we don't require any k.

[01:09:53]So the minimum will be zero and we will continue to check next uh next test case.

[01:10:00]So here we have answer which is the K and uh we have uh this okay will tell us if it is uh if it uh is sorted or not for this K. So we are just iterating from 1 to 1 to 20 and uh the gap the block and the size of blocks is the 2 to the^ i here.

[01:10:31]So it be calculating the size of the block. Then we are iterating from iterating in each block uh at rating for each block and finding the the uh this is uh iterating block by block. We are iterating this block by block. So that's why we are taking this gap as the the size of block as the increment.

[01:11:02]So we are uh for each block we are finding one maximum. We are finding the maximum and finding the minimum. If the minimum of the next block this this minimum of next block.

[01:11:18]So if the maximum is greater than minimum then uh if the maximum is greater than minimum then it's not sorted because we have something like in this thing here. If maximum is greater than minimum then we have something some element in this block greater than some element in this block greater than minimum of this element in this block.

[01:11:53]So we have so it is not a nondereasing it's a decreasing so we have something greater here. So it's kind it is not sorted. So we will just uh put the answer zero and just break it.

[01:12:09]So now if it is one if the it's true then we will put the okay as true and the answer will be k 2 ^ i I minus 1 okay and uh we will just break it because if the k is if we have some k then we have 2 to the power k blocks so the actual is 2 to the uh the k will be 2 to the power i minus one.

[01:12:40]Okay. And now uh if it's true, we will just output the answer.

[01:12:47]So that's what we will doing we are doing here.

[01:12:52]Uh hope you understood the approach and uh if we talk about the time complexity here the time complexity is this is uh 21 then uh this is n and then iterating in each of these. So it uh it will take and then also we are iterating in each of them. So it will take O of N login and the space complexity is O of space complexity what we are storing we storing the vector only.

[01:13:36]So it will take O of N space and so this was the approach for D for D1.

[01:13:53]For D2 we have I think we had some queries some updates and uh we have to output uh the smallest K for each update. smallest K for each update.

[01:14:09]So what I think we can do there is like uh uh we can uh we can use segment three tree for that for that part but I was not able to solve it correctly so I can't uh explain that uh uh clearly. So what I can give a hint that uh that will require segment trees and for each update we have to find we have to find that where actually where we are breaking this uh this sequence here this sequence here actually at what places we are breaking that sequence and uh how will it affect the k how will it affect the k so we have to think about that in the D2.

[01:15:08]So this was the this was for today's session.

[01:15:13]I hope you all understood all the four questions. If there is any doubt you can uh write in comments I will try to reply that.

[01:15:27]So okay let's end this stream.