AtCoder Beginner Contest 457 | Video Solutions - A to G | by Anish | TLE Eliminators

Ajouté : 2026-05-10

[00:00:00]Hello everyone. Today we are solving problems of adder contest beginner contest 457. So let's start. The first question is given here. Uh you are given a sequence a a1 a2 a n of length a n after add an integer x between 1 and n and we have to output the value of x. So what we are given? We are given uh uh an array for example 1 2 3 4 and then an integer is given which will be between 1 and n and we have to value of the we have to output the value of a x. It's just a straightforward question uh which uh in which we have to just output the value of x. One thing we have to take care about is that this is this array is one indexed. So we don't we can't store it in like the way uh from zero index.

[00:00:48]So we have to store it uh starting from one. Let's go through the uh code of this.

[00:00:56]Uh so here just uh the we uh we build a vector of size n + one because we are storing from the ind from index one and uh just we are taking the inputs and uh then outputting the value required value.

[00:01:15]So now let's move to the the second question. So in the second question we are given n sequences. In the previous question we were given n integers. In this we are given n sequences and the length of each sequence is li and ai is a i1 ai2 till a i li. After that inteious x and y are given and we have to up to the value of a xy basically this is like a 2D vector.

[00:01:42]So what we are given let's take a look on the constants here n is less than 2 10 5 and uh length is also 10 less than 10^ 5 and uh the values are less than 10 3. So these are the standard constraints. So don't have to care about uh long long integers or integers.

[00:02:05]So uh what input we are given? First we will be given uh an integer n.

[00:02:10]Then we have given n sequences and first uh the first uh input of the all the sequence we will be given the length of the sequences. For example, let's take an example. For example, here here we have given three n equal to three in which we have means we have given three sequences.

[00:02:30]First sequence is uh of size three. size three and then we have given uh the value of these uh numbers inteious in the sequence. So the values are 10 20 30 and uh the second sequence is of length 1 one and the values are 7. In the third sequence, the length is four.

[00:02:56]4 and the values are 5 6 7 8 5 6 7 8.

[00:03:03]And what we have to output? We have to output the inteious uh wait a second.

[00:03:12]Uh we have to output the integers three and four. 3 4. So we will go to the third uh third row and go to the fourth column. So this is the uh uh integer we have to output. So how will we write code for this? This is just a 2D vector.

[00:03:28]So we can uh build a 2D vector uh a let's go through the direct go direct to the code. Uh here is the code of this that question.

[00:03:40]We will build a 2D vector and uh then for each vector we are we will be uh taking input of the length of the sequence uh uh for uh this. And one more thing here is that is the vector is one indexed. So we will we have to take care about that. So in the code we are starting from the one and then taking the input of the size of the sequence and we have to then resize the uh all the corresponding vector to the size we are given and uh then we are taking the input of the uh uh current sequence and we have to just output the uh uh value of a xy just a normal way to output uh the inteious uh contents of a 2D vector.

[00:04:27]So this is a this is also a very straightforward question. So now let's go to the third question.

[00:04:34]The third question is named long sequence. So let's uh read out the question first. Uh we are given uh two inteious n and k and along with we have given n in interior sequences a1 to n and the length n interior sequence c1 to cn. The length of interior sequence ai is li and a i is a i1 to a i. I need to guarantee that one is less than equal to k like k will lie between one and the sum of the uh sum of the sequences into the ci.

[00:05:06]So what this actually means is that the k will lie between the total number of integers and one.

[00:05:15]So we see it it's similar to the previous question.

[00:05:18]It was also a 2D vector where the first input was the length of sequence and then the integers of the sequences. In here also we are given an n and then in the n sequences here with first input as the length of the sequence and then at last we are given c1 c2 till cn which is the uh let's read out the next question. Construct an integer sequence uh B which will be having B1 B2 till B uh summation of till B summation of CI to LI from A and C using the following procedure. Let B be an integer sequence of length zero. So we have to build B in B vector which which is the size zero currently and for I equal to 1 to N uh in this order perform the following operation. do this ci* app and a i to the end of b. Okay. So what we actually have to do that for example let's say let's take this as an example. So we have a sequences a we have three sequences. The first the first sequence have size three and the inteious are 1 2 3. The second sequence have size one and the inteious are three. The third sequence is of size two and the inteious are 4a 3.

[00:06:41]And this CI vector is 1 3 2. So basically we have to build a B vector.

[00:06:49]So we are building a B vector where we have to copy the corresponding uh sequence uh into C times. For example, here is the first sequence.

[00:07:01]Uh for example, here is the first sequence.

[00:07:04]This is the C vector is C for the first sequence is one one. This for C vector for the second sequence is three and the C vector for the second sequence is two.

[00:07:16]So what will be our V vector? Our V vector will be uh we will write uh the A1 this is A1 this is A2 and this sequence is A3.

[00:07:29]We will write first A1 then uh A1 into 1*s because c equal to 1. Then we will write a2 into three times. A2 into three times and we will write a3 into two times.

[00:07:43]A3 into two times. So what will be our uh uh output vector of b? uh 1 2 3 uh this these are a1 then uh 3 * a2 that means 1 1 3 * a2 and then 2 * a3 so we will uh repeat the a3 two times 4 3 4 3 so and what we are uh we have to output we have to output uh the uh what do we have to output the kth integer the kth integer of the uh vector b which we have found. So here what is k is equal to k equal to here it is 9. So we will count till 9 1 2 3 what 4 5 6 7 8 9 and we have the answer four. So in this case the four is uh four is the answer. Uh we can check it out the answer is four.

[00:08:47]So how will we write it in code uh efficiently? So let's uh check out the constraint first. So we can see that uh the uh the li summation of li like the length of the sequences is less than equal to 2 into 10^ 5 and the uh the uh integer integer vector elements are have constant 10^ 9 and ci is also 10^ 9 and k will be the summation less than equal to summation of ci li.

