AtCoder Beginner Contest 460 | Video Solutions - A to E | by Vikas Soni | TLE Eliminator

本站添加: 2026-06-01

[00:00:00]Yeah. So hello everyone. My name is Vikas Sony and I welcome you all in this post contest discussion of uh at coder beginner contest 460.

[00:00:10]So without any ado let's start the discussion uh by solving the first question.

[00:00:17]Uh so yeah first question is mode while positive.

[00:00:24]So in this question we are given two positive integers n and m and the operation this is repeated while the value of m is not zero. So the thing is let's say we find the value x which is the remainder when n is divided by m and then I replace that value m with the x and and yeah m will become zero after some finite operation and I just we just have to print how many operation it takes to become n is equal to z. So let's see by test case here. So uh assume that like n is 8 and uh m is equal to 5. So now the remainder is 8 mod 5 which is three.

[00:01:12]Right? So in one operation now my n is equal to 8 and m is equal to 3. Again I will find the remainder. So 8 modul 3 is 2. So now my m will become 2. This is my second operation. And in I will again find the remainder.

[00:01:29]8 modulo 2 is zero.

[00:01:32]So now after third operation my m is equal to zero and I will stop it. So yeah that's it. Now the observation here is that if let's say my current modulo is m sorry my this is my m. So I know that the modulo like n modulo m will be in range of 0 to m minus one. So you can see that this will be at least reduced by one. Right? So therefore uh and also the range of the n and mr is 100. So in 1,00 operation the m will become zero.

[00:02:07]So that's why we can just use the brute force and yeah that's what we did here.

[00:02:12]I take the input n and m. This is the counter which is zero until m is greater than zero. I just find the remainder x which is n modul and I change uh the m with x. uh and yeah I do counter ++ and this will run until the m is greater than zero and after that I just print the counter. So that's it in this question and yeah this was just the brute force type question.

[00:02:40]Now let's move to the second question and in this question there are two circles C1 and C2 on the XY plane and uh let's say the circle C1 has a center at X1 Y1 and it has radius R1 and the circle C2 has center at X2 Y2 and it has radius R2 and we have to determine whether the circle C1 and C2 has a common point in other words uh if they if they both circle are intersecting at some point or not.

[00:03:11]That's it. So yeah, this is just uh the fundamental question of uh our like high school or in JWE maybe.

[00:03:24]So there can be uh some taste or some different cases like let's say the two circles are intersecting when let's say this is our first radius and this is the second radius. You can say that the distance between the center which is D.

[00:03:39]This D is less than R1 + R2 then they both are intersecting. Right? When this uh D is R1 + R2 these are both are equal then we can see that the circle are just touching at one point. Right? So yeah you can say this is one example right that if D is less than R1 R2 then our answer is yes. else. Yeah, you can see this is D and this D is greater than R1 + R2 then they will not intersect.

[00:04:10]That's it. But but but there is uh some another case here that we can maybe we forgot to see the case is uh let me write it here.

[00:04:25]The case is that maybe one circle can uh can just cover the another full circle, right? So let's say this is the smaller circle and this is our bigger circle. It has center at this point. Okay, this can also be possible. So what is the condition for this thing? So like you don't have to find this. Let's say the circles are given. Okay, now the circles are given. So now let's say what is the minimum radius that should be of this circle of this uh sorry of this smaller circle such that it like just touch somewhere right just touch somewhere so you can see here let's say so this total distance uh this uh total distance is B right uh sorry so this is okay let's write it again so this total distance is R1 at the radius of the bigger circle.

[00:05:27]This distance is D. So I know that just to touch here, just to touch this point, this distance should be R1 minus D, right? Yeah. So we found this.

[00:05:39]So that's it. So like we found that this R2 should be greater than this R1 - D.

[00:05:45]So from this we found that R1 - R2 should be greater than D. So that's it.

[00:05:51]And yeah this is the distance between the two centers. So this will be our D. So we have to find the D. And these are the two cases we have to find. Right. So what are the two cases? The two cases are just that uh R1 + R2. This thing should be less than equal to D. Uh sorry this thing should be greater than equal to D and R1 - R2 should be greater than equal to D.

[00:06:22]Yeah that's it.

