《战略忽悠局外传》超大飞翔天宇原创 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

《战略忽悠局外传》超大飞翔天宇原创 (转载)

《战略忽悠局外传》超大飞翔天宇原创 (转载)# Joke - 肚皮舞运动

a*m2011-01-15 08:01

1 楼

You have to paint N boards of length {B1, B2, B3… BN}. There are K
painters available and you are also given how much time a painter takes to
paint 1 unit of board. You have to get this job done as soon as possible
under the constraints that any painter will only paint continuous sections
of board, say board {2, 3, 4} or only board {1} or nothing but not board
{2, 4, 5}.
know it could be solved by DP. But solution space seems quite big. What is
the optimal solution? Thx.

m*g2011-01-15 08:01

2 楼

寻kindercare的Referral--各有$200 Tuition Credit
不在同一家或地区，也可以refer。有意者请回信，谢谢！
http://www.kindercare.com/refer-a-friend/
Refer a Friend
As a Kindercare parent, you see first-hand how our programs and dedicated
teachers ensure that your child gets the positive learning experiences
needed to grow up happy and confident. Spread the word to other parents and
we’ll reward you both. It’s our way of saying thanks.
You and the parent you refer will receive a $200 center credit if they
enroll. You will also receive a $20 center credit if a parent you refer
takes a center tour*

m*d2011-01-15 08:01

3 楼

【以下文字转载自 Military 讨论区】
发信人: fatblackliar (轻风拂山岗), 信区: Military
标题: 《战略忽悠局外传》超大飞翔天宇原创 (转载)
发信站: BBS 未名空间站 (Sat Jan 15 14:06:00 2011, 美东)
发信人: digoxin (大内高手), 信区: Military2
标题: 《战略忽悠局外传》超大飞翔天宇原创
发信站: BBS 未名空间站 (Fri Jan 14 13:54:17 2011, 美东)
《战略忽悠局外传》
超大原创
走上这条道路，是很久以前的事情，那时我还是一个青涩的大学生，怀揣报国梦。
一天，团委老师叫我去2教202，说：有人在等我。
开门之后，我见到两个人，西装革履，貌不惊人。见我进来，他们问了我第一句话
：“你愿意为了国家，一辈子隐姓埋名么？”
经过简单的面试，他们给了我讲解了其单位的名性质，并告知我这是绝密。我才知
道，他们希望参加国家战略忽悠局的考试。
那一天，我心情很激动。几天后，我被一辆没有车牌的汽车带到了到了一个不知名
的房间里，接受了笔试，房间里只有我一个人。不久，他们通知我，我被录取了，让我
某天去某地参加面试。
我还记得面试那天，当我七拐八拐，在一个胡同的深处，找到了一所古朴的大门的
时候，我再三确认了地址。于是，我轻步向前，红砖绿树下的道路，很漫长，里面很安
逸，像大学校园。走不多久，来到第二道大门前，荷枪实弹的警卫拦住了我。我拿出录
取通知书跟他说：我是来面试的。那警卫告诉我：“今天的面试取消了，明天再来。”
“明天？”我很懊恼，毕竟，在这个夏天里，找到那么僻静的一个院落还是挺累人
的，为什么改变了时间也不通知一声？我带着这样的牢骚转身往回走。
忽然，门口的牌子，在我眼前闪过：国家战略忽悠局，忽悠？忽悠~！这个念头坚
定了起来，这是国家战略忽悠局的面试，难道？这就是第一道面试题？
我于是再次转身，往里走，警卫再次拦住了我的去路：“告诉你了，是明天面试。”
我指了指面试的时间说：“我只相信组织，让我进去~！”
警卫严肃的脸庞，没有表情，几秒钟后，他挥手放行。
沿着大路继续向前，不就看到，有人迎了过来，是X同学么，欢迎你通过了第一道
测验。
您好，我热情的过去握手，请问您怎么称呼？
他笑了，笑的很慈祥：“我不能告诉你，即便告诉了你，也是假的，呵呵，请进吧
。”
绿树环绕下的一栋小楼，静谧。进得楼里，有一道长长的走廊，两面墙上，铺满了
黑色的大理石板，更显得庄严肃穆。我发现墙面上星星点点的，有几个白色的大理石质
地的五角星，我觉得很诧异，于是慢慢贴近墙面才发现，原来，墙面上其实整齐的贴满
了一个个大理石质地的五角星，只不过有些是黑色的因为跟墙壁的颜色一致，所以，并
不容易看出来。这些星星，质地精致，略微突出墙面，白色的五角星里，刻着一些代号
，和日期。黑色的却往往什么也没有。
“呵呵，感兴趣？”带我来的中年男子，忽然出现在我身后。
我笑着点点头：“这些是？”
他环视了整面墙，眼里充满了感情，然后压制住激动的心情，慢慢的说：“这些，
就是局里的前辈，每个星星都是一个不屈不挠的故事，每个星星都有一段辛酸的往事，
他们为了共和国忍辱负重，呵呵，都是英雄。”
“那么，为什么有的是白色，有的是黑色呢？”
“墙壁为什么是黑色？”他反问。
我摇摇头。
“黑色，代表着敌对势力，是他们工作的环境。他们在敌人的眼皮下工作，潜伏，
时刻和危险为伴。所以，他们隐蔽在黑色之中。”
“那么白色的星星呢？”
“如果，他暴露了、牺牲了、或者功成身退了，总之，终于可以大白天下了，就会
，这样，我们叫，翻白。”说着他伸出手去，轻轻抓住一个黑色五角星的边缘，慢慢抽
了出来，我才发现，原来大理石五角星的背面，是璀璨的汉白玉。
我觉得这些，像棋子。
是啊，没听人说么，我们的国家再下一盘棋，大棋。
我们继续往里走，墙上的点点星，仿佛一个个前辈，注视着我们，走进共和国最保
密的机构之一，不由的为之自豪。
面试过后，我被正式录取，永远记得，上的第一堂课，局长张召忠亲自授课，他笑
言，自己大概是第一个在位期间就被翻了白面的人。
很久以后，有一天，和张局长并行出门，走着走着，他停住了脚步，伸手，在诸多
黑星中，点中了一颗，他眼含微泪，轻轻点了两下。看我不解，他笑笑说，老部下了。
不知道什么人能让张局如此动容，我伸手，拉起，问局长：“可以看下白面么？”局长
笑笑说：“下不为例。”然后转身走了。我抽出那颗星星，白面赫然刻着：
“北美站，平”