[00:09:20]So we can handle this uh k as the blocks as uh we can check like the whether k will lie in the uh with in which in block of which sequence. For example in this in the first question we will check the uh we will check how many elements does uh the block of a a1 have. For example a1 had had three elements. So a1 will have three elements into how many times a1 is repeated? It is repeated only one time. So A1 a block A1 will be have only three elements. Now how many elements does A2 block have? A2 block have uh 1 into three because it's repeated three times. It is also have three elements. And how many elements does A a3 block have?

[00:10:08]And the A3 block have 2 into 2. 2 into 2 4. So the K equal to 9.

[00:10:19]K equal to 9 will lie in which block. So we will check whether the we will first calculate the uh number of elements in block of A1 and then if the number of blocks in the uh A1 is less than equal to K then it will uh it won't lie in the block of A1 because it will pass through the block of A1 and then go to A2. So we will just skip that and we will decrease the K by the number of elements in the block of A1. So now we will have k equal to 6.

[00:10:51]Now we will check whether it is uh less than equal to the block of a2. Number of elements in block of a2. So no here the number of elements in block of a2 is only three and the k equal to 6. So we will again decrease the k by three. So now the k equal to 3.

[00:11:08]Uh so now we will have we have k equal to 3 and we will go to the block a3. So a3 block have four elements.

[00:11:15]So is k less than equal to four? Yes. So the k will lie in the so we have we have found out that k will lie in the block of a3. So uh so we will we don't know we know don't have to uh check for a1 and a2. We will only check for a3. So let's uh understand the next part uh from the code only.

[00:11:38]Uh this is the long sequence code.

[00:11:41]uh we will build a 2D vector and uh write right uh just as the previous question we build the 2D vector as the first we will took the length of the sequence and the build then build the sequence. Now we we have the vector C which was which was given the repetition of the all the sequences in 2D vector A and then we are checking the block like uh for example here uh the we have given K we have to check K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K K will lie in which block. So uh we have given block which will which is calculating the length of the sequence and the repetition of the sequence. So the the block of this the number of elements in the block will be the multiplication of the both integers.

[00:12:26]So if k is less than equal to block like if k pass through the block like k is greater than block then we will just decrease the integer k by the number of elements in the block and we will continue checking for the next block.

[00:12:40]But what if k is less than equal to then we will we have found out that k lies in the current sequence li. So we will just uh output that uh for example here what we are doing uh we are doing now we can check that uh for example uh in the B vector where here here B vector uh the length of the sequences is sequence is 4 3 4 3 and we have K equal to 3 K= 3 so now we have three and the four elements of this block A3. So we will count out the third element 1 2 3 4. So third element is four. So we will output four. But how to handle this thing? For example, if we have we would having uh 4 3 4 3 repeat equal to four. Let's say the repetition was equal to four and we have we would have k equal to uh 3.

[00:13:42]Let's say k equal to 5. So we will just count out the 1 2 3 4 5. the answer would be four. So what we are doing actually so the uh size of the sequence a3 is two. So we are just uh we don't have to check out on these uh these k uh sequences where we don't uh the k doesn't lie on because it is repetitive.

[00:14:07]We can just uh divide k by the length of the sequence and take out the remainder for uh the for getting the value in uh optimal time.

[00:14:18]So here what what was the k it was five and if we divide it by length of sequence which is two we will get one.

[00:14:26]So we will just check on the sequence 4 three and the first index will be the answer. So uh let's go through the back to the code here. Uh we we are checking the k minus one. But why will we do did k minus one? Because uh we are taking from zero index. So we have to uh uh evaluate using k minus one here. And we will divide checking the remainder using the uh length of the sequence and then just outputting the value and once we get the value we will break from the loop and the answer is uh accepted. Uh here you can see that.

[00:15:03]So now the third question is completed.

[00:15:07]Let's uh go to this fourth question.

[00:15:11]So now uh what is the question here given? Huh? So the question here is raise minimum. What is the problem statement? Let's read out it. Uh you are given a sequence a a1 to a n of length n and integer k. You can perform the following operation between 0 and k times and uh what is the operation? So first write out what we are given the array a from 1 to n and an integer k and uh how many times we can uh uh do the operation.

[00:15:44]Choose any integer i between satisfying uh one i less than equal to 10 and I add i to a i. And so what we can what we can do like uh uh if we have given an array 1 2 3 uh 5 then we can do the following like uh we have we can uh transform ai to ai plus i.

[00:16:11]So for example if we choose the this index uh we then uh the uh index will be 1 2 3 and the ai plus here i is equal to 4. So here the new sequence will be 1 2 3 9.

[00:16:27]So we can do this operation uh till uh between 0 and k times. So what is the question actually?

[00:16:36]Uh here you can uh see that observe that uh that uh once we go further like uh once we go ahead of the uh array a the difference in the uh difference in the integers by operating this uh by doing this operation is will be greater because the i will increase as we go to the right of this sequence. So it was just an observation. Uh let's say if we need that in the question or not. Now uh what is the question given? Find the maximum possible value of minimum AI for the sequence after the operation. So we have to find find out the maximum possible value of minimum AI. Like we have to maximize the minimum of this array. For example currently the integer is array is 1 2 3 5. So what uh the we first uh have in the mind that we will just put out the check the minimum of the value of minimum of the array a and uh then increase it. Um for example here 1 2 3 5. So if we put uh if we choose the first index the new add will be 1 + 1 then 2 3 5.

[00:17:48]Then next we will choose the minimum of the array which is two. So we can choose either. Then uh if we choose this one then again the minimum will be two. Then we have to choose this one. And then I repeat the process till the uh maximum till we get the maximum minimum.

[00:18:04]So but here check out the constraints.

[00:18:09]The ai is less than equal to 10^ 18 and the n is less than equal to 10^ 5 and k is less than equal to 10^ 18.

[00:18:18]So we can do 10^ 18 uh operations and uh for the maximum value we can check that it is too large. So if we if we do like this uh the check the minimum and increase them one by one we can have something like limit ex or memory limit ex.

[00:18:38]So we can't do this. So we have to uh check out some other method.