[00:06:25]Uh another uh thing that you can by solve that uh because there is square root so you have to use the double here and maybe there can be some precision error. So what we do is just we just uh find the square right. So like here we do square here do square. So yeah we just find this thing that R1 + R2 whole square should be greater than D square.

[00:06:46]Now you can find this into long long format. So let's read the code and we will understand this.

[00:06:55]So uh so this is three test cases are there and so for each test case these six values are given. X this is the coordinates of the circle of a circle one. the radius of circle one, center of circle two and radius of circle two.

[00:07:14]Then I find the square of the distance between the center. So yeah, you know the formula it is just x1 - x2 square + y1 - y2 square. Then this is our condition right that this r1us r2 like this should be less than distance. But here the R1 - R2 squared should be less than equal to this distance squared and also the distance should be greater than less than this value. Yeah, if this is true then we have to find uh we have to print the yes else we will print no. So yeah that is also for this question like this was just the formula based question. Yeah, the only problem you uh maybe mistake you can do is using double here and maybe you can get the precision error on some test case and got the wrong answer.

[00:08:07]Yeah. Uh let's move to the third question. So in this question there are n pieces of sari and m pieces of netta.

[00:08:17]So this both are ingredients for sushi and uh the weight of the i is ai and the weight of the jets neta is bi. So we have the given array a which gives us the weight of sari and the another array b which gives us the size of neta and we will make a sushi by combining one sari and one netta. Now the only condition is that for making a sushi uh the weight of the na must be at most twice of the weight of the sari that this is the condition and yeah and yeah in the sushi at least one uh exactly one n and exactly one s will be there that's it and we have to output that how what is the maximum number of sushi we can Okay. So this is question C and first thing is uh the first thing like you have to see is that uh whenever the ordering is not important like you can just uh I mean you can sort the element then always just sort the element because maybe you can get some more information in sorting right. So let's take for this case. So first of all let's see that like what is the like for this s what is the condition. So for this s the maximum size of na can be 1 into two w is two right. So the only range of na you can take is this one right? So you can take any na from this two that's it.

[00:10:03]Let's say for this five. So the maximum weight of na can be 5 into 2 is 10. So yeah for this also this is uh let's say for this seven. So the range of na will be 14. So this range right? So you can take any element of this and pair it with seven to make the sushi right. Okay. So how we will do this.

[00:10:31]So here this can be like easily done by the like two pointer approach.

[00:10:36]How will you solve this? So let's say I mean it can be done in any way you can go right to left and or you can go left to right. What we will do now is let's say we see the first element here and first element here. So this is P1 this is P2 right now we will check that can we make our can we make our sushi with these two elements. So what is the range on this uh I mean what is the condition? So this is 1 + 2 two. So I mean uh for this one the condition is that the weight of na should be at most one.

[00:11:14]So yeah this can be paired. So we will just pair these two element to make the sushi.

[00:11:20]Now my P2 will point here and P1 will point here. Now I will check again that can they both make a sushi. So uh for this the size can be at most six of the na right. So this both can also make a sushi. So I will make the sushi with them. And now comes the nice part. So then I will move the pointer. Okay. So p1 will point here. P2 will point here.

[00:11:49]Now see here for this five like for this weight is equal to 5. The weight of na can be at most 5 into 2 is equal to 10 only. Right? But the weight for here is 12.

[00:12:04]So you cannot make the sushi with this one. You cannot do this. So now what to do? Now what to do? I mean you have to do something. You have to either remove this 12 or or you you have to either remove this sorry. What will you do?

[00:12:22]Now the question is that I mean see here for this five let's say you remove this 12 and you see this you cannot also pair it with this for this five you cannot pair with this one or this one. So because like five as limit is equal to 10 right this is bigger and there each value is bigger than 12. So this everything will be always bigger than 10 right. So therefore you just have to remove the five because there is no way you can find the matching for this file.

[00:12:51]you can not find this. So you will just uh do the P1 ++ right because see here for this 12 there is someone that can be matched but for this five if this matching failed then every other matching will be failed. So we will just remove this five and move ahead. That's it. So that was it in this like question and uh this was yeah again a easy two pointer based question. So what we do is we take the input of nm. Then we take the array and I have sorted both of the array and this answer initially initialize by zero.