b*82011-01-15 08:01

4 楼

感觉DP不好弄，主要是Painter之间顺序也可以变化，递归形式过于复杂。

f*e2011-01-15 08:01

5 楼

等你们孩子去了给我们点feedback吧，我们也想送那里

k*i2011-01-15 08:01

6 楼

北美站，平!

g*s2011-01-15 08:01

7 楼

this is google interview q?
i think it is a top coder srm question. not easy.

to
sections
is

【在 a**m 的大作中提到】

: You have to paint N boards of length {B1, B2, B3… BN}. There are K
: painters available and you are also given how much time a painter takes to
: paint 1 unit of board. You have to get this job done as soon as possible
: under the constraints that any painter will only paint continuous sections
: of board, say board {2, 3, 4} or only board {1} or nothing but not board
: {2, 4, 5}.
: know it could be solved by DP. But solution space seems quite big. What is
: the optimal solution? Thx.

y*w2011-01-15 08:01

8 楼

xiangpi在Kindercare, San Diego, CA.行么？

【在 m****g 的大作中提到】

: 寻kindercare的Referral--各有$200 Tuition Credit
: 不在同一家或地区，也可以refer。有意者请回信，谢谢！
: http://www.kindercare.com/refer-a-friend/
: Refer a Friend
: As a Kindercare parent, you see first-hand how our programs and dedicated
: teachers ensure that your child gets the positive learning experiences
: needed to grow up happy and confident. Spread the word to other parents and
: we’ll reward you both. It’s our way of saying thanks.
: You and the parent you refer will receive a $200 center credit if they
: enroll. You will also receive a $20 center credit if a parent you refer

