AtCoder Regular Contest 219 | Video Solutions - A to D | by Anish | TLE Eliminators

Hinzugefügt: 2026-05-11

[00:00:01]Hello everyone. So today we are going to solve problems A, B and D of add coder regular contest 2019.

[00:00:09]So let's start with first problem. First problem is similarity.

[00:00:13]Uh let's read out the problem statement.

[00:00:15]You are given n distinct strings s1 to sn and each of these strings is a string of length m consisting of 0 and one. So uh there are n binary strings.

[00:00:30]They are in binary strings and uh we what we have to do determine whether there exist string t of length m consisting of 0 and one satisfying the following conditions. What is the condition? uh every string si matches t in at least one position. Uh like what exactly it means mostly for every integer i from 1 to n there exist an integer x i such that the x i character of s i and the x i character of t are the same.

[00:01:16]So what exactly we have to do? We have to find out. We are given n binary strings. N binary strings uh from s1 to sn.

[00:01:28]And uh we have to find out a uh binary string t which has at least one uh which has at least one element uh at this at a position which is uh from which is same in every uh band every given input boundary string. For better clarity, let's uh see an example. There is this is the example.

[00:01:54]So what we have given here? We have given n= 5. n= 5 and m= 3. Uh m= 3. M is the length of length of string and uh there are five strings given here and we have to output a string t which must have at least one element common.

[00:02:24]At least one element common uh at any place.

[00:02:45]So uh let's check it out here. So for example here first element is 0 0 0 and second element is 1 1 1 and third element is 1 1 0.

[00:03:00]Fourth is 1 0 0 and fifth is 0 1 1. So how can we uh think of uh uh the approach to uh find out the uh output uh string t. So first of all uh there uh like uh we have to think about the t which have at least one element common at any place uh to each of the five strings.

[00:03:26]So uh we can think like uh instead of thinking what strings must be t. Instead of thinking what strings what strings uh t must be we must think what t cannot be because uh there let's say we have five strings then uh the D string cannot be a string where uh uh any of these uh any of these s S any of the S SI string has no elements common. So uh what are the uh strings which cannot be t. So we can take we can simply take comp complement of each of the string. For example, the complements are here. Uh the complements are 1 one and uh 0 0 0 then uh 0 0 1 then 0 1 1 and 1 0 0. So if t is any of this string, if t is any of this string, then uh it uh will not have any common element from at least one si.

[00:05:15]So for example, if t is 111, then uh it will not satisfy the s1. If it is uh 000, then it will not satisfy the 111 and so on. So we can think out uh uh like this uh that what and what are the total number of elements the t can be like what are the total set the t can be. So t is the it is of length m length m.

[00:05:45]So what are the total number of antior t can be? Uh it is uh 2 ^ m uh minus one.

[00:05:58]So for example uh t to the power n minus one. So for example if the here m= 3 m= 3 then the possible possible t's are 0 0 0 1 0 0 1 0 0 1 1 then 1 0 0 1 0 1 1 0 1 1 1 These are the all possible T's.

[00:06:34]And what and uh here we have the uh list of ts which cannot be the output. So we will just remove them. One here uh here the 111 is removed. Then 0000 is removed.

[00:06:56]Then 001 is removed. then 0 1 1 and 1 0 0. So the possible answers are 1 1 0 1 0 1 and 0 1 0. So uh these are my this will be the my answer for this uh for the question here for this question this will be the any of these will be the correct answer.

[00:07:22]So what we actually what we actually doing uh so uh let's say let's uh check out the constraints on uh check take a look on the constraints. So here the constraints are the n is between 1 and 2 2 10 2 that means 20,000 and uh m is 1 to 100. So m is 1 to 100 and uh yeah these are the constraints.

[00:08:07]So our idea is we we can iterate from one uh actually zero we can iterate from zero to 2 ^ m minus one and uh then and just uh checking out that each string each binary string for the z uh integers if they are in the in this list or not. If there is let's say call this list forbidden list.

[00:08:40]So we can just iterate over 0 to 2 or n minus one. And uh let's and then check every if the integer is in the form list or not. If it is uh if it is yes, if it is in the in the list, then uh we will continue to iterate iterate and if it is not in the for forbidden list, then just uh uh print the output the integer and that will be our answer.

[00:09:07]But there is a catch here that 2^ 2 ^ mus 1 here m is between 0 and 200 between 1 to 100 2 the^ 100 minus 1 it is a very large number uh so so here the here the constraints of n will help us because the number of the n is less than equal to 20,000.