[00:13:32]Then my first pointer points to zero and the P2 which is the which will point to the element of the array and initially it is zero. So now like while the P1 and P2 both are less than uh the range I mean both are in the bound. I will check the condition that hey uh this I know that this this element should be at most 2 into p1 right a of p1 so if this is true I will pair them so answer will be added by one and I just move ahead because this both are used else what I do I will just remove the current sorry that's it and then I will print the answer so that Was it in this question?

[00:14:22]Yeah. Um I guess you can do like do pointer in many ways. I mean you can also add it from right to left and remove something or yeah like try thinking on that methods also. Now let we come to the I guess best uh question of our discussion. I mean this was not so algorithmic but the first of all like the observation you have to take are kind of tough one.

[00:14:54]Uh [clears throat] so let's read the question. So in this we have a grid with H rows and W columns and the select I rows from the top and the J row from column is I you know this and uh okay so like what we have given is we have given some grid like this the cell uh if this is has it means it is black and it it is dot means that this cell is colored in white okay now there will be 10 to^ 100 times operation and in each operation what will happen is so if the cell is black it will become white. So after operation it will become white and if the cell is white before operation what will happen is he will see it's all neighbors. So there will be all eight neighbors right the adjacent and the diagonal both once and if any neighbor is black then this will also become black else it will stay white that's it and yeah the constraints are the size I mean the total elements will is still 186 so you have to find like O of total elements or O of total elements cross log of total elements and uh yeah we have to Find that after this much operation what will be the color of each cell in the grid that's it. So like for this thing if we do the 10 to^ 100 operation the grid will become like this.

[00:16:25]Okay. So yeah initially this may look very confusing or like complex but let's take by let's try to solve this by like taking smaller question uh smaller cases. Okay.

[00:16:39]So let's say I take uh this test. Okay.

[00:16:42]So one is B and one is W. What will happen? So now you can see that uh for this black yeah we know that for black they become white after operation. And for this white he will see into his neighbors right if there is any black.

[00:16:57]Yes there is a black. So he will become black also. Then after one operation yeah they will be repeating. So you can see that uh the values are kind of o repeating or you can say oxillating right now right. So this is BW then WB BW then WB something like this. So this is our observation one. So it is like this is B and this B is like a ball. So it is passing to this one. This is passing to this one. Right. So like if there are this much one. So what will happening is like in one move uh this B will be just uh pass to the all of the other other elements and okay one thing is that I mean you can see for sure is that if there are neighbors that have different color for always the both cell will be just oscalating right so 0 1 0 1 they will periodic uh they will find the uh follow this pattern that's it why because see here this is black this is white so after one move the black will come here and it will become white and so it this ball b is like a ball like I already said right so this is passed and after one move this will uh take the ball in after one move this will pass the ball to each one so it's like this okay so this is our like observation one that uh if two adjacent cell which have different color then they will keep osculating that's it.

[00:18:42]Now the one thing is other like if you take um other test case like this one.

[00:18:49]So you can see that what will happen is these three cells are connected with the black one. So they will become black and after that they will uh they will become black after. So I mean this is after one operation and after second operation all of the blacks will become white and like all of the whites are connected with this blacks right. So they all will become black now.

[00:19:16]So maybe just uh I hope that uh the one observation you can see that initially only these four cells were were oscillating right but after one move now you can see that because for this cell also for this cell also it has a neighbor which is black.

[00:19:36]So now this will also start oscalating right and you can see here that they are just oscillating and after this this position will come here. So you can see that the region of this oscillating cells are kind of expanding right. Let's take a smaller example and you will understand this.

[00:19:57]Let's say example is this bwww.

[00:20:00]So initially the region of the osculating cells are this one. Okay I mean you can assume that this is just of length two and it will osculating for sure for lifetime.

[00:20:13]Now after one operation it will become BWB and now you can see that the region is increased by one length right after one operation the increased by one length more.

[00:20:26]So this was a the another observation that this thing is like keep increas expanding but the point is that like in one operation like at least one one can be changed right I mean uh the region of this uh oscillating region can be expanded by one cell in one move right so it can take only five operation and I can like we cannot do this much of operation because like per operation it will take n cross m operation like so it will be n cross m into 1 which will surely give us a t okay so that's good but uh let's take now a different test case now let's assume oh so we know that what will happen if the thing is oscalating but let's say what if there is like a big region of white itself else because this is now not osculating right now, right? So what will happen to them? Let's try to see something on this.