[00:18:44]So uh what we have we can observe here that that uh if we can uh like for example if the let the answer is x let the answer is x. So what is the x the minimum maximum of this uh sorry maximum minimum of the sequence the uh we have to maximize the minimum of the sequence.

[00:19:03]So if we maximize the minimum of the sequence 2x for example if we make uh the uh minimum minimum element of the sequence bx they can then then we can also make the minimum of the sequence x - 1 we can also make this minimum of the sequence x -2 and because we are adding one like we are we can uh uh we can increase the sequence we can never decrease the elements of the sequence we can always increase the sequence. So if we can reach out to the maximum x then we can also reach out the maximum x - 2 and when we can also reach out the reach out the maximum x - 3 and so on and if we cannot uh make let's say we cannot reach maximum x maximum y let's say maximum y uh for example uh if uh uh let's say if we cannot reach the maximum y whatever number of operations we uh apply to the sequence then we can also can't reach y + 1 and uh we can also can't reach y + 2 and so on. So here uh by this we can uh think out of the approach that the x the answer the answer x is is the is fixed like if uh the answer is x then we can also approach we can also make this maximum x - 1 x - 2 x - 3 so on and if the uh we can't make y then we can also uh can't make y + 2 y + 3 y + 4 and so on. So we can just uh so we have fixed answer X. So we can just binary search on the element X and find out the answer. So what we actually are doing that we shifted our problem statement from like uh first we were thinking that uh wait first we were thinking that which index should I uh increase next.

[00:21:09]So first we were thinking of out for this one like we have to think that which index should I increase next. So but this was taking too much time and uh this was very inefficient approach. So now what we are thinking that uh we shifted this question to can I make all elements uh at least x like uh the minimum maximum minimum at least x using less than equal to k operations.

[00:22:01]So uh we shifted our question to this from this to this. uh take a moment to understand this. Uh which index should I increase next? Like we first we were thinking about which index should I increase next to uh maximize the minimum of the array. And now what we are thinking that can I make all elements at least x using less than key operations.

[00:22:20]So now we will use bandy search to find out the x. So how will we use the bendy search method? So let's go to uh so here we can check that the uh what were the constraints uh the constraints were 10^ 18.

[00:22:40]So first we have to check the limits where uh between which we are have to apply the uh band search. So so we will take the the minimum can be zero and the maximum we will take uh here it is 2 18 by 18. So we will take 2 into 10^ 18 for safer side and then apply the bandage search. So how will we uh apply the bandage search in this problem? So for any first we will find out the mid uh as the which will be l + rx2 uh it is the it is the common uh step for boundary search. So now we will check that for this x this is the value of x which we are checking for. So we will check that for this x how many times we have to apply the operation. So we for this text we will iterate the uh sequence a and for any sequence ai we will check that how many times we have to approach uh we have to apply the operation to make this ai greater than equal to x. So uh for AI how can we make this X? We have to we can only uh add some add I to this in one operation. So how many times we actually have to let's say we have to uh make we have to apply this operation Y times. So A I + I Y should be greater than equal to X. So Y greater than equal to X minus A I by I.

[00:24:17]But as of C++ uh uh rule for division uh it only takes the lower value if it's in a decimal. So we have to make this greater than equal to sign to the less than less than sign. So for that we can y we can add + one here and y + 1 less than x minus a i by i. So y will be less than uh x - a i - i by a i - y i. And uh but this will make a huge mistake uh if uh we have the perfect equality between y= - x - a i by i. It will make uh uh uh this decrease the by y by one if we apply this only. So for uh for handling this thing the equality thing we will add plus one here. So what uh we will we will have y = uh x - a i - i + 1 by i. This will be number of operations.

[00:25:26]Number of operations uh required for uh making AI to X.

[00:25:48]So this is the number of operations required for making AI to X. So we will just so what we are doing so we will we have we had an x and we have to find out that the maximum number of operations required to make all elements greater than equal to x. Uh here what what we have what was our uh request accept can I make all the elements at least x using less than equal to key operations.

[00:26:16]So we will find out the number of operations maximum operations uh which I have to do to uh make all elements greater than equal to x. So uh using this formula y we will find out the number of operations required for making ai to x. So we will u uh find out the value of ai for each of the uh index a a1 a2 a3 a4 and so on and uh we will sum uh we will take sum of all the integers here.

[00:26:50]This will be the total number of operations required to make all elements greater than equal to x.

[00:26:57]And then we will check that the total number of operations required here is less than or not the what we were given the value of k uh what we were given the value of k here and if it is uh inside the loop like if it's if uh let's say the sum is equal to y and if y less than equal to k if y is less than equal to k then uh we can try greater x like uh here it was zero 218 and uh if for this x we have found uh the sum is sum less than equal to k then we can try the greater x because we have to maximize the value of x. So we will try greater x but if the value of value is less than k uh sorry greater than k then uh we will try uh the lower x. So we will just update the r equal r by mid of x. So let's uh check this check out through the code walk through.

[00:27:58]So uh here is the code for raise minimum.

[00:28:03]First we are taking input uh here it is k and we are taking the input of the sequence. Then we are doing the band size and l equal to zero and the uh right ended uh extended till 2 into 10 18 and uh this uh will uh this is the answer which we are finding out and uh we are now applying the band search. First we are taking the mid then this is the count uh this is the count of uh number of operations and uh for finding out the number of operation we are just iterating through this array and if it's less than less than the x less than the x we are finding for then we will count the operations to make it greater than equal to x through the formula which we discussed before. So because uh and if what if the ai is greater than mid then we don't have to make the at greater than equal to x because it's already greater than x. So we just find out the count to make this operation greater than equal to x. If uh see and uh once this count is greater than k we can break this loop because we don't want uh to exceed the value of k. And if this is less than equal to k then uh let's say we've completed this loop. If uh c is less than equal to k then uh we will uh uh update the answer by mid and uh we will check for greater x. So we will uh shift the l from zero l from zero to the mid one. And if the c is less than k then then we will shift the r from r. We will check for smaller x. So we will shift the r from two to 18 to mid and then we will then it will continue the loop and then we will get the n c out.

