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<[email protected]> 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<[email protected]> wrote:
Amir
Could you please explain with an example in detail?
On Dec 6, 7:02 pm, Amir hossein Shahriari
<[email protected]> 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<[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected]<algogeeks%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 [email protected].
To unsubscribe from this group, send email to
[email protected]<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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