[00:09:34]So if we clearly see this then this is around uh uh this is around uh 2k power 15. Uh what is 2k^ 15? 2^ 15 is about uh 30,000. Yeah, this is about 30,000. So this is about 2^ 15. So there are maximum uh max. So what it actually means that there are maximum 2 to the^ 15 uh elements uh there maximum 2^ 15 uh elements in the forbidden list.

[00:10:24]So while iterating from 1 to 2 the^ n minus one while iterating from 1 to 2 the^ n minus one if m is less than equal to 15 then we uh we can uh uh do the our iteration normally it will take about uh 30k steps and if m is greater than 50 then we can add it from 1 to n + 1.

[00:10:53]Why it is so? because there are maximum there maximum n elements in the forbital list. Uh there are maximum n elements in the forbital list. So if we are trade from 1 to n + 1, there must be an uh an element which is not in orbital in the forbital list.

[00:11:24]uh so let's say our n is 20,000 then uh if we are trade from 1 to n + 1 then it is guaranteed that the n plus uh the 20 20,1 element can be our answer.

[00:11:50]So this this is our whole idea to solve this problem. So so there is a now there is a question that how should we uh how should we uh store the n elements in the list.

[00:12:19]So we can use map or set uh for that.

[00:12:29]So what will the time complexity for uh this approach? So here we are processing uh n strings of uh length m and uh uh n strings of length m to build the hashmap or set to build the uh map.

[00:12:49]Yes, map or set. So it and then uh we are uh and then we are checking it up to n plus number. This is the our first step. Then we are checking uh n + one numbers uh at most n + 1 numbers because it is the maximum we are checking uh n + one numbers that if they are in the list or not and what then we are doing is uh we also have to convert the integer to binary integer to binary uh for checking in map because we storing the uh inteious the strings in the map for checking in set map.

[00:13:42]Uh it uh this will take uh around m steps and then we are checking checking will take uh around of m time.

[00:14:00]So this the maximum so the maximum time complexity will be around O of M into N and uh here uh M is 100 and N is 20,000 so it will guaranteed pass uh it is actually given 100 but uh we are uh the maximum that we will use is 15 so that's not the case here and Uh and about the space complexity uh the hashmap uh a hashmap set and what is it storing? It is storing n strings n strings of length m. So it is about of m into n.

[00:14:53]So that's it. That is acceptable. Let's go to the code for walk through.

[00:15:02]So here is the code.

[00:15:05]We are taking inputs n and m then uh uh initializing the set and uh they then taking the input string and for each string we are taking complement of them.

[00:15:17]Uh if x if this character is one then we we are replacing the character by zero and if uh if it's zero then we replacing by one. then we are inserting that uh string into the set and then uh the k is the maximum number of times we have to iterate. So if m is less than 15 then we will just find out the 2 2 the^ n minus one which is uh can be found using the bit set operation and uh if it's greater than 15 then we can use n + one and uh then we will iterate from 0 to k and uh then we are using this method uh to convert integer to string.

[00:16:02]Then uh uh we if the string is uh a string find that if this string is found in the set then uh we will just uh output the no.

[00:16:16]If this string is it can't be found in the set then we will just uh output that string and yes yes and if the string is found in in this set that like in the forbidden set then we'll just continue our search and if we didn't get any of this string then we will just uh see out uh no. So that's all for the first question.

[00:16:41]Now, now let's move to the second question here.

[00:16:49]So, now let's uh check out the second question. The second question is the reverse permutation. So, let's read out the problem statement. You are given integer n and a permutation p1 p2 till pn of 1 to n and uh first I'll write out what is given. We are given a permutation p uh which is uh a permutation is the sequence of uh numbers from 1 to n 1 to n in any order.

[00:17:18]And uh for a permutation q= to q q1 to qn of 1 to n let dash be q1 dash to q1 dash be the lexographically smallest permutation obtained by the performing following operation exactly once. What is the operation? Choose a pair of integers L and R and uh reverse the uh inteious between the positions L and R and more precisely like what it actually means replace Q with Q1 Q2 to Q L - 1 R to R - 1 L uh and what it exactly is saying that for example if I have a string uh 1 1 2 6 4 5 3 So what we can do that we can choose any of the any of the strings L equal to let's say uh two and uh R equal to let's say four then we can choose two swipe reverse this the inteious between this L and R. So L equal to 2 is here and L r= 4 is here.

