由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
_DC版 - 劳动节 -- WSN 绣花 (已解决)
相关主题
凄美的恋爱问题(转帖)[报到] E300
又来献宝啦!周日有人去salsa么?
天朝威武!提醒:今天是wsn的盛大节日
惨绝人寰!WSN为解Google难题舍身取义去跳楼WSN 的好消息:美国华人女多于男 by 21万
参赛★☆【WSN组歌】☆★第6章合唱《WSN啊WSN》 (转载)请转 马里兰版 -- 超级WSN (转载)
sigh, bbs上WSN忒多了最近WSN们都很NB啊
Wsn 们应该都搬去纽约。。。自然数集合被积与平方和决定吗?
今天在DC酒吧看球时为中国WSN争光了 (转载)航母事件,其实小将,老将都不是啥好鸟!
相关话题的讨论汇总
话题: wsn话题: 矩阵话题: 记做话题: 正整数话题: 时间
1 (共1页)
c*********t
发帖数: 1861
1
Solution 见楼底。。。
这次N 个 WSN 因为已经脑残了,所以相约劳动节去绣花 。。。好了,废话就不说了,大家帮我想这个题:
不同的 WSN 绣不同的款式需要的时间不一样。如果我们把 WSN # i 绣 j 款式需要的时间记做 T(i,j), 那么,T(i,j)组成了一个 N by N 的正整数矩阵。
现在要找出一个方案,让 WSN 总体用最短的时间把所有款式都绣出来
例1 [不可以每行都选时间最短的]:考虑如下3x3的矩阵:
1 2 2
2 1 2
2 2 9 ==> choose (2,2,2) = 6
例2:[有时候还必须 include 时间最长的]: 考虑如下3x3的矩阵:
1 4 4
4 1 4
4 4 5 ==> choose (1,1,5) = 7
当然,Naively, 可以把 N! 种可能性都试一遍。但是 N (max N = 75) 很大的时候,这个方法无法满足要求。是否有更聪明的算法呢?
原题链接:
http://code.google.com/codejam/contest/dashboard?c=32014#s=p3
i*********n
发帖数: 219
2
这张图片是送给你的
以表彰你的丰功伟绩
c*********t
发帖数: 1861
3
哈,这张狠威风,偶笑纳了。。。

【在 i*********n 的大作中提到】
: 这张图片是送给你的
: 以表彰你的丰功伟绩

i*********n
发帖数: 219
4
谢版主兔恩
j*******a
发帖数: 2681
5
咱不出这样的题目成么,猫从来做不出的。。。
抗议~

我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题:
果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N
的正整数矩阵。
的)
。。。

【在 c*********t 的大作中提到】
: 哈,这张狠威风,偶笑纳了。。。
n********6
发帖数: 1511
6
谢版兔隆恩。

【在 i*********n 的大作中提到】
: 谢版主兔恩
s*******u
发帖数: 5796
7
motel没有这样做生意的啊!不同顾客入住房价不一样,还想不想干了?!告你
discrimination!疯兔你还是换个比喻好了。这样太confusing~
h********r
发帖数: 3291
8
我要是wsn,要么住霸王店,要么搭帐篷。住个店都怎么麻烦,你说以后还有哪个ppmm
会跟你出去玩?真是脑子彻底进水了。
(这个问题应该是np-complete,还是不要最便宜,只要差不多便宜就可以了。用随机
mutation+tunneling)

我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题:
果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N
的正整数矩阵。
的)
。。。

【在 c*********t 的大作中提到】
: 哈,这张狠威风,偶笑纳了。。。
c*********t
发帖数: 1861
9
如你所愿,题目已做改动。
我土,什么叫做 tunneling 啊? Is it something like aborting search
pre-maturely?

ppmm
N

