Author |
Topic: Matrix transformation (Read 1252 times) |
|
kg
Newbie
Posts: 18
|
 |
Matrix transformation
« on: Oct 27th, 2009, 1:48pm » |
 Quote  Modify
|
Given two matrix A B of size NxN containing only 0 and 1, compute least number of cells to toggle in A to reach B.
The catch is toggling any cell will toggle the surrounding cells.
For example
A=
------------
1 0 1
1 1 1
0 0 1
------------
B=
------------
0 1 1
0 0 1
0 0 1
------------
Answer is to toggle [0,0] cell
Is there a general solution to compute the cells to toggle given A and B
Adding more detail:
Toggling a cell toggles all surrounding cells that means toggling the middle cell toggles entire matrix[all 8 cells surround it]
|
| « Last Edit: Oct 28th, 2009, 9:27am by kg » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Matrix transformation
« Reply #1 on: Oct 27th, 2009, 2:03pm » |
Quote Modify
|
I'd start by XORing A and B and then just solve to remove all 1's.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kg
Newbie
Posts: 18
|
|
Re: Matrix transformation
« Reply #2 on: Oct 27th, 2009, 3:59pm » |
Quote Modify
|
Can you explain the second part of solving it to remove all 1's
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Matrix transformation
« Reply #3 on: Oct 28th, 2009, 12:49am » |
Quote Modify
|
Since toggling the same spot twice simply returns to the starting position, it is clear that each position needs to be toggled at most once.
Suppose we have found the right positions to toggle in the first row.
In the next row, we have to toggle all positions that have a 1 in the row above, because there is no other way to get them right. We also can't toggle any other position, because they'd introduce new 1s in the row above.
By the same sort of reasoning, there are only two ways to clear the first row. (Toggling the first element or not; the rest is determined.)
|
| « Last Edit: Oct 28th, 2009, 3:39am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Matrix transformation
« Reply #4 on: Oct 28th, 2009, 1:27am » |
Quote Modify
|
I got your logic, but I don't know how to recognize the 1's in the XORed matrix which should be toggled to convert the matrix to a ZERO matrix.
PS: It should be in CS section.
|
| « Last Edit: Oct 28th, 2009, 1:30am by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Matrix transformation
« Reply #5 on: Oct 28th, 2009, 1:54am » |
Quote Modify
|
on Oct 28th, 2009, 1:27am, R wrote:| I got your logic, but I don't know how to recognize the 1's in the XORed matrix which should be toggled to convert the matrix to a ZERO matrix. |
|
There is a 1 in the XORed matrix if the values in that position don't match in the two original matrices. Since they don't match, that means there needs to be a toggle there.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Matrix transformation
« Reply #6 on: Oct 28th, 2009, 2:19am » |
Quote Modify
|
on Oct 28th, 2009, 1:54am, towr wrote:
There is a 1 in the XORed matrix if the values in that position don't match in the two original matrices. Since they don't match, that means there needs to be a toggle there.
|
|
So do you mean, every entry that is equal to 1 in the XORed matrix should be toggled?
See this example:
Suppose the XORed matrix is
0 1 1
0 1 1
0 0 0
then toggling just the third entry in first row will set the XORed matrix to a zero matrix. We didn't toggle every entry which is 1. Of-course we have to find the minimum number of entries to be toggled.
|
| « Last Edit: Oct 28th, 2009, 2:20am by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Matrix transformation
« Reply #7 on: Oct 28th, 2009, 3:04am » |
Quote Modify
|
on Oct 28th, 2009, 2:19am, R wrote:| So do you mean, every entry that is equal to 1 in the XORed matrix should be toggled? |
|
In the sense it should change value.
As kg said "toggling any cell will toggle the surrounding cells" So you don't need to actively toggle every '1', some will be toggled as result of toggling other cells.
Quote:See this example:
Suppose the XORed matrix is
0 1 1
0 1 1
0 0 0
then toggling just the third entry in first row will set the XORed matrix to a zero matrix. |
|
That brings up the question whether we are working in a 4-connected or 8-connected mode. I was assuming 4-connected, which in your example would leave the middle position as a 1.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Matrix transformation
« Reply #8 on: Oct 28th, 2009, 3:14am » |
Quote Modify
|
on Oct 28th, 2009, 3:04am, towr wrote:
As kg said "toggling any cell will toggle the surrounding cells" So you don't need to actively toggle every '1', some will be toggled as result of toggling other cells.
|
|
That's what I asked in my previous posts. How will you recognize the 1 entries (minimum in total) which should be toggled to convert the matrix to zero matrix?
Quote:
That brings up the question whether we are working in a 4-connected or 8-connected mode. I was assuming 4-connected, which in your example would leave the middle position as a 1. |
|
The example given with the problem statement clearly suggests that we are talking of an 8-connected node.
The question remains: how will we decide, which 1's should be toggled (for minimum number of toggling) in the XORed matrix.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Matrix transformation
« Reply #9 on: Oct 28th, 2009, 3:39am » |
Quote Modify
|
on Oct 28th, 2009, 3:14am, R wrote:
That's what I asked in my previous posts. How will you recognize the 1 entries (minimum in total) which should be toggled to convert the matrix to zero matrix? |
|
That's not the point of that step of the process; the point is to simplify the problem to one matrix. Whatever turns the XORed matrix to all zeros will turn A to B.
Quote:| The example given with the problem statement clearly suggests that we are talking of an 8-connected node. |
|
Nothing is so clear, or I can succeed in failing to notice it!
Quote:| The question remains: how will we decide, which 1's should be toggled (for minimum number of toggling) in the XORed matrix. |
|
Well, apparently nothing I've said in the thread so far, since it doesn't apply. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kg
Newbie
Posts: 18
|
|
Re: Matrix transformation
« Reply #10 on: Oct 28th, 2009, 9:33am » |
Quote Modify
|
I was able to reduce it to set a equations but dont know how to solve that equation. Here is my logic,
Each cell can give rise to one equation.
Lets say c00 c01 c02 c10 c11 c12 c20 c21 c22 denotes number of togglings
seeing first cell from A and B if there is change then there is odd number of togglings in the surrounding 4 cells.
that means
c00+ c01 + c10 + c11 = odd
we can get one such equation for each cell.
So we have N equations and n variables but the right hand side we only know if its odd or even.
Is there a way to solve such system of equations ?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print