Redian新闻
>
按十字题的O(M*N)时间解
avatar
按十字题的O(M*N)时间解# JobHunting - 待字闺中
c*p
1
题目:
给你一个M*N boolean
矩阵,定义一个操作叫做“在x,y处按键”,这一按将导致x行所有元素和y列所有元素
0变1,1变0,现在给你任意一个矩阵,写个程序打印出任意一系列“按键”操作把它变
成全0矩阵。
几个基本观点:
1.按键顺序不重要
2.一个被按过奇数次的点再被按一次相当于从来没有按过这个点,所以对于给定的图案
,找使之变成全零的解相当于找从全零变成当前图案的按键组合。
avatar
M*a
2
用位操作
boolean row[] , col[]
来记录该行/该列被inverse的次数
所以对于m[x][y],只要看row[x] + col[y]是偶数还是奇数就行

【在 c****p 的大作中提到】
: 题目:
: 给你一个M*N boolean
: 矩阵,定义一个操作叫做“在x,y处按键”,这一按将导致x行所有元素和y列所有元素
: 0变1,1变0,现在给你任意一个矩阵,写个程序打印出任意一系列“按键”操作把它变
: 成全0矩阵。
: 几个基本观点:
: 1.按键顺序不重要
: 2.一个被按过奇数次的点再被按一次相当于从来没有按过这个点,所以对于给定的图案
: ,找使之变成全零的解相当于找从全零变成当前图案的按键组合。