[00:29:51]uh finally we will get the optimal x. So this was the approach. This was a very beautiful beautiful question. And so let's now go to the next question. Uh yeah.

[00:30:07]Okay.

[00:30:10]So now let's uh go to the next question which is the crossing table cloth question. This is also a very beautiful question. Let's read out the problem statement. There are n cells arranged in a horizontal row. The I from the left is called cell I and there are M pieces of cloth laying cloth 1 to M covers cells LI through RA I and then we have Q queries uh for the Q query indq and TQ are given and answer the we have to answer the following problem uh determine whether it is possible to choose exactly two pieces of cloth from the MPCs and uh lay them so that the following conditions cells sq through TQ are covered by at least one piece of cloth and no other sales are covered by any cloth.

[00:30:53]So uh what uh exactly we have the in the problem statement. So we have uh n number of what the there are n cells arranged in horizontal row. So we have n number of cells number of cells and we have n pieces of cloth. So this is the number of cloths and then we have uh uh m rows here the l1, li and ra i shows the the indices the left and right till the cloth the cloth mi uh covers. For example, uh if the uh array is 1 2 3 4 5 uh let's say uh denoted by cells 1 2 3 4 5 and uh uh the M1 cloth let's say covers the cloth from 1 to 3 then the M1 will be here and the M2 cloth cloth let's say cover from 2 to five then uh it is it will be here this is M2. So these are these are the visuals of this problem statement that we have given n cells n cells and we are given m cloth and every cloth covers from left index to right index fully. Now what we have given in the question we have given kq queries. So we have to output the uh output the answer for these q queries only. So what do we have to output? Uh for example, if for any query if we are given s S and T.

[00:32:42]So we have to find find out this uh uh we have to count whether it is possible to choose exactly two pieces of cloth from the MPs and lay them the following conditions like SQ by at least one piece of cloth and no other by any cloth. So we have to find out exactly two pieces of cloth from M1 from M exactly two. No, no, not not even one and not not even three. Exactly two pieces of cloth to cover cells from S till and the uh combination of the cloth and the combination of the cloth should not cover any of the other cells. For example, any cloth covering the uh cells outside this range is will not we can't be taken. So the combination of the cloth for example let's say we have the clause M1 M2. So the combination of clause should cover the uh uh from s to t only. For example, if m1 covers this one and m2 covers this one, then uh it is okay. But if even if uh uh m1 covers this and m2 covers uh this then it will can't be taken because it is covering the cells outside s.

[00:33:55]So we have to find out only we have to find out exact two pieces of cloth which which can uh all together covered from s to t only.

[00:34:10]So how can we think of uh the approach uh required here?

[00:34:15]So we can think of like this that uh if we have any cell s to t then if we choose two cloths m_sub_1 and m_sub_2 then one of the uh cloth should cover the range starting from s till something uh let's say uh r1 and m_sub_2 must start from let's say l1 and it should end to t and here from s2 r1 let's say this is M1, S2, R1, and this is M2, uh, L1 to T. And to cover whole cells from S to T, we must have the length of the cloth M1 and the length of the cloth Y. So, we must have uh let's not X and Y. Let's uh forget that the must we must have L1 less than equal to R1 which means L1 less than equal to R1. So so that it covers a hole from S to T. So it the L1 must have must have present on the left of the R1. So that uh if uh R1 is present on the left of L1 then the the clo the cells between these L1 and R1 will not be covered.

[00:35:39]So what we actually have to think of that we have to find out the two m clots m1 m2 uh one which should start from uh s and one should end uh on t and uh the m the m1 range of m1 the maximum we have to find out the maximum value of uh right end of any cloth which start from s max we what we have to find out uh Maximum value of R1.

[00:36:16]What is R1? Uh the right end of clo starting from S. So what we have to find out maximum value of R1 and the right what is R1?

[00:36:40]the right end of the cloth starting from S and uh also the max minimum value of uh L1 the left end of clo uh ending on D.

[00:37:11]So we have to find two things. Maximum value of R1 the right end of the cloth starting from S and minimum value of L1 the left end of cloth ending on T. So and one more thing you can observe here that the R1 R1 must be less than equal to T and L1 must be greater than equal to S.

[00:37:33]Why? Why this is so? Because if uh this is not uh satisfied then the uh then the union of these two cloths will start covering the cells outside of the range s and t. So the uh r1 must be less than equal to t and l1 must be greater than equal to s.

[00:37:52]Uh why we are emphasizing on maximum value here and minimum value of here?

[00:37:57]because we have to find out the maximum length of cloth because uh pardon the maximum length of cloth will actually help us uh to cover most of the cells at one time. So we will emphasize on maximum maximum length of cloth starting from s and minimum length of cloth start ending on t. Okay.

[00:38:16]So this is what we actually have to do.

[00:38:18]We can uh now go to the code to how to see how to apply this. And uh and before that uh one edge case will be here that what if uh there is uh a cloth M1 the cloth M which actually has a range S t uh as we are we have given in the queries like uh if what if the one cloth covers whole of the S and T entirely by itself only then to find and but we want exactly two clothes. So we have to find out the cloth m M2 which can start from anywhere inside this range and end anywhere inside this range. So we don't have any constraint on M2. The only constraint is it should lie uh wholly whole inside the range HD.

[00:39:06]Uh to find this M2 we have two cases. uh one case is uh that uh it can start from the s and uh end on anywhere between the t or uh uh start from start from anywhere between the s and end on t or start from anywhere between the like its ending and starting point all are uh between s and t. So how can we handle this optimally? So first we will make a list of what actually we have to do in this question. So, so what we actually have to do in this question? First thing is that so what we have to do is uh first uh for any number of cells there we are given a what number of cells uh n number of cells and we have given m clots m clots and uh the queries s and s and t and we have defined exactly two cloths two clots which covers entirely s and T but not uh should cover entirely S&T and but uh and also not should not cover the sales outside of this range. So what we have to exactly calculate? So first uh first what we have to do is we have to find find out uh the maximum length of cloths. Uh this thing maximum uh length of cloth starting from starting from S to any R1 and R1 should be less than equal to T.

