logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
G题一道（2）
avatar
G题一道（2）# JobHunting - 待字闺中
s*n
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
avatar
S*t
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
avatar
s*u
3 楼
求具体解法

【在 S********t 的大作中提到】
: 其实就是写成二进制就好办了。不过感觉偏数学了点
avatar
b*m
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
avatar
s*n
5 楼
我不知道行不行，呵呵。感觉上好像不行。

【在 b***m 的大作中提到】
: 能不能用溢出的方式把某些数字清零啊？
avatar
p*2
6 楼

感觉大牛现在做的都是非人类的题目。

【在 s*****n 的大作中提到】
: 我不知道行不行，呵呵。感觉上好像不行。
avatar
b*m
7 楼
为什么不行呢？乘二不就是左移一位吗，最左边的位是不是就木有了？

【在 s*****n 的大作中提到】
: 我不知道行不行，呵呵。感觉上好像不行。
avatar
D*d
8 楼
这是为什么特别说明 数 没有 range 的原因吧

【在 b***m 的大作中提到】
: 为什么不行呢？乘二不就是左移一位吗，最左边的位是不是就木有了？
avatar
b*m
9 楼
也许本题可以理解为默认没有溢出，否则这题就没意思了，一直往左移就完了。
avatar
p*2
10 楼

一直往左移就是最优吗？

【在 b***m 的大作中提到】
: 也许本题可以理解为默认没有溢出，否则这题就没意思了，一直往左移就完了。
avatar
b*m
11 楼

呵呵，当然不一定是最优了，但是这可以是选择之一了。

【在 p*****2 的大作中提到】
:
: 一直往左移就是最优吗？
avatar
p*2
12 楼

这题是要求最优。

【在 b***m 的大作中提到】
:
: 呵呵，当然不一定是最优了，但是这可以是选择之一了。
avatar
b*m
13 楼

我知道。我只是说，如果考虑溢出的话，情况就复杂了。应该不是本题要考虑的因素。

【在 p*****2 的大作中提到】
:
: 这题是要求最优。
avatar
p*2
14 楼

大牛有什么好的思路？

【在 b***m 的大作中提到】
:
: 我知道。我只是说，如果考虑溢出的话，情况就复杂了。应该不是本题要考虑的因素。
avatar
b*m
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 的大作中提到】
:
: 大牛有什么好的思路？
avatar
s*n
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;
: }
avatar
b*m
17 楼
我的意思是careercup，不是书。
优化还在考虑，目前思路不太清晰。

【在 s*****n 的大作中提到】
: 新版的150收了这题？
: 这个程序是一个基本解，可以考虑一些优化。
avatar
p*2
18 楼

能不能先谈谈你思路呀？

【在 b***m 的大作中提到】
: 我的意思是careercup，不是书。
: 优化还在考虑，目前思路不太清晰。
avatar
b*m
19 楼
思路不太清晰的意思就是迷茫得木有思路。;-)

【在 p*****2 的大作中提到】
:
: 能不能先谈谈你思路呀？
avatar
p*2
20 楼

没思路都把code写完了，实在是太牛了。

【在 b***m 的大作中提到】
: 思路不太清晰的意思就是迷茫得木有思路。;-)
avatar
b*m
21 楼

