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.