[00:40:59]And second thing uh minimum length sorry maximum length here also we have to uh find out the maximum length of cloth ending on t ending on t uh uh and starting at starting from L1 and this L1 must be greater than equal to s. So first of all we have to do these two steps and uh for this we can do we can store this uh uh these cloths in the form of two arrays a and b. Here what uh we will store here uh exactly like 2D array because we have to handle both uh the end the left ending indices of the cloth and the right ending indices of the cloth separately. So we can build a 2D array a and b where a of a ai a ai will store the indices of cloth indices of clothes starting from from i and similarly bi will store indices of cloth uh ending at i.

[00:42:28]uh then we will just sort these arrays uh uh in ascending order to uh make it easier for us uh uh to solve this problem.

[00:42:42]Let's go through the code to understand better. So first this is the code of this uh problem.

[00:42:49]We have built a 2D vector A and B and uh let's uh leave this minimum vector. We will I will explain later about that.

[00:42:57]And what we are doing here is uh uh taking integers L and R and uh we will push uh the what is the A vector? A vector is that the A L will store the number of indices and sorry the A will store the indices which the cloth starting from L uh is ending on. For example, a A1 will store indices of the clo which start from one and end on uh uh R. So uh similarly we will store indices uh of the cloth from which the cloth is starting on but end on the indices index r.

[00:43:37]Uh leave this minimum vector for now.

[00:43:40]Then we are sorting that uh those two arrays to apply the functions like upper bound because we have to find out maximum uh length of uh those two close uh >> which are required to find out in the question. Now we we are just uh iterating through the queries here. Uh the we are taking inputs L and R and uh now we are finding out the upper bound. What what does upper bound means? The first iteration is that uh first uh index.

[00:44:14]This will return index which at which the clothes starting from L.

[00:44:20]Here Al represents the clothes starting from L.

[00:44:24]uh but uh the upper bound is r. So it will find out the first element uh from the vector a of l which is greater than equal to r. First element which is greater than equal to r.

[00:44:39]So uh if uh now for example let's take an example for that which uh we'll explain better.

[00:44:50]So let's take an example uh n equal to let's say 10 and uh we have to find find out uh the s 2a 8 right we have to find out the uh two clots which cover entirely two 2 and 8 2 to 8 indexes.

[00:45:10]So and the a vector we are given we are having is 4 6 7 9 we only we only have to take care of the a of 2. So we are not uh printing a whole uh a vector. So let's say a2 is 4 6 7 9 and b8 is 1 3 5. So what is uh the A2 represents the uh it represent there are four cloths starting from index two and ending on index one cloth ending on index four then six then seven then 9 uh and as they are all in sorted in ascending order it is there and uh B index is representing the clothes which end on 8 and the first clo there are three clothes which ending on eight the first is starting from one then three then five. So we have to find out uh I first uh uh here you can see we have to find out IT1 which is the upper bound uh to find the first clo which we are which we find greater than equal to R.

[00:46:21]So if we apply the lower bound formula for this so so there are four 6 7 9. So here the it dot begins and here is the upper bound. So what is the upper bound actually do that it will check out the first element which is greater than equal to r. So here r equal to 8. So first element which is greater than equal to 8. So here the first element is 9 which is greater than equal to 8. So here the it1 will uh come and uh we have but we want the index less than equal to 8. So get the largest index uh less than equal to 8. So we will just decrease this it1 by minus minus by one index. So it will come from uh 9 to 7 and this will be the final uh answer which we we are waiting for. And if if the IT1 is equal to the uh it begin uh sorry AB begin so here it is A2 A2 if it1 is equal to A2 begin that means it couldn't find any uh inteious greater than equal to 8 so it will just uh return the output no so that's exactly what uh we are doing here if it is equal to a begin then we will simply answer no uh we can't found any cloth but and if uh if we found any it1 then we will decrease it uh by one index because we want the greatest index less than equal to r not greater than equal to r but upper bound is finding an index uh smallest index less than greater than equal to r. Similarly for IT2 it is founding uh we find finding lower bound of this lower bound. What lower bound does that it founds uh the uh lower low in the first number which is greater than or equal to two.

[00:48:34]What exactly two here is this is this one. So B8 represents the uh close indexes which uh close starting indexes which are ending on the index 8. So here we have three clothes. Uh let's here is this here we have three clothes 18 38 and 58.

[00:49:00]the the lower bound what lower bound tells us lower bound that uh it tells us the first number which are is greater than equal to the uh r first number which is greater than equal to r and this is exactly what we want so here the first number which is greater than equal to r two is three so this this one will be the required cloth so that's exactly it is written here i2 lower bound uh and the first index which is is the greater than equal to l if it is uh equal to B.

[00:49:32]Similarly, from here it doesn't didn't it means that it didn't find any clothes. Uh so we will simply print no and continue to the next query. And if we found out that then we will just uh okay we have to store the I1.

[00:49:56]So uh if we found out the uh optimal optimal uh uh optimal right index which we found found out earlier into x and the optimal left index for the second cloth ending on t uh we found out we stored in y and uh let's uh ignore this for now and if this is the main equation if x + 1 is greater than equal to y what this uh actually means what this actually means x + 1 is greater than equal to y. So what was x? x was the uh taking example of this one.