[00:18:28]So we can by reversing this string we will get 1 4 6 2 uh 5 3. Uh for example if we again want to reverse it then we choose L= 3 and R = 6 then the L= 3 is here R= 6 is here. So so if we want to apply the operation once again then 1 4 3 2 5 6.

[00:18:55]So this is what the operation is saying of. So we have to find the number modulo this one of permutation q such that q d equal to p. So what we are given here that uh uh we have given P like uh what we have to do is uh we have to apply uh here we have to we have to do the operation only exactly once like we can't in fact cannot do more than one operations on this on the string. So if we have a string Q, we do an operation uh here and make this Q dash and this Q dash must be lexographically smallest string.

[00:19:43]So graphically smallest string or smallest sequence uh smallest sequence possible. Okay.

[00:19:54]So what is the lexographically smallest sequence? That means uh uh the smallest sequence in the uh dictionary order. For example uh here if we take example of here 1 2 6 4 5 3.

[00:20:12]So by one operation what is the minimum what is the smallest lexographically sequence we can achieve using one operation only. So here one and two are uh already there at the start. So we don't have to uh include these in the uh flipping uh include these in the swapping of the flipping the reversing the substring. So we can choose uh among these four only.

[00:20:43]So we have uh many methods many options to do this. For example, if we if we reverse the string four and five, so we will get 1 2 6 5 4 3. If we reverse the string 3 and four, then we will get 1 2 6 3 5 4. If we reverse the string uh 3 and 6, we will get 1 2 3 uh 4 5 6.

[00:21:14]So here uh which is the most uh which is the smallest lexographical uh string. So we can clearly see that uh this one is the most lexographical smallest string.

[00:21:26]So what exactly we have to do to find out the which one is the will be the lexographically smallest string. So we have to bring out the smallest possible string here. For example, if it is the third position of this string. So here it must be three. It must be three.

[00:21:48]So we will just check out the for example here 1 2 6 4 5 3. Then these one and two are in on the correct position. On the first question it is one. On the second question it is two.

[00:22:04]And uh on the third position it is six.

[00:22:06]So we will must replace six by three.

[00:22:11]So we will just check uh where where is the three and we will just replace uh the the the just next element to the element which was which was supposed to be there there. So we will uh by replacing the those uh reversing these this string we will get 1 2 3 and 5 4 6.

[00:22:39]So what can we deduce from this thing?

[00:22:42]Uh so what uh let's say we have a string Q.

[00:22:50]Uh we have a string Q and uh first uh to choose what must our L and R will be. We have to iterate from iterate in the Q sequence and check whether the elements are on the correct position. For example, if the first position is uh uh one, then we will go ahead and second position is the two then also we will go ahead. If the third position is three, then we also we will continue iterating till uh when we will find a mistake here. For example, if the on the fourth position, let's say there is a five then uh we have got the uh five got the wrong element here. So we our L will be this one and then we will search for the four in the next element next elements and wherever the four will be we will uh uh make that index R and then reverse this string.

[00:23:44]So if uh we can reduce that if uh the string q has uh first k elements correct then the string q dash and q dash will First k + one correct elements.

[00:24:25]Now come back to the question. Uh here here in the question we were given P. Here we have given we are given a P.

[00:24:37]Uh we are given a P that means we are given we are given the correct sequence. We are uh the given the uh uh let's not say correct uh we are given the final sequence and that means we have given which is given as q dash. So we have given q dash and we have to deduce how many q are possible how many q are possible uh to which if uh if I apply the operation then we will get the exact p given in the input. So what we have to find out find the number of permutations q uh 1 to n such that q dash equal to p. So we are given the final sequence after the operation and we have to find out number of possible Q's to which if we we apply this operation on that we will get the same P which are which is given on the in the question input.

[00:25:46]Now what should be our approach to solve this problem? Uh let's check it out using a question here in the input 1 2 64 53. So let's say our question is uh our P p given is 1 2 6 4 5 3.

[00:26:07]So if uh let's so here we we can see that the first position is correct uh the second position is correct and uh rest are not in the correct position. So we can deduce that the Q must have at least uh the Q must have at most one position correct. For examp if if Q have more than one elements correct. If Q have more than one elements correct then the P will must have more than two elements correct because uh uh currently we see that if Q has first K elements correct then QS will have first K + one correct elements. So from that we can deduce that the Q must have uh less than equal to one elements correct.