[00:21:37]So we have to like only find that what is the time for the some uh white cell when it starts oscillating.

[00:21:47]So one of the like very nice approach you can use is the B uh the DFS sorry BFS approach which is like you will just find that let's say this B is here right so just uh see this carefully if this B is here the observation is the only thing you need is the minimum distance from the back black cell that's it for any white cell you only need the minimum distance from the black That's it. Why? Just see here for this white the minimum distance is one.

[00:22:22]Right? This one.

[00:22:24]So this will start uh this will start oscalating at time is equal to zero. For this w the distance is 2. So it will start oscalating at t is equal to 1. For this cell the distance is three. So it will start at oscalating at t is equal to 2. Yeah. So this is the observation I took by just like taking the test cases like this and that's it. So I mean so like I can just find this right and the now the question is different. Now the question is what? So given grid given a grid for each cell for each cell find the nearest distance uh find the distance of distance of nearest black cell.

[00:23:28]And now if you know that this is like a fundamental question of uh uh that can be solved by the BFS approach. So what will you do is like from all the B. Okay. So let's say from all the B you will start your DFS.

[00:23:44]You will start your DFS, right? And now this point they will also start their DFS and that's it. And at some point we will just cover all of the grid.

[00:23:54]Right?

[00:23:56]Okay. Now comes another good point. So we talked what will happen if the values are like BWBW something like this. We also talked about what uh when there is a big region of white cells right but now what happen when the when it is like big region of black cells what will happen to them because they are not kind of oscillating right let's see just see here if you see that this test case like this is white and then there are four black cells what will happen maybe you can assume that oh hey the distance is distance is two. So maybe at t is equal to 1 it should start oscillating.

[00:24:39]But you see here like the region is this one of oscillating right after one operation this will be www. Yeah. So you can see here that still the region of osculation is still this much only it has not expanded after when it is like going expanded but we don't know exactly like what is the thing and what is the case.

[00:25:01]What is the problem here is that because if there is a big region of black cells after one operation there will become a big region of white cells that is our problem but this problem is also our solution why because like I know that I don't know the answer for this thing but I know how to solve this case right I know that when there is a big region of white cells I know how to solve them and also there is a amazing observation that after one operation after one operation the only blacks that was remaining are the blacks which are osculating that's it why because see here this is white this should have got this black color from somewhere else right so which means that it is oscalating already like if this is oscalating then and only then this white should have become black right so that's it. So I I that is our main observation and like I wasted many so much time in this finding this observation that after an operation the only be there are the oscillating oscillating ones. Okay. So that's it and that's just the code. So I mean what you have to do is just uh do one operation manually. Do one operation manually.

[00:26:32]and then do the DFS sorry BFS to find the main distance find the main distance from zero that's it let's see the code and we will understand this thing and also like in the last the thing is only we care about parity right because the thing is they will keep oscillating so 0 1 0 1 so like we you have to only see that at what parity at what time they came.

[00:27:04]So let's see the code and you will understand this more properly. So uh first of all I have taken the input n and m and this is my dum vector. So we know that we have to do one operation right. So before operation the array is dum and after operation my grid will be ar a r r. So I take the input and in the input it is given has right but I change it to black B as the D of I is white.

[00:27:36]Now I do the operation what I do is I run on uh I iterate on each element.

[00:27:43]Then if the current value is black, I know that after one operation that value will be compulsory white, right? Because that is the given in the uh question that the black becomes white after one operation else what I do is and and and then I do continue else if the if it is white. So I will make the ar of I is equal to white and then the c all of its eight neighbor. So this is like uh from row changing minus1 to +1 and this dj is changing from minus1 to + one like this final index. So these are the index of the neighbor. It is just i + d and j + dj uh sorry. So now I check that like if if this is d i is equal to z and d j is equal to z. So which means that I am just seeing for the current element only. So if this is the case or or this the neighbor the index of the neighbor is just out of the bound I will just do the continue else what I will do I will check that hey hey neighbor are you not equal to me I mean are you different than me if that is the case or this is nothing this is just saying that hey neighbor are you black so you can you can also like say that dumb of f_subi comma f_sub_j is equal to b. So then you will make this a r of i is equal to b. That's it. So this is our uh first uh first operation done manually. And now we have to do the bfs.