[00:50:38]So here we have to find out the clothes starting from s and s2 r1 and r1 must be less than equal to t. So here r1 is the x and uh here l1 is the y. So what is actually X and Y in the cells and let's say here is S here is T and S to R1 it is X and T to R2 it is Y. So to cover this whole cells from S to T we have we want the let's say the first cloth ends on X ends on X then the second cloth must start from the exact next uh index X + 1 to cover whole of the S and T. So the Y must be uh greater than equal to uh sorry Y must be less than equal to X + one to cover the whole index whole uh S range S to T. So if x + 1 is greater than equal to y then it's yes and otherwise no. Now let's come to the uh edge case part which I told you before that what if one cloth m1 covers whole index from s and t then what should we do? So the uh m2 cloth can uh start from anywhere between s and end anywhere between the t. So what we are doing here it is the handling that case that if x is equal to r that if x is equal to r that means the x the x here is exactly equal to t then one cloth will recover hole from s to t then we have two cases to make this uh to choose the second clo that it if if it1 is not equal to a a not begin here. We have decreased the IT by IT1 by one index. So if the IT1 is still not at the beginning of A uh what I am actually saying is that uh uh let's say here it was for example here in the example 4 6 7 9 4 6 7 9 the IT1 we found out was here then we decrease it by So it comes here and the begin A2 dot begin is here. So if it is still not equal to it a2 begin then we can say that we have uh one more cloth which is we can say that one more cloth is available here which starts from the s uh and end in between this uh uh s and t block but uh uh other than the block other than the clo m1 which covers uh whole of the like this means that the uh there are multiple clothes available. There is one more cloth available which starts from s and end uh anywhere between this t.

[00:54:00]So yeah, if it's there only then we can say that we can output yes that uh yeah we have found the two clothes and other thing we handle the situation where the s was uh where the cloth was starting at s but what if the clo wasn't starting at s uh it can the second cloth can start anywhere between this range and end anywhere between this range so what should we do for that part so to handle the exact thing we built the min which I skipped before. So what is the min array exactly? So min array is exactly storing the right end point of any clo starting exactly at L. So uh what mean array is currently storing that the right end point of any array uh any clo that starts exactly at L. So for example uh the shortest like uh it is storing the shortest like here as minimum of L min of L is minimum of min of L given R. So so here let's say we while taking input L and R we are update Ps are updating the minimum min of L by the minimum of min of L and R. So it is storing the lowest the shortest R of the clo which starts from L. So and what we are doing in the next loop we are updating the min of I by minimum of min of I and min of I + 1. So what exactly we are by applying this exact operation we are getting the the the values in mean uh now exactly tells what is the minimum minimum value of index r which starts anywhere from the i uh index till the uh end of the table. uh what exactly what I am saying is uh let's understand using an example uh let's say we have uh our clo one which is 1 uh close one starts from 1 to 6 uh m1 which is and m2 is uh 2 to 7 and m3 is uh 4 to 5 so what I'm saying that uh and let's say the sn given query is 1 to 6 only so here we can see that m1 exactly covers the whole 1 2 six. So this is the seven and 1 6 4 5.

[00:56:34]So this 1 2 6 covers the whole of the cloth. So what is the min mean array here? So min array will be uh the 1 for 1 2 3 4 5 six indices and there are there are six indices here.

[00:56:56]So mean for one is six.

[00:57:00]Then uh the min for two is seven. Then min for three is there's nothing uh no close on the three. So and we are starting from the minimum value. So it will be 2 to 18. We here you can see we start from very a very large value. So let's say it is infinity.

[00:57:19]Now from the four it is five for four cloth and uh for six and seven uh for five and six cloth it is uh again infinity.

[00:57:31]So this is the mean value currently uh at this state at this state. uh now by applying this we can uh we are getting the mean value as uh for the i for i equal to 1. So it's here six will be six will be uh here we are updating this value by uh minimize by taking let's see the code here we are updating min of i is equal to min of min of i and comma min of i + 1 and uh we are updating backwards so here uh the infinity will infinity only and uh uh for this question for this one it is also inative for this one the minimum of five and 5 + 1. Minimum of five and infinity is five only. And here for the index three uh the minimum of infinity comma 5 it is five.

[00:58:28]And here minimum of 7a 5 is five and here minimum of five uh 5 and 6 is five.

[00:58:37]So our updated minimum is this. So what it is exactly exact actually saying is uh it is saying it is telling us the exact uh index of clothes ending at uh let's write that exact index of clothes uh we can say the earliest earliest index of clothes uh ending uh at earliest ending of lo index of cloth ending at like uh for example uh uh in the above in the mean before it was uh uh at the index one let's write the index 1 2 3 4 5 6. So at index one minimum was see min was seeing the index 6. So it only knows that the cloth is ending at six. For index two it only know the cloth ending at seven. For index three there are no clause. So it knows that uh it knows nothing that and uh for index four it knows that the cloth is ending at five. But now 1 2 3 4 5 6. Now the index one knows that the earliest index where the cloth is ending. So the earliest index where any cloth is ending is five. So now index one knows that cloth the earliest ending of cloth is five. For two, it's earliest known cloth of ending at two is five. At three also it now knows that the earliest ending of cloth index is five and for four it was five only and and after five uh there is no cloth ending.

[01:00:18]So it it remains infinity.

[01:00:21]So it is exactly what it is it's exactly saying that the min value tells us that the exact earliest ending of cloth index after the value I. Um what mean?

[01:00:36]I say that earliest ending of cloth index starting from I to uh it can start from anywhere from I to uh the n like the whole sales number of sales plus I to the table only like it can start from I + 1 also I + 2 also and so on I + 2 and t so eariest ending of cloth it's uh just it's uh telling us so uh here what we are checking like that uh if one cloth covers the whole of the set s to t then we are checking that minimum of min of l + 1 what is l + 1 uh here we already checked for the cloth which are which is starting from the index L uh in this section. Now we will check that any is there any cloth which is starting from uh index l + 1 or greater than that and but the ending of the the earliest ending of the cloth is less than equal to r which means we are checking that in l tor we are checking that is there any clo which starts from index l + 1 or later that it it can start from l +2 also and it uh ends on any index it ends on any index t which is less than equal to r. So we can here we can the mean what it actually tells is the earliest ending of cloth index starting from i. So here we can find out this by mean of l + one. it will uh uh give us the answer of uh the earliest ending index of clo which starts from l + 1 or l + 2 or any index from that but ends uh uh is less than equal to r. So that's what we actually want that uh is there any cloth from L is there any cloth between L to R that starts from index L + one because we already checked for the index L. We have already checked for index L here that if there are multiple clothes starting from index L or not. So now we are checking for index from index l + 1 and finding out if there is any clo which starts from index l+1 or later and ends uh before the index r. So we can so then we will have an uh a cloth which starts between the uh range l and also ends between the range l to r. So if minimum of L + 1 is less than equal to R then we can also then output yes and then continue this question. So it was a very beautiful question.