[00:27:01]Less than equal to one one elements correct.

[00:27:08]So now we have uh we are then we will be having two cases here. We will be having two cases. One case is uh there are zero correct elements in the Q. Zero correct elements uh in Q.

[00:27:30]And the second case is uh one incorrect element in Q.

[00:27:42]So how can we reduce Q from P? So here what we the P is given 1 2 6 4 5 3.

[00:27:53]So if we apply the uh one if we apply the operation on P for example here if here the one character element in Q. So the Q must start with one here. This one is always the Q must start with one here. So what are the options on this place? This place cannot start with two because uh uh the two because it has only one correct element in Q. So uh this place cannot start with two. It must start with either six or four or five or three. So let's say it start with six.

[00:28:31]So when you so to start with six, it must uh be swapped with two only. Uh so it's here will be two uh then four then five then three. So Q can be 1 62 4 53 and uh because if and then if we apply the operation on L= 2 from L= 2 and R= 3 we will get the uh result P.

[00:28:59]Now second one is one will also always be here. Then at the second position we can have four. We can have four if two have four on the second position. We must uh reverse this string from 2 to four. So what we will get four 6 2 5 3 here choosing L= 2 and R= 3 we will get the P.

[00:29:26]Similarly uh if we choose one here then uh uh and the second position let's uh uh we will choose if to five then for that we must uh swap between uh 2 to 5 we swap uh we must reverse not swipe reverse the string between two to five.

[00:29:46]So we will get five then four then six then two then three. So uh uh here choosing l= 2 and r = 4.

[00:30:00]Here you got r= 4 and r = 5 and we will get p and uh what is the next option for the second place? We can have uh three on the second place. So if we have three here then we must uh reverse the string between two and three. So what will we get then? 1 3 then 5 then 4 then 6 then 2. Here choosing L= 3 uh L= 2 and R = 6 we will get P.

[00:30:33]So how many options we have? If we choose one correct element in the cube we will have we will have 1 + 2 + 3 + 4. We have four options.

[00:30:51]Uh similarly if we choose uh similarly if we choose for uh this zero correct elements in Q then for Q it must must start with uh uh it must not start with one. It the first element cannot be one. So it must start with uh either let's uh write P here. Uh what is the P here? P is 1 2 6 4 5 3 uh and then Q it uh it is not it has zero correct elements in Q. So the first uh element cannot be one. So it can be two. So if it is two then uh if it is two here then uh we uh for to keep two on the first place we can we'll have to reverse this string 1 and two.

[00:31:55]So we will get 2 1 6 4 53. Here choosing L= 1 and R= 2 will give us P.

[00:32:04]And similarly we if we choose here six next element six then we have to reverse the string between 6 and 1. So we will get 6 2 1 5 4 3 uh sorry 4 53 4 5 3. So here choosing L equal to 1 and R= 3 we will get P.

[00:32:25]Similarly if we choose four on the first then four and we have to reverse for between the string 1 and four then we will get 4 6 2 1 6 2 1 and 53.

[00:32:39]Here choosing L= 1 and R= 4 will give us P. And then again uh if we choose five then we will reverse between 1 and five and five then uh 4 6 2 1 4 6 2 1 3.

[00:32:58]Here choosing L = 1 and R= 5 will give P.

[00:33:04]And uh if the first element is six uh sorry three the first element is three then we have to reverse the string between 1 and 3. So 3 5 4 6 1 3 5 4 6 2 1 we choosing L= 1 and R = 6 will give P. So how many options are there? If we choose uh zero correct elements in Q we have 1 2 3 4 5 we have five options.

[00:33:37]So total options are four and five. So total options will be 5 + 4 equal to 9.

[00:33:46]Uh you can we can see here in this in the problem statement we have answer 9.

[00:33:54]So how can we code this? So here you can see a pattern pattern that uh if we are having uh let's say we are having n elements in the p and and uh the first uh let's say the first k elements are in the correct position in p uh in p uh correct position n elements in uh uh p total n in And uh we have to we have K correct elements in P. So for each elements for let's say then we can have so here we can reduce Q will have 1 to K minus one correct position. Q can have uh one 0 to K minus one correct position.

