g*******y
发帖数: 1930 | 1 1. N台机器，每台机器有N个数
找median (2个数组找median的扩展版)
2. 已知coin denominator set，例如,2cent, 3cent, 5cent...
给定一个目标数，比如126cents
最少需要多少个coin。
这个题我以前问过一次，没人回。。。我觉得是很好的题，贪心，回溯，DP都可以试试
。但是我一直没找到最满意的解。
3. 一个整数数组，找3个数满足勾股定理。求比O(n^2)更好的解 |
k***e
发帖数: 556 | 2 2. 我也考虑过 什么时候greedy可以work
dp画表来求用时Nk
3. wiki 3sum，there is no bettern solution than n^2 and there is no better
algorithm for it.
【在 g*******y 的大作中提到】
: 1. N台机器，每台机器有N个数
: 找median (2个数组找median的扩展版)
: 2. 已知coin denominator set，例如,2cent, 3cent, 5cent...
: 给定一个目标数，比如126cents
: 最少需要多少个coin。
: 这个题我以前问过一次，没人回。。。我觉得是很好的题，贪心，回溯，DP都可以试试
: 。但是我一直没找到最满意的解。
: 3. 一个整数数组，找3个数满足勾股定理。求比O(n^2)更好的解
|
r**u
发帖数: 1567 | 3 第一题，如果没有space限制，就吧N^2个数都搞在一起，然后找median？？？
【在 g*******y 的大作中提到】
: 1. N台机器，每台机器有N个数
: 找median (2个数组找median的扩展版)
: 2. 已知coin denominator set，例如,2cent, 3cent, 5cent...
: 给定一个目标数，比如126cents
: 最少需要多少个coin。
: 这个题我以前问过一次，没人回。。。我觉得是很好的题，贪心，回溯，DP都可以试试
: 。但是我一直没找到最满意的解。
: 3. 一个整数数组，找3个数满足勾股定理。求比O(n^2)更好的解
|
g*******y
发帖数: 1930 | 4 greedy单独用应该不work，可以和回溯结合起来，也许会快一些(?)
dp你是怎么做到NK的？另外值得考虑的一点是,DP的复杂度是伪多项式的。
第3个题，我知道上次讨论过了，3sum是最少要n^2，但是这个勾股数有些不同啊，最显著的一点，满足勾股定理的三个数显然比满足a+b=c的数稀少很多。忘了说了，题目是整数数组。
【在 k***e 的大作中提到】
: 2. 我也考虑过 什么时候greedy可以work
: dp画表来求用时Nk
: 3. wiki 3sum，there is no bettern solution than n^2 and there is no better
: algorithm for it.
|
g*******y
发帖数: 1930 | 5 第一题的考点是利用多个机器并行的来做计算
【在 r**u 的大作中提到】
: 第一题，如果没有space限制，就吧N^2个数都搞在一起，然后找median？？？
|
k***e
发帖数: 556 | 6 for prob1, I suggest using the randomized algorithm.
there is an algorithm in textbook CLRS that do the selection in linear
expection time. thus we can expect to get the solution intime O(#machine*#
number)
【在 g*******y 的大作中提到】
: 1. N台机器，每台机器有N个数
: 找median (2个数组找median的扩展版)
: 2. 已知coin denominator set，例如,2cent, 3cent, 5cent...
: 给定一个目标数，比如126cents
: 最少需要多少个coin。
: 这个题我以前问过一次，没人回。。。我觉得是很好的题，贪心，回溯，DP都可以试试
: 。但是我一直没找到最满意的解。
: 3. 一个整数数组，找3个数满足勾股定理。求比O(n^2)更好的解
|
g*******y
发帖数: 1930 | 7 you mean O(N*N)?
But at least you can achieve O(NlogN) by first sort and then do some tricks.
【在 k***e 的大作中提到】
: for prob1, I suggest using the randomized algorithm.
: there is an algorithm in textbook CLRS that do the selection in linear
: expection time. thus we can expect to get the solution intime O(#machine*#
: number)
|
k***e
发帖数: 556 | 8 i think i see this problem before.
the memory is limited and we cannot move everything to one machine. ok.
lets make some parmeters clear. suppose there are N machines, each one has m
numbers
1) if each machine cannot hold more than O(m) numbers, what is the min total
time? (consider parallel computation)
2) if each machine can hold all the numbers, what is the min total time?
tricks.
【在 g*******y 的大作中提到】
: you mean O(N*N)?
: But at least you can achieve O(NlogN) by first sort and then do some tricks.
|
m*****f
发帖数: 1243 | 9 这道题其实很open, 因为优化的目标不清楚, 是要优化time还是space, 或是network
traffic, 都可以得出不一样的算法
m
total
【在 k***e 的大作中提到】
: i think i see this problem before.
: the memory is limited and we cannot move everything to one machine. ok.
: lets make some parmeters clear. suppose there are N machines, each one has m
: numbers
: 1) if each machine cannot hold more than O(m) numbers, what is the min total
: time? (consider parallel computation)
: 2) if each machine can hold all the numbers, what is the min total time?
:
: tricks.
|
g*******y
发帖数: 1930 | 10 I like your point of view~
Previously I just ignore the network traffic and latency and only focused on
computing time.
【在 m*****f 的大作中提到】
: 这道题其实很open, 因为优化的目标不清楚, 是要优化time还是space, 或是network
: traffic, 都可以得出不一样的算法
:
: m
: total
|
|
|
r**u
发帖数: 1567 | 11 给说说怎么parallel这个东西吧
【在 g*******y 的大作中提到】
: 第一题的考点是利用多个机器并行的来做计算
|
H*M
发帖数: 1268 | 12 第二题好像是deminator符合什么规则就可以用贪心,比如现在美国的币制
【在 g*******y 的大作中提到】
: 1. N台机器，每台机器有N个数
: 找median (2个数组找median的扩展版)
: 2. 已知coin denominator set，例如,2cent, 3cent, 5cent...
: 给定一个目标数，比如126cents
: 最少需要多少个coin。
: 这个题我以前问过一次，没人回。。。我觉得是很好的题，贪心，回溯，DP都可以试试
: 。但是我一直没找到最满意的解。
: 3. 一个整数数组，找3个数满足勾股定理。求比O(n^2)更好的解
|
H*M
发帖数: 1268 | 13 ps,第二题point是什么?我咋觉得就是个经典的coin change问题?
还是我 miss什么?
ps,如果有1的话,保证永远有解,否则有可能没解.
出错
【在 H*M 的大作中提到】
: 第二题好像是deminator符合什么规则就可以用贪心,比如现在美国的币制
|
a****n
发帖数: 1887 | 14 极大独立集==最大独立集
出错
【在 H*M 的大作中提到】
: 第二题好像是deminator符合什么规则就可以用贪心,比如现在美国的币制
|
H*M
发帖数: 1268 | 15 你是说那个条件?详细说说?
【在 a****n 的大作中提到】
: 极大独立集==最大独立集
:
: 出错
|
g*******y
发帖数: 1930 | 16 你说的经典coin change问题是什么？
这个题目里面，coin denominators 可以是一组任意的input
如果gcd(coin denominators)==1 应该就大于某个数以后都有解了。
【在 H*M 的大作中提到】
: ps,第二题point是什么?我咋觉得就是个经典的coin change问题?
: 还是我 miss什么?
: ps,如果有1的话,保证永远有解,否则有可能没解.
:
: 出错
|
H*M
发帖数: 1268 | 17 就叫coin change problem, 经典的DP题目.如果denominator符合某规则(比如美国现行
的1,5,10,25),则可以贪心,否则不行.在哪看过,记不起来地址了..
【在 g*******y 的大作中提到】
: 你说的经典coin change问题是什么？
: 这个题目里面，coin denominators 可以是一组任意的input
: 如果gcd(coin denominators)==1 应该就大于某个数以后都有解了。
|
a****n
发帖数: 1887 | 18 具体你可以查矩阵胚（matroid）
大致意思就是如果你的集合系统是矩阵胚， 那么你的解得过程就是是正确的。
由他推导出来了一些相关的性质， 其实就是判断矩阵胚的方法
【在 H*M 的大作中提到】
: 你是说那个条件?详细说说?
|
h*******e
发帖数: 1377 | 19 第三题似乎一般一个整数的勾股数个数是确定的。大概只有几组解 可以先 (nlog n)
sort之后再查找那几组数是否存在。 3 可以知道勾股数大概是 (3*3+1)/2 (3*3-1)/2
4 可以知道勾股数 也有公式 4/2=2 2^2-1 2^2+1 这样只用 binary search 就可以了
总复杂性nlog n |
r**u
发帖数: 1567 | 20 是啊。DP就行了吧，这题难道还有别的trick?
【在 H*M 的大作中提到】
: 就叫coin change problem, 经典的DP题目.如果denominator符合某规则(比如美国现行
: 的1,5,10,25),则可以贪心,否则不行.在哪看过,记不起来地址了..
|
|
|
c*********n
发帖数: 1057 | 21 但是好象美刀这样，1 5 10 25的就可以啊，有什么规律呢
【在 H*M 的大作中提到】
: 就叫coin change problem, 经典的DP题目.如果denominator符合某规则(比如美国现行
: 的1,5,10,25),则可以贪心,否则不行.在哪看过,记不起来地址了..
|
f****b
发帖数: 486 | 22 2. see http://people.csail.mit.edu/bdean/6.046/dp/
problem #2
【在 g*******y 的大作中提到】
: 1. N台机器，每台机器有N个数
: 找median (2个数组找median的扩展版)
: 2. 已知coin denominator set，例如,2cent, 3cent, 5cent...
: 给定一个目标数，比如126cents
: 最少需要多少个coin。
: 这个题我以前问过一次，没人回。。。我觉得是很好的题，贪心，回溯，DP都可以试试
: 。但是我一直没找到最满意的解。
: 3. 一个整数数组，找3个数满足勾股定理。求比O(n^2)更好的解
|
n*******s
发帖数: 482 | 23 prob2 is the first example of topcoder tutorial (DP)
Vi is the coin's face value
Set Min[i] equal to Infinity for all of i
Min[0]=0
For i = 1 to S
For j = 0 to N - 1
If (Vj<=i AND Min[i-Vj]+1
Then Min[i]=Min[i-Vj]+1
Output Min[S] |
g*******y
发帖数: 1930 | 24 actually my concern is that this DP solution is pseudo-polynomial. I was
wondering if there's better solution.
coin: 2cents,3cents
S=2 result=1
S=3 result=1
S=4 result=2
S=5 result=2
S=6 result=2
S=7 result=3
S=8 result=3
obverse that, for S>=8, we can calculate S' = S - 6*n so that 2<=S'<=7, then:
result[S] = n*2 + result[S']
so obviously the DP solution is not an optimal solution especially when S is
super large
【在 n*******s 的大作中提到】
: prob2 is the first example of topcoder tutorial (DP)
: Vi is the coin's face value
: Set Min[i] equal to Infinity for all of i
: Min[0]=0
: For i = 1 to S
: For j = 0 to N - 1
: If (Vj<=i AND Min[i-Vj]+1: Then Min[i]=Min[i-Vj]+1
: Output Min[S]
|
s**y
发帖数: 223 | 25 像这种题每个机器都sort一遍的运算是不是就不算了
tricks.
【在 g*******y 的大作中提到】
: you mean O(N*N)?
: But at least you can achieve O(NlogN) by first sort and then do some tricks.
|
C***n
发帖数: 452 | 26 whats the trick point here for this problem? thanks.
tricks.
【在 g*******y 的大作中提到】
: you mean O(N*N)?
: But at least you can achieve O(NlogN) by first sort and then do some tricks.
|
i****e
发帖数: 451 | 27 Nice observation. I think you can do this. Suppose the max coin value is K.
First compute f(S) for S=2,3,4, until you find in K adjacent solutions they
all include at least one Max-value
coin. Then you just use the max-value coin to fill the rest value, I guess.
【在 g*******y 的大作中提到】
: actually my concern is that this DP solution is pseudo-polynomial. I was
: wondering if there's better solution.
: coin: 2cents,3cents
: S=2 result=1
: S=3 result=1
: S=4 result=2
: S=5 result=2
: S=6 result=2
: S=7 result=3
: S=8 result=3
|
i****e
发帖数: 451 | 28 For the first problem, I think you can do this:
Suppose K machines, each N numbers. Assume K is even, say, and to make it
simple, N=2^m. Then
1. compute the median for each machine, O(N)=O(2^m);
2. find the median two numbers of those medians O(K);
3. assume the machines are ranked based on their median values (don't need
to rank it actually) and you can
remove the top half numbers for the first K/2 machines, and the bottom half
numbers for the rest machines.
This reduces the number in each mach
【在 g*******y 的大作中提到】
: 1. N台机器，每台机器有N个数
: 找median (2个数组找median的扩展版)
: 2. 已知coin denominator set，例如,2cent, 3cent, 5cent...
: 给定一个目标数，比如126cents
: 最少需要多少个coin。
: 这个题我以前问过一次，没人回。。。我觉得是很好的题，贪心，回溯，DP都可以试试
: 。但是我一直没找到最满意的解。
: 3. 一个整数数组，找3个数满足勾股定理。求比O(n^2)更好的解
|
t***b
发帖数: 38 | 29 What do you mean it is pseudo-polynomial?
The complexity is O(S x N). The computation time increases linearly with
respect to S and N, right?
Do I miss anything here?
【在 g*******y 的大作中提到】
: actually my concern is that this DP solution is pseudo-polynomial. I was
: wondering if there's better solution.
: coin: 2cents,3cents
: S=2 result=1
: S=3 result=1
: S=4 result=2
: S=5 result=2
: S=6 result=2
: S=7 result=3
: S=8 result=3
|