N*d2011-01-15 08:01

9 楼

可夫同志吗？

【在 k**********i 的大作中提到】

: 北美站，平!

c*w2011-01-15 08:01

10 楼

这个似乎是G的题目，我当时on-site就死在类似的一个题目上，呵呵。我后来在板上问这个题目，因为没有说明是G的题目，也就没有人讨论。

g*s2011-01-15 08:01

11 楼

maybe different. don't read it very closely.

【在 c******w 的大作中提到】

: 这个似乎是G的题目，我当时on-site就死在类似的一个题目上，呵呵。我后来在板上问这个题目，因为没有说明是G的题目，也就没有人讨论。

c*w2011-01-15 08:01

12 楼

Maybe the same.......Funny

【在 g*********s 的大作中提到】

: maybe different. don't read it very closely.

u*e2011-01-15 08:01

13 楼

多背包问题啊～
遇到这种题就头疼-_-

【在 a**m 的大作中提到】

i*e2011-01-15 08:01

14 楼

I believe this is the same as the partition problem. Basically, you want to
use DP to minimize the maximum sum over all partitions. Another way of
interpreting is try to partition in a way that is as fair to each painter as
possible (ie, the difference between each painter's assignment is as small
as possible).

【在 a**m 的大作中提到】

j*w2011-01-15 08:01

15 楼

This is my 0.02.
Say painter i need p_i time to paint one unit of board.
T_{opt} = (B_1 + B_2 + .. . + B_n) / (p_1 + p_2 + ... + p_k)
If T_{opt} is an integer, done.
If not, say floor of T_{opt} = T_1. (that is, if T_{opt} = 4.33, T_1 = 4).
Set B_{remain} = (B_1 + B_2 + .. . + B_n) - T_1 * (p_1 + p_2 + ... + p_k)
If B_{remain} < p_1 + p_2 + ... + p_k, done (choose the top p_i such that
their sum is equal or just larger than B_{remain}).
Otherwise,
T_{opt2} = B_{remain}/ (p_1 + p_2 + ... + p_k). Recursively

r*l2011-01-15 08:01

16 楼

This problem equals to find a way to assign N boards to k painters, k <= K,
such that the maximum workload(max) for each painter is the smallest among
the search space.
For example:
B = {2, 3, 8, 7, 5, 6, 3}
max = 8, k = 6 // the assignment is {2,3} {8} {7} {5} {6} {3}
max = 9, k = 5
max = 10, k = 5
max = 11, k = 5
max = 12, k = 4 // the assignment is {2,3} {8} {7,5} {6,3}
... ,...
max = 34, k = 1 // the assignment is {all}
if K = 5, we return max = 9. Because the smaller the max is, the less time
it takes to paint all the boards.
The way to calculate k is easy, just use greedy algorithm.
At last we use binary search to solve the problem:
int painting(int B[], int N, int K) {
int low = max(B, N);
int high = sum(B, N);
int i, mid, painterNeeded, alreadyPainted;
while (low < high) {
mid = low + (high - low) / 2;
// calculate k when max = mid
i = 0;
painterNeeded = 1;
alreadyPainted = 0;
while (i < N) {
if (alreadyPainted + B[i] <= mid) {
alreadyPainted += B[i];
i++;
}
else { // exceeds one painter's maximum workload, assign another
painter
alreadyPainted = 0;
painterNeeded++;
}
}
if (painterNeeded <= K) {
high = mid;
}
else {
low = mid + 1;
}
}
return low;
}
Given the maximum workload for each painter, we can easily print out the
assignment for each painter.
Time complexity O(NlogM), where M is the search space(sum(B)-max(B)).

i*e2011-01-15 08:01

17 楼