[00:34:46]And uh let's say if uh Q has k as correct position in in this uh in the P then it will have options. For example, here we had one correct element in P then we had four options. Why? Uh because uh uh we had uh we had fixed the first position and uh the second position had only uh four options. It can't be one and it can't be two. So it had four options. So if I have k dash elements in p then we will have n minus k dash minus one uh options for uh uh options for uh uh that case. So let's say here we have k dash. So when we have k dash correct position k dash correct uh then we will have k dash correct k dash elements fixed here and we the first element from where on which we have to apply the operation we'll add k dash + one positions.

[00:35:48]So let it be uh m. So let's let it be m like uh we have to uh apply the operation on the m mth position. So then we will have we will have the answer uh n minus m. So m will start from where? For example, if uh the if q has zero correct position then answer will be n minus0 uh sorry n minus one. If Q had have one correct position then it answer will then its number of possible ways will be N minus 2 and if Q has two correct position then N minus 3.

[00:36:31]So uh similarly if uh it will go till uh k minus one correct position then it will be n - k + 1 sorry n minus k only.

[00:36:48]So uh for the simplicity we can iterate from we can iterate from 0 to from 0 to k minus 1. Instead we can iterate from 1 to k and just uh sum from n minus k.

[00:37:05]Here we can write it in the form summation uh k equal to 1 to k and n minus k. This is uh the uh uh all possible ways for n minus k element. All right. This is the all possible way is to choose Q.

[00:37:25]Choose Q such that Q dash equal to P.

[00:37:32]And what is N minus? This summation of N minus K is what uh it is it can be written as uh this summation n minus summation k = 1 to k. So uh k so it can be n into k minus k into k - 1 by 2 this is the total number of possible ways to choose q.

[00:38:04]So there is and there is one more catch here that what if the current uh uh the current string uh the uh the current string is already perfect.

[00:38:32]Uh for example, if P = 1 2 3 4 5 6 then this answer let's say this answer is A.

[00:38:45]Then the answer A is still valid but there let's read read the question again here. What is the question?

[00:39:00]We can choose L equal to R.

[00:39:05]Here we can choose L equal to R. What what that what does this mean? That we can choose to not uh reverse the any of these uh string elements.

[00:39:17]For example, if we choose uh L= 2 and R= 2, then we we'll get the same elements.

[00:39:27]So we can choose to uh go with the same uh Q by applying an operation. So we can choose the any an operation and we can get the same uh uh uh string again. So this is also a one also one method. So if the string uh is already sorted in lexographically manner then we can choose to stay with the string and so the number of ways will be added up by one because we have one more uh we got one more one more way to get the Q. So here for for the P we can also get Q the same as P 1 2 3 4 5 6. So the set of the possible uh Q's will can also be uh same as P.

[00:40:23]So hope you understand understood this question. Let's go through the code and uh uh this is the code for this.

[00:40:33]So here is the question. uh we took the integer uh and uh as input then we are counting uh the and how many number of elements are in this are on the correct position and uh this is for assistant in the counting. So if the bool is true and the x the num element is same as the index then we will increase the count and if it is not then we will just uh uh make the bool zero bool false so that it doesn't count anymore and uh we'll we will update the answer by the formula we just uh we just saw and took it modulo the given number and one more thing if the count is equal to n that means Say the number of elements in the correct order is exactly equal to the total number of elements. Then we will increase the answer by one. Then again modulo for uh safer side and we will just output the answer here. What is the time complexity of this code and space complexity? We are just iterating from once in the whole array. So we can say that the time complexity will be big of n. And uh what about space complexity? The space complexity we are here you can see we are not storing anything here. We are just uh iterating on the way of go on the w and uh the answer is also just a mathematical calculation. It doesn't use any stored value. So it will be also one. It is uh we are not storing anything. So that's all for second question. Uh we can now move to the third and third question which is so now we will be solving question number D grid game. Uh let's read the problem statement here. There is an N and N into N grid. The cell at the I rows from the top and J column column from the left is denoted as cell is and cell is contains a I stones. So Alice and Bob play the following game using the grid. Starting with Ellis uh the two players alternate taking runs and uh on each turn the player chooses a cell and moves at least one and at most kstones from it together to an adjacent cell above or to the left. So what exactly it is saying that uh uh we have a grid uh let's say we get of three 4 into 3 and uh we have some stones uh trapped up uh on each of the boxes and we have two optations and uh Alice and Bob are playing a game uh turn by turn and we have two operations either we can move uh a stone on the left or or we can move a stone on the top. So now let's read the next statement uh starting with choose a cell and from it above or to the left specifically the following steps are performed in order.