[01:03:44]Hope you understand this. Uh you can it may be some difficulty while understanding this question.

[01:03:50]So you can uh watch this video uh again also. So now let's go to the next question uh which is G.

[01:04:12]uh here it is the next question G which is the catch all apples.

[01:04:17]First read out the question the problem statement. The uh there are n apples fall on a number line and apple I falls at coordinate x at uh and at time ti.

[01:04:27]You want to place some robots on number line to collect all animals. The robots can be placed at any coordinates and each robot starts operating from time zero and can move freely along the number line at a speed of at most one.

[01:04:40]Multiple robots may occupy the same coordinate at the same time and each robot can collect apple i if and only if it is coordinate x i at the time ti and we have to find the minimum number of robots needed to collect all apples.

[01:04:53]So what we have actually given there uh there is a number line and we have given n apples which is falling at any position x i and any time ti and we have to place robots here which can move freely here you can uh here take care of this one that the speed of robot can be at most one at most one that means uh the robot can can be stationary at any time. Uh it can also be zero. So uh yeah so let's uh go to the uh input uh here we have given n and uh we are uh having the n indexes of the the apples the t is time and the x is position where the apple will fall and we have to find out minimum number of rows need to collect all apples so how can we approach this question so let's say for an apple a there is two apples A and So let's say the robot is currently at A. Uh we assigned a robot to collect uh the apple A. Now to collect this apple B from the same robot uh what uh it can what is the criteria to collect the same robot uh the apple B. So the position between them the distance between them the x a minus xb the modulus of because uh it can be can be either on the left or on on the right. So the distance between them must be less than equal to the time between the time of fall between them.

[01:06:41]uh what I am saying that uh for example uh the position and time of apple a is and this is position x and time t the position and time of apple x is 1 comma 1 and uh position time for apple b is uh let's say 5 comma 6 then here the distance between the apples is four and the time difference between the apples is five. So uh here the robot can uh catch the apple a and then immediately go to the apple b. So it will the robot can robot will reach the apple b at exact time t= 5 sorry t equal to 6.

[01:07:33]Uh no no like uh the distance the speed of the uh robot is one. So uh after collecting the apple at a it can reach the distance reach the apple b at time equal to 1 + 4 which is five. So and it will then stop there and after 1 second the apple will fall and it will catch it. But what if this uh there it is uh the apple will fall at two time equal to two. then the the robot uh standing at A cannot uh catch the apple B also because the distance between them is four and the time difference between them is one.

[01:08:10]So after the falling of apple A the after 1 second later the apple B will fall but it can reach uh it can't reach uh the position X to position uh five position one to position five in 1 second only. So here we can say that to catch uh apple b let's say the robot is at apple a and to catch the apple b this should follow the x - xb the modulus of x - xb less than equal to tus so what's what is this actually so uh let's uh like we don't have to handle the complex mathematics of mod so we will uh uh break it into two two pieces two equations. First is x A minus XB less than equal to T A minus DB and second is XB minus X A less than equal to DA minus DB.

[01:09:11]Uh for this to be true for this to be true uh the both equations should be true.

[01:09:19]So uh transforming these equations we can get that uh x a minus da uh let's say x x a minus da is less than equal to x a - ta is less than equal to so less than equal to uh or let's say t - x let's do ta - x a less than equal to uh t - X will be greater than equal to TB - XB TB min - XB and from the second equation TA + X A is greater than equal to TB plus XB. So here we have got two equations to if the apple is at currently a and to make sorry if the robot is at currently position of apple a to catch the apple b also it must satisfy these two equations.

[01:10:24]So we can make this uh uh look at uh so let's here we can let uh u equal to t minus x and uh v = t + x t + x.

[01:10:41]So to catch apple B from A uh we should have U A greater than equal to U B and VA greater than equal to VB here I have made a mistake that we are going from A to B. So we should uh subtract from B time of B to uh from time of A from time of B not A minus B it should be B minus A. Similarly here also B minus A and uh similarly it should be B A B and here should be B A B A.

[01:11:30]Uh now similarly here uh da minus x a less than equal to here must be a will be less than equal to here also less than equal to. So here ua will be less than equal to and here also less than equal to.

[01:11:54]So if a robot is at currently position of apple a and it could also catch the apple b these two uh set equations must satisfy. So now what we have to find? We have to find the number of minimum robots.

[01:12:10]Minimum robots uh required to catch all the apples.

[01:12:26]So how can we find out uh these?

[01:12:31]So, so let's say uh we have uh like we have nles. So, let's say we have uh m number of apples.

[01:12:44]We can have a pair of apple uh a comma b which uh uh we cannot uh make a robot catch the apple a and apple b together.

[01:12:56]uh as see we seen and uh this example if the first position of the t index of first apple a is 1 and one and for b it is uh uh 2 and five then it can't reach a to b. So we have to we must have to deploy two robots uh one for a and one for b. So here we can see that if uh the two robots are not reachable from each other then we have to apply deploy two different robots for each of the apple.

[01:13:32]So we so to find the minimum number of robots so we can find the minimum number of minimum number of apples which are not reachable from each other.

[01:13:46]So here we can we can check out for that thing only. So our problem is not converted to we have to find minimum number minimum number of apples which are not reachable from each other.

[01:14:18]So now there is one more case thing which uh some of you can get confused about. So we will discuss. So let's go to the code and we will discuss there only. So let's go to the code for apples. Uh here is the code one. So what we are doing that uh we are making a pair vector of pair. Uh in the pair we are we will be storing the u and v values. And uh we have this uh this equation u must uh u aa must be less than equal to u b and va also must be less than equal to vb. So we will store in this format u and b.