[00:29:23]So what I do is that I make the distance array that will store me the distance from the uh nearest zero. So this is the que. So first of all I just uh initialize the queue with I mean so whichever value is blue it black itself I will just push them in the que and for them yeah distance is zero obviously and while Q is not empty I take the front element and pop it then I just go from for it all its neighbors right and I like tell its neighbor that hey like I the nearest zero to me is at uh this much distance. Let's say it is at current distance. So the nearest zero to u can be at current plus one distance only. So if you want to take that you you can take that that's it. So I I check for the current uh these are the index of the neighbor. I check this like if the neighbor is not out of the bound and if the neighbor is not the me itself and I check that I mean if the distance of the zero like if this uh like the neighbor was thoughting that the uh I'm sorry let's just see that if the distance is greater than the this one so I will just change this value and in the Q I will push the current index so that this neighbor will also pass its values to another uh neighbors. That's it. And now in the last I I check the parity like if the parity is equal to one I print the black. If the else I uh print white I mean like uh in this is just intuitively done. Uh first I did the if this iig modulo 2 is equal to zero print this and I saw that the answer is just inverted.

[00:31:14]So I did this. That's it. So that was it in in the code and I hope that you understand this thing.

[00:31:23]Let's move to the last uh question of uh our discussion. So in this question like let's say if there are two integers a so concat of a so this is the function it will return integer after concent uh uh like after writing a and b one after another right so uh this is the function and then I want to the two integer are given n comma m and I have to find the number of pairs That's that such that the x and y both is not both are at most n only such that this concrete of x y will be x + y modul m so I mean the concate of x y modul m is same as x + y modul m that's it and we have to find the number of pairs possible also the t is still 14 and n is 118 which is a pretty big value so Let's try to solve this thing.

[00:32:32]So now first of all let's analyze what does this uh this concrete function means right? I mean let's say if if the two numbers are 1 2 and 3 4 then they will become 1 2 3 4. So the thing is you can write this as like this 12 will be multiplied by 10^2 right you can see here that it is 1200 + 34 right so 34 is same as here but 12 has become 1200 here uh more properly you can write it as 12 into 10^ digit of b because this 12 will be shifted into left this much times and more formally you can write this thing that concent will be this thing a into 10^ of b plus this b right. So now like what what we want is this thing right that concent of a mod m should be equal to a + b modul m. So first of all let's write uh let's write this thing this formula instead of this. Okay. So let's write this. So a into 10^ a b modul m and this is b mod this should be this should be equal to a mod m plus b mod and you can see that this thing is same so it will be cancelled out right now the only thing is remaining is a into this and on the right right side this there is a modul m so I can have this a in into the left of the equation so Now, now I have find the some like maybe a better thing, right? Because I know here that this is zero modul. So like I can say that this m is a divisor of this value, right?

[00:34:31]Okay. So uh taking the a common uh there will be this minus one. So I know that this a cross 10 to power digit minus one is a sorry this m is a divisor of it. Uh m is a divisor of it right or this thing is multiple of m this will be better. Okay.

[00:35:03]So just see here uh this was our a here is our 10 to power digit of b minus one and this should be zero modul m which means that this thing is multiple of m right. So now first of all like this a and how many variables are there? So there are two variables right.

[00:35:33]So the thing is you should try to fix some value and then think that how many possible values are there are. So you can like fix this a and find the how many possible values of this are or you can find this fix this and find how many possible a there are. The better way will be this one because uh the digit of b can be only vary from 1 to 19 right because the n is still only 118.

[00:36:01]So let's say we fix some value of this.

[00:36:04]So we have fixed this value. I know the value of this one. And now I want to find that how many possible a values are there for this fixed this value. And let's call this value y. Okay let's call this value y. So how I'm going to do this? So I know first of thing I know that this a cross y is a multiple of is multiple of m.