[00:44:03]Choose a cell. We choose a cell IC and that contains at least one stone. And uh cell one common one cannot reach of course because the it is doesn't have any option neither left. It can't go left or right left or top. So we can't choose one comma one. And let's see the number of stones in the cell and choose an integer x satisfying x. So we can choose um any number of stones. Let's say it if it has five stones then we know don't have to choose all all of that ones. We can choose any number of stones. So any al can choose any number of stones and choose as a destination either cell I minus p or cell i jus then remove x stones from i and move all of them to that cell. So we can uh even we can choose any of these direction either left or top and uh then move these stones from that cell to the uh destination cell. Now the player who cannot take a turn first loses. So now after playing optimally one of them will uh then after optimally then at a point all of the stones all of these stones will effectively eventually go to the one cell and if all of these stones then when come to one cell then it doesn't have any of these uh operations. So it can't there can't be any operation on those stones now. So uh uh there it will be a case where neither Alis nor Bob can take out turn first then you have to determine which player wins the when play both optimally. So we have to determine which player will win. So here uh starting with Alice. So Alice is starting the game. So now uh uh concentrate let's concentrate on this what on is it given in this question.

[00:46:00]So we can uh first we must calculate distance between them uh distance between the grids. So here so we have to eventually put all the stones to the 2 1 comma 1. So let's calculate the distance between them. So from here the distance uh is one. Here distance is two 3 4. Here also 1 2 3.

[00:46:39]Here 2 uh 3 4 uh here it is five 5 6 and 7. So distance is basically for example if uh we have to calculate distance from I J I comm Z to 1 comma 1 we it's just I -1 + J minus one.

[00:47:11]So these are the distances between them.

[00:47:15]Uh now let's focus on a shorter grid.

[00:47:19]Let's say this uh 3x3 grid here.

[00:47:24]It's a 3x3 grid here. So, uh for example, if Alis put this uh uh stones from uh this grid to here, then uh Bob can uh for example, let's say Alice put two stones from uh the grid one uh 2a 2 to 1 comma 2 uh 2 comma 1. Then the bob can put the same number of stones from 2 comma 1 to 1 comma 1.

[00:47:58]Let's call this u.

[00:48:01]So what actually happened here? So when the alis put two stones from here to here and the bob place the same stones from here to one common one. So these stones got get uh uh collected at one but there's nothing changed for the uh for the sake of game because again there it is the again the allies next allies turns come again the allies turn. So now we can say that if we put uh uh because the distance between this cell distance between this cell uh is from 1 is even uh the Bob can always mirror uh let's say Bob can always replicate this step taken by Alis to cancel out the uh Alis turn because always for example there this is also an even distance cell. So if Alis put some stones here then Bob can put the same number same stones to one comma one and the then again the alist turns will come. So we can say that if the distance between a cell from 1 comma one is even then uh there is no meaning of the making that it will don't affect the overall answer that who will win it. uh uh this makes the cells with even distance very useless for the game. So we can safely ignore that. So we can ignore these cells, these cells and these cells all these cells with even distance because the Bob can always mirror replicate or mirror the same number of same step taken by Alis to cancel out the alis step. So it is uh very and the even sales are useless.

[00:50:01]So we must focus on only the uh odd sales. So for example, let's make another uh let's make another table.

[00:50:23]So here and we will erase out these cells with even these are useless cells.

[00:50:41]Not check out on the cells on odd number of place or distance places.

[00:50:48]Okay. This is one 1 then three 3 this is five and this is five.

[00:51:06]So now let's focus on k equal to let's uh focus on the question next. Let's say k equal to 2. What was k? gave us the maximum number of stones uh which uh uh one can carry. One can carry at once.

[00:51:22]One can carry. So let's say a shorter grid and uh this is 3x3 grid and let's say the k equal to 2. For example, if if I assume k equal to 2, then uh if any cell here have a uh uh if any cell here has two stones in uh then uh let's say it has let's say it has four stones. Uh let's say it has one stones, it has four stones, it has three stones. Then uh if at the end uh if at the end two stones are left then of course the whoever's turns weight will be uh we'll put all those two stones into the one into one into the one one cell so that the other person don't get a move and he loses. So if the if if it if it is two stones then he can safely move all the two stones all two stones into the one common one cell. And if it is one stone he can also move uh the one stone into the one cell in one move. But what if the stone number is three? So but k so here k equal to two but number of stones is three. So he can either choose one stone or choose two stones.