【在 h********r 的大作中提到】
: 我要是wsn,要么住霸王店,要么搭帐篷。住个店都怎么麻烦,你说以后还有哪个ppmm
: 会跟你出去玩?真是脑子彻底进水了。
: (这个问题应该是np-complete,还是不要最便宜,只要差不多便宜就可以了。用随机
: mutation+tunneling)
:
: 我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题:
: 果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N
: 的正整数矩阵。
: 的)
: 。。。

A*********t
发帖数: 7481
10
我觉得这个版都进水了。

。。不要问我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个
题:
们把 WSN No.i 搞定 MM No.j 需要的时间记做 T(i,j), 那么,T(i,j)组成了一个 N
by N 的正整数矩阵。
不必要的流血事件,不可以让两个 WSN 去泡同一个MM。。。

【在 c*********t 的大作中提到】
: 如你所愿,题目已做改动。
: 我土,什么叫做 tunneling 啊? Is it something like aborting search
: pre-maturely?
:
: ppmm
: N

D********e
发帖数: 475
11
I guess google wants an exact algorithm for this problem.

ppmm
N

【在 h********r 的大作中提到】
: 我要是wsn,要么住霸王店,要么搭帐篷。住个店都怎么麻烦,你说以后还有哪个ppmm
: 会跟你出去玩?真是脑子彻底进水了。
: (这个问题应该是np-complete,还是不要最便宜,只要差不多便宜就可以了。用随机
: mutation+tunneling)
:
: 我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题:
: 果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N
: 的正整数矩阵。
: 的)
: 。。。

i*********n
发帖数: 219
12
泡妞太低俗了?
那改成泡美眉吧
c*********t
发帖数: 1861
13
真是踏破旅游鞋。。。昨天无意中搜到一个 Hungarian 算法,O(N^4)把问题解决了。
思想方法是先找到(冲突的)局部最优,然后逐步放松(找次优)调整消除冲突。不过
这个算法比较 non-intuitive. 有兴趣的群众可以参考:
http://en.wikipedia.org/wiki/Hungarian_algorithm
真不知道那些得满分的疯子怎么会在2小时内记得这些东西。。。

,大家帮我想这个题:
的时间记做 T(i,j), 那么,T(i,j)组成了一个 N by N 的正整数矩阵。

【在 c*********t 的大作中提到】
: 如你所愿,题目已做改动。
: 我土,什么叫做 tunneling 啊? Is it something like aborting search
: pre-maturely?
:
: ppmm
: N

D********e
发帖数: 475
14
Just realized this is maximum weighted bipartite matching. Should be easily
solvable with augmenting path algorithm.

【在 c*********t 的大作中提到】
: 真是踏破旅游鞋。。。昨天无意中搜到一个 Hungarian 算法,O(N^4)把问题解决了。
: 思想方法是先找到(冲突的)局部最优,然后逐步放松(找次优)调整消除冲突。不过
: 这个算法比较 non-intuitive. 有兴趣的群众可以参考:
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: 真不知道那些得满分的疯子怎么会在2小时内记得这些东西。。。
:
: ,大家帮我想这个题:
: 的时间记做 T(i,j), 那么,T(i,j)组成了一个 N by N 的正整数矩阵。

1 (共1页)
相关主题
航母事件,其实小将,老将都不是啥好鸟!参赛★☆【WSN组歌】☆★第6章合唱《WSN啊WSN》 (转载)
不得不说,北美 WSN 真是 naive 得可以sigh, bbs上WSN忒多了
天朝要投2600亿修渤海隧道了Wsn 们应该都搬去纽约。。。
WSN都too young too simple sometimes naive今天在DC酒吧看球时为中国WSN争光了 (转载)
凄美的恋爱问题(转帖)[报到] E300
又来献宝啦!周日有人去salsa么?
天朝威武!提醒:今天是wsn的盛大节日
惨绝人寰!WSN为解Google难题舍身取义去跳楼WSN 的好消息:美国华人女多于男 by 21万
相关话题的讨论汇总
话题: wsn话题: 矩阵话题: 记做话题: 正整数话题: 时间