[00:36:29]So now assume that uh this m is equal to 2 + 3 + 5 + 7 and this y is equal to 2 + 3. So now I know because like this a cross y is a multiple of m right. So it should contain every divisor every prime divisor right the y has only 2 + 3. So this 5 + 7 other part it should be and it must be come from this a. So I know that in this divisor in the divisor list of a there will be five there will be seven there can be any many other elements but five and seven will compulsorily come right. So then and only then this a comma y will be the multiple of m that that is the another observation right.

[00:37:22]So how we will going to do that.

[00:37:28]So first of thing like we have to find what is the how many like what is the smallest value of a it it is possible.

[00:37:37]So first of all we will find that how many values there are in common in the a and y. So we have to find the common values.

[00:37:48]So this thing can be just found by gcd of y comm right. Uh because let's say if you do the gcd of this thing you will get six. So you will find the common values. Now you have to find that what you want from a what prime divisor you want. So it is just so total divisor m have this much and this much divisor are made from y.

[00:38:12]So now this much divisor will be made from a.

[00:38:20]So yeah this I mean this much divisor will a will have.

[00:38:25]Okay. So now this is the smallest value.

[00:38:29]So like uh so I get that a should be the multiple of a should be the multiple of this m / gcd of y comma m that's it now let's say let's uh let me ask you a question okay so assume that I ask that like in range 1 to 100 how many values there are that are multiple of three and this is also just like a fundamental formula the answer is just 100 divided by 3 that's it so for here also like there are total n possible values and the multiple is this one. So the answer will be this.

[00:39:16]That's it. So this is my possible answer of c value of a. This is it. Okay. So now we have talked about the cnt of a.

[00:39:27]Okay. How many possible pairs?

[00:39:29]How many possible values a can have for a fixed digit? Right?

[00:39:34]Uh remember we have fixed the digit. But what about the b? What about B?

[00:39:40]Uh I know that the digit of B are fixed, right? Digit of B are fixed.

[00:39:49]But it can have uh also there is another constraint on this. So that's it. That's a easy one. I mean let's say let's say if digit is equal to two.

[00:40:00]So you can just take any any two-digit uh number as a b that's it. So how many twodigit number there are. So it is nothing but 100^ 2 minus so this is uh so 10^ 2 - 1 this is the biggest value we can make and 10^ 1 this is the smallest value we can make and + 1 yeah so this is the range that is nothing but it is just 10^ 2 - 10^ 1 so yeah so like for some particular digit The CNT of B will be equal to 10 to power digit minus 10^ digit minus one. That's it.

[00:40:54]So yeah that is it we have to do in the question and let me see the code also there were some bugs in my code. So and also there was the snippet I used. So I take the code of the editorial. So u 64 is just long long and this is mode dm max is 19 and what I did is made a array p10 which gives me the power of 10. So uh and I have just it and just found the power of 10 till 19. So from here I take the input t and for each test case I take input n and m. So initially answer is equal to zero. Okay. Then I I iterate on each digit. So d8 can be one from 1 to 19.

[00:41:40]Now I found that like like I find the what is the left what is the smallest possible value of this digit as we discussed here right the smallest will be 10^ digit minus one so that's it we find here what is the biggest value that can we find so yeah it can be 5 to power uh sorry 10^ d but what is the n value smaller So n is like a cap on that right? So uh let's say if I want three-digit number so three-digit numbers can be anything from 100 to 999.

[00:42:23]But what if the n is equal to 300 only.

[00:42:26]So then I can just find the values from g 100 to 300 only. So that's it. So n is like a cap on the right values. So I whatever is minimum I take it. So this will be my right range. Okay. CNT of Y will be just R minus L. Right? And now I have to find the CNT of A.

[00:42:47]So first of all I find the common values. So common values are just the gcd of this thing like I was talking y but yeah you know what was y right? Uh yeah this is y. So 10^ digit of b minus one. So I write here. So this is 10^ digit minus one and this is m. So I found that what is the common then I see that what is the need I mean what like a should be multiple of what number? So a should be multiple of this number and then I find the cd of a is just n divided by need. That's it. So this is just done in in the line here. So this is the gcd. So n / m by g. So this is my CNT of A. This is my CNT of B. And the multiplication of them is I will just add it to my answer and I'll answer it more. And in the end I just uh print the answer. So that is it in this code and in case you have any doubt you can share in the comment box. Uh so that's it for the for now.