avatar
l*8
3
板凳
avatar
c*p
4
3.简单起见,一个格子被直接按中导致的0-1翻转称为主翻转,和它同行同列的翻转导致
的翻转称为副翻转。那么需要找到一个将主翻转和副翻转区分开来的办法。可以考虑异
或。
4.对于给定图案中的任意一点x,y,可以把它所在的行和列的所有元素相异或。对于M+N
为偶的,若结果为1,则说明该点被按过;对于M+N为奇数的,若结果为0,则说明该点被
按过。
举个例子(我自己写的一个生成图案的函数)
A是图案,D是被按过的键,也即我们要找的解
>> [A,D] = gen_pad(4,4,.2)
A =
1 0 0 1
1 0 0 1
1 1 1 1
0 0 1 0
D =
0 1 0 0
0 1 0 0
0 0 1 0
0 0 0 0
假设解为S矩阵,我们要求出S=D
假设左上角元素为A[1,1],则
S[1,1]=xor(A[1,1],A[1,2],...A[1,4],A[2,1],A[3,1]...A[4,1])=0;
同理S[1,2]=1
为了降低时间复杂度,我们可以开两个数组xor_row和xor_col,分列记录每行每列的xo
r值,第一遍pass计算每行每列的xor值,第二遍pass算每个点的xor值:
int flag = (M+N) & 1;
int xor_row[M], xor_col[N];
int x,y;
int S[M][N];
set_zeros(xor_row,M);
set_zeros(xor_col,N);
for(x = 0; x{
for(y = 0; y{
xor_row[x] ^= A[x][y];
xor_col[y] ^= A[x][y];
}
}
for(x = 0; x{
for(y = 0; y{
S[x][y] = xor_row[x]^xor_col[y]^A[x][y]^flag;
if(S[x][y])
print_pair(x,y);
}
}
总时间复杂度M*N,空间复杂度M+N

【在 c****p 的大作中提到】
: 题目:
: 给你一个M*N boolean
: 矩阵,定义一个操作叫做“在x,y处按键”,这一按将导致x行所有元素和y列所有元素
: 0变1,1变0,现在给你任意一个矩阵,写个程序打印出任意一系列“按键”操作把它变
: 成全0矩阵。
: 几个基本观点:
: 1.按键顺序不重要
: 2.一个被按过奇数次的点再被按一次相当于从来没有按过这个点,所以对于给定的图案
: ,找使之变成全零的解相当于找从全零变成当前图案的按键组合。

avatar
l*8
5
牛!
avatar
l*8
6
补充一点:
得到可能的答案之后,需要生成图案并与原图案对比。 如果两者不同,说明原图案不
能被翻转为全零矩阵。
比如:
A =
1 0 0
0 0 0
0 0 0
用这个算法得到:
D =
1 0 0
0 0 0
0 0 0
由D生成A'
A' =
1 1 1
1 0 0
1 0 0
A'不等于A
所以输入A无解

导致
+N
点被

【在 c****p 的大作中提到】
: 3.简单起见,一个格子被直接按中导致的0-1翻转称为主翻转,和它同行同列的翻转导致
: 的翻转称为副翻转。那么需要找到一个将主翻转和副翻转区分开来的办法。可以考虑异
: 或。
: 4.对于给定图案中的任意一点x,y,可以把它所在的行和列的所有元素相异或。对于M+N
: 为偶的,若结果为1,则说明该点被按过;对于M+N为奇数的,若结果为0,则说明该点被
: 按过。
: 举个例子(我自己写的一个生成图案的函数)
: A是图案,D是被按过的键,也即我们要找的解
: >> [A,D] = gen_pad(4,4,.2)
: A =

avatar
c*p
7
这个不对。。。。。。。
任何一个图案都是有解的
你给的那个例子,D应该等于:
1 1 1
1 0 0
1 0 0

【在 l*********8 的大作中提到】
: 补充一点:
: 得到可能的答案之后,需要生成图案并与原图案对比。 如果两者不同,说明原图案不
: 能被翻转为全零矩阵。
: 比如:
: A =
: 1 0 0
: 0 0 0
: 0 0 0
: 用这个算法得到:
: D =

avatar
M*a
8
看错题了orz

虑异
于M

【在 l*********8 的大作中提到】
: 补充一点:
: 得到可能的答案之后,需要生成图案并与原图案对比。 如果两者不同,说明原图案不
: 能被翻转为全零矩阵。
: 比如:
: A =
: 1 0 0
: 0 0 0
: 0 0 0
: 用这个算法得到:
: D =

avatar
l*8
9
我手算了一下:
D =
1 1 1
1 0 0
1 0 0
得到 A
A =
1 1 1
1 0 0
1 0 0

【在 c****p 的大作中提到】
: 这个不对。。。。。。。
: 任何一个图案都是有解的
: 你给的那个例子,D应该等于:
: 1 1 1
: 1 0 0
: 1 0 0

avatar
l*8
10
或者说:

A1 =
1 1 1
1 0 0
1 0 0
用你的方法算出
D1 =
1 1 1
1 0 0
1 0 0
但如果
A2 =
1 0 0
0 0 0
0 0 0
也得出
D2 =
1 1 1
1 0 0
1 0 0
因为D2 == D1,所以A2也必须等于A1, 矛盾

【在 l*********8 的大作中提到】
: 我手算了一下:
: D =
: 1 1 1
: 1 0 0
: 1 0 0
: 得到 A
: A =
: 1 1 1
: 1 0 0
: 1 0 0

avatar
l*8
11
类似的方法构造出两个A矩阵
1 1 1
0 0 0
0 0 0
1 0 0
1 0 0
1 0 0
也得到同样的D

【在 l*********8 的大作中提到】
: 或者说:
: 由
: A1 =
: 1 1 1
: 1 0 0
: 1 0 0
: 用你的方法算出
: D1 =
: 1 1 1
: 1 0 0

avatar
l*8
12
上面说的是,不同的A用你的算法可能得到相同的D。
而不同的D也能生成相同的A
比如
D1 =
1 0 0
0 0 0
0 0 0
D2 =
1 1 1
1 0 0
1 0 0
都能生成A
1 1 1
1 0 0
1 0 0
你的算法得到的是一个可行解,不一定是最少按键的解。
不过我觉得你的算法真的很厉害。有解的A应该都能很快找到一个可行解吧。

【在 l*********8 的大作中提到】
: 类似的方法构造出两个A矩阵
: 1 1 1
: 0 0 0
: 0 0 0
: 1 0 0
: 1 0 0
: 1 0 0
: 也得到同样的D

avatar
c*p
14
那说明我的算法有问题,我再想想。

【在 l*********8 的大作中提到】
: 我手算了一下:
: D =
: 1 1 1
: 1 0 0
: 1 0 0
: 得到 A
: A =
: 1 1 1
: 1 0 0
: 1 0 0

avatar
l*8
15
厉害
我之前也想过用解方程组的方法。不过我想用普通的高斯消去法,时间复杂度 O( (M*N
)^3 ), 空间复杂度 O( (M*N)^2 )

【在 b******v 的大作中提到】
: 用解方程的办法可以直接得到解或判断无解,也是O(M*N)时间,O(M+N)空间。我的解法如下:
: http://mytechmemo.blogspot.co.uk/2012/05/find-clicks-to-convert
: matrix-into.html

avatar
r*l
16
这个题能否用DFS遍历图?每个状态看作一个node,按一次能变到的状态就是它的
neighbor,这样可以构造一个图(一共2^MN个node,每个node有MN个neighbor)。从给
定的那个状态出发,DFS遍历图,直到对应全0的那个状态。
这个图不用事先构造好,从给定的node出发,每走到一个node就构造一个就可以。每个
node可以用一个MN位的二进制数表示,所以很容易可以查到某个node是否已经visited
(已经构造出来了)。
我在G家on site时碰到过这个题(不过当时是说3x3的矩阵),我当时只想出上面的方
法,也不知道好不好。我最后被G拒了,不知道是不是因为这道题没答好,呵呵。
avatar
l*8
17
主要时间复杂度太大。m,n稍大的时候,就无法计算了。

visited

【在 r******l 的大作中提到】
: 这个题能否用DFS遍历图?每个状态看作一个node,按一次能变到的状态就是它的
: neighbor,这样可以构造一个图(一共2^MN个node,每个node有MN个neighbor)。从给
: 定的那个状态出发,DFS遍历图,直到对应全0的那个状态。
: 这个图不用事先构造好,从给定的node出发,每走到一个node就构造一个就可以。每个
: node可以用一个MN位的二进制数表示,所以很容易可以查到某个node是否已经visited
: (已经构造出来了)。
: 我在G家on site时碰到过这个题(不过当时是说3x3的矩阵),我当时只想出上面的方
: 法,也不知道好不好。我最后被G拒了,不知道是不是因为这道题没答好,呵呵。

avatar
l*y
19
What about
A = [1, 1];
Or
A = [1, 1, 0];

导致
+N
点被

【在 c****p 的大作中提到】
: 3.简单起见,一个格子被直接按中导致的0-1翻转称为主翻转,和它同行同列的翻转导致
: 的翻转称为副翻转。那么需要找到一个将主翻转和副翻转区分开来的办法。可以考虑异
: 或。
: 4.对于给定图案中的任意一点x,y,可以把它所在的行和列的所有元素相异或。对于M+N
: 为偶的,若结果为1,则说明该点被按过;对于M+N为奇数的,若结果为0,则说明该点被
: 按过。
: 举个例子(我自己写的一个生成图案的函数)
: A是图案,D是被按过的键,也即我们要找的解
: >> [A,D] = gen_pad(4,4,.2)
: A =

avatar
h*g
20
好象是能在多项式时间内解决,先用线性方程组然后再动态编程,但O(M*N)的时间复杂
度好象很难达到,还没想出更好的办法。
avatar
h*g
21
把思路整理了一下,最终得到:
1 当M和N都是偶数时,解总是存在的,列出的线性方程组可以通过MOD 2代数求解,
时间复杂度是O(M*N)。
2 当M和N中有一个是奇数时,问题的结构发生了变化,有的情况下可能不存在解, 但
可以通过动态编程来确定是否有解,并找到一个解,动态编程的时间复杂度是O(M^3
N^3),空间复杂度是O(M^3N^3)。
不知道情形2下面是否有更快的解法。
avatar
z*i
22
以前一个ID给了一个漂亮的解发,怎么不见了? 概述如下:
let x_{ij} be the number of pressing/clicking at position (i,j), m_{ij} be
the original input element at (i,j), n_{ij} be the final element after all
pressing/clicking.
1. x_{ij}=R_i+C_j-2x_{ij}+m_{ij}-n{ij}=R_i+C_j+m_{ij}-n{ij} mod 2.
Queistion: how to get R_i(the summation of x_{ij} at row i)and C_j(the
summation of x_{ij} at column j)?
Answer: simply sum x_{ij} for 1<=j2. R_i=nR_i+X+summation of(m_{ij}-n_{ij}) mod 2 at row i.
where X is the summation of x_{ij} for 1<=i<=m, 1<=j<=n.
So we hget
3. (n-1)R_i=X+summation of(m_{ij}-n_{ij}) mod 2 at row i.
Now we need find X to get R_i. Simple sum R_i for all i. We get
4. (n-1)X=mX+summation of (m_{ij}-n_{ij}) mod 2 for all 1<=i<=m,1<=j<=n.
from 4, we have
5. (n-1-m)X=summation of (m_{ij}-n_{ij}) mod 2 for all 1<=i<=m,1<=j<=n.
Note that from 5, X can be computed in time O(mn) since m_{ij} and n_{ij}
are given as inputs.
Then from 3, R_i can be computed in time O(mn) for m R_is, each of which
takes time O(n). Similarily, C_j can be computed in O(mn).
Finally from 1, x_{ij} can be computed in time O(mn).

【在 h********g 的大作中提到】
: 把思路整理了一下,最终得到:
: 1 当M和N都是偶数时,解总是存在的,列出的线性方程组可以通过MOD 2代数求解,
: 时间复杂度是O(M*N)。
: 2 当M和N中有一个是奇数时,问题的结构发生了变化,有的情况下可能不存在解, 但
: 可以通过动态编程来确定是否有解,并找到一个解,动态编程的时间复杂度是O(M^3
: N^3),空间复杂度是O(M^3N^3)。
: 不知道情形2下面是否有更快的解法。

avatar
h*g
23
您所写的正是我所列的情形1,我写得很清楚,在这种情形下用MOD 2代数可以求解,
不过只有当M,N都是偶数时才能使用,您再仔细推敲一下为什么是这样,另外我提到当
M和N中有一个是奇数时有可能无解,您能否构造一个这种情况出来。

【在 z********i 的大作中提到】
: 以前一个ID给了一个漂亮的解发,怎么不见了? 概述如下:
: let x_{ij} be the number of pressing/clicking at position (i,j), m_{ij} be
: the original input element at (i,j), n_{ij} be the final element after all
: pressing/clicking.
: 1. x_{ij}=R_i+C_j-2x_{ij}+m_{ij}-n{ij}=R_i+C_j+m_{ij}-n{ij} mod 2.
: Queistion: how to get R_i(the summation of x_{ij} at row i)and C_j(the
: summation of x_{ij} at column j)?
: Answer: simply sum x_{ij} for 1<=j: 2. R_i=nR_i+X+summation of(m_{ij}-n_{ij}) mod 2 at row i.
: where X is the summation of x_{ij} for 1<=i<=m, 1<=j<=n.

avatar
z*i
24
According to equation 5, (n-1-m)X=summation of (m_{ij}-n_{ij}) mod 2 for all
1<=i<=m,1<=j<=n. 如果这个方程不满足,就无解。比如说,n-m-1是奇数,但
summation of (m_{ij}-n_{ij}) mod 2不为零,为1。
例子:(1)m=1,n=2. [1 0]。(2)m=1,n=4. [1 0 0 0], or [1 1 1 0], or [1 0 1
1], etc 。(3) m=2,n=3.
1 0 0
0 0 0
所以算法就是先解方程5,如方程无解,原问题无解。然后解方程3,如无解,原问题无
解。最后方程1肯定有解(无系数在x_{ij}前面)。

【在 h********g 的大作中提到】
: 您所写的正是我所列的情形1,我写得很清楚,在这种情形下用MOD 2代数可以求解,
: 不过只有当M,N都是偶数时才能使用,您再仔细推敲一下为什么是这样,另外我提到当
: M和N中有一个是奇数时有可能无解,您能否构造一个这种情况出来。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。