i have devised another apporah for same but i would have liked to understand what terence has said ?
On Sat, Dec 25, 2010 at 3:01 PM, Ankur <ankur.kkhur...@gmail.com> wrote: > when you are talking abt starting from 1 that means that array is 1 > based , right ? > > and how did you get the steps calculated. please can you explain, once > more > take this example, a trivial but albeit will help me explain. > > 111 > 000 > 000 > > and > 011 > 100 > 100 > > if it is feasible for you to reply . > > On Dec 8, 1:45 pm, Terence <technic....@gmail.com> wrote: >> As Amir pointed out:> convert the first row and first column to all zeros >> >> In details: >> >> 1. choose operations on first row and first column to make up-left >> element 0. >> * There are 2 cases, 2 choices for each case: >> 1. If the up-left element is 0, then >> 1. toggle both first row and first column, or >> 2. leave both untouched. >> 2. If the up-left element is 1, then >> 3. toggle first row, or >> 4. toggle first column >> 2. for each 1 on the first row, toggle the corresponding column, to >> change first row to all 0s. >> 3. for each 1 on the first column, toggle the corresponding row, to >> change first column to all 0s. >> >> After above 3 steps, if there are still some 1's, no solution is possible. >> Otherwise, compare the 2 choice, and choose the minimum steps. >> >> ----------------------------------------------------------------------------------------------------------------------------------- >> >> In fact, we can directly calculate the number of steps in choice a)-d): >> >> 1. number of 0's on the first row and first column >> 2. number of 1's on the first row and first column >> 3. number of 0's on the first row + number of 1's on the first column >> 4. number of 1's on the first row + number of 0's on the first column >> >> And if we denote the j'th element on i'th row as M[i,j] (start from 1), >> then the problem have valid solution if and only if: >> for each element M[i,j], M[1,1]+M[1,j]+M[i,1]+M[i,j] is even. >> >> On 2010-12-7 22:59, Prims wrote: >> >> > Hello Rajan >> >> > Suppose we have the following matrix >> >> > 1 1 >> > 0 0 >> >> > If a toggle operation performed on first row, it will change all 1s to >> > 0s and 0s to 1s which result in the followig matrix >> >> > 0 0 >> > 0 0 >> >> > It is zero matrix and the result. >> >> > Similarly if a toggle operation is performed on column, it will change >> > all 1s to 0s and 0s to 1s in that particular column. >> >> > Say you have a function toggle(int , Type) which does the toggle >> > operation. >> >> > where number is the number of row or column >> > Type can be of Type.Row or Type.Column. >> >> > Hope it is clear >> >> > -Prims >> > On Dec 7, 5:33 pm, rajan goswami<rajan.goswam...@gmail.com> wrote: >> >> @Prims >> >> >> Can you please elaborate the problem in detail... >> >> >> What do you mean by toggling row and column... >> >> >> 1 Interchanging a row with some column ? >> >> 2 Changing 0s to 1s and 1s to 0s of that row ? >> >> or Some thing else ? >> >> >> In both options mentioned above .. no of 1s present in a matrix can not be >> >> changed to 0s in any ways ... >> >> Please explain the step that can be performed on given matrix. >> >> >> regards, >> >> Rajan. >> >> >> On Mon, Dec 6, 2010 at 11:55 PM, Prims<topcode...@gmail.com> wrote: >> >>> Amir >> >>> Could you please explain with an example in detail? >> >>> On Dec 6, 7:02 pm, Amir hossein Shahriari >> >>> <amir.hossein.shahri...@gmail.com> wrote: >> >>>> actually a greedy approach for this problem exists: >> >>>> just convert the first row and first column to all zeros >> >>>> if after this step matrix is not a complete zero matrix then it's >> >>> impossible >> >>>> to make it >> >>>> On Sun, Dec 5, 2010 at 9:10 AM, Prims<topcode...@gmail.com> wrote: >> >>>>> How do i convert a binary matrix(containing only 0s and 1s) to a >> >>>>> complete zero matrix? Only operations allowed are u can toggle a whole >> >>>>> row or a whole column. The conversion has to be done in minimum number >> >>>>> of steps (a step is defined as toggling a whole row or whole column >> >>>>> -- >> >>>>> You received this message because you are subscribed to the Google >> >>> Groups >> >>>>> "Algorithm Geeks" group. >> >>>>> To post to this group, send email to algoge...@googlegroups.com. >> >>>>> To unsubscribe from this group, send email to >> >>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups�.com> >> >>> <algogeeks%2bunsubscr...@googlegroups�.com> >> >>>>> . >> >>>>> For more options, visit this group at >> >>>>>http://groups.google.com/group/algogeeks?hl=en.-Hidequoted text - >> >>>> - Show quoted text - >> >>> -- >> >>> You received this message because you are subscribed to the Google Groups >> >>> "Algorithm Geeks" group. >> >>> To post to this group, send email to algoge...@googlegroups.com. >> >>> To unsubscribe from this group, send email to >> >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups�.com> >> >>> . >> >>> For more options, visit this group at >> >>>http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - >> >> - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
