E********a
发帖数: 124 | 1 一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
pieces,
i.e.,
minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？ |
h********e
发帖数: 1972 | 2 典型动态规划。。。。。应该还有加速方法， 如果你没学过动态规划做出来了，那就是高手；如果学过了，还用提示，有点说不过去 |
r**u
发帖数: 1567 | 3 k=2还好, k>2感觉挺复杂的,你怎么做的?
【在 E********a 的大作中提到】
: 一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
: pieces,
: i.e.,
: minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
: 大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？
|
a****n
发帖数: 1887 | |
f***g
发帖数: 214 | 5 能给个Link吗
【在 a****n 的大作中提到】
: 又见这道题 binary search
|
E********a
发帖数: 124 | 6 如果没学过，或者忘了动态规划，遇到这样的题，面试人给了很多提示，勉强能做出来
的话，还算是可以的了？
就是高手；如果学过了，还用提示，
有点说不过去
【在 h********e 的大作中提到】
: 典型动态规划。。。。。应该还有加速方法， 如果你没学过动态规划做出来了，那就是高手；如果学过了，还用提示，有点说不过去
|
a********1
发帖数: 750 | 7 就怕人假设你应该知道动态规划阿
你递归的？
【在 E********a 的大作中提到】
: 如果没学过，或者忘了动态规划，遇到这样的题，面试人给了很多提示，勉强能做出来
: 的话，还算是可以的了？
:
: 就是高手；如果学过了，还用提示，
: 有点说不过去
|
E********a
发帖数: 124 | 8 我觉得，interviewer是假设candidate可能知道dp，也可能不知道，关系不大。
interviewer希望看到candidate不知道
dp的时候，在一步一步给出提示的情况下，如何找更优的解法？
candidate用了一些提示，想出递归的算法，但是进一步优化到多项式复杂度的过程比
较费力
【在 a********1 的大作中提到】
: 就怕人假设你应该知道动态规划阿
: 你递归的？
|
z****n
发帖数: 1379 | 9 任何时候，经提示做出应该都是最好的结果，我个人认为比直接做出效果更好。面试不
是找做题机器，而是找以后能一起相处工作的人。工作时候遇到不会的最直接的就是同
事讨论，让面试官觉得你是一个让人愿意愉快进行讨论并且能讨论出结果的人，无疑比
做题本身更加重要。会想你中学时候，是不是有的人你愿意跟他讨论问题，有的人你不
愿意？想想你愿意跟哪种人共事就知道了
【在 E********a 的大作中提到】
: 如果没学过，或者忘了动态规划，遇到这样的题，面试人给了很多提示，勉强能做出来
: 的话，还算是可以的了？
:
: 就是高手；如果学过了，还用提示，
: 有点说不过去
|
a****n
发帖数: 1887 | |
|
|
h********e
发帖数: 1972 | 11 啊。。我没认真看题目。。应该是二分。。不是那种一个字串砍k段，让求最大和 |
w***9
发帖数: 13 | 12 好巧妙的运用二分啊
【在 a****n 的大作中提到】
: 0 < sum of piece < sum all, 在这个区间进行二分
: http://poj.org/problem?id=3273
: http://poj.org/bbs?problem_id=3273
|
d**f
发帖数: 264 | 13
不明白题目的意思,能给个例子吗?
【在 E********a 的大作中提到】
: 一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
: pieces,
: i.e.,
: minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
: 大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？
|
h********e
发帖数: 1972 | 14 其实这题DP也不是一无是处。。。如果数字及其长的话，DP速度比二分快。二分的速度
基本是log^2(所有数字和)*n, DP是2nklog和。 |
w***g
发帖数: 5958 | 15 动态规划, 基本题. 这种题目出了就是为了考动态规划. 动态规划用递归解也是可以的
, 但是不符合套路, 需要扣分. 如果给出指数时间的递归那肯定毙掉 -- 如果是我是面
试官的话.
【在 E********a 的大作中提到】
: 一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
: pieces,
: i.e.,
: minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
: 大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？
|
E********a
发帖数: 124 | 16 我不是想考dp，如果candidate懂dp，我想看他们能不能做到log加速，如果candidate
不会dp，我想看他们能不能在我
给提示告诉他dp思想的情况下做出dp的解法。
btw，我是interviewer。
【在 w***g 的大作中提到】
: 动态规划, 基本题. 这种题目出了就是为了考动态规划. 动态规划用递归解也是可以的
: , 但是不符合套路, 需要扣分. 如果给出指数时间的递归那肯定毙掉 -- 如果是我是面
: 试官的话.
|
a****n
发帖数: 1887 | 17 现在招人搞得跟竞赛似的,对实际项目上的东西没一点帮助
招个senior level developer, 人家15年工作经验, 还要考算法, |
h********e
发帖数: 1972 | 18 这玩意儿就是考考基本功。。竞赛题比这些难多了。。这题目出到竞赛去所有的人都得
做出来了 |
a****n
发帖数: 1887 | |
h*k
发帖数: 984 | |
|
|
E********a
发帖数: 124 | 21 此言诧异了。
比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
scope：
如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
顺利的解决这个
问题，写出clean的code，我也就很满意了。
DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
计算而已。你可以
完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
能力的话，有
了这些提示，应该是能做出来的。而你这个从不会到会的学习和领悟的能力，才是我考
察的。
如果candidate很熟悉DP，那么我希望他能找到优化方案，我希望看他的思考能力，如
何去优化，从什么
地方入手想，当然，我也可以给一些log加速的提示。
如果candidate很熟悉DP，也知道log加速方案，我很高兴，但是我会继续move on到下
一个问题。
【在 a****n 的大作中提到】
: 现在招人搞得跟竞赛似的,对实际项目上的东西没一点帮助
: 招个senior level developer, 人家15年工作经验, 还要考算法,
|
a****n
发帖数: 1887 | 22 不是高深不高深的问题，实际项目多半用不上这些东西。招人是做项目，不是做题。
问算法还不如问问他读过哪些书。
我自己也在国内的一个外企写过几年程序，有些职位根本发挥不了你的能力，就是实现feature，连high level design都是写好的。一个师兄 topcoder 2186, 4年前去的MS，一直没涨级，今年年初去google了，你能力好怎么了，你所处的位置决定你做什么，项目可能根本用不到你的能力。
MS里面大多数人在SDE2位置待5年以上，如果你能力很强，而且很能说，还要看你做的项目以及和MANAGER的关系，哪个公司都是这样。AMAZON 的SDE2 到senior更难升级。 |
E********a
发帖数: 124 | 23 我主要的意思是，问算法coding题的目的，是想找头脑灵活善于思考解决问题，而且有扎实编程基础的
人，因为这样的人做项目时能很快上手，能做好项目，我也希望与这样的人共同工作讨论问题。
即便是有几年经验的人，我觉得善于思考解决问题这一点仍然是很重要的，因为他的经验很可能用不
上，就算他的职位跟经验match，他以后换组呢，以后遇到他没经历过的问题呢? 况且我们这里是
general hiring，candidate以后来什么组都还不知道，所以除非是candidate特别擅长某类
领域，in general我们希望招解决问题能力强的人，做什么都能上手。
问算法题，其实只是一个手段。虽然说，有的时候，是不太容易做出公平的评价， 对于 一个头脑灵
活的人面试的时候因为紧张或者想偏了等原因没发挥好 vs 一个因为做了充分准备和练习/做过原题而
发挥好的人。
TC2186去MS是可惜了，好歹也去个FB啥的，现在不就爽了。 |
i**********e
发帖数: 1145 | 24 我觉得算法固然重要，但是如果你聘请一个人完全取决于他的算法能力，那也太说不过
去了。
我觉得一个好的程序员除了需要有很好的problem solving，更重要的是他对你们公司
做的项目到底感不敢兴趣，有没有热忱。就算有幸给你聘请到，如果他天天来上班对你
们做的项目不感兴趣，那这是公司要请的人吗？
况且，一来就给面试者出DP题，我觉得作为面试题也太过了。毕竟DP题不是很多人懂，
而且要有DP的思路是需要经过不断的练习和总结才训练出来的。要知道身为面试的人会
比平时紧张，思路很容易就不清楚，然后陷入更紧张的状态。
我觉得一个好的面试题应该是有多种解法的。可以很容易想到brute force的解法，但
是也有不那么明显的方法来优化。可以先让面试者以brute force写代码（brute force
的代码不一定都很直接，也有存在很多陷阱，不容易写对的情况）。这时候面试者已经
放松一些了，才更深入地问怎么优化等等。这样我觉得能让面试者比较正常发挥自己的
水平。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
solving
【在 E********a 的大作中提到】
: 此言诧异了。
: 比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
: scope：
: 如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
: 顺利的解决这个
: 问题，写出clean的code，我也就很满意了。
: DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
: 计算而已。你可以
: 完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
: 能力的话，有
|
a****n
发帖数: 1887 | 25 算法问题就是的准备，即使有工作经验的也需要大量时间准备算法，而不是我项目做的
好，我算法也会很好。现在像MS，GOOGLE，AMAZON这类公司不可能只问一些基本算法和
数据结构。
ANYWAY反正我算法不好，也不想准备，跟这类公司是没啥缘分。
有扎实编程基础的
讨论问题。
经验很可能用不
且我们这里是
长某类
对于 一个头脑灵
练习/做过原题而
【在 E********a 的大作中提到】
: 我主要的意思是，问算法coding题的目的，是想找头脑灵活善于思考解决问题，而且有扎实编程基础的
: 人，因为这样的人做项目时能很快上手，能做好项目，我也希望与这样的人共同工作讨论问题。
: 即便是有几年经验的人，我觉得善于思考解决问题这一点仍然是很重要的，因为他的经验很可能用不
: 上，就算他的职位跟经验match，他以后换组呢，以后遇到他没经历过的问题呢? 况且我们这里是
: general hiring，candidate以后来什么组都还不知道，所以除非是candidate特别擅长某类
: 领域，in general我们希望招解决问题能力强的人，做什么都能上手。
: 问算法题，其实只是一个手段。虽然说，有的时候，是不太容易做出公平的评价， 对于 一个头脑灵
: 活的人面试的时候因为紧张或者想偏了等原因没发挥好 vs 一个因为做了充分准备和练习/做过原题而
: 发挥好的人。
: TC2186去MS是可惜了，好歹也去个FB啥的，现在不就爽了。
|
r********9
发帖数: 1116 | 26 怎么个log加速法？
candidate
【在 E********a 的大作中提到】
: 我不是想考dp，如果candidate懂dp，我想看他们能不能做到log加速，如果candidate
: 不会dp，我想看他们能不能在我
: 给提示告诉他dp思想的情况下做出dp的解法。
: btw，我是interviewer。
|
g***s
发帖数: 3811 | 27 算法真正的掌握是让它变成你思考的一个方法，而不是死记。
就像贪心，其实没学过算法的人很多也能直接想到贪心。
动态规划也一样，变成你的思想的时候，就算10年没做，回来还是能马上pickup。
【在 a****n 的大作中提到】
: 算法问题就是的准备，即使有工作经验的也需要大量时间准备算法，而不是我项目做的
: 好，我算法也会很好。现在像MS，GOOGLE，AMAZON这类公司不可能只问一些基本算法和
: 数据结构。
: ANYWAY反正我算法不好，也不想准备，跟这类公司是没啥缘分。
:
: 有扎实编程基础的
: 讨论问题。
: 经验很可能用不
: 且我们这里是
: 长某类
|
d*******l
发帖数: 338 | 28 我认为在状态转移的时候，要找max(dp[i-k][j-1], sum[i]-sum[i-k])中的最小值，而
这个随k的变化是一个单峰函数，只有一个极小值点（可能有俩，细节还需商榷）。而
找单峰函数的极值是可以用三分还是某种方法用log的复杂度找到的
【在 r********9 的大作中提到】
: 怎么个log加速法？
:
: candidate
|
c****m
发帖数: 179 | 29 ?
你怎么状态划分的?
.
【在 h********e 的大作中提到】
: 其实这题DP也不是一无是处。。。如果数字及其长的话，DP速度比二分快。二分的速度
: 基本是log^2(所有数字和)*n, DP是2nklog和。
|
g*********s
发帖数: 1782 | 30 你说的有道理。但是你要意识到不同的人思维和学习方式不同。
有的人反应快，上手快。但也有人反应慢一些，但想的深，有后劲。现在这种面试方式
，基本上就是当
年搞竞赛那一套，比反应快，或者做题多。这种情况工作过的人哪里比的过刚毕业的小
年轻们？
有扎实编程基础
的
讨论问题。
经验很可能用不
且我们这里是
长某类
对于 一个头脑灵
练习/做过原题
而
【在 E********a 的大作中提到】
: 我主要的意思是，问算法coding题的目的，是想找头脑灵活善于思考解决问题，而且有扎实编程基础的
: 人，因为这样的人做项目时能很快上手，能做好项目，我也希望与这样的人共同工作讨论问题。
: 即便是有几年经验的人，我觉得善于思考解决问题这一点仍然是很重要的，因为他的经验很可能用不
: 上，就算他的职位跟经验match，他以后换组呢，以后遇到他没经历过的问题呢? 况且我们这里是
: general hiring，candidate以后来什么组都还不知道，所以除非是candidate特别擅长某类
: 领域，in general我们希望招解决问题能力强的人，做什么都能上手。
: 问算法题，其实只是一个手段。虽然说，有的时候，是不太容易做出公平的评价， 对于 一个头脑灵
: 活的人面试的时候因为紧张或者想偏了等原因没发挥好 vs 一个因为做了充分准备和练习/做过原题而
: 发挥好的人。
: TC2186去MS是可惜了，好歹也去个FB啥的，现在不就爽了。
|
|
|
a****n
发帖数: 1887 | 31 这个题最佳的解法就是二分法， 而且大多数面试官也不知道这个方法。
【在 g***s 的大作中提到】
: 算法真正的掌握是让它变成你思考的一个方法，而不是死记。
: 就像贪心，其实没学过算法的人很多也能直接想到贪心。
: 动态规划也一样，变成你的思想的时候，就算10年没做，回来还是能马上pickup。
|
g***s
发帖数: 3811 | 32 二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
DP could be O(nklogn)
【在 h********e 的大作中提到】
: 其实这题DP也不是一无是处。。。如果数字及其长的话，DP速度比二分快。二分的速度
: 基本是log^2(所有数字和)*n, DP是2nklog和。
|
d*******l
发帖数: 338 | 33 问一下，这题dp的优化是靠在状态转移时用找单峰函数极值的方法么？
这题二分确实更好，其实这种二分答案的方法还是很常见的，不过对有些题只能用dp
【在 g***s 的大作中提到】
: 二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
: DP could be O(nklogn)
|
g***s
发帖数: 3811 | 34 yes. you alredy gave the answer in your previous post. :)
【在 d*******l 的大作中提到】
: 问一下，这题dp的优化是靠在状态转移时用找单峰函数极值的方法么？
: 这题二分确实更好，其实这种二分答案的方法还是很常见的，不过对有些题只能用dp
|
h***o
发帖数: 30 | 35 这两个问题还是有区别的
在你提供的链接里的这个问题中，顺序是定的。
当k = 2是，
如输入
3，2，2，1
则二分输出 5， {[3, 2], [2, 1]}
如输入
1，3，2，2
则二分输出 4, {[1, 3], [2, 2]}
搂主的问题是找到无序的情况下的最小值
【在 a****n 的大作中提到】
: 0 < sum of piece < sum all, 在这个区间进行二分
: http://poj.org/problem?id=3273
: http://poj.org/bbs?problem_id=3273
|
h***o
发帖数: 30 | 36 请问楼主具体解法是什么呢？
这个问题和Multiprocessor scheduling应该是一样的
http://en.wikipedia.org/wiki/Multiprocessor_scheduling
给出approximate algorithm的比较多
solving
【在 E********a 的大作中提到】
: 此言诧异了。
: 比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
: scope：
: 如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
: 顺利的解决这个
: 问题，写出clean的code，我也就很满意了。
: DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
: 计算而已。你可以
: 完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
: 能力的话，有
|
i**********e
发帖数: 1145 | 37 高手请指教，DP 我能想到的是 O(kN^2)，怎么优化成 O（NklogN）呢？
我的思路在这里:
http://www.ihas1337code.com/2011/04/the-painters-partition-prob
利用 Binary Search 的二分搜索，复杂度应该是 O(N log ( Sum of(A) ) 才对吧？不
对请指正一下，谢谢。
我的二分思路在这里：
http://www.ihas1337code.com/2011/04/the-painters-partition-prob
【在 g***s 的大作中提到】
: 二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
: DP could be O(nklogn)
|
g*********s
发帖数: 1782 | 38 lz means order fixed.
pls notice he said "piece".
【在 h***o 的大作中提到】
: 这两个问题还是有区别的
: 在你提供的链接里的这个问题中，顺序是定的。
: 当k = 2是，
: 如输入
: 3，2，2，1
: 则二分输出 5， {[3, 2], [2, 1]}
: 如输入
: 1，3，2，2
: 则二分输出 4, {[1, 3], [2, 2]}
: 搂主的问题是找到无序的情况下的最小值
|
g***s
发帖数: 3811 | 39 sum(i)表示到第i个元素的和。O(n)可以做。
用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
那么这个p=5 sum(5)=10,sum(4）=8不行
然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
小于等
于max(a[])
所以，负责度是O(nlogn + n log max(a[])
对于DP，因为
dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
所以是 O(NKLogN)
另外，空间复杂度可以用O(n)因为任何dp函数，k都只和dp[k-1]相关。所以，用两个长
度为n
的array就可以了。（另外还要一个sum（i）的数组，那么空间是3×n）
【在 i**********e 的大作中提到】
: 高手请指教，DP 我能想到的是 O(kN^2)，怎么优化成 O（NklogN）呢？
: 我的思路在这里:
: http://www.ihas1337code.com/2011/04/the-painters-partition-prob
: 利用 Binary Search 的二分搜索，复杂度应该是 O(N log ( Sum of(A) ) 才对吧？不
: 对请指正一下，谢谢。
: 我的二分思路在这里：
: http://www.ihas1337code.com/2011/04/the-painters-partition-prob
|
g**e
发帖数: 6127 | 40 学习
【在 g***s 的大作中提到】
: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
|
|
|
g**e
发帖数: 6127 | 41 sum(p-1)->sum(p)二分怎么操作？倒着来?
？不
【在 g***s 的大作中提到】
: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
|
g***s
发帖数: 3811 | 42 min=sum(p-1) 这个不满足
max=sum(p) 这个满足
这个范围里面有的数字就是max-min+1=a[p]+1
【在 g**e 的大作中提到】
: sum(p-1)->sum(p)二分怎么操作？倒着来?
:
: ？不
|
g**e
发帖数: 6127 | 43 明白了，这个比ihascode那个要高效。赞大牛
【在 g***s 的大作中提到】
: min=sum(p-1) 这个不满足
: max=sum(p) 这个满足
: 这个范围里面有的数字就是max-min+1=a[p]+1
|
i**********e
发帖数: 1145 | 44 你的加速法非常巧妙，太好太强大，一定要狂赞！
非常感谢你，小弟学习了！
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g***s 的大作中提到】
: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
|
g*****i
发帖数: 2162 | 45 没学过dp,就看过介绍,能详细说下你这里这个max()的意思吗?
【在 d*******l 的大作中提到】
: 我认为在状态转移的时候，要找max(dp[i-k][j-1], sum[i]-sum[i-k])中的最小值，而
: 这个随k的变化是一个单峰函数，只有一个极小值点（可能有俩，细节还需商榷）。而
: 找单峰函数的极值是可以用三分还是某种方法用log的复杂度找到的
|
g**********y
发帖数: 14569 | 46 这个解法很好，但是跟DP没什么关系吧？
总结起来就是：
1. 用二分找到分割点p
2. 再用二分找出精确值，这个值在sum[p-1]和sum[p]之间
【在 g***s 的大作中提到】
: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
|
i**********e
发帖数: 1145 | 47 max() 是函数 maximum 的意思，就是两个值的比较，返回较大的那个值。
max(a,b) = a --> if (a > b)
else
max(a,b) = b
而递归的公式是：
M[n, k] = min { max (from j=1..n) { M[j, k-1], ∑(i=j..n-1) Ai } }
如果利用以上公式硬递归的话，就会非常慢，所以用 dp 来优化。可以顺序渐进，将计
算结果储存在数组里，这样就不用反复计算 M[j, k-1] 的值。其实主要思路还是怎么
获得这个公式，获得了之后用 dp 来优化就很直观了。
更多有关 dp 的思路请看这里：
http://www.ihas1337code.com/2011/04/the-painters-partition-prob
【在 g*****i 的大作中提到】
: 没学过dp,就看过介绍,能详细说下你这里这个max()的意思吗?
|
g***s
发帖数: 3811 | 48 DP is another algo to solve this question.
【在 g**********y 的大作中提到】
: 这个解法很好，但是跟DP没什么关系吧？
: 总结起来就是：
: 1. 用二分找到分割点p
: 2. 再用二分找出精确值，这个值在sum[p-1]和sum[p]之间
|
d*****e
发帖数: 29 | 49 sum(i)表示到第i个元素的和。O(n)可以做。
nlogn)
────────
可以解释一下什么是满足题意吗？是说sum(p) = maximum吗？如果大数字都在队尾，p
可能不存在。
Number array: 1, 1, 10 k=2
p = ? |
g**e
发帖数: 6127 | 50 p=3
p
【在 d*****e 的大作中提到】
: sum(i)表示到第i个元素的和。O(n)可以做。
: nlogn)
: ────────
: 可以解释一下什么是满足题意吗？是说sum(p) = maximum吗？如果大数字都在队尾，p
: 可能不存在。
: Number array: 1, 1, 10 k=2
: p = ?
|
|
|
d*****e
发帖数: 29 | 51 if p=3, then the array has only one piece, which is smaller than k (2). How
to explain it has satisfied the requirement? |
g***s
发帖数: 3811 | 52 of coz it does. you let one guy to do everyting and the other just take a
rest. but it is not the optimal answer.
so, we now know, sum(3) = 12 OK sum(2) = 2 Not OK
search between 2 and 12 using bi-search to find the correct answer, and
you will get it is 10.
How
【在 d*****e 的大作中提到】
: if p=3, then the array has only one piece, which is smaller than k (2). How
: to explain it has satisfied the requirement?
|
d*****e
发帖数: 29 | 53 Thanks for the explanation. It makes sense. |
g*****i
发帖数: 2162 | 54 谢谢解释,你的网站很好,这题的子问题我想不出来,你的网站解释的很好.不过你的算法
复杂度是kn^2,对O(nklogn)的dp算法我还是有写不明白:
max(dp[i-k][j-1], sum[i]-sum[i-k]) 如何看出是基于k的单峰函数?网上说单峰函数
判断用求导,谁能解释下?
单峰函数求极值我搜了一篇文章
http://hi.baidu.com/kyno_yang/blog/item/938a912dd0e3e3e58a1399c
类似log加速,前面说的3分法应该也是这样的吧,不过关键是要先判断出是单峰函数.
总之单峰函数以前没处理过,有点意思啊.
【在 i**********e 的大作中提到】
: max() 是函数 maximum 的意思，就是两个值的比较，返回较大的那个值。
: max(a,b) = a --> if (a > b)
: else
: max(a,b) = b
: 而递归的公式是：
: M[n, k] = min { max (from j=1..n) { M[j, k-1], ∑(i=j..n-1) Ai } }
: 如果利用以上公式硬递归的话，就会非常慢，所以用 dp 来优化。可以顺序渐进，将计
: 算结果储存在数组里，这样就不用反复计算 M[j, k-1] 的值。其实主要思路还是怎么
: 获得这个公式，获得了之后用 dp 来优化就很直观了。
: 更多有关 dp 的思路请看这里：
|
i**********e
发帖数: 1145 | 55 恩
虽然明白了 grass 的二分优化法
但是也不知道怎么处理单峰函数
希望 grass 能展开说说
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*****i 的大作中提到】
: 谢谢解释,你的网站很好,这题的子问题我想不出来,你的网站解释的很好.不过你的算法
: 复杂度是kn^2,对O(nklogn)的dp算法我还是有写不明白:
: max(dp[i-k][j-1], sum[i]-sum[i-k]) 如何看出是基于k的单峰函数?网上说单峰函数
: 判断用求导,谁能解释下?
: 单峰函数求极值我搜了一篇文章
: http://hi.baidu.com/kyno_yang/blog/item/938a912dd0e3e3e58a1399c
: 类似log加速,前面说的3分法应该也是这样的吧,不过关键是要先判断出是单峰函数.
: 总之单峰函数以前没处理过,有点意思啊.
|
r*******t
发帖数: 99 | 56 dp[i-k][j-1]随k单调下降，sum[i]-sum[i-k]随k单调上升，画两条单增和单减的线取
max一定是单峰（其实应该是单谷），峰在两线相交处。
【在 g*****i 的大作中提到】
: 谢谢解释,你的网站很好,这题的子问题我想不出来,你的网站解释的很好.不过你的算法
: 复杂度是kn^2,对O(nklogn)的dp算法我还是有写不明白:
: max(dp[i-k][j-1], sum[i]-sum[i-k]) 如何看出是基于k的单峰函数?网上说单峰函数
: 判断用求导,谁能解释下?
: 单峰函数求极值我搜了一篇文章
: http://hi.baidu.com/kyno_yang/blog/item/938a912dd0e3e3e58a1399c
: 类似log加速,前面说的3分法应该也是这样的吧,不过关键是要先判断出是单峰函数.
: 总之单峰函数以前没处理过,有点意思啊.
|
g*****i
发帖数: 2162 | 57 多谢解释!
【在 r*******t 的大作中提到】
: dp[i-k][j-1]随k单调下降，sum[i]-sum[i-k]随k单调上升，画两条单增和单减的线取
: max一定是单峰（其实应该是单谷），峰在两线相交处。
|
s*****y
发帖数: 897 | 58 刚看了一下1337 code上面这题的update，用了grass的优化
Using the above example:
A = { 100, 200, 300, 400, 500, 600, 700, 800, 900 }, and k = 3.
We build the cumulative array B:
B = { 100, 300, 600, 1000, 1500, 2100, 2800, 3600, 4500 }
After we apply binary search, we are able to find that B[4] = 1500, B[5] =
2100, because for costmax = 1500, x = 4; while costmax = 2100, x =3.
这里我们用这个2分找到lo是1500
那么为什么不可以直接用最大的sum/worker = 4500/3 = 1500 当为我们的lo呢？
如果1500不在sum array里面，我们最多也就是算比1500小的一个sum和比1500大的一个
sum需要的worker数目。
这样做有什么问题吗？
请指教。
【在 g***s 的大作中提到】
: min=sum(p-1) 这个不满足
: max=sum(p) 这个满足
: 这个范围里面有的数字就是max-min+1=a[p]+1
|
s*****y
发帖数: 897 | 59 顶一个。
刚看了一下1337 code上面这题的update，用了grass的优化
Using the above example:
A = { 100, 200, 300, 400, 500, 600, 700, 800, 900 }, and k = 3.
We build the cumulative array B:
B = { 100, 300, 600, 1000, 1500, 2100, 2800, 3600, 4500 }
After we apply binary search, we are able to find that B[4] = 1500, B[5] =
2100, because for costmax = 1500, x = 4; while costmax = 2100, x =3.
这里我们用这个2分找到lo是1500
那么为什么不可以直接用最大的sum/worker = 4500/3 = 1500 当为我们的lo呢？
如果1500不在sum array里面，我们最多也就是算比1500小的一个sum和比1500大的一个
sum需要的worker数目。
这样做有什么问题吗？
请指教。
【在 s*****y 的大作中提到】
: 刚看了一下1337 code上面这题的update，用了grass的优化
: Using the above example:
: A = { 100, 200, 300, 400, 500, 600, 700, 800, 900 }, and k = 3.
: We build the cumulative array B:
: B = { 100, 300, 600, 1000, 1500, 2100, 2800, 3600, 4500 }
: After we apply binary search, we are able to find that B[4] = 1500, B[5] =
: 2100, because for costmax = 1500, x = 4; while costmax = 2100, x =3.
: 这里我们用这个2分找到lo是1500
: 那么为什么不可以直接用最大的sum/worker = 4500/3 = 1500 当为我们的lo呢？
: 如果1500不在sum array里面，我们最多也就是算比1500小的一个sum和比1500大的一个
|
k*n
发帖数: 150 | 60 你是什么公司的？
solving
【在 E********a 的大作中提到】
: 此言诧异了。
: 比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
: scope：
: 如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
: 顺利的解决这个
: 问题，写出clean的code，我也就很满意了。
: DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
: 计算而已。你可以
: 完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
: 能力的话，有
|
|
|
g***s
发帖数: 3811 | 61 yes. you can.
So, you can skip all sum(i) < sum(n)/k. in your case, 100,300,600,1000.
but we still need to use binary search to check sum[4] to sum[8]. it
could be still O(nlogn).
But in the following case, it can get much improvement by your changes:
O(n) for this step.
1,1,1,1,1,1......,1, 10000, 10000 k=3 |
s*****y
发帖数: 897 | 62 Thanks da niu for the conform.
【在 g***s 的大作中提到】
: yes. you can.
: So, you can skip all sum(i) < sum(n)/k. in your case, 100,300,600,1000.
: but we still need to use binary search to check sum[4] to sum[8]. it
: could be still O(nlogn).
: But in the following case, it can get much improvement by your changes:
: O(n) for this step.
: 1,1,1,1,1,1......,1, 10000, 10000 k=3
|