不是吧，写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候，用A*算法
对所有关卡的地图数据做预处理，最大的512x512的地图，用当时配置的机器运行需要2
个小时（没办法，当时机器太慢了）。后来CTO嫌太慢，人家熬了一个通宵对算法做了
优化，结果同样的地图在同样的机器上运行，只要10分钟。简直羞愤得我要死啊……差
距太大了。人家现在在硅谷某中型软件公司做CTO。:-(

【在 p*****2 的大作中提到】
:
: 没思路都把code写完了，实在是太牛了。
avatar
p*2
22 楼

要2
我的意思是说你现在写的code 是什么思路呀？不是说最优思路。

【在 b***m 的大作中提到】
:
: 不是吧，写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候，用A*算法
: 对所有关卡的地图数据做预处理，最大的512x512的地图，用当时配置的机器运行需要2
: 个小时（没办法，当时机器太慢了）。后来CTO嫌太慢，人家熬了一个通宵对算法做了
: 优化，结果同样的地图在同样的机器上运行，只要10分钟。简直羞愤得我要死啊……差
: 距太大了。人家现在在硅谷某中型软件公司做CTO。:-(
avatar
b*m
23 楼
现在的思路就是一个劲把当前行的大数字往下降呗，一直降到所有数字都是1，不知道
有哪些地方可以优化呢？
avatar
b*m
24 楼

哦，刚刚回复一帖大概解释了一下。

【在 p*****2 的大作中提到】
:
: 要2
: 我的意思是说你现在写的code 是什么思路呀？不是说最优思路。
avatar
b*m
25 楼
貌似可以考虑不要把当前行的最小数字减到1，这样要double好多次才能尽量跟最大数
凑齐。也许可以考虑什么公倍数之类的？
avatar
p*2
26 楼

这个能保证是最优的吗？
我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。

【在 b***m 的大作中提到】
: 现在的思路就是一个劲把当前行的大数字往下降呗，一直降到所有数字都是1，不知道
: 有哪些地方可以优化呢？
avatar
b*m
27 楼

肯定不是最优的，理由我在上面说过了。还在思考中……

【在 p*****2 的大作中提到】
:
: 这个能保证是最优的吗？
: 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
avatar
C*U
28 楼
对!现在不是程序优不优的问题，而是对不对的问题。题目要求最少操作次数。

【在 p*****2 的大作中提到】
:
: 这个能保证是最优的吗？
: 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。
avatar
b*m
29 楼

嗯，有了思路后，程序的实现很简单。现在的问题就是思路还不是最优。

【在 C***U 的大作中提到】
: 对!现在不是程序优不优的问题，而是对不对的问题。题目要求最少操作次数。
avatar
b*m
30 楼
我又稍微想了一下，觉得现在的程序有个致命问题，导致几乎肯定不是最优解（最少操
作次数）：我们是解决了一行（全为0）后，再解决下一行，由于使得数字变小的唯一
操作就是该行全部减1，因此某行最少操作次数不可能少于该行最大的数字。由于我们
不断地把某些列乘2，其后果很可能是某些行最大的数字会被增大，导致操作次数增加
。这是由于我们只着眼于局部，而忽略了全局。改变一下思路，我们不苛求先解决一行
，而是扫描所有的行，把所有行的最小数字减到1，然后把所有含1的列都加倍，再扫描
所有的行，然后再加倍……这样应该可以避免增加无谓的减1的操作，几乎肯定比我前
面那个策略更优（但是我还无法确定是否最优）。请大家指正。
avatar
b*m
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步。
大家请提提意见。
avatar
l*b
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步。
avatar
b*m
33 楼

是哦，这个可怎搞。

【在 l*******b 的大作中提到】
: 这个有问题吧
: 1 50
: 50 1
: 是不是越来越大了
avatar
l*8
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
avatar
b*m
35 楼
嗯，看来还不仅仅是翻番，还得考虑倍数关系。有什么通则呢？
avatar
l*8
36 楼
不知道啊，这题很复杂，水很深……
avatar
b*m
37 楼
嗯，解出来不难，最优解看来不易。与其说是道编程算法题，不如说是道数学题。
avatar
l*b
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
avatar
q*m
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
相关阅读
电面结束了，有被欺骗的感觉。同时求助----我现在的情况怎么办？有人了解Saxo Bank这家银行吗？会发包子～会有人为工作 LD去Kansas吗？要培训一到2个月得icc有人去过么？情况如何对方回复说：STAY TUNED!一道关于SMP and threading 题目H1B gap问两个题西装哪里去买物美价廉？OPT要过期了， H－１B公司不给办，咋办学经济的在湾区好找工作些还是西雅图？有不少公司要网上填简历申请很繁琐A Google Problem关于一个面试的问题hit and run 背景调查会被查出来么？是accept了offer才做background check吗C++ Q89: function template and overloading请问让HR发个详细的职位介绍过来是不是很离谱。。。明知只能工作一个半月，还去接Offer，是否太伤人品？不是show off. 两个offers痛苦选择中
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。