这题原来是 topcoder 的 SRM 169 DIV 1 Lvl 2 "FairWorkload" http://www.topcoder.com/stat?c=problem_statement&pm=1901&rd=4650，照理说应该非常有难度，但赛题的 N 最大值为 15，直接用穷举法就可以搞定。（但是如果想到穷举的思路，利用 DP 来优化成 O(k * N^2) 其实很直接）。
楼上贴的解法很漂亮，利用 binary search 的巧妙思路。
有兴趣的朋友可以参考 topcoder 有关 binary search 的完整解析：（搜
FairWorkload）
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binary
学习了，收益匪浅。
以下我贴的 O(k * N^2) DP 解法。
const int MAX_N = 100;
int findMax(int A[], int n, int k) {
int M[MAX_N+1][MAX_N+1] = {0};
int cum[MAX_N+1] = {0};
for (int i = 1; i <= n; i++)
cum[i] = cum[i-1] + A[i-1];
for (int i = 1; i <= n; i++)
M[i][1] = cum[i];
for (int i = 1; i <= k; i++)
M[1][i] = A[0];
for (int i = 2; i <= k; i++) {
for (int j = 2; j <= n; j++) {
int best = INT_MAX;
for (int p = 1; p <= j; p++) {
best = min(best, max(M[p][i-1], cum[j]-cum[p]));
}
M[j][i] = best;
}
}
return M[n][k];
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

d*12011-01-15 08:01

18 楼

没看明白题
如果给了每个painter的工作效率，选最高的那个全部paint完不就得了么。。
谁能给个formal的description啊

to
sections
is

【在 a**m 的大作中提到】

f*g2011-01-15 08:01

19 楼

大概看了你的思路。有个问题，如果不对请指正。
你的assumption是，painter是排好序的。
也就是说，第一个painter要不do nothing，要不就要从第一个开始。
如果任何一个painter都可以从第一个开始，结果就复杂的多了。

【在 i**********e 的大作中提到】

: 这题原来是 topcoder 的 SRM 169 DIV 1 Lvl 2 "FairWorkload" http://www.topcoder.com/stat?c=problem_statement&pm=1901&rd=4650，照理说应该非常有难度，但赛题的 N 最大值为 15，直接用穷举法就可以搞定。（但是如果想到穷举的思路，利用 DP 来优化成 O(k * N^2) 其实很直接）。
: 楼上贴的解法很漂亮，利用 binary search 的巧妙思路。
: 有兴趣的朋友可以参考 topcoder 有关 binary search 的完整解析：（搜
: FairWorkload）
: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binary
: 学习了，收益匪浅。
: 以下我贴的 O(k * N^2) DP 解法。
: const int MAX_N = 100;
: int findMax(int A[], int n, int k) {
: int M[MAX_N+1][MAX_N+1] = {0};

g*s2011-01-15 08:01

20 楼

it is incorrect. you assumed all worker painting time is same.
give a sample:
10 10 10 10
2 workers, one paiting time is 1 and another one is 3
Based your algorithm, it should be split to (10 10) (10 10)
but the correct one should be (10 10 10) (10)

<= K,
among

【在 r****l 的大作中提到】

: This problem equals to find a way to assign N boards to k painters, k <= K,
: such that the maximum workload(max) for each painter is the smallest among
: the search space.
: For example:
: B = {2, 3, 8, 7, 5, 6, 3}
: max = 8, k = 6 // the assignment is {2,3} {8} {7} {5} {6} {3}
: max = 9, k = 5
: max = 10, k = 5
: max = 11, k = 5
: max = 12, k = 4 // the assignment is {2,3} {8} {7,5} {6,3}

w*f2011-01-15 08:01

21 楼

someone already give answer
http://www.ihas1337code.com/category/google-interview

g*s2011-01-15 08:01

22 楼

The answer there is also based on: all worker paiting speed is same. Then
it is a easy question. otherwise, it is a difficult question.

【在 w******f 的大作中提到】

: someone already give answer
: http://www.ihas1337code.com/category/google-interview

b*82011-01-15 08:01

23 楼

原来题目没说清楚。每个Painter的效率是一样的啊。

f*g2011-01-15 08:01

24 楼

同感，除非我理解错了。
如果效率不一样，并且可以有do nothing的情况，上面有人说了，找一个效率最高的，
全都做了不就行了？

【在 g***s 的大作中提到】

: The answer there is also based on: all worker paiting speed is same. Then
: it is a easy question. otherwise, it is a difficult question.