[01:14:59]So here uh the we stored in the in the form of vector of pair. The first uh the first equation first element will be t - x and the t plus x. What here you can see what was the u u by t - x and v t + x. So we are storing in that form t for each apple t - x and t + x. Now we will sort this uh vector of pair. Then what we will will we get uh u1 v1 uh u2 v2 u3 v3 u4 v4 and like this and uh this u is in ascending order and as it is in the all it is in ascending order and v1 is v is also in ascending order. we have to find out the uh list of the apples which are which can't be mutually reached by any of the other apple.

[01:16:01]So for that uh here let's say here u1 is less than equal to u2 less than equal to u3 less than equal to u4 and uh currently here v_sub1 is also less than equal to v_sub_2 less than equal to v2 this will the v1 is arranged in ascending order if and only if the uh u are same for two apples so let's not consider this one it was just for sorting explanation. So now what we have to do let the uh u1 is already less than equal to u2 then what we can say that that a the we can reach from 1 to 2 if and only if the both should be satisfied. So for 1 to two we to reach from 1 to 2 we must have u1 less than equal to u2 and also v_sub_1 must be less than equal to v_sub_2 but we want the unreachability thing that we want the number the number of the uh elements which can't be which is unreachable from each other. So for that we have to find out the v uh v_sub_2 which is less than equal to v_sub_1 that the next element must be less than equal to the previous element.

[01:17:16]So for that what so we what basically we have to find out we have to find out the maximum number of longest decreasing subsequence.

[01:17:26]So for example if v_sub_2 is less than equal to v_sub_1 then uh the 1 and 2 is unreachable then v_sub3 is if less v3 is greater than equal to v_sub1 greater than equal to v2 then 2 and 3 is reachable but uh if v_sub4 is uh less than equal to v_sub_2 then uh uh it is unreachable. So we have to find out the longest decreasing subsequence we have to apply this uh algorithm on the uh on V.

[01:18:10]So but uh the to apply to solve it using the algorithm of LIS which is an standard algorithm we uh longest increasing subsequence we can multiply v into v by minus one which will convert the question from longest decreasing subsequence to longest increasing subsequence and we can apply this uh to the question. So now let's uh work jump to the code of this question. uh the we uh stored the value t minus x and t plus x and then uh we the we sorted these these values then we applied the longest increasing subsequence algorithm here.

[01:18:54]So this answer will is is storing the uh elements where which are unachable. Not exactly the elements which are unable but uh it's just storing the buttoring that uh the smallest possible values to keep our like future options uh uh as open as possible so that we can extend the chain as long as we can.

[01:19:19]So we converted it into the longest increasing subsequence and then applied the LIS algorithm uh using the lower bound that uh first we find out the lower bound of the value in the uh answer uh in answer vector. If the index is uh at the end then we will push back the value again in the answer and if uh it's not then we will replace the value the last value to the value to keep the uh options to keep the options future options as open as possible.

[01:19:54]Let's uh check it out uh by applying this on one of the input test case. So here is our test case.

[01:20:12]Here is our test case. So there are uh four. The positions are 0 2 1 0 uh 2 1 2 3 and uh it is a T index. D here it is D and it is X. So first what we are doing that we are storing the U and V values.

[01:20:34]So uh let's just so now we are calculating the U and B values U V. So this will be minus - 2 and 1 1 and the v will be 2 1 3 5.

[01:21:05]Now we will sort this. So we will when we will sort this then -2 sorry this will minus 1 - 2 then uh - 2a 2 - 1a 5 1 comma 3 1 then 1a 3. So it will sort sorted one. Then uh we are applying the LIS algorithm.

[01:21:30]So let's check out for these two these two apples.

[01:21:34]Uh so for for applying the LI process we will multiply the V values by minus1 -2 -5 -1 and minus 3. Uh here we have to find the longest increasing subsequence.

[01:21:47]Uh so first we will iterate through minus2. So currently the first we will through the minus2. So currently the answer will be empty. So we will just uh push back the value. So now this is the answer vector answer vector. So currently we will push the minus2 minus2 value. And uh so now the answer vector has one element. So now we will we require one robot one robot.

[01:22:16]Now come come to minus five. So here uh we will look for lower bound. Lower bound means we will search for the first number which is greater than equal to minus 5. So here we have find out the first number which is greater than equal to -2 sorry - 5 which is -2. So we will just override this index - 5. Override this index to - 5. We will not increase the number of robot because as the this is uh the v uh second one second v is greater than v1. So we will not require uh second robot for here.

[01:22:50]Uh the first robot can uh automatically reach this second robot.

[01:22:56]Uh sorry second. Um as we can see here the this is the this is this is the fifth one. This is the fifth one. The second apple and uh this is the first apple. So here you can see uh the the difference in the distance is only one and the difference between time is two.

[01:23:14]So the uh same robot can take two of both apples. So we will not need the uh second robot. We will just replace this from minus five.

[01:23:23]Now we will come to minus one. So here we will check the lower the lower bound.

[01:23:29]Is there any element in the answer uh which is greater than equal to minus one. So no we have not any integer. So we will just u push back this uh minus one into the answer. So now we have we are having two robots. So we will need not two robots.

[01:23:47]So now we will come to minus 3. We will check for any index in the answer vector which is G lower bound which basically which is greater than equal to minus 3.

[01:23:56]So here we have one uh row one which have the v value greater than equal to minus 3. This is minus1. So we will just replace the minus1 with minus3. So this is the my fin our final answer vector and uh the size of the answer vector the robot number will be the size of the answer vector.

[01:24:25]So this this is the our final answer.

[01:24:27]You can see this is this is our final answer the answer size uh we can check out by running this.

[01:24:34]So now this is the end of this video.

[01:24:38]you can you must uh I hope you all uh have understood all these six questions which I explained and uh uh let me know in the comments if uh you have any doubt in these questions uh or explanations or uh if you caught a mistake uh where I did and uh and if uh any uh if uh any place where I need improve in my explanations and also do subscribe to the daily TV channel and uh also hit the like button if you would like the explanations and uh thank you.