Re: [algogeeks] Re: convert binary matrix to zero matrix
when you are talking abt starting from 1 that means that array is 1 based , right ? Right. 111 000 000 Up-left element: 1 Choice 3: 0 (number of 0's on the first row) + 1 (number of 1's on the first column) = 1 Choice 4: 3 (number of 1's on the first row) + 2 (number of 0's on the first column) = 5 Best choice: 3, with 1 toggle. (toggle the first row) 011 100 100 Up-left element: 0 Choice 1: 1 (number of 0's on the first row) + 1 (number of 0's on the first column) = 2 Choice 2: 2 (number of 1's on the first row) + 2 (number of 1's on the first column) = 4 Best choice: 1, with 2 toggles. (toggle the first row and first column) Clarification: In choice 1 and 2, the up-left element is counted twice, ie. 1. number of 0's on the first row and (number of 0's on the) first column 2. number of 1's on the first row and (number of 1's on the) first column The idea is simple: 1) toggle the first row or not? When 1) is decided and applied, 2) toggle columns to make first row all 0. -- the number of 1's in the first row (original or inverted) 3) toggle rows to make first column 0.-- the number of 1's in the first column (after step 2) On 2010-12-25 17:31, Ankur 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, Terencetechnic@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 goswamirajan.goswam...@gmail.comwrote: @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, Primstopcode...@gmail.comwrote: Amir Could you please explain with an example in detail? On Dec 6, 7:02 pm, Amir hossein Shahriari amir.hossein.shahri...@gmail.comwrote: 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, Primstopcode...@gmail.comwrote: 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
[algogeeks] Re: convert binary matrix to zero matrix
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 goswamirajan.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, Primstopcode...@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, Primstopcode...@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.comalgogeeks%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.comalgogeeks%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
Re: [algogeeks] Re: convert binary matrix to zero matrix
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 goswamirajan.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, Primstopcode...@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, Primstopcode...@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.comalgogeeks%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.comalgogeeks%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
Re: [algogeeks] Re: convert binary matrix to zero matrix
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 goswamirajan.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, Primstopcode...@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, Primstopcode...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%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.
Re: [algogeeks] Re: convert binary matrix to zero matrix
@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: convert binary matrix to zero matrix
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%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.
[algogeeks] Re: convert binary matrix to zero matrix
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.comalgogeeks%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.
