s*****n 发帖数: 162 | 1 Given an N x M matrix having only positive values, we have to nullify the
matrix i.e make all entries 0.
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time
Find the minimum number of operations required to nullify the matrix.
Note: no range of input was given
http://www.careercup.com/question?id=14691685 |
S********t 发帖数: 3431 | 2 其实就是写成二进制就好办了。不过感觉偏数学了点
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given an N x M matrix having only positive values, we have to nullify the : matrix i.e make all entries 0. : We are given two operations : 1) multiply each element of any one column at a time by 2. : 2) Subtract 1 from all elements of any one row at a time : Find the minimum number of operations required to nullify the matrix. : Note: no range of input was given : http://www.careercup.com/question?id=14691685
|
s***u 发帖数: 101 | 3 求具体解法
【在 S********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其实就是写成二进制就好办了。不过感觉偏数学了点
|
b***m 发帖数: 5987 | 4 能不能用溢出的方式把某些数字清零啊?
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given an N x M matrix having only positive values, we have to nullify the : matrix i.e make all entries 0. : We are given two operations : 1) multiply each element of any one column at a time by 2. : 2) Subtract 1 from all elements of any one row at a time : Find the minimum number of operations required to nullify the matrix. : Note: no range of input was given : http://www.careercup.com/question?id=14691685
|
s*****n 发帖数: 162 | 5 我不知道行不行,呵呵。感觉上好像不行。
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能不能用溢出的方式把某些数字清零啊?
|
p*****2 发帖数: 21240 | 6
感觉大牛现在做的都是非人类的题目。
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不知道行不行,呵呵。感觉上好像不行。
|
b***m 发帖数: 5987 | 7 为什么不行呢?乘二不就是左移一位吗,最左边的位是不是就木有了?
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不知道行不行,呵呵。感觉上好像不行。
|
D**********d 发帖数: 849 | 8 这是为什么特别说明 数 没有 range 的原因吧
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么不行呢?乘二不就是左移一位吗,最左边的位是不是就木有了?
|
b***m 发帖数: 5987 | 9 也许本题可以理解为默认没有溢出,否则这题就没意思了,一直往左移就完了。 |
p*****2 发帖数: 21240 | 10
一直往左移就是最优吗?
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 也许本题可以理解为默认没有溢出,否则这题就没意思了,一直往左移就完了。
|
|
|
b***m 发帖数: 5987 | 11
呵呵,当然不一定是最优了,但是这可以是选择之一了。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 一直往左移就是最优吗?
|
p*****2 发帖数: 21240 | 12
这题是要求最优。
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 呵呵,当然不一定是最优了,但是这可以是选择之一了。
|
b***m 发帖数: 5987 | 13
我知道。我只是说,如果考虑溢出的话,情况就复杂了。应该不是本题要考虑的因素。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这题是要求最优。
|
p*****2 发帖数: 21240 | 14
大牛有什么好的思路?
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我知道。我只是说,如果考虑溢出的话,情况就复杂了。应该不是本题要考虑的因素。
|
b***m 发帖数: 5987 | 15
刚刚花了一点儿时间写了代码,后来发现跟150上的思路差不多。没什么特别的,凑数
吧,还在考虑怎么优化。
void DoubleColumn(int **ppn, int nNumRows, int idCol)
{
if( !ppn ) return;
for( int i = 0; i < nNumRows; i++ )
{
ppn[i][idCol] *= 2;
}
}
void DecreaseRow(int **ppn, int nNumCols, int idRow)
{
if( !ppn ) return;
for( int i = 0; i < nNumCols; i++ )
{
ppn[idRow][i]--;
}
}
vector GetColsWithMinValue(int **ppn, int nNumCols, int idRow)
{
int i, nMin = MAX_INT;
vector vecMinCols;
if( !ppn || nNumCols <= 0 || idRow < 0 )
return vecMinCols;
for( i = 0; i < nNumCols; i++ )
{
if( ppn[idRow][i] < nMin )
nMin = ppn[idRow][i];
}
for( i = 0; i < nNumCols; i++ )
{
if( ppn[idRow][i] == nMin )
vecMinCols.push_back(i);
}
return vecMinCols;
}
void NullifyMatrix(int **ppn, int M, int N) // Matrix, NumCols, NumRows
{
if( !ppn || M <= 0 || N <= 0 ) return;
for( int i = 0; i < N; i++ )
{
vector vecMinCols = GetColsWithMinValue(ppn, M, i);
if( vecMinCols.size() == 0 ) break; // Something wrong
int nMin = ppn[i][vecMinCols[0]];
for( int j = 0; j < nMin - 1; j++ )
DecreaseRow(ppn, M, i);
bool bFoundGreaterThan1 = false;
for( j = 0; j < M; j++ )
{
if( ppn[i][j] > 1 )
{
bFoundGreaterThan1 = true;
break;
}
}
if( bFoundGreaterThan1 )
{
for( int k = 0; k < vecMinCols.size(); k++ )
DoubleColumn(ppn, i, k);
i--;
}
else
DecreaseRow(ppn, M, i);
}
}
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 大牛有什么好的思路?
|
s*****n 发帖数: 162 | 16 新版的150收了这题?
这个程序是一个基本解,可以考虑一些优化。
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 刚刚花了一点儿时间写了代码,后来发现跟150上的思路差不多。没什么特别的,凑数 : 吧,还在考虑怎么优化。 : void DoubleColumn(int **ppn, int nNumRows, int idCol) : { : if( !ppn ) return; : for( int i = 0; i < nNumRows; i++ ) : { : ppn[i][idCol] *= 2; : }
|
b***m 发帖数: 5987 | 17 我的意思是careercup,不是书。
优化还在考虑,目前思路不太清晰。
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 新版的150收了这题? : 这个程序是一个基本解,可以考虑一些优化。
|
p*****2 发帖数: 21240 | 18
能不能先谈谈你思路呀?
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的意思是careercup,不是书。 : 优化还在考虑,目前思路不太清晰。
|
b***m 发帖数: 5987 | 19 思路不太清晰的意思就是迷茫得木有思路。;-)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 能不能先谈谈你思路呀?
|
p*****2 发帖数: 21240 | 20
没思路都把code写完了,实在是太牛了。
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 思路不太清晰的意思就是迷茫得木有思路。;-)
|
|
|
b***m 发帖数: 5987 | 21
不是吧,写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候,用A*算法
对所有关卡的地图数据做预处理,最大的512x512的地图,用当时配置的机器运行需要2
个小时(没办法,当时机器太慢了)。后来CTO嫌太慢,人家熬了一个通宵对算法做了
优化,结果同样的地图在同样的机器上运行,只要10分钟。简直羞愤得我要死啊……差
距太大了。人家现在在硅谷某中型软件公司做CTO。:-(
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 没思路都把code写完了,实在是太牛了。
|
p*****2 发帖数: 21240 | 22
要2
我的意思是说你现在写的code 是什么思路呀?不是说最优思路。
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不是吧,写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候,用A*算法 : 对所有关卡的地图数据做预处理,最大的512x512的地图,用当时配置的机器运行需要2 : 个小时(没办法,当时机器太慢了)。后来CTO嫌太慢,人家熬了一个通宵对算法做了 : 优化,结果同样的地图在同样的机器上运行,只要10分钟。简直羞愤得我要死啊……差 : 距太大了。人家现在在硅谷某中型软件公司做CTO。:-(
|
b***m 发帖数: 5987 | 23 现在的思路就是一个劲把当前行的大数字往下降呗,一直降到所有数字都是1,不知道
有哪些地方可以优化呢? |
b***m 发帖数: 5987 | 24
哦,刚刚回复一帖大概解释了一下。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 要2 : 我的意思是说你现在写的code 是什么思路呀?不是说最优思路。
|
b***m 发帖数: 5987 | 25 貌似可以考虑不要把当前行的最小数字减到1,这样要double好多次才能尽量跟最大数
凑齐。也许可以考虑什么公倍数之类的? |
p*****2 发帖数: 21240 | 26
这个能保证是最优的吗?
我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在的思路就是一个劲把当前行的大数字往下降呗,一直降到所有数字都是1,不知道 : 有哪些地方可以优化呢?
|
b***m 发帖数: 5987 | 27
肯定不是最优的,理由我在上面说过了。还在思考中……
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这个能保证是最优的吗? : 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
|
C***U 发帖数: 2406 | 28 对!现在不是程序优不优的问题,而是对不对的问题。题目要求最少操作次数。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这个能保证是最优的吗? : 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
|
b***m 发帖数: 5987 | 29
嗯,有了思路后,程序的实现很简单。现在的问题就是思路还不是最优。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对!现在不是程序优不优的问题,而是对不对的问题。题目要求最少操作次数。
|
b***m 发帖数: 5987 | 30 我又稍微想了一下,觉得现在的程序有个致命问题,导致几乎肯定不是最优解(最少操
作次数):我们是解决了一行(全为0)后,再解决下一行,由于使得数字变小的唯一
操作就是该行全部减1,因此某行最少操作次数不可能少于该行最大的数字。由于我们
不断地把某些列乘2,其后果很可能是某些行最大的数字会被增大,导致操作次数增加
。这是由于我们只着眼于局部,而忽略了全局。改变一下思路,我们不苛求先解决一行
,而是扫描所有的行,把所有行的最小数字减到1,然后把所有含1的列都加倍,再扫描
所有的行,然后再加倍……这样应该可以避免增加无谓的减1的操作,几乎肯定比我前
面那个策略更优(但是我还无法确定是否最优)。请大家指正。 |
|
|
b***m 发帖数: 5987 | 31 现在的策略如下:
1、设当前行为第1行;
2、如果该行数字全部相同,假设是N,那么进行N次减1操作,并且跳到第5步;
3、扫描出最小的数字,假设是A;
4、把该行进行A-1次减1操作;
5、如果不是最后一行,移动到下一行,并且回到第2步;
6、设当前列为第1列;
7、扫描该列是否有1,有的话该列进行乘2操作;
8、如果不是最后一列,移动到下一列,并且回到第6步;
9、回到第1步。
大家请提提意见。 |
l*******b 发帖数: 2586 | 32 这个有问题吧
1 50
50 1
是不是越来越大了
【在 b***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在的策略如下: : 1、设当前行为第1行; : 2、如果该行数字全部相同,假设是N,那么进行N次减1操作,并且跳到第5步; : 3、扫描出最小的数字,假设是A; : 4、把该行进行A-1次减1操作; : 5、如果不是最后一行,移动到下一行,并且回到第2步; : 6、设当前列为第1列; : 7、扫描该列是否有1,有的话该列进行乘2操作; : 8、如果不是最后一列,移动到下一列,并且回到第6步; : 9、回到第1步。
|
b***m 发帖数: 5987 | 33
是哦,这个可怎搞。
【在 l*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个有问题吧 : 1 50 : 50 1 : 是不是越来越大了
|
l***8 发帖数: 149 | 34 32 50
1600 1
18 36
1600 1
36 36
3200 1
0 0
3200 1
0 0
3200 2048
0 0
2304 1152
0 0
2304 2304
0 0
0 0 |
b***m 发帖数: 5987 | 35 嗯,看来还不仅仅是翻番,还得考虑倍数关系。有什么通则呢? |
l***8 发帖数: 149 | |
b***m 发帖数: 5987 | 37 嗯,解出来不难,最优解看来不易。与其说是道编程算法题,不如说是道数学题。 |
l*******b 发帖数: 2586 | 38 厉害,这样每一行都会解了。
exactly需要这一行的MAX次减法和对每一项a_k m次乘以2,2^{m-1}a_k < MAX <= 2^m
a_k.
多行的情形,还是很复杂。。。每一行的MAX和没一项的m值都是刻画这个问题混乱程度
的指标。
【在 l***8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 32 50 : 1600 1 : 18 36 : 1600 1 : 36 36 : 3200 1 : 0 0 : 3200 1 : 0 0 : 3200 2048
|
q****m 发帖数: 177 | 39 能套用 DP吗 ?
不过感觉情况太多了.
第一步就有 M + N种情况.
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given an N x M matrix having only positive values, we have to nullify the : matrix i.e make all entries 0. : We are given two operations : 1) multiply each element of any one column at a time by 2. : 2) Subtract 1 from all elements of any one row at a time : Find the minimum number of operations required to nullify the matrix. : Note: no range of input was given : http://www.careercup.com/question?id=14691685
|