[00:52:56]So if you choose one stone then uh the next uh player will choose the rest two stones at once and the person choosing one stone will have to lose. For example, if Alice uh choose one stone then Bob will choose two and Alice will lose.

[00:53:19]If Alice choose two stones, then Bob will choose one.

[00:53:26]Again, Alice loses.

[00:53:32]So the problem started at the uh three stones. Three stones. So if there are stones so we can calculate that if there are three stones and the whoever's turn it will be he will definitely lose.

[00:53:56]So we can for example if I have uh uh here six stones left for example if I have five stones left then uh we we can uh choose to so what we can say here that the three stones the group of three stones was a trap here. So if there are three stones in a group then it's a it's can it can be called a trap. It can be called a trap that whoever's turns will remain with three stones he will absolutely lose. So we can choose to uh make the remaining stones uh in a group of three. For example, if there are five stones, then we will uh make a pack of the three stones and the remaining stones will be two stones. So we can choose to make a group of three stones, packs of three stones and uh then calculate the remainder of stones uh using uh using the total number of stones available.

[00:55:01]So what actually we have to calculate that if there are uh at last at last of the steps if there is any trap boxes uh left or not. So if there is any trap box left for any uh any uh player Alice or Bob then he will definitely lose. So let's uh go to the next part of this question. So now after taking remainders uh in the grid after taking remainder in the grid we will left with uh uh and uh we have already skipped the cells with even distance. So we are left with what? We are left with we are left with the number of stones less than equal to K in each boxes with order distance or distance. So for example here the number of stones is less than equal to k because we have already uh take uh took the remainder uh k + 1 and uh so we have get the got the uh the remaining number of stones less than equal to k.

[00:56:17]So now and we can always uh see that for example if any number of stones are available on this cell and this cell then if a player if a player moves these stones from uh odd cell to even cell then the next player can always move the those stones to even cell to again odd cell then again even then again odd. So uh this doesn't matter that the number of these stones are uh on are there where on this uh cell uh it will always turn back to the odd cell to one one comma one cell.

[00:56:57]Uh so here we can put the remaining remaining k uh le remaining less than k stones into chunks. So we have to basically what we have to do is to uh pair up these stones because uh for example if uh now so now what will we do is break our for example we have remaining chunks here uh remaining chunks which which are all less than equal to k. So we will what we will do that we will break the remaining chunks remaining stones into chunks of uh uh of just for example one chunk will contain the one stone then other chunk will contain two and the next will contain four then again next will contain eight and uh so on next will be 16. So we will chunk we will break this uh the number of the all these stones into uh 2 to the^ k uh places 2 to the power k uh uh like one chunk will have 2 to the^ k stones for each of these uh for each of these stones.

[00:58:20]For example, if I have uh five stones left, then we will break them into 1 + 4. Uh if I have uh six, then 2 + 4. If I have 7, then 4 + 2 + 1. So what why we are doing this uh in this method?

[00:58:37]because uh we have we can always write any integer we can always write any integer into sum of uh uh sum of 2 to the^ k chunk 2 to the power k inteious. So we are so that's why we are breaking the number of the remaining number of stones the remaining number of stones into 2 to the^ k chunks.

[00:59:00]So uh now you will get in in few minutes that why we are doing so. So now what we will have we will have so now in our uh grid instead of having number of stones we will have uh chunks in the places uh this was even place so we will ignore this. So we will have uh chunks in these places. For example, two uh the chunks with two stones, chunk with four stones or eight stones or one stones. uh we will have only chunks here.

[00:59:35]uh and uh yeah so why we are uh making them into chunk because let's say Alice uh let's say it is Alis's turn let's say it is Alis turn and he uh put some of the chunks for example it put two the chunk of two stones into one one common one then uh the Bob have to let's take.

[01:00:04]So understand with uh uh smaller grid let's say there is a grid of 3x3 and here uh let's say here we have uh uh chunks which uh we uh divide for remaining let's say the remaining the remaining chunks the remaining stones which was left uh by after uh uh make making a remainder with k + 1.

[01:00:37]We are dividing those stones into chunks. Here the chunks are of weight.

[01:00:42]Uh remember the eight chunk can contain two stones, four stones, eight stones, 16 stones and whatsoever. And here also two four etc. So let's say if Alice put the two stone chunk here then uh Bob can also put the two stone chunk here and uh it can it will be cancelled out because it doesn't then it is uh cancelled and the Alice turns will move again and then again if Alice makes this uh port chunk to the one in one then the Bob will again make this port chunk into one comma one and then again Alice have it her turn and then uh then again she can uh move this uh remaining chunks uh 8 and 16 8 and 16 turn chunks all together to one comma one and win the and she can then win the game. So we can say that if at any uh if at any time of turn if at any time of turn time of turn uh if let's come back here uh uh also if uh at any time of turn it uh if the p for example here uh the two was uh Here the two chunk the chunks of two stones was covered with um here was paired with a chunk of two stone here and similarly if a chunk of four stones was covered with a chunk of four stones here. So was paired with. So if the uh uh remaining stones remaining stones are not in pair of chunks are not in pairs actually. So then the player uh who's turn will be the winner because the player then first choose the that chunk which the other player also have and at last the the current player will have those chunks uh have the remaining chunks which the other player doesn't have and uh then he he or she can always put all the chunks together into one common and win the game.

[01:03:26]So what actually we have we are we have done till now. First of all what we are doing first of all we have are ignoring uh the event cells even distance cells.

[01:03:44]Second uh we are uh second we are taking remaind uh remainder of k + 1. Actually we are making traps of k + 1 k + one stones and uh after those traps we are have making a remaining uh remaining stones uh by calculating remainder from k + 1.

[01:04:14]Now uh after that what we are doing? What uh we are doing is uh k + 1 uh the remaining stones uh turn remaining stones into uh chunks or into chunks of 2 ^ k and y to the power k you will get to know.

[01:04:53]So y 2 to the^ k here uh as we are turning the remaining stones into chunks of 2 to the^ k we can have for example uh let's say we have five chunks five stones then we will turn them into 1 + 4. So what is one actually 0 0 1 and what is four actually uh this one uh the four will be uh 1 0 0.

[01:05:26]So then we can see that this chunk and this uh there is a chunk of one and a chunk of four this this is not balanced.

[01:05:35]So we can say that it is an unbalanced.

[01:05:38]This is unbalanced.

[01:05:42]So uh the person which which will have the current turn will always win. Uh current turn will win.

[01:05:58]And now so what actually we are uh doing is that uh we are for example here we have a chunk of uh four and uh one and we have a chunk of 0 0 and one. So we in one cell we have chunk of four and one and one cell we have chunk of only one. So here we can see that there is a pair of one. So we will apply an operation so that the pair is must be cancelled out. So here we it will have zero. Here both have zero so it will must have zero and here this is not uh this is an unbalanced like it doesn't have any pair so it must have one so what operation makes uh this what operation is this actually this is z operation this z op output zero output zero if pair and uh uh uh it's it output one uh if it's not appear uh now let's go to the code and understand it.

[01:07:11]So here is the code for that question.

[01:07:15]Uh we are taking inputs n and k. The k is the maximum number of stones which one can carry and uh the n is the number of cell number of cells uh sorry n is the grid and uh uh we are initializing x which is the result of zord with zero because we are assuming they already appear and uh the a is uh uh the element which we are taking input. So what we are doing we are taking input and checking if the uh input is uh if the cell is even or odd cell is having even distance or odd distance. So if it is even distance then we will continue only we are because we are ignoring the even distances even distance cells and if it is odd we are taking zord with a with rem uh taking remainder by dividing only by k + one.

[01:08:09]So when uh when we will take Zord with we will uh get an output if uh it is not zero that means uh it uh uh doesn't have perfect pairs for each chunk and uh that means if it it is uh balanced it is unbalanced and the uh person which which is starting this uh uh it is which is starting his or her turn will win. So Alice is starting his turn, her turn. So Alice will definitely win and uh uh if it is zero then it has perfect pairs and Bob's uh Bob Bob's action can always cancel out the Alice's action. It can uh mirror out the Alice's action. So uh the Bob will always end up uh making an action to cancel out Alice's action and Bob will win because then Alice uh will not have an option to make a move.

[01:09:10]So this is all for this question and I hope you understood those.

[01:09:16]Uh uh always uh make a comment if uh you have any doubt in any question or uh uh if you want uh me to improve explanation for any part and if also if uh I made a mistake uh in any problem here and always also do subscribe to the daily channel and uh like if you uh if this explanation helped you in any way and so thanks for your watching.