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 的大作中提到】
: 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 的大作中提到】
: 其实就是写成二进制就好办了。不过感觉偏数学了点
|
b***m
发帖数: 5987 | 4 能不能用溢出的方式把某些数字清零啊？
【在 s*****n 的大作中提到】
: 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 的大作中提到】
: 能不能用溢出的方式把某些数字清零啊？
|
p*****2
发帖数: 21240 | 6
感觉大牛现在做的都是非人类的题目。
【在 s*****n 的大作中提到】
: 我不知道行不行，呵呵。感觉上好像不行。
|
b***m
发帖数: 5987 | 7 为什么不行呢？乘二不就是左移一位吗，最左边的位是不是就木有了？
【在 s*****n 的大作中提到】
: 我不知道行不行，呵呵。感觉上好像不行。
|
D**********d
发帖数: 849 | 8 这是为什么特别说明 数 没有 range 的原因吧
【在 b***m 的大作中提到】
: 为什么不行呢？乘二不就是左移一位吗，最左边的位是不是就木有了？
|
b***m
发帖数: 5987 | 9 也许本题可以理解为默认没有溢出，否则这题就没意思了，一直往左移就完了。 |
p*****2
发帖数: 21240 | 10
一直往左移就是最优吗？
【在 b***m 的大作中提到】
: 也许本题可以理解为默认没有溢出，否则这题就没意思了，一直往左移就完了。
|
|
|
b***m
发帖数: 5987 | 11
呵呵，当然不一定是最优了，但是这可以是选择之一了。
【在 p*****2 的大作中提到】
:
: 一直往左移就是最优吗？
|
p*****2
发帖数: 21240 | 12
这题是要求最优。
【在 b***m 的大作中提到】
:
: 呵呵，当然不一定是最优了，但是这可以是选择之一了。
|
b***m
发帖数: 5987 | 13
我知道。我只是说，如果考虑溢出的话，情况就复杂了。应该不是本题要考虑的因素。
【在 p*****2 的大作中提到】
:
: 这题是要求最优。
|
p*****2
发帖数: 21240 | 14
大牛有什么好的思路？
【在 b***m 的大作中提到】
:
: 我知道。我只是说，如果考虑溢出的话，情况就复杂了。应该不是本题要考虑的因素。
|
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 的大作中提到】
:
: 大牛有什么好的思路？
|
s*****n
发帖数: 162 | 16 新版的150收了这题？
这个程序是一个基本解，可以考虑一些优化。
【在 b***m 的大作中提到】
:
: 刚刚花了一点儿时间写了代码，后来发现跟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 的大作中提到】
: 新版的150收了这题？
: 这个程序是一个基本解，可以考虑一些优化。
|
p*****2
发帖数: 21240 | 18
能不能先谈谈你思路呀？
【在 b***m 的大作中提到】
: 我的意思是careercup，不是书。
: 优化还在考虑，目前思路不太清晰。
|
b***m
发帖数: 5987 | 19 思路不太清晰的意思就是迷茫得木有思路。;-)
【在 p*****2 的大作中提到】
:
: 能不能先谈谈你思路呀？
|
p*****2
发帖数: 21240 | 20
没思路都把code写完了，实在是太牛了。
【在 b***m 的大作中提到】
: 思路不太清晰的意思就是迷茫得木有思路。;-)
|
|
|
b***m
发帖数: 5987 | 21
不是吧，写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候，用A*算法
对所有关卡的地图数据做预处理，最大的512x512的地图，用当时配置的机器运行需要2
个小时（没办法，当时机器太慢了）。后来CTO嫌太慢，人家熬了一个通宵对算法做了
优化，结果同样的地图在同样的机器上运行，只要10分钟。简直羞愤得我要死啊……差
距太大了。人家现在在硅谷某中型软件公司做CTO。:-(
【在 p*****2 的大作中提到】
:
: 没思路都把code写完了，实在是太牛了。
|
p*****2
发帖数: 21240 | 22
要2
我的意思是说你现在写的code 是什么思路呀？不是说最优思路。
【在 b***m 的大作中提到】
:
: 不是吧，写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候，用A*算法
: 对所有关卡的地图数据做预处理，最大的512x512的地图，用当时配置的机器运行需要2
: 个小时（没办法，当时机器太慢了）。后来CTO嫌太慢，人家熬了一个通宵对算法做了
: 优化，结果同样的地图在同样的机器上运行，只要10分钟。简直羞愤得我要死啊……差
: 距太大了。人家现在在硅谷某中型软件公司做CTO。:-(
|
b***m
发帖数: 5987 | 23 现在的思路就是一个劲把当前行的大数字往下降呗，一直降到所有数字都是1，不知道
有哪些地方可以优化呢？ |
b***m
发帖数: 5987 | 24
哦，刚刚回复一帖大概解释了一下。
【在 p*****2 的大作中提到】
:
: 要2
: 我的意思是说你现在写的code 是什么思路呀？不是说最优思路。
|
b***m
发帖数: 5987 | 25 貌似可以考虑不要把当前行的最小数字减到1，这样要double好多次才能尽量跟最大数
凑齐。也许可以考虑什么公倍数之类的？ |
p*****2
发帖数: 21240 | 26
这个能保证是最优的吗？
我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
【在 b***m 的大作中提到】
: 现在的思路就是一个劲把当前行的大数字往下降呗，一直降到所有数字都是1，不知道
: 有哪些地方可以优化呢？
|
b***m
发帖数: 5987 | 27
肯定不是最优的，理由我在上面说过了。还在思考中……
【在 p*****2 的大作中提到】
:
: 这个能保证是最优的吗？
: 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
|
C***U
发帖数: 2406 | 28 对!现在不是程序优不优的问题，而是对不对的问题。题目要求最少操作次数。
【在 p*****2 的大作中提到】
:
: 这个能保证是最优的吗？
: 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
|
b***m
发帖数: 5987 | 29
嗯，有了思路后，程序的实现很简单。现在的问题就是思路还不是最优。
【在 C***U 的大作中提到】
: 对!现在不是程序优不优的问题，而是对不对的问题。题目要求最少操作次数。
|
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 的大作中提到】
: 现在的策略如下：
: 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 的大作中提到】
: 这个有问题吧
: 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 的大作中提到】
: 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 的大作中提到】
: 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
|
