logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
现在也不知道是谁更懂中文。。。
avatar
现在也不知道是谁更懂中文。。。# Joke - 肚皮舞运动
h*3
1 楼
There is a straight roads with 'n' number of milestones. You are given an
array with the distance between all the pairs of milestones in some random
order. Find the position of milestones.
Example:
Consider a road with 4 milestones(a,b,c,d) :
a bcd
Distance between a and b = 3
Distance between a and c = 8
Distance between a and d = 10
Distance between b and c = 5
Distance between b and d = 7
Distance between c and d = 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3,5,2 or 2,5,3
avatar
c*7
2 楼
哦也
avatar
m*2
3 楼
so, N is known when you run the program?
first step is obvious to sort it, and get the first and last position.
2) break the distance down to 2 segments so that
10 = segment1 + segment2 （any pair of segments will do)
3) repeat 2

an
random

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
a*e
4 楼
看来百度也是韩国人发明的
avatar
g*e
5 楼
既然数组是随机的，怎么保证最后所有点的位置？比如你这例子，为什么不能输出5,3,
2?

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
A*r
6 楼
中國大陸人會找漢語拼音表？ 更有可能找韓語吧
字典也一般會找新華字典

【在 c*******7 的大作中提到】
: 哦也
avatar
g*y
7 楼
5, 3, 2产生的序列将会是：
5， 3， 2， 8， 5， 10
有两个5，跟条件不一样。

3,

【在 g**e 的大作中提到】
: 既然数组是随机的，怎么保证最后所有点的位置？比如你这例子，为什么不能输出5,3,
: 2?
avatar
N*C
8 楼
扯，中国会有几个人找韩语？

【在 A********r 的大作中提到】
: 中國大陸人會找漢語拼音表？ 更有可能找韓語吧
: 字典也一般會找新華字典
avatar
g*y
9 楼
给的例子很容易解，推广到N好象不容易
我能观察到的，只有：
1. 最小的两个数，一定是两个相邻milestone的间距。但是不保证这两个间距之间有任
何关系。
2. 最大的数，是所有间距的和。
3. 第二大的数，是所有间距去掉min{头，尾}
题目就是把以下C(n,2)个数随机序排出来，要你恢复A1, ... An-1
A1, A2, A3, ... An-1
A1+A2, A2+A3, ... An-2+An-1
...
A1+A2+..An-2, A2+...+An-1
A1+A2+...An-1
等高手出来给个解。
avatar
g*e
10 楼
最小的两个一定是milestone，但是不一定相邻。op的例子就是。
还有最大的减去第二大的就是一个开头或末尾的milestone. 剩下的没想出来
感觉象解一个线性方程组……

【在 g**********y 的大作中提到】
: 给的例子很容易解，推广到N好象不容易
: 我能观察到的，只有：
: 1. 最小的两个数，一定是两个相邻milestone的间距。但是不保证这两个间距之间有任
: 何关系。
: 2. 最大的数，是所有间距的和。
: 3. 第二大的数，是所有间距去掉min{头，尾}
: 题目就是把以下C(n,2)个数随机序排出来，要你恢复A1, ... An-1
: A1, A2, A3, ... An-1
: A1+A2, A2+A3, ... An-2+An-1
: ...
avatar
g*y
11 楼
对，就是一个线性方程组，但是这个随机性很麻烦，一方面觉得可以解；另一方面，感
觉这个解不一定是唯一的, LZ举的情况两个解其实是一样的，就是反个方向。而且要找
一种普适的办法，好象不容易。

【在 g**e 的大作中提到】
: 最小的两个一定是milestone，但是不一定相邻。op的例子就是。
: 还有最大的减去第二大的就是一个开头或末尾的milestone. 剩下的没想出来
: 感觉象解一个线性方程组……
avatar
b*y
12 楼
感觉好像先找最大的距离
然后依次找第二大的距离，第三大的距离...

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
g*y
13 楼
第三大的距离不确定，以5个点为例，假设第二大的是a2+a3+a4, 也就是说 a4>a1,
第三大，既可以是a1+a2+a3, 也可以是a3+a4

【在 b*******y 的大作中提到】
: 感觉好像先找最大的距离
: 然后依次找第二大的距离，第三大的距离...
avatar
g*s
14 楼
s_1_1
s_2_1 s_2_2
s_3_1 s_3_2 s_3_3
...
s_t_1 s_t_2 s_t_3 s_t_t
t = n - 1 (n is the number of point)
s(i,j) means the sum of lj to li (li is the what we want to output)
e.g. s(2,4) = l2+l3+l4
so, s(i,i) = li
rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
s(t,1) = longest length
Use dfs and edge cut to fill the matrix, then output s(i,i) i=1 to t
for the sample:
7, 10, 5, 2, 8, 3
?
? ?
10 ? ?
1) try 8 in s(3,2)
?
? ?
10 8 ?
-> (based on rule1)
2
? ?
10 8 ?
1-1) try 7 in s(2,1)
2
7 ?
10 8 ?
-> (based on rule1, 10-7=3, 7-2=5)
2
7 5
10 8 3
1-2) try 5 in s(2,1),skip since 10-5 is not in the list
1-3) try 3 in s(2,1),skip since 3-2 is not in the list
2) try 7 in s(3,2)
...
the lots of edges will be cut, so it will not be slow.
avatar
g*s
15 楼
if it is a math question for n=4,
s_2_2 = sum(all) - s_3_1 * 3
in our sample, s_2_2 = 35 - 10 * 3 = 5
s_3_2 could only be 7 or 8, considering the matrix is symmetric,
let s_3_2 = 8, then s_1_1 = 10 - 8 = 2, s_2_1 = 5 + 2 = 7, s_3_3 = 8 - 5
=3
2
7 5
10 8 3

【在 g***s 的大作中提到】
: s_1_1
: s_2_1 s_2_2
: s_3_1 s_3_2 s_3_3
: ...
: s_t_1 s_t_2 s_t_3 s_t_t
: t = n - 1 (n is the number of point)
: s(i,j) means the sum of lj to li (li is the what we want to output)
: e.g. s(2,4) = l2+l3+l4
: so, s(i,i) = li
: rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
avatar
m*k
16 楼
假设有n个milestones,
1， 对给的array排序
2， 最大-第二大= 头or 尾
3， 建n-2个hashtable, 每个table是从 2个milstones的和到n-1个milestones的和
4, 在n-1个milestone的和的hashtable里找 sum= 最大-头or尾的milestones的组合
5, 在n-2个milestones的和的table里找 sum1=sum- 任意4里找出来的组合的一个
mileston
e,
继续这么找下去直到结束。。
不过忒麻烦了。。

【在 g**********y 的大作中提到】
: 对，就是一个线性方程组，但是这个随机性很麻烦，一方面觉得可以解；另一方面，感
: 觉这个解不一定是唯一的, LZ举的情况两个解其实是一样的，就是反个方向。而且要找
: 一种普适的办法，好象不容易。
avatar
g*y
17 楼
给个10个点的例子，谁写个DFS把它算出来 ->
2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23 24 25 26 28
29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56
手算出来也行 :)
avatar
g*e
18 楼
nb呀，不过这bar raiser也太高了，够不着
我也把这三角矩阵画出来了，就是没想到这茬

【在 g***s 的大作中提到】
: s_1_1
: s_2_1 s_2_2
: s_3_1 s_3_2 s_3_3
: ...
: s_t_1 s_t_2 s_t_3 s_t_t
: t = n - 1 (n is the number of point)
: s(i,j) means the sum of lj to li (li is the what we want to output)
: e.g. s(2,4) = l2+l3+l4
: so, s(i,i) = li
: rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
avatar
r*y
19 楼
sort firstly?

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
g*s
20 楼
Answer:
2 7 2 4 8 8 8 10 7
2
9 7
11 9 2
15 13 6 4
23 21 14 12 8
31 29 22 20 16 8
39 37 30 28 24 16 8
49 47 40 38 34 26 18 10
56 54 47 45 41 33 25 17 7
Total running time : 63 ms

28

【在 g**********y 的大作中提到】
: 给个10个点的例子，谁写个DFS把它算出来 ->
: 2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23 24 25 26 28
: 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56
: 手算出来也行 :)
avatar
g*y
21 楼
wow, that's very good performance.

【在 g***s 的大作中提到】
: Answer:
: 2 7 2 4 8 8 8 10 7
: 2
: 9 7
: 11 9 2
: 15 13 6 4
: 23 21 14 12 8
: 31 29 22 20 16 8
: 39 37 30 28 24 16 8
: 49 47 40 38 34 26 18 10
avatar
g*e
22 楼
帅哥，贴个完整代码吧，谢谢

【在 g***s 的大作中提到】
: Answer:
: 2 7 2 4 8 8 8 10 7
: 2
: 9 7
: 11 9 2
: 15 13 6 4
: 23 21 14 12 8
: 31 29 22 20 16 8
: 39 37 30 28 24 16 8
: 49 47 40 38 34 26 18 10
avatar
g*s
23 楼
public class FindSegments {
public static void main(String args[]) throws InterruptedException {
// List segs = Arrays.asList(new Integer[]{2, 3, 5, 7,
8, 10});
List segs = Arrays.asList(new Integer[]
{2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,2
6,28,
29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56});
long startTime = System.currentTimeMillis();
findSegs(segs);
System.out.printf("Total running time : %d ms",
System.currentTimeMillis() - startTime);
}
private static void findSegs(List segs) {
int t = getN(segs.size())-1;
Collections.sort(segs, Collections.reverseOrder());
HashMap leftSet = new HashMapInteger>();
for (Integer i : segs)
leftSet.put(i, leftSet.containsKey(i) ? leftSet.get(i) + 1 :
1);
HashMap markedMap = new HashMap
();
HashSet unmarkedSet = new HashSet();
for (int i = 1; i <= t; i++)
for (int j = i; j <= t; j++)
unmarkedSet.add(new Point(j, i));
mark(new Point(t, 1), segs.get(0), leftSet, markedMap,
unmarkedSet);
mark(new Point(t, 2), segs.get(1), leftSet, markedMap,
unmarkedSet);
dfs(leftSet, markedMap, unmarkedSet, t);
}
private static void dfs(HashMap leftSet,
HashMap markedMap, HashSet unmarkedSet, int t) {
if (unmarkedSet.isEmpty()) {
print(markedMap, t);
return;
}
Point p = unmarkedSet.iterator().next();
int downLimit = getDownLimit(markedMap, p);
int upLimit = getUpLimit(markedMap, p, t);
for (Integer tmp : leftSet.keySet()) {
if (tmp <= downLimit || tmp >= upLimit) continue;
HashMap localLeftSet = (HashMapInteger>) leftSet.clone();
HashMap localMarkedPoint = (HashMapInteger>) markedMap.clone();
HashSet localUnmarkedPoint = (HashSet)
unmarkedSet.clone();
if (!mark(p, tmp, localLeftSet, localMarkedPoint,
localUnmarkedPoint)) continue;
dfs(localLeftSet, localMarkedPoint, localUnmarkedPoint, t);
}
}
private static void print(HashMap markedMap, int t)
{
System.out.println("Answer: ");
for (int i = 1; i <= t; i++)
System.out.print(markedMap.get(new Point(i, i)) + "\t");
System.out.println();
for (int i = 1; i <= t; i++) {
for (int j = 1; j <= i; j++)
System.out.print(markedMap.get(new Point(i,j)) + "\t");
System.out.println();
}
}
private static int getUpLimit(HashMap markedMap,
Point p, int t) {
int max = Integer.MAX_VALUE;
for (int i = p.x + 1; i <= t; i++) {
Point checkPoint = new Point(i, p.y);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) < max)
max = markedMap.get(checkPoint);
}
for (int i = p.y - 1; i >= 1; i--) {
Point checkPoint = new Point(p.x, i);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) < max)
max = markedMap.get(checkPoint);
}
return max;
}
private static int getDownLimit(HashMap markedMap,
Point p) {
int min = Integer.MIN_VALUE;
for (int i = p.x - 1; i >= p.y; i--) {
Point checkPoint = new Point(i, p.y);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) > min)
min = markedMap.get(checkPoint);
}
for (int i = p.y + 1; i <= p.x; i++) {
Point checkPoint = new Point(p.x, i);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) > min)
min = markedMap.get(checkPoint);
}
return min;
}
private static boolean mark(Point point, Integer value,
HashMap leftSet, HashMap markedMap,
HashSet unmarkedSet) {
unmarkedSet.remove(point);
markedMap.put(point, value);
if (!leftSet.containsKey(value) || leftSet.get(value).equals(0))
return false;
if (leftSet.get(value) > 1)
leftSet.put(value, leftSet.get(value) - 1);
else leftSet.remove(value);
HashMap candidatePoint = new HashMapInteger>();
for (Map.Entry entry : markedMap.entrySet()) {
Point markedPoint = entry.getKey();
Point mappingPoint = getMappingPoint(point, markedPoint);
if (mappingPoint == null) continue;
Integer markedValue = entry.getValue();
Integer mValue = (markedPoint.x - markedPoint.y > point.x -
point.y) ? markedValue - value : value - markedValue;
candidatePoint.put(mappingPoint, mValue);
}
for (Map.Entry entry :
candidatePoint.entrySet()) {
Point mappingPoint = entry.getKey();
Integer mValue = entry.getValue();
if (unmarkedSet.contains(mappingPoint))
return mark(mappingPoint, mValue, leftSet, markedMap,
unmarkedSet);
else if (!markedMap.get(mappingPoint).equals(mValue))
return false;
}
return true;
}
private static Point getMappingPoint(Point point, Point markedPoint)
{
if ((point.x != markedPoint.x && point.y != markedPoint.y) ||
point.equals(markedPoint)) return null;
return (point.x == markedPoint.x) ?
new Point(Math.max(point.y, markedPoint.y) - 1,
Math.min(point.y, markedPoint.y)) :
new Point(Math.max(point.x, markedPoint.x),
Math.min(point.x, markedPoint.x) + 1);
}
private static int getN(int size) {
int i = 0;
for (; i * (i - 1) < 2 * size; i++) ;
if (i * (i - 1) != 2 * size) throw new RuntimeException("Wrong
Input");
return i;
}
}

【在 g**e 的大作中提到】
: 帅哥，贴个完整代码吧，谢谢
avatar
i*e
24 楼
My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A = {3,8,2,6,5,3}
Answer:
3 3 2
2 3 3
A = {7,10,16,9,3,6,2,8,5,14}
Answer:
2 5 3 6
6 3 5 2
A = {4,1,6,1,2,4,2,2,3,3}
Answer:
2 1 1 2
A = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5}
Answer:
1 1 2 2 3 3
3 3 2 2 1 1
#include
#include
#include
using namespace std;
typedef hash_map Hash;
typedef Hash::const_iterator HashIter;
// Decrement the key's value by one in the hash table.
// Key's value reaches 0 implies that the number is already
// selected (no longer available), so remove it from the table.
void decrementByOne(Hash &hash, int key) {
assert(hash[key] > 0);
hash[key]--;
if (hash[key] == 0)
hash.erase(key);
}
// Generates all combinations that will be used as the next combinations.
bool generatePartialSolution(int last, const vector &inCombinations, vector &outCombinations, Hash &hash) {
assert(outCombinations.empty());
int n = inCombinations.size();
for (int i = 0; i < n; i++) {
int sumPair = last + inCombinations[i];
if (hash[sumPair] == 0)
return false;
outCombinations.push_back(sumPair);
decrementByOne(hash, sumPair);
}
return true;
}
void solve(const Hash &hash, const vector &combinations, vector solution) {
// No more numbers to pick from, a new solution exists.
if (hash.empty()) {
int n = solution.size();
for (int i = 0; i < n; i++)
cout << solution[i] << " ";
cout << endl;
return;
}
for (HashIter iter = hash.begin(); iter != hash.end(); ++iter) {
int num = iter->first;
Hash hashCopy = hash;
solution.push_back(num);
decrementByOne(hashCopy, num);
vector nextCombinations;
if (generatePartialSolution(num, combinations, nextCombinations, hashCopy)) {
nextCombinations.push_back(num);
solve(hashCopy, nextCombinations, solution);
}

solution.pop_back();
}
}
void solve(int A[], int n) {
Hash hash;
for (int i = 0; i < n; i++) {
hash[A[i]]++;
}
solve(hash, vector(), vector());
}
int main() {
int A[] = {7,10,5,2,8,3};
//int A[] = {1,1,1,2,3,2};
//int A[] = {3,8,2,6,5,3};
//int A[] = {7,10,16,9,3,6,2,8,5,14};
//int A[] = {4,1,6,1,2,4,2,2,3,3};
//int A[] = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5};
/*int A[] = {2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,26,28,29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56};*/
int n = sizeof(A)/sizeof(int);
solve(A, n);
return 0;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
avatar
g*s
25 楼
因为对称性我把第二大元素固定在(t,2).
mark(new Point(t, 2), segs.get(1), leftSet, markedMap, unmarkedSet);
你算出的两个是对称的。

【在 i**********e 的大作中提到】
: My code found two valid answers for the following input in about 3 secs (
: obviously not as good as grass, but the algorithm is easier to code).
: Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
: 24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
: Answer:
: 2 7 2 4 8 8 8 10 7
: 7 10 8 8 8 4 2 7 2
: grass, can you explain whether your code generates the solution {7 10 8 8 8
: 4 2 7 2} ?
: Test cases:
avatar
t*g
26 楼
From the length of the array n, we can get the number of the milestones i.
And the i-1 smallest numbers should be the distances between the consecutive
milestones. The rest of the numbers are derived.
avatar
t*g
27 楼
O(nlgn)

consecutive

【在 t******g 的大作中提到】
: From the length of the array n, we can get the number of the milestones i.
: And the i-1 smallest numbers should be the distances between the consecutive
: milestones. The rest of the numbers are derived.
avatar
g*e
28 楼
wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a
milestone.

consecutive

【在 t******g 的大作中提到】
: From the length of the array n, we can get the number of the milestones i.
: And the i-1 smallest numbers should be the distances between the consecutive
: milestones. The rest of the numbers are derived.
avatar
t*g
29 楼
You're right.

【在 g**e 的大作中提到】
: wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a
: milestone.
:
: consecutive
avatar
g*y
30 楼
写了个简化版的：
public class Gloomyturkey implements IMilestone {
private int N;
private int M;
private int[] sequence;
private int[] answer;
private HashMap map;
private boolean[] used;
private int[] sum;
private boolean found;
public int[] findMilestones(int[] segs) {
M = segs.length;
sum = segs;
calcN();
initMap(segs);
used = new boolean[M];
found = false;
sequence = new int[N];
answer = new int[N];
assign(0, M-1);
assign(1, M-2);
dfs(2);
return found? answer : new int[0];
}
private void assign(int index, int from) {
sequence[index] = sum[from];
used[from] = true;
if (index > 0) answer[index-1] = sequence[index-1] - sequence[index];
if (index == N-1) answer[N-1] = sequence[N-1];
}
private void backtrack(int from) {
used[from] = false;
}
private void dfs(int len) {
if (len == N) return;
for (int i=M-3; i>=0; i--) {
if (used[i]) continue;
assign(len, i);
if (validate(len+1)) {
if (len+1 == N) found = true;
dfs(len+1);
if (found) break;
}
backtrack(i);
}
}
private boolean validate(int len) {
int size = len==N? len : len-1;
HashMap partial = new HashMap();
for (int i=1; i<=size; i++) {
for (int j=0; j<=size-i; j++) {
int S = 0;
for (int k=j; kS += answer[k];
}
int count = partial.get(S)!=null? partial.get(S) :
map.get(S)==null? 0 : map.get(S);
if (count == 0) return false;
partial.put(S, count-1);
}
}
return true;
}
private void calcN() {
N = (int) ((Math.sqrt(1 + 8*M) - 1) / 2 + 0.5);
}
private void initMap(int[] segs) {
map = new HashMap();
for (int seg : segs) {
if (map.get(seg) == null) {
map.put(seg, 0);
}
map.put(seg, map.get(seg)+1);
}
}
}
avatar
g*y
31 楼
不过这个版本好象还是没能通过ultimate performance test ->
2,4,4,5,5,6,6,6,8,8,
9,9,9,11,11,11,12,13,13,13,
13,13,13,14,16,16,17,17,17,17,
18,19,19,20,22,22,22,22,22,23,
25,25,26,26,26,26,27,27,28,28,
28,29,31,33,35,35,36,36,37,38,
38,38,39,39,39,40,41,42,42,43,
44,45,45,46,48,48,49,50,51,51,
51,51,53,53,55,55,57,58,59,59,
61,63,64,64,64,64,64,64,64,65,
66,68,70,71,72,73,73,75,76,77,
77,77,77,80,81,81,81,83,84,86,
86,86,89,90,90,90,91,92,92,94,
97,99,99,100,101,102,103,103,103,106,
107,108,109,109,111,112,112,114,115,116,
117,117,119,120,122,123,123,125,128,128,
128,128,129,130,132,134,134,136,137,139,
140,141,141,145,145,145,147,150,150,151,
152,154,156,156,158,162,163,167,169,173
Answer is:
4 13 5 4 13 6 8 12 16
9 13 13 13 16 9 2 6 5
6
已经算了5分钟了，还在运行。

【在 g**********y 的大作中提到】
: 写了个简化版的：
: public class Gloomyturkey implements IMilestone {
: private int N;
: private int M;
: private int[] sequence;
: private int[] answer;
: private HashMap map;
: private boolean[] used;
: private int[] sum;
: private boolean found;
avatar
g*y
32 楼
grass的code和test code都check-in进做题小组的subversion了，有兴趣且有闲的同学不妨挑战ultimate performance test.
avatar
g*s
33 楼
n=20
Answer:
4 13 5 4 13 6 8 12 16
9 13 13 13 16 9 2 6 5
6
4
17 13
22 18 5
26 22 9 4
39 35 22 17 13
45 41 28 23 19 6
53 49 36 31 27 14 8
65 61 48 43 39 26 20 12
81 77 64 59 55 42 36 28 16
90 86 73 68 64 51 45 37 25
9
103 99 86 81 77 64 58 50 38
22 13
116 112 99 94 90 77 71 63 51
35 26 13
129 125 112 107 103 90 84 76 64
48 39 26 13
145 141 128 123 119 106 100 92 80
64 55 42 29 16
154 150 137 132 128 115 109 101 89
73 64 51 38 25 9
156 152 139 134 130 117 111 103 91
75 66 53 40 27 11 2
162 158 145 140 136 123 117 109 97
81 72 59 46 33 17 8 6
167 163 150 145 141 128 122 114 102
86 77 64 51 38 22 13 11 5
173 169 156 151 147 134 128 120 108
92 83 70 57 44 28 19 17 11
6
Total running time : 69530 ms. dfs was called 115001 times

学不
妨挑战ultimate performance test.

【在 g**********y 的大作中提到】
: grass的code和test code都check-in进做题小组的subversion了，有兴趣且有闲的同学不妨挑战ultimate performance test.
avatar
g*y
34 楼
是你贴的code, 还是另外改进的？按前面贴的code, 我运行很久都没出来结果。

【在 g***s 的大作中提到】
: n=20
: Answer:
: 4 13 5 4 13 6 8 12 16
: 9 13 13 13 16 9 2 6 5
: 6
: 4
: 17 13
: 22 18 5
: 26 22 9 4
: 39 35 22 17 13
avatar
g*s
35 楼
your answer here should be wrong:
correct is:
4 13 5 4 13 6 8 12 16 9
13 13 13 16 9 2 6 5 6

【在 g**********y 的大作中提到】
: 不过这个版本好象还是没能通过ultimate performance test ->
: 2,4,4,5,5,6,6,6,8,8,
: 9,9,9,11,11,11,12,13,13,13,
: 13,13,13,14,16,16,17,17,17,17,
: 18,19,19,20,22,22,22,22,22,23,
: 25,25,26,26,26,26,27,27,28,28,
: 28,29,31,33,35,35,36,36,37,38,
: 38,38,39,39,39,40,41,42,42,43,
: 44,45,45,46,48,48,49,50,51,51,
: 51,51,53,53,55,55,57,58,59,59,
avatar
g*y
36 楼
是我剪贴是剪错了 :)

【在 g***s 的大作中提到】
: your answer here should be wrong:
: correct is:
: 4 13 5 4 13 6 8 12 16 9
: 13 13 13 16 9 2 6 5 6
avatar
g*s
37 楼
change two places:
1. Always fill the left-bottow first
2. Add ranges. pre-caculate the upLimit and lowLimit for all positions

【在 g**********y 的大作中提到】
: 是你贴的code, 还是另外改进的？按前面贴的code, 我运行很久都没出来结果。
avatar
s*y
38 楼
写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
using namespace std;
void DecreaseKey(hash_map& map, int key)
{
map[key]--;
if(map[key] <= 0)
map.erase(key);
}
int check_hash(hash_map& hash, int key) {
for(hash_map::iterator HashIter = hash.begin();HashIter != hash
.end();HashIter++ ) {
if (HashIter->first == key)
return 1;
}
return 0;
}
void Recursive_solve(hash_map& orig_hash,vector& input,vector<
int>& solutions, int index, int range, int length, bool& find)
{
if (find == true)
return;
hash_map hash = orig_hash;
//create a new hash table base on the latest result*/
for (int i = 0; i < solutions.size(); i++) {
int length = solutions[i];
DecreaseKey(hash, length);
for (int j = i + 1; j < solutions.size(); j++) {
length += solutions[j];
DecreaseKey(hash, length);
}
}
if (!hash[input[index]])
return;
/*try to put this one at the back*/
int back = input[index];
/*try to put this one at the front*/
int front = range - input[index];
/* check if the front and back are right */
if(!check_hash(hash,back) || !check_hash(hash, front))
return;
solutions.push_back(front);
//give a try to see if we find a solution ugly brute force */
hash_map try_hash = orig_hash;
solutions.push_back(back);
//update a new hash table base on the latest result*/
for (int i = 0; i < solutions.size(); i++) {
int length = solutions[i];
DecreaseKey(try_hash, length);
for (int j = i + 1; j < solutions.size(); j++) {
length += solutions[j];
DecreaseKey(try_hash, length);
}
}
if (try_hash.size() == 0) {
for (int i = 0; i < solutions.size(); i++)
cout << solutions[i] << endl;
find = true;
return;
} else {
solutions.pop_back();
}
for (int i = index-1; i >= 0; i--) {
vector temp_solutions = solutions;
Recursive_solve(orig_hash,input, temp_solutions, i, back,length,
find);
}
return;
}
void solve(vector& input) {
hash_map orig_hash;
bool find = false;
vector solutions;
sort(input.begin(), input.begin() + input.size());
for( int i = 0; i < input.size(); i++)
orig_hash[input[i]]++;
Recursive_solve(orig_hash, input,solutions,input.size()-2,input[input.
size()- 1],input[input.size()- 1], find);
}
int main() {
// int A[] = {7,10,5,2,8,3}; //work
//int A[] = {1,1,1,2,3,2}; //work
//int A[] = {3,8,2,6,5,3}; //work
// int A[] = {7,10,16,9,3,6,2,8,5,14}; //work
//int A[] = {4,1,6,1,2,4,2,2,3,3}; //work
int A[] = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5}; //work
//int A[] = {2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,
23,24,25,26,28,29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56}; //work
int n = sizeof(A)/sizeof(int);
vector input(A, n +A);
solve(input);
return 0;
}
avatar
g*y
39 楼
剪枝不够，你看grass 69秒结果就出来了。我也正在改。Subversion里还有好些比较大
的例子，从10个点到18个点，你可以试试。

server

【在 s*****y 的大作中提到】
: 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
: 样，但是我是算好了一个result，就return了，其他的就不算了。
: 速度还行，1337的几个例子都是10-20ms就算好了。
: 但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
: 算.....
: #include "stdafx.h"
: #include
: #include
: #include
: #include
avatar
h*t
40 楼
我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
的多了点，好在都是数。
time ./milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
real 1m5.827s
user 1m5.776s
sys 0m0.028s
假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
prev_pos之和。
基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
以及逐个累加prev_pos里milestone所得到的路程，都在a里，则认为该a[i]可以作为新
的milestone，进行递归。
#! /usr/bin/env python
import sys
DEBUG=1
def milestone(a, total, prev_pos):
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
#print total
return prev_pos + [total]
a.sort()
if a[0] == total:
#print a[0]
return prev_pos + [total]
prev_v = 0
for i in range(len(a) - 1):
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
aa = a[:]
aa.remove(a[i]) # remove first: to avoid b == a[i]
b = total - a[i]
if b in aa: # here use aa!
is_cand = 1
aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 - j]
# reverse
if c in aa:
aa.remove(c)
continue
is_cand = 0
break
if is_cand:
#print a[i]
tmp_pos = milestone(aa, b, prev_pos + [a[i]])
if len(tmp_pos) > 0:
return tmp_pos
return []
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 18,
20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38, 39, 40, 41, 45,
47, 47, 49, 54, 56]
a = [2,4,4,5,5,6,6,6,8,8, 9,9,9,11,11,11,12,13,13,13, 13,13,13,14,16,16,17,
17,17,17, 18,19,19,20,22,22,22,22,22,23, 25,25,26,26,26,26,27,27,28,28, 28,
29,31,33,35,35,36,36,37,38, 38,38,39,39,39,40,41,42,42,43, 44,45,45,46,48,48
,49,50,51,51, 51,51,53,53,55,55,57,58,59,59, 61,63,64,64,64,64,64,64,64,65,
66,68,70,71,72,73,73,75,76,77, 77,77,77,80,81,81,81,83,84,86, 86,86,89,90,90
,90,91,92,92,94, 97,99,99,100,101,102,103,103,103,106, 107,108,109,109,111,
112,112,114,115,116, 117,117,119,120,122,123,123,125,128,128, 128,128,129,
130,132,134,134,136,137,139, 140,141,141,145,145,145,147,150,150,151, 152,
154,156,156,158,162,163,167,169,173]
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])

【在 g***s 的大作中提到】
: s_1_1
: s_2_1 s_2_2
: s_3_1 s_3_2 s_3_3
: ...
: s_t_1 s_t_2 s_t_3 s_t_t
: t = n - 1 (n is the number of point)
: s(i,j) means the sum of lj to li (li is the what we want to output)
: e.g. s(2,4) = l2+l3+l4
: so, s(i,i) = li
: rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
avatar
s*y
41 楼
是算最长那个 66秒吗？

【在 h*****t 的大作中提到】
: 我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
: 的多了点，好在都是数。
: time ./milestone_pos.py
: [4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
: real 1m5.827s
: user 1m5.776s
: sys 0m0.028s
: 假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
: prev_pos之和。
: 基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
avatar
h*t
42 楼
是的，那个ultimate的

【在 s*****y 的大作中提到】
: 是算最长那个 66秒吗？
avatar
g*s
43 楼
再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
算出答案是26s，全部扫描完是32s。
Answer: (running time from start : 26396ms)
4 13 5 4 13 6 8 12 16 9 13 13 13 16
9 2 6 5 6
4
Total running time : 32052 ms, count of dfs=100342
avatar
h*t
44 楼
我的优化后是33秒，CPU是C2D T8100. 递归的次数是58539.
D:\download>d:\Python27\python.exe milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
cnt 58539
time 33.2269999981
Mod:
@@ -1,10 +1,15 @@
#! /usr/bin/env python
import sys
+import time
#DEBUG=1
DEBUG=0
+global cnt
+cnt = 0
def milestone(a, total, prev_pos):
+ global cnt
+ cnt += 1
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
@@ -16,17 +21,21 @@
#print a[0]
return prev_pos + [total]
prev_v = 0
- for i in range(len(a) - 1):
+ for i in range(len(a) - 1): # can safely disgard the last
one as b must exist.
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
- aa = a[:]
- aa.remove(a[i]) # remove first: to avoid b ==
a[i]
+ #aa = a[:]
+ #aa.remove(a[i]) # remove first: to
avoid b == a[i]
+ #if b in aa: # here use aa!
b = total - a[i]
- if b in aa: # here use aa!
+ if (b != a[i] and b in a) or (b == a[i] and i < len(a)
- 1 and a[i+1] == a[i]):
is_cand = 1
- aa.remove(b)
+ aa = a[:]
+ aa.remove(a[i])
+ if b != a[i]:
+ aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 -
j] # reverse
@@ -42,6 +51,7 @@
return tmp_pos
return []
+start_time=time.time()
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16,
17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38,
39, 40, 41, 45, 47, 47, 49, 54, 56]
@@ -49,3 +59,6 @@
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])
+print "cnt", cnt
+end_time=time.time()
+print "time", end_time - start_time

16


【在 g***s 的大作中提到】
: 再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
: 算出答案是26s，全部扫描完是32s。
: Answer: (running time from start : 26396ms)
: 4 13 5 4 13 6 8 12 16 9 13 13 13 16
: 9 2 6 5 6
: 4
: Total running time : 32052 ms, count of dfs=100342
avatar
b*r
45 楼
Run the ultimate example around 400 ms
here is my code
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167,
4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
14, 26, 42, 51, 64, 77, 90, 106, 115, 117, 123, 128, 8, 20, 36, 45, 58,
71, 84, 100, 109, 111, 117, 122, 12, 28, 37, 50, 63, 76, 92, 101, 103,
109, 114, 16, 25, 38, 51, 64, 80, 89, 91, 97, 102, 9, 22, 35, 48, 64,
73, 75, 81, 86, 13, 26, 39, 55, 64, 66, 72, 77, 13, 26, 42, 51, 53, 59,
64, 13, 29, 38, 40, 46, 51, 16, 25, 27, 33, 38, 9, 11, 17, 22, 2, 8, 13,
6, 11, 5,
406 ms
Recursion count 77985
[4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167]
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
, 9, 13, 13, 13, 16, 9, 2, 6, 5,
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FindMilestones {
private static int recurCount = 0;
/**
* @param args
*/
public static void main(String[] args) {
int[] points = generatePoints ();
print(points);
int[] dists = generateDists(points);
print(dists);
long start = System.currentTimeMillis();
List founded = findMilestones(dists);
long end = System.currentTimeMillis();
System.out.println((end-start)+" ms");
System.out.println("Recursion count "+recurCount);
Collections.sort(founded);
System.out.println(founded);
System.out.print(founded.get(0)+", ");
for (int i = 1; i < founded.size(); i++){
System.out.print(founded.get(i)-founded.get(i-
1));
System.out.print(", ");
}
System.out.println("");
}
private static List findMilestones(int[] dists){
int L = dists.length;
int N = (int)((1+Math.sqrt(1+8*L))/2);
Arrays.sort(dists);
List founded = new ArrayList ();
int max = dists[dists.length-1];
int[] map = new int[max+1];
for (int i = 0; i < map.length; i++){
map[i] = 0;
}
for (int i = 0; i < dists.length; i++){
map[dists[i]]++;
}
int cur = dists.length-1;
search (founded, dists, N, cur, map);
return founded;
}
private static boolean search (List founded, int[]
sortedDists, int N, int cur, int[] map){
recurCount++;
if (founded.size() == N-1){
return true;
}
//Optimize the lower bound of the index for the next
search nodes
int nextMax = sortedDists[cur];
int delta = 0;
if (founded.size() >=2){
delta = founded.get(0) -
founded.get(founded.size()-1);
}
int minPossible = nextMax-delta;
int lb = 0;
if (minPossible > 0){
lb = Arrays.binarySearch(sortedDists,
minPossible);
if (lb < 0){
lb = -1*lb;
}
}
int remaining = N-founded.size();

lb = Math.max(remaining*(remaining-1)/2-1, lb-1);
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}

private static boolean isCandidate (List founded, int
cand, int[] map){
boolean isCan = true;
if (map[cand] == 0){
return false;
}
for (int val : founded){
int diff = val-cand;
if (map[diff] == 0){
isCan = false;
break;
}
}
return isCan;
}


private static int[] generatePoints (){
//int[] diffs = {2, 3, 5, 7, 8, 10};
int[] diffs = {4,13,5,4,13, 6, 8, 12, 16,9, 13, 13, 13,
16, 9, 2, 6, 5};//{2, 7, 2, 4, 8, 8, 8, 10, 7};
print(diffs);
int[] points = new int[diffs.length+1];
points[0] = 0;
for (int i = 1; i < points.length; i++){
points[i] = points[i-1]+diffs[i-1];
}
return points;
}
private static int[] generateDists (int[] points){
int N = points.length;
int[] dists = new int[N*(N-1)/2];
int k = 0;
for (int i = 0; i < N-1; i++){
for (int j = i+1; j < N; j++){
dists[k++] = points[j] - points[i];
}
}
return dists;
}

private static void print (int[] arry){
for (int i = 0; i < arry.length; i++){
System.out.print(arry[i]+", ");
}
System.out.println("");
}
}

【在 h*****t 的大作中提到】
: 我的优化后是33秒，CPU是C2D T8100. 递归的次数是58539.
: D:\download>d:\Python27\python.exe milestone_pos.py
: [4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
: cnt 58539
: time 33.2269999981
: Mod:
: @@ -1,10 +1,15 @@
: #! /usr/bin/env python
: import sys
: +import time
avatar
b*r
46 楼
Can anyone try this example?
10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
the all dists is
1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
50, 51, 51, 53, 53, 54, 54, 54, 55, 55, 56, 56, 57, 57, 58, 59, 60, 61,
62, 62, 64, 64, 66, 66, 68, 69, 70, 72, 74, 74, 76, 76, 78, 80, 82, 84,
86, 94

an
random

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
h*t
47 楼
如果我理解的不错的话，map数据结构很精巧，在选择candidate时避免了数组的copy。
佩服！学
习了：）

156,
139,

【在 b**********r 的大作中提到】
: Run the ultimate example around 400 ms
: here is my code
: 4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
: 0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167,
: 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
: 152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
: 145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
: 145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
avatar
h*t
48 楼
This one is harder! Still running after 12 minutes...
Now got the results:
time ./milestone_pos.py
[8, 4, 2, 2, 2, 2, 10, 7, 1, 6, 9, 2, 4, 3, 7, 5, 10, 10]
cnt 1227534
time 859.453764915
real 14m19.570s
user 14m19.070s
sys 0m0.280s

8,
8,
15,
20,
25,
33,
41,
50,

【在 b**********r 的大作中提到】
: Can anyone try this example?
: 10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
: the all dists is
: 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
: 8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
: 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
: 20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
: 25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
: 35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
: 41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
avatar
s*y
49 楼
今天研究了一下你的算法，写了一个c++版本的，实在很巧妙，
grass的算法太高了，一般人肯定想不到，你的算法比较适合平常人。
你的算法其实关键的地方在于:
你一开始用这个方程式算出了有多少个点
int N = (int)((1+Math.sqrt(1+8*L))/2);
因为N 个点，总的数组大小就是N + (N-1) + .....+1； 只要解了这个方程式，就知道
点数了。
然后后面，你应用同样的方程式
lb = Math.max(remaining*(remaining-1)/2-1, lb-1);
去推断剩下你只需要search 数组里面的哪些点，这个范围一般就是1-2之内，从而大大
减少了search的空间
真得很巧妙，很容易学习。而且速度的确快，运行火鸡同学的终极测试大概只需要200-
300ms的样子。
但是你得code似乎有个小bug，算
{7,10,5,2,8,3}; 得出2,3,5
原因是因为你的founded 里面是10,8的时候，你check 5的时候没有先把map[5]-- ,但
是10- 5 = 5,所以后面return 了true.
所以我觉得你的function 一进去就应该map[cand]--， 然后return的时候map[cand]++；
private static boolean isCandidate (List founded, int cand, int
[] map){
boolean isCan = true;
if (map[cand] == 0){
return false;
}
for (int val : founded){
int diff = val-cand;
if (map[diff] == 0){
isCan = false;
break;
}
}
return isCan;

【在 b**********r 的大作中提到】
: Run the ultimate example around 400 ms
: here is my code
: 4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
: 0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167,
: 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
: 152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
: 145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
: 145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
avatar
d*l
50 楼
上面的方法都非常好，区别在于搜索的目标不一样。感觉上搜索点的话，要搜索的空间
小一些，数据大了应该更有优势。这道题当时自己想了半天也没什么思路，实在惭愧，
大家给出这么多好的思路，受益匪浅。
avatar
m*k
51 楼
23
8
why bother?
2 7 2 4 8 8 8 10 7
avatar
g*y
52 楼
赞思路！稍微改了一点，运行我给的那个ultimate test只递归了232次，0ms.
运行bravethinker后面那个例子用了723234次递归，运行了469ms。

【在 b**********r 的大作中提到】
: Run the ultimate example around 400 ms
: here is my code
: 4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
: 0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167,
: 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
: 152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
: 145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
: 145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
avatar
s*y
53 楼
can you share your optimization?

【在 g**********y 的大作中提到】
: 赞思路！稍微改了一点，运行我给的那个ultimate test只递归了232次，0ms.
: 运行bravethinker后面那个例子用了723234次递归，运行了469ms。
avatar
g*y
54 楼
主要是Bravethinker的code, 改动很小：
1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
2. founded不用ArrayList, 改成数组，速度更快。
3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
紧要，不怎么影响速度。
public class BraveThinker implements IMilestone {
private int dfsCount = 0;
public int[] findMilestones(int[] dists) {
long t0 = System.currentTimeMillis();

dfsCount = 0;

int L = dists.length;
int N = (int) ((Math.sqrt(1 + 8 * L) - 1) / 2);
int[] founded = new int[N+1];
int max = dists[dists.length - 1];
int[] map = new int[max + 1];
for (int i = 0; i < map.length; i++) {
map[i] = 0;
}
for (int i = 0; i < dists.length; i++) {
map[dists[i]]++;
}
int cur = dists.length - 1;
search(founded, 0, dists, N, cur, map);
int[] solution = new int[N];
for (int i=0; isolution[i] = founded[i] - founded[i+1];
}

long t1 = System.currentTimeMillis();
System.out.println("DFS count = " + dfsCount + ", takes " + (t1-t0)
+ "ms.");
return solution;
}
private boolean search(int[] founded, int len, int[] dists,
int N, int cur, int[] map) {
dfsCount++;
if (len == N) return true;
// Optimize the lower bound of the index for the next search nodes
int nextMax = dists[cur];
int delta = 0;
if (len >= 2) {
delta = founded[0] - founded[len-1];
}
int minPossible = nextMax - delta;
int lb = 0;
if (minPossible > 0) {
lb = Math.abs(Arrays.binarySearch(dists, minPossible));
}
int remaining = N - len;
lb = Math.max(remaining * (remaining + 1) / 2 - 1, lb - 1);
for (int i = cur; i >= lb; i--) {
int candidate = dists[i];
while (i>=lb && candidate==dists[i-1]) i--;

if (isCandidate(founded, len, candidate, map)) {
founded[len] = candidate;
if (search(founded, len+1, dists, N, i - 1, map)) {
return true;
}
map[candidate]++;
for (int j=0; jmap[founded[j] - candidate]++;
}
}
}
return false;
}
private boolean isCandidate(int[] founded, int len, int candidate
, int[] map) {
if (map[candidate] == 0) return false;
map[candidate]--;
for (int i=0; iif (map[founded[i]-candidate] == 0) { // revert
map[candidate]++;
for (int j=0; jmap[founded[j]-candidate]++;
}
return false;
}
else {
map[founded[i]-candidate]--;
}
}
return true;
}
}

【在 s*****y 的大作中提到】
: can you share your optimization?
avatar
s*y
55 楼
赞，我今晚也要try try。

【在 g**********y 的大作中提到】
: 主要是Bravethinker的code, 改动很小：
: 1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
: 2. founded不用ArrayList, 改成数组，速度更快。
: 3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
: 紧要，不怎么影响速度。
: public class BraveThinker implements IMilestone {
: private int dfsCount = 0;
: public int[] findMilestones(int[] dists) {
: long t0 = System.currentTimeMillis();
:
avatar
b*r
56 楼
Refined the search logic by calculate the lower bound more precisely
Now even this example can be done around 1 second
0, 10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
50, 51, 51, 53, 53, 54, 54, 54, 55, 55, 56, 56, 57, 57, 58, 59, 60, 61,
62, 62, 64, 64, 66, 66, 68, 69, 70, 72, 74, 74, 76, 76, 78, 80, 82, 84,
86, 94,
1094 ms
Recursion count 408249
[10, 20, 25, 32, 35, 39, 41, 50, 56, 57, 64, 74, 76, 78, 80, 82, 86, 94]
10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8,
following is the improved code
private static boolean search (List founded, int[]
sortedDists, int N, int cur, int[] map){
recurCount++;
if (founded.size() == N-1){
return true;
}
if (cur < 0){
return false;
}
int remaining = N-founded.size();

//The mini possible candidate would be the max of the
following 2 cases
//(1) The sum of the least remaining-2 intervals in the
map
//(2) or the remaining*(remaining-1)/2 -th smallest
value in the map

int order = remaining*(remaining-1)/2-1;
int minDist = -1; //The calculate order-th value int the
remaining map
int prevValid = 0;
int count = 0;
int minPossible = 0; //The sum of the least remaining-2
intervals in the map
for (int i = 0; i < map.length; i++){
if (order <= 0){
minDist = prevValid;
break;
}
if (map[i] > 0){
prevValid = i;
if (count < remaining-1){
minPossible += map[i]*i;
count += map[i];
if (count > remaining-1){
minPossible -= (count-
remaining+1)*i;
}
}
}
order -= map[i];
}

minDist = Math.max(minDist, minPossible);
int lb0 = Math.abs(Arrays.binarySearch(sortedDists,
minDist))-1;
int lb = Math.max(lb0, 0);
int prevVal = -1;
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (can == prevVal){
prevVal = can;
continue;
}
prevVal = can;
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}

【在 g**********y 的大作中提到】
: 主要是Bravethinker的code, 改动很小：
: 1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
: 2. founded不用ArrayList, 改成数组，速度更快。
: 3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
: 紧要，不怎么影响速度。
: public class BraveThinker implements IMilestone {
: private int dfsCount = 0;
: public int[] findMilestones(int[] dists) {
: long t0 = System.currentTimeMillis();
:
avatar
g*y
57 楼
这个计算我可以理解。
昨天的code, 仔细想一下，算low bound是：
delta = founded[0] - founded[last]
founded序列不外乎两种可能：
a[1]+a[2]+...a[n], a[1]+a[2]+..a[n-1], ..., a1+a2, a1
或
a[1]+a[2]+...a[n], a[2]+... + a[n], ... a[n-1]+a[n], a[n]
以第一种为例
delta = founded[0] - founded[k] = a[n]+...+a[n-k+1]
下面要找的数是a[1]+...+a[n-k-1]，也就是founded[k+1]
这两个数之间有什么必然联系？nextMax是一个比founded[k]小的下一个数。
计算里假设founded[k+1] >= nextMax - delta, 这个为什么？

【在 b**********r 的大作中提到】
: Refined the search logic by calculate the lower bound more precisely
: Now even this example can be done around 1 second
: 0, 10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
: 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
: 8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
: 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
: 20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
: 25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
: 35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
: 41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
avatar
g*y
58 楼
另外计算lower-bound, 只用remaining*(remaing-1)/2-1也行，效率差别不大，最复杂的那个例子，只要单条件，我机器上也只算了600ms； 加上额外条件，也要算469ms.
avatar
c*n
59 楼
有没有人同意题目说给的是 all the pairs of milestones 意思是
如果是 4 milestones的，那排序后的输入肯定是下面序列？
||||
a b c a+b b+c a+b+c
如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
avatar
g*y
60 楼
不是，你看前面例子就知道。

【在 c*******n 的大作中提到】
: 有没有人同意题目说给的是 all the pairs of milestones 意思是
: 如果是 4 milestones的，那排序后的输入肯定是下面序列？
: ||||
: a b c a+b b+c a+b+c
: 如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
avatar
c*n
61 楼

我看LZ的就符合..
其他牛人给的是更通用的解法，那些太难了
I just wanna make my life easier

【在 g**********y 的大作中提到】
: 不是，你看前面例子就知道。
avatar
g*y
62 楼
我们都希望life有个easy button, 但是没有 :)

【在 c*******n 的大作中提到】
:
: 我看LZ的就符合..
: 其他牛人给的是更通用的解法，那些太难了
: I just wanna make my life easier
avatar
c*n
63 楼

好吧，我希望题目中的all the pairs可以理解成这个easy button
不知道你是怎么理解的，莫非是 only some of pairs of milestone are given?
不过不管怎么说，严格要求自己还是没有错的

【在 g**********y 的大作中提到】
: 我们都希望life有个easy button, 但是没有 :)
avatar
g*y
64 楼
all the pairs就是all the pairs, n个点，当然就是n(n-1)/2个距离值。这个没什么
歧义。
问题是你不能指望这些值排序后符合什么规律，除了一两条显然的。

【在 c*******n 的大作中提到】
:
: 好吧，我希望题目中的all the pairs可以理解成这个easy button
: 不知道你是怎么理解的，莫非是 only some of pairs of milestone are given?
: 不过不管怎么说，严格要求自己还是没有错的
avatar
c*n
65 楼

哦，对
我举的4个milestones的例子还有可能是
a b a+b c b+c a+b+c 可能c > a+b
不过肯定有个规律是 a+b+c肯定是最大的一个（升序排序序列的最后一个），其他的不
能保证顺序。
另外，和为a+b+c的最长子序列一定是 a, b ,c
如果是这样，就转成我说的那个求“指定和”找“最长子序列”的问题

【在 g**********y 的大作中提到】
: all the pairs就是all the pairs, n个点，当然就是n(n-1)/2个距离值。这个没什么
: 歧义。
: 问题是你不能指望这些值排序后符合什么规律，除了一两条显然的。
avatar
r*g
66 楼
考个古，这道题有没有人愿意把grass的算法的讲解一下，关键是不清楚如果dfs下去失
败了之后怎么往回走。
这题好难，如果考我我准备直接放弃了。

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
C*l
67 楼
印象中LSAT有很多类似题目，不过是靠人自己分析的。
觉得这条可以计算出来，不用尝试的。
avatar
f*3
68 楼
i have an idea，not sure if it is correct:
1.先找到最小的2个，假设是a和b.
2.remove ab, a+b from the array
3. find the next smallest left in the array - c, which must be a stone to stone distance.
4. remove a+c, b+c, a+b+c from the array if the array contain those values.
5 find the next smallest value left in the array, repeat the process from 4,
until the value you got a+b+c+d+e...adds up to the biggest value in the
array.
avatar
h*3
69 楼
There is a straight roads with 'n' number of milestones. You are given an
array with the distance between all the pairs of milestones in some random
order. Find the position of milestones.
Example:
Consider a road with 4 milestones(a,b,c,d) :
a bcd
Distance between a and b = 3
Distance between a and c = 8
Distance between a and d = 10
Distance between b and c = 5
Distance between b and d = 7
Distance between c and d = 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3,5,2 or 2,5,3
avatar
m*2
70 楼
so, N is known when you run the program?
first step is obvious to sort it, and get the first and last position.
2) break the distance down to 2 segments so that
10 = segment1 + segment2 （any pair of segments will do)
3) repeat 2

an
random

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
g*e
71 楼
既然数组是随机的，怎么保证最后所有点的位置？比如你这例子，为什么不能输出5,3,
2?

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
g*y
72 楼
5, 3, 2产生的序列将会是：
5， 3， 2， 8， 5， 10
有两个5，跟条件不一样。

3,

【在 g**e 的大作中提到】
: 既然数组是随机的，怎么保证最后所有点的位置？比如你这例子，为什么不能输出5,3,
: 2?
avatar
g*y
73 楼
给的例子很容易解，推广到N好象不容易
我能观察到的，只有：
1. 最小的两个数，一定是两个相邻milestone的间距。但是不保证这两个间距之间有任
何关系。
2. 最大的数，是所有间距的和。
3. 第二大的数，是所有间距去掉min{头，尾}
题目就是把以下C(n,2)个数随机序排出来，要你恢复A1, ... An-1
A1, A2, A3, ... An-1
A1+A2, A2+A3, ... An-2+An-1
...
A1+A2+..An-2, A2+...+An-1
A1+A2+...An-1
等高手出来给个解。
avatar
g*e
74 楼
最小的两个一定是milestone，但是不一定相邻。op的例子就是。
还有最大的减去第二大的就是一个开头或末尾的milestone. 剩下的没想出来
感觉象解一个线性方程组……

【在 g**********y 的大作中提到】
: 给的例子很容易解，推广到N好象不容易
: 我能观察到的，只有：
: 1. 最小的两个数，一定是两个相邻milestone的间距。但是不保证这两个间距之间有任
: 何关系。
: 2. 最大的数，是所有间距的和。
: 3. 第二大的数，是所有间距去掉min{头，尾}
: 题目就是把以下C(n,2)个数随机序排出来，要你恢复A1, ... An-1
: A1, A2, A3, ... An-1
: A1+A2, A2+A3, ... An-2+An-1
: ...
avatar
g*y
75 楼
对，就是一个线性方程组，但是这个随机性很麻烦，一方面觉得可以解；另一方面，感
觉这个解不一定是唯一的, LZ举的情况两个解其实是一样的，就是反个方向。而且要找
一种普适的办法，好象不容易。

【在 g**e 的大作中提到】
: 最小的两个一定是milestone，但是不一定相邻。op的例子就是。
: 还有最大的减去第二大的就是一个开头或末尾的milestone. 剩下的没想出来
: 感觉象解一个线性方程组……
avatar
b*y
76 楼
感觉好像先找最大的距离
然后依次找第二大的距离，第三大的距离...

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
g*y
77 楼
第三大的距离不确定，以5个点为例，假设第二大的是a2+a3+a4, 也就是说 a4>a1,
第三大，既可以是a1+a2+a3, 也可以是a3+a4

【在 b*******y 的大作中提到】
: 感觉好像先找最大的距离
: 然后依次找第二大的距离，第三大的距离...
avatar
g*s
78 楼
s_1_1
s_2_1 s_2_2
s_3_1 s_3_2 s_3_3
...
s_t_1 s_t_2 s_t_3 s_t_t
t = n - 1 (n is the number of point)
s(i,j) means the sum of lj to li (li is the what we want to output)
e.g. s(2,4) = l2+l3+l4
so, s(i,i) = li
rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
s(t,1) = longest length
Use dfs and edge cut to fill the matrix, then output s(i,i) i=1 to t
for the sample:
7, 10, 5, 2, 8, 3
?
? ?
10 ? ?
1) try 8 in s(3,2)
?
? ?
10 8 ?
-> (based on rule1)
2
? ?
10 8 ?
1-1) try 7 in s(2,1)
2
7 ?
10 8 ?
-> (based on rule1, 10-7=3, 7-2=5)
2
7 5
10 8 3
1-2) try 5 in s(2,1),skip since 10-5 is not in the list
1-3) try 3 in s(2,1),skip since 3-2 is not in the list
2) try 7 in s(3,2)
...
the lots of edges will be cut, so it will not be slow.
avatar
g*s
79 楼
if it is a math question for n=4,
s_2_2 = sum(all) - s_3_1 * 3
in our sample, s_2_2 = 35 - 10 * 3 = 5
s_3_2 could only be 7 or 8, considering the matrix is symmetric,
let s_3_2 = 8, then s_1_1 = 10 - 8 = 2, s_2_1 = 5 + 2 = 7, s_3_3 = 8 - 5
=3
2
7 5
10 8 3

【在 g***s 的大作中提到】
: s_1_1
: s_2_1 s_2_2
: s_3_1 s_3_2 s_3_3
: ...
: s_t_1 s_t_2 s_t_3 s_t_t
: t = n - 1 (n is the number of point)
: s(i,j) means the sum of lj to li (li is the what we want to output)
: e.g. s(2,4) = l2+l3+l4
: so, s(i,i) = li
: rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
avatar
m*k
80 楼
假设有n个milestones,
1， 对给的array排序
2， 最大-第二大= 头or 尾
3， 建n-2个hashtable, 每个table是从 2个milstones的和到n-1个milestones的和
4, 在n-1个milestone的和的hashtable里找 sum= 最大-头or尾的milestones的组合
5, 在n-2个milestones的和的table里找 sum1=sum- 任意4里找出来的组合的一个
mileston
e,
继续这么找下去直到结束。。
不过忒麻烦了。。

【在 g**********y 的大作中提到】
: 对，就是一个线性方程组，但是这个随机性很麻烦，一方面觉得可以解；另一方面，感
: 觉这个解不一定是唯一的, LZ举的情况两个解其实是一样的，就是反个方向。而且要找
: 一种普适的办法，好象不容易。
avatar
g*y
81 楼
给个10个点的例子，谁写个DFS把它算出来 ->
2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23 24 25 26 28
29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56
手算出来也行 :)
avatar
g*e
82 楼
nb呀，不过这bar raiser也太高了，够不着
我也把这三角矩阵画出来了，就是没想到这茬

【在 g***s 的大作中提到】
: s_1_1
: s_2_1 s_2_2
: s_3_1 s_3_2 s_3_3
: ...
: s_t_1 s_t_2 s_t_3 s_t_t
: t = n - 1 (n is the number of point)
: s(i,j) means the sum of lj to li (li is the what we want to output)
: e.g. s(2,4) = l2+l3+l4
: so, s(i,i) = li
: rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
avatar
r*y
83 楼
sort firstly?

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
g*s
84 楼
Answer:
2 7 2 4 8 8 8 10 7
2
9 7
11 9 2
15 13 6 4
23 21 14 12 8
31 29 22 20 16 8
39 37 30 28 24 16 8
49 47 40 38 34 26 18 10
56 54 47 45 41 33 25 17 7
Total running time : 63 ms

28

【在 g**********y 的大作中提到】
: 给个10个点的例子，谁写个DFS把它算出来 ->
: 2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23 24 25 26 28
: 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56
: 手算出来也行 :)
avatar
g*y
85 楼
wow, that's very good performance.

【在 g***s 的大作中提到】
: Answer:
: 2 7 2 4 8 8 8 10 7
: 2
: 9 7
: 11 9 2
: 15 13 6 4
: 23 21 14 12 8
: 31 29 22 20 16 8
: 39 37 30 28 24 16 8
: 49 47 40 38 34 26 18 10
avatar
g*e
86 楼
帅哥，贴个完整代码吧，谢谢

【在 g***s 的大作中提到】
: Answer:
: 2 7 2 4 8 8 8 10 7
: 2
: 9 7
: 11 9 2
: 15 13 6 4
: 23 21 14 12 8
: 31 29 22 20 16 8
: 39 37 30 28 24 16 8
: 49 47 40 38 34 26 18 10
avatar
g*s
87 楼
public class FindSegments {
public static void main(String args[]) throws InterruptedException {
// List segs = Arrays.asList(new Integer[]{2, 3, 5, 7,
8, 10});
List segs = Arrays.asList(new Integer[]
{2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,2
6,28,
29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56});
long startTime = System.currentTimeMillis();
findSegs(segs);
System.out.printf("Total running time : %d ms",
System.currentTimeMillis() - startTime);
}
private static void findSegs(List segs) {
int t = getN(segs.size())-1;
Collections.sort(segs, Collections.reverseOrder());
HashMap leftSet = new HashMapInteger>();
for (Integer i : segs)
leftSet.put(i, leftSet.containsKey(i) ? leftSet.get(i) + 1 :
1);
HashMap markedMap = new HashMap
();
HashSet unmarkedSet = new HashSet();
for (int i = 1; i <= t; i++)
for (int j = i; j <= t; j++)
unmarkedSet.add(new Point(j, i));
mark(new Point(t, 1), segs.get(0), leftSet, markedMap,
unmarkedSet);
mark(new Point(t, 2), segs.get(1), leftSet, markedMap,
unmarkedSet);
dfs(leftSet, markedMap, unmarkedSet, t);
}
private static void dfs(HashMap leftSet,
HashMap markedMap, HashSet unmarkedSet, int t) {
if (unmarkedSet.isEmpty()) {
print(markedMap, t);
return;
}
Point p = unmarkedSet.iterator().next();
int downLimit = getDownLimit(markedMap, p);
int upLimit = getUpLimit(markedMap, p, t);
for (Integer tmp : leftSet.keySet()) {
if (tmp <= downLimit || tmp >= upLimit) continue;
HashMap localLeftSet = (HashMapInteger>) leftSet.clone();
HashMap localMarkedPoint = (HashMapInteger>) markedMap.clone();
HashSet localUnmarkedPoint = (HashSet)
unmarkedSet.clone();
if (!mark(p, tmp, localLeftSet, localMarkedPoint,
localUnmarkedPoint)) continue;
dfs(localLeftSet, localMarkedPoint, localUnmarkedPoint, t);
}
}
private static void print(HashMap markedMap, int t)
{
System.out.println("Answer: ");
for (int i = 1; i <= t; i++)
System.out.print(markedMap.get(new Point(i, i)) + "\t");
System.out.println();
for (int i = 1; i <= t; i++) {
for (int j = 1; j <= i; j++)
System.out.print(markedMap.get(new Point(i,j)) + "\t");
System.out.println();
}
}
private static int getUpLimit(HashMap markedMap,
Point p, int t) {
int max = Integer.MAX_VALUE;
for (int i = p.x + 1; i <= t; i++) {
Point checkPoint = new Point(i, p.y);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) < max)
max = markedMap.get(checkPoint);
}
for (int i = p.y - 1; i >= 1; i--) {
Point checkPoint = new Point(p.x, i);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) < max)
max = markedMap.get(checkPoint);
}
return max;
}
private static int getDownLimit(HashMap markedMap,
Point p) {
int min = Integer.MIN_VALUE;
for (int i = p.x - 1; i >= p.y; i--) {
Point checkPoint = new Point(i, p.y);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) > min)
min = markedMap.get(checkPoint);
}
for (int i = p.y + 1; i <= p.x; i++) {
Point checkPoint = new Point(p.x, i);
if (markedMap.containsKey(checkPoint) &&
markedMap.get(checkPoint) > min)
min = markedMap.get(checkPoint);
}
return min;
}
private static boolean mark(Point point, Integer value,
HashMap leftSet, HashMap markedMap,
HashSet unmarkedSet) {
unmarkedSet.remove(point);
markedMap.put(point, value);
if (!leftSet.containsKey(value) || leftSet.get(value).equals(0))
return false;
if (leftSet.get(value) > 1)
leftSet.put(value, leftSet.get(value) - 1);
else leftSet.remove(value);
HashMap candidatePoint = new HashMapInteger>();
for (Map.Entry entry : markedMap.entrySet()) {
Point markedPoint = entry.getKey();
Point mappingPoint = getMappingPoint(point, markedPoint);
if (mappingPoint == null) continue;
Integer markedValue = entry.getValue();
Integer mValue = (markedPoint.x - markedPoint.y > point.x -
point.y) ? markedValue - value : value - markedValue;
candidatePoint.put(mappingPoint, mValue);
}
for (Map.Entry entry :
candidatePoint.entrySet()) {
Point mappingPoint = entry.getKey();
Integer mValue = entry.getValue();
if (unmarkedSet.contains(mappingPoint))
return mark(mappingPoint, mValue, leftSet, markedMap,
unmarkedSet);
else if (!markedMap.get(mappingPoint).equals(mValue))
return false;
}
return true;
}
private static Point getMappingPoint(Point point, Point markedPoint)
{
if ((point.x != markedPoint.x && point.y != markedPoint.y) ||
point.equals(markedPoint)) return null;
return (point.x == markedPoint.x) ?
new Point(Math.max(point.y, markedPoint.y) - 1,
Math.min(point.y, markedPoint.y)) :
new Point(Math.max(point.x, markedPoint.x),
Math.min(point.x, markedPoint.x) + 1);
}
private static int getN(int size) {
int i = 0;
for (; i * (i - 1) < 2 * size; i++) ;
if (i * (i - 1) != 2 * size) throw new RuntimeException("Wrong
Input");
return i;
}
}

【在 g**e 的大作中提到】
: 帅哥，贴个完整代码吧，谢谢
avatar
i*e
88 楼
My code found two valid answers for the following input in about 3 secs (
obviously not as good as grass, but the algorithm is easier to code).
Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
Answer:
2 7 2 4 8 8 8 10 7
7 10 8 8 8 4 2 7 2
grass, can you explain whether your code generates the solution {7 10 8 8 8
4 2 7 2} ?
Test cases:
A = {7,10,5,2,8,3}
Answer:
2 5 3
3 5 2
A = {1,1,1,2,3,2}
Answer:
1 1 1
A = {3,8,2,6,5,3}
Answer:
3 3 2
2 3 3
A = {7,10,16,9,3,6,2,8,5,14}
Answer:
2 5 3 6
6 3 5 2
A = {4,1,6,1,2,4,2,2,3,3}
Answer:
2 1 1 2
A = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5}
Answer:
1 1 2 2 3 3
3 3 2 2 1 1
#include
#include
#include
using namespace std;
typedef hash_map Hash;
typedef Hash::const_iterator HashIter;
// Decrement the key's value by one in the hash table.
// Key's value reaches 0 implies that the number is already
// selected (no longer available), so remove it from the table.
void decrementByOne(Hash &hash, int key) {
assert(hash[key] > 0);
hash[key]--;
if (hash[key] == 0)
hash.erase(key);
}
// Generates all combinations that will be used as the next combinations.
bool generatePartialSolution(int last, const vector &inCombinations, vector &outCombinations, Hash &hash) {
assert(outCombinations.empty());
int n = inCombinations.size();
for (int i = 0; i < n; i++) {
int sumPair = last + inCombinations[i];
if (hash[sumPair] == 0)
return false;
outCombinations.push_back(sumPair);
decrementByOne(hash, sumPair);
}
return true;
}
void solve(const Hash &hash, const vector &combinations, vector solution) {
// No more numbers to pick from, a new solution exists.
if (hash.empty()) {
int n = solution.size();
for (int i = 0; i < n; i++)
cout << solution[i] << " ";
cout << endl;
return;
}
for (HashIter iter = hash.begin(); iter != hash.end(); ++iter) {
int num = iter->first;
Hash hashCopy = hash;
solution.push_back(num);
decrementByOne(hashCopy, num);
vector nextCombinations;
if (generatePartialSolution(num, combinations, nextCombinations, hashCopy)) {
nextCombinations.push_back(num);
solve(hashCopy, nextCombinations, solution);
}

solution.pop_back();
}
}
void solve(int A[], int n) {
Hash hash;
for (int i = 0; i < n; i++) {
hash[A[i]]++;
}
solve(hash, vector(), vector());
}
int main() {
int A[] = {7,10,5,2,8,3};
//int A[] = {1,1,1,2,3,2};
//int A[] = {3,8,2,6,5,3};
//int A[] = {7,10,16,9,3,6,2,8,5,14};
//int A[] = {4,1,6,1,2,4,2,2,3,3};
//int A[] = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5};
/*int A[] = {2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,23,24,25,26,28,29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56};*/
int n = sizeof(A)/sizeof(int);
solve(A, n);
return 0;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
avatar
g*s
89 楼
因为对称性我把第二大元素固定在(t,2).
mark(new Point(t, 2), segs.get(1), leftSet, markedMap, unmarkedSet);
你算出的两个是对称的。

【在 i**********e 的大作中提到】
: My code found two valid answers for the following input in about 3 secs (
: obviously not as good as grass, but the algorithm is easier to code).
: Input, A = {2 2 4 6 7 7 8 8 8 9 9 10 11 12 13 14 15 16 16 17 18 20 21 22 23
: 24 25 26 28 29 30 31 33 34 37 38 39 40 41 45 47 47 49 54 56 }
: Answer:
: 2 7 2 4 8 8 8 10 7
: 7 10 8 8 8 4 2 7 2
: grass, can you explain whether your code generates the solution {7 10 8 8 8
: 4 2 7 2} ?
: Test cases:
avatar
t*g
90 楼
From the length of the array n, we can get the number of the milestones i.
And the i-1 smallest numbers should be the distances between the consecutive
milestones. The rest of the numbers are derived.
avatar
t*g
91 楼
O(nlgn)

consecutive

【在 t******g 的大作中提到】
: From the length of the array n, we can get the number of the milestones i.
: And the i-1 smallest numbers should be the distances between the consecutive
: milestones. The rest of the numbers are derived.
avatar
g*e
92 楼
wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a
milestone.

consecutive

【在 t******g 的大作中提到】
: From the length of the array n, we can get the number of the milestones i.
: And the i-1 smallest numbers should be the distances between the consecutive
: milestones. The rest of the numbers are derived.
avatar
t*g
93 楼
You're right.

【在 g**e 的大作中提到】
: wrong. consider 1, 1, 3. you will have 1, 1, 2, 3, 4, 5. And 2 is not a
: milestone.
:
: consecutive
avatar
g*y
94 楼
写了个简化版的：
public class Gloomyturkey implements IMilestone {
private int N;
private int M;
private int[] sequence;
private int[] answer;
private HashMap map;
private boolean[] used;
private int[] sum;
private boolean found;
public int[] findMilestones(int[] segs) {
M = segs.length;
sum = segs;
calcN();
initMap(segs);
used = new boolean[M];
found = false;
sequence = new int[N];
answer = new int[N];
assign(0, M-1);
assign(1, M-2);
dfs(2);
return found? answer : new int[0];
}
private void assign(int index, int from) {
sequence[index] = sum[from];
used[from] = true;
if (index > 0) answer[index-1] = sequence[index-1] - sequence[index];
if (index == N-1) answer[N-1] = sequence[N-1];
}
private void backtrack(int from) {
used[from] = false;
}
private void dfs(int len) {
if (len == N) return;
for (int i=M-3; i>=0; i--) {
if (used[i]) continue;
assign(len, i);
if (validate(len+1)) {
if (len+1 == N) found = true;
dfs(len+1);
if (found) break;
}
backtrack(i);
}
}
private boolean validate(int len) {
int size = len==N? len : len-1;
HashMap partial = new HashMap();
for (int i=1; i<=size; i++) {
for (int j=0; j<=size-i; j++) {
int S = 0;
for (int k=j; kS += answer[k];
}
int count = partial.get(S)!=null? partial.get(S) :
map.get(S)==null? 0 : map.get(S);
if (count == 0) return false;
partial.put(S, count-1);
}
}
return true;
}
private void calcN() {
N = (int) ((Math.sqrt(1 + 8*M) - 1) / 2 + 0.5);
}
private void initMap(int[] segs) {
map = new HashMap();
for (int seg : segs) {
if (map.get(seg) == null) {
map.put(seg, 0);
}
map.put(seg, map.get(seg)+1);
}
}
}
avatar
g*y
95 楼
不过这个版本好象还是没能通过ultimate performance test ->
2,4,4,5,5,6,6,6,8,8,
9,9,9,11,11,11,12,13,13,13,
13,13,13,14,16,16,17,17,17,17,
18,19,19,20,22,22,22,22,22,23,
25,25,26,26,26,26,27,27,28,28,
28,29,31,33,35,35,36,36,37,38,
38,38,39,39,39,40,41,42,42,43,
44,45,45,46,48,48,49,50,51,51,
51,51,53,53,55,55,57,58,59,59,
61,63,64,64,64,64,64,64,64,65,
66,68,70,71,72,73,73,75,76,77,
77,77,77,80,81,81,81,83,84,86,
86,86,89,90,90,90,91,92,92,94,
97,99,99,100,101,102,103,103,103,106,
107,108,109,109,111,112,112,114,115,116,
117,117,119,120,122,123,123,125,128,128,
128,128,129,130,132,134,134,136,137,139,
140,141,141,145,145,145,147,150,150,151,
152,154,156,156,158,162,163,167,169,173
Answer is:
4 13 5 4 13 6 8 12 16
9 13 13 13 16 9 2 6 5
6
已经算了5分钟了，还在运行。

【在 g**********y 的大作中提到】
: 写了个简化版的：
: public class Gloomyturkey implements IMilestone {
: private int N;
: private int M;
: private int[] sequence;
: private int[] answer;
: private HashMap map;
: private boolean[] used;
: private int[] sum;
: private boolean found;
avatar
g*y
96 楼
grass的code和test code都check-in进做题小组的subversion了，有兴趣且有闲的同学不妨挑战ultimate performance test.
avatar
g*s
97 楼
n=20
Answer:
4 13 5 4 13 6 8 12 16
9 13 13 13 16 9 2 6 5
6
4
17 13
22 18 5
26 22 9 4
39 35 22 17 13
45 41 28 23 19 6
53 49 36 31 27 14 8
65 61 48 43 39 26 20 12
81 77 64 59 55 42 36 28 16
90 86 73 68 64 51 45 37 25
9
103 99 86 81 77 64 58 50 38
22 13
116 112 99 94 90 77 71 63 51
35 26 13
129 125 112 107 103 90 84 76 64
48 39 26 13
145 141 128 123 119 106 100 92 80
64 55 42 29 16
154 150 137 132 128 115 109 101 89
73 64 51 38 25 9
156 152 139 134 130 117 111 103 91
75 66 53 40 27 11 2
162 158 145 140 136 123 117 109 97
81 72 59 46 33 17 8 6
167 163 150 145 141 128 122 114 102
86 77 64 51 38 22 13 11 5
173 169 156 151 147 134 128 120 108
92 83 70 57 44 28 19 17 11
6
Total running time : 69530 ms. dfs was called 115001 times

学不
妨挑战ultimate performance test.

【在 g**********y 的大作中提到】
: grass的code和test code都check-in进做题小组的subversion了，有兴趣且有闲的同学不妨挑战ultimate performance test.
avatar
g*y
98 楼
是你贴的code, 还是另外改进的？按前面贴的code, 我运行很久都没出来结果。

【在 g***s 的大作中提到】
: n=20
: Answer:
: 4 13 5 4 13 6 8 12 16
: 9 13 13 13 16 9 2 6 5
: 6
: 4
: 17 13
: 22 18 5
: 26 22 9 4
: 39 35 22 17 13
avatar
g*s
99 楼
your answer here should be wrong:
correct is:
4 13 5 4 13 6 8 12 16 9
13 13 13 16 9 2 6 5 6

【在 g**********y 的大作中提到】
: 不过这个版本好象还是没能通过ultimate performance test ->
: 2,4,4,5,5,6,6,6,8,8,
: 9,9,9,11,11,11,12,13,13,13,
: 13,13,13,14,16,16,17,17,17,17,
: 18,19,19,20,22,22,22,22,22,23,
: 25,25,26,26,26,26,27,27,28,28,
: 28,29,31,33,35,35,36,36,37,38,
: 38,38,39,39,39,40,41,42,42,43,
: 44,45,45,46,48,48,49,50,51,51,
: 51,51,53,53,55,55,57,58,59,59,
avatar
g*y
100 楼
是我剪贴是剪错了 :)

【在 g***s 的大作中提到】
: your answer here should be wrong:
: correct is:
: 4 13 5 4 13 6 8 12 16 9
: 13 13 13 16 9 2 6 5 6
avatar
g*s
101 楼
change two places:
1. Always fill the left-bottow first
2. Add ranges. pre-caculate the upLimit and lowLimit for all positions

【在 g**********y 的大作中提到】
: 是你贴的code, 还是另外改进的？按前面贴的code, 我运行很久都没出来结果。
avatar
s*y
102 楼
写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
样，但是我是算好了一个result，就return了，其他的就不算了。
速度还行，1337的几个例子都是10-20ms就算好了。
但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
算.....
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
using namespace std;
void DecreaseKey(hash_map& map, int key)
{
map[key]--;
if(map[key] <= 0)
map.erase(key);
}
int check_hash(hash_map& hash, int key) {
for(hash_map::iterator HashIter = hash.begin();HashIter != hash
.end();HashIter++ ) {
if (HashIter->first == key)
return 1;
}
return 0;
}
void Recursive_solve(hash_map& orig_hash,vector& input,vector<
int>& solutions, int index, int range, int length, bool& find)
{
if (find == true)
return;
hash_map hash = orig_hash;
//create a new hash table base on the latest result*/
for (int i = 0; i < solutions.size(); i++) {
int length = solutions[i];
DecreaseKey(hash, length);
for (int j = i + 1; j < solutions.size(); j++) {
length += solutions[j];
DecreaseKey(hash, length);
}
}
if (!hash[input[index]])
return;
/*try to put this one at the back*/
int back = input[index];
/*try to put this one at the front*/
int front = range - input[index];
/* check if the front and back are right */
if(!check_hash(hash,back) || !check_hash(hash, front))
return;
solutions.push_back(front);
//give a try to see if we find a solution ugly brute force */
hash_map try_hash = orig_hash;
solutions.push_back(back);
//update a new hash table base on the latest result*/
for (int i = 0; i < solutions.size(); i++) {
int length = solutions[i];
DecreaseKey(try_hash, length);
for (int j = i + 1; j < solutions.size(); j++) {
length += solutions[j];
DecreaseKey(try_hash, length);
}
}
if (try_hash.size() == 0) {
for (int i = 0; i < solutions.size(); i++)
cout << solutions[i] << endl;
find = true;
return;
} else {
solutions.pop_back();
}
for (int i = index-1; i >= 0; i--) {
vector temp_solutions = solutions;
Recursive_solve(orig_hash,input, temp_solutions, i, back,length,
find);
}
return;
}
void solve(vector& input) {
hash_map orig_hash;
bool find = false;
vector solutions;
sort(input.begin(), input.begin() + input.size());
for( int i = 0; i < input.size(); i++)
orig_hash[input[i]]++;
Recursive_solve(orig_hash, input,solutions,input.size()-2,input[input.
size()- 1],input[input.size()- 1], find);
}
int main() {
// int A[] = {7,10,5,2,8,3}; //work
//int A[] = {1,1,1,2,3,2}; //work
//int A[] = {3,8,2,6,5,3}; //work
// int A[] = {7,10,16,9,3,6,2,8,5,14}; //work
//int A[] = {4,1,6,1,2,4,2,2,3,3}; //work
int A[] = {2,4,12,9,6,1,3,11,1,8,5,10,4,2,7,2,3,3,6,8,5}; //work
//int A[] = {2,2,4,6,7,7,8,8,8,9,9,10,11,12,13,14,15,16,16,17,18,20,21,22,
23,24,25,26,28,29,30,31,33,34,37,38,39,40,41,45,47,47,49,54,56}; //work
int n = sizeof(A)/sizeof(int);
vector input(A, n +A);
solve(input);
return 0;
}
avatar
g*y
103 楼
剪枝不够，你看grass 69秒结果就出来了。我也正在改。Subversion里还有好些比较大
的例子，从10个点到18个点，你可以试试。

server

【在 s*****y 的大作中提到】
: 写了好几个小时，终于用差不多brute force得解了，算了1337的几个例子，全部都一
: 样，但是我是算好了一个result，就return了，其他的就不算了。
: 速度还行，1337的几个例子都是10-20ms就算好了。
: 但是算火鸡同学的那个终极测试，真的是算了10分钟还没有好，难道要用公司的server
: 算.....
: #include "stdafx.h"
: #include
: #include
: #include
: #include
avatar
h*t
104 楼
我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
的多了点，好在都是数。
time ./milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
real 1m5.827s
user 1m5.776s
sys 0m0.028s
假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
prev_pos之和。
基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
以及逐个累加prev_pos里milestone所得到的路程，都在a里，则认为该a[i]可以作为新
的milestone，进行递归。
#! /usr/bin/env python
import sys
DEBUG=1
def milestone(a, total, prev_pos):
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
#print total
return prev_pos + [total]
a.sort()
if a[0] == total:
#print a[0]
return prev_pos + [total]
prev_v = 0
for i in range(len(a) - 1):
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
aa = a[:]
aa.remove(a[i]) # remove first: to avoid b == a[i]
b = total - a[i]
if b in aa: # here use aa!
is_cand = 1
aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 - j]
# reverse
if c in aa:
aa.remove(c)
continue
is_cand = 0
break
if is_cand:
#print a[i]
tmp_pos = milestone(aa, b, prev_pos + [a[i]])
if len(tmp_pos) > 0:
return tmp_pos
return []
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 18,
20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38, 39, 40, 41, 45,
47, 47, 49, 54, 56]
a = [2,4,4,5,5,6,6,6,8,8, 9,9,9,11,11,11,12,13,13,13, 13,13,13,14,16,16,17,
17,17,17, 18,19,19,20,22,22,22,22,22,23, 25,25,26,26,26,26,27,27,28,28, 28,
29,31,33,35,35,36,36,37,38, 38,38,39,39,39,40,41,42,42,43, 44,45,45,46,48,48
,49,50,51,51, 51,51,53,53,55,55,57,58,59,59, 61,63,64,64,64,64,64,64,64,65,
66,68,70,71,72,73,73,75,76,77, 77,77,77,80,81,81,81,83,84,86, 86,86,89,90,90
,90,91,92,92,94, 97,99,99,100,101,102,103,103,103,106, 107,108,109,109,111,
112,112,114,115,116, 117,117,119,120,122,123,123,125,128,128, 128,128,129,
130,132,134,134,136,137,139, 140,141,141,145,145,145,147,150,150,151, 152,
154,156,156,158,162,163,167,169,173]
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])

【在 g***s 的大作中提到】
: s_1_1
: s_2_1 s_2_2
: s_3_1 s_3_2 s_3_3
: ...
: s_t_1 s_t_2 s_t_3 s_t_t
: t = n - 1 (n is the number of point)
: s(i,j) means the sum of lj to li (li is the what we want to output)
: e.g. s(2,4) = l2+l3+l4
: so, s(i,i) = li
: rule1: s(i,j) = s(i-k,j) + s(i,i-k+1)
avatar
s*y
105 楼
是算最长那个 66秒吗？

【在 h*****t 的大作中提到】
: 我想到一个递归解法，用python写的，代码比较简单。速度是66秒，不过递归空间会用
: 的多了点，好在都是数。
: time ./milestone_pos.py
: [4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
: real 1m5.827s
: user 1m5.776s
: sys 0m0.028s
: 假设Input: a 是数列，prev_pos是已经知道的milestone数组，total是总路程减去
: prev_pos之和。
: 基本思路是从a里小的数扫描起，如果扫描的数a[i]满足条件：a[i], total - a[i],
avatar
h*t
106 楼
是的，那个ultimate的

【在 s*****y 的大作中提到】
: 是算最长那个 66秒吗？
avatar
g*s
107 楼
再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
算出答案是26s，全部扫描完是32s。
Answer: (running time from start : 26396ms)
4 13 5 4 13 6 8 12 16 9 13 13 13 16
9 2 6 5 6
4
Total running time : 32052 ms, count of dfs=100342
avatar
h*t
108 楼
我的优化后是33秒，CPU是C2D T8100. 递归的次数是58539.
D:\download>d:\Python27\python.exe milestone_pos.py
[4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
cnt 58539
time 33.2269999981
Mod:
@@ -1,10 +1,15 @@
#! /usr/bin/env python
import sys
+import time
#DEBUG=1
DEBUG=0
+global cnt
+cnt = 0
def milestone(a, total, prev_pos):
+ global cnt
+ cnt += 1
if DEBUG: print "#", prev_pos, total, a
if len(a) <= 0:
@@ -16,17 +21,21 @@
#print a[0]
return prev_pos + [total]
prev_v = 0
- for i in range(len(a) - 1):
+ for i in range(len(a) - 1): # can safely disgard the last
one as b must exist.
if a[i] == prev_v:
continue # ignore the same value
prev_v = a[i]
- aa = a[:]
- aa.remove(a[i]) # remove first: to avoid b ==
a[i]
+ #aa = a[:]
+ #aa.remove(a[i]) # remove first: to
avoid b == a[i]
+ #if b in aa: # here use aa!
b = total - a[i]
- if b in aa: # here use aa!
+ if (b != a[i] and b in a) or (b == a[i] and i < len(a)
- 1 and a[i+1] == a[i]):
is_cand = 1
- aa.remove(b)
+ aa = a[:]
+ aa.remove(a[i])
+ if b != a[i]:
+ aa.remove(b)
c = a[i]
for j in range(len(prev_pos)):
c = c + prev_pos[len(prev_pos) - 1 -
j] # reverse
@@ -42,6 +51,7 @@
return tmp_pos
return []
+start_time=time.time()
#a=[5,1,4,6,10,5]
a=[7, 10, 5, 2, 8, 3]
a=[2, 2, 4, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 16,
17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 37, 38,
39, 40, 41, 45, 47, 47, 49, 54, 56]
@@ -49,3 +59,6 @@
max_a=max(a)
a.remove(max_a)
print milestone(a, max_a, [])
+print "cnt", cnt
+end_time=time.time()
+print "time", end_time - start_time

16


【在 g***s 的大作中提到】
: 再删除了一些不必要的clone，速度提高了近3倍（家里电脑，没改前是90秒左右）
: 算出答案是26s，全部扫描完是32s。
: Answer: (running time from start : 26396ms)
: 4 13 5 4 13 6 8 12 16 9 13 13 13 16
: 9 2 6 5 6
: 4
: Total running time : 32052 ms, count of dfs=100342
avatar
b*r
109 楼
Run the ultimate example around 400 ms
here is my code
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167,
4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
14, 26, 42, 51, 64, 77, 90, 106, 115, 117, 123, 128, 8, 20, 36, 45, 58,
71, 84, 100, 109, 111, 117, 122, 12, 28, 37, 50, 63, 76, 92, 101, 103,
109, 114, 16, 25, 38, 51, 64, 80, 89, 91, 97, 102, 9, 22, 35, 48, 64,
73, 75, 81, 86, 13, 26, 39, 55, 64, 66, 72, 77, 13, 26, 42, 51, 53, 59,
64, 13, 29, 38, 40, 46, 51, 16, 25, 27, 33, 38, 9, 11, 17, 22, 2, 8, 13,
6, 11, 5,
406 ms
Recursion count 77985
[4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167]
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
, 9, 13, 13, 13, 16, 9, 2, 6, 5,
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FindMilestones {
private static int recurCount = 0;
/**
* @param args
*/
public static void main(String[] args) {
int[] points = generatePoints ();
print(points);
int[] dists = generateDists(points);
print(dists);
long start = System.currentTimeMillis();
List founded = findMilestones(dists);
long end = System.currentTimeMillis();
System.out.println((end-start)+" ms");
System.out.println("Recursion count "+recurCount);
Collections.sort(founded);
System.out.println(founded);
System.out.print(founded.get(0)+", ");
for (int i = 1; i < founded.size(); i++){
System.out.print(founded.get(i)-founded.get(i-
1));
System.out.print(", ");
}
System.out.println("");
}
private static List findMilestones(int[] dists){
int L = dists.length;
int N = (int)((1+Math.sqrt(1+8*L))/2);
Arrays.sort(dists);
List founded = new ArrayList ();
int max = dists[dists.length-1];
int[] map = new int[max+1];
for (int i = 0; i < map.length; i++){
map[i] = 0;
}
for (int i = 0; i < dists.length; i++){
map[dists[i]]++;
}
int cur = dists.length-1;
search (founded, dists, N, cur, map);
return founded;
}
private static boolean search (List founded, int[]
sortedDists, int N, int cur, int[] map){
recurCount++;
if (founded.size() == N-1){
return true;
}
//Optimize the lower bound of the index for the next
search nodes
int nextMax = sortedDists[cur];
int delta = 0;
if (founded.size() >=2){
delta = founded.get(0) -
founded.get(founded.size()-1);
}
int minPossible = nextMax-delta;
int lb = 0;
if (minPossible > 0){
lb = Arrays.binarySearch(sortedDists,
minPossible);
if (lb < 0){
lb = -1*lb;
}
}
int remaining = N-founded.size();

lb = Math.max(remaining*(remaining-1)/2-1, lb-1);
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}

private static boolean isCandidate (List founded, int
cand, int[] map){
boolean isCan = true;
if (map[cand] == 0){
return false;
}
for (int val : founded){
int diff = val-cand;
if (map[diff] == 0){
isCan = false;
break;
}
}
return isCan;
}


private static int[] generatePoints (){
//int[] diffs = {2, 3, 5, 7, 8, 10};
int[] diffs = {4,13,5,4,13, 6, 8, 12, 16,9, 13, 13, 13,
16, 9, 2, 6, 5};//{2, 7, 2, 4, 8, 8, 8, 10, 7};
print(diffs);
int[] points = new int[diffs.length+1];
points[0] = 0;
for (int i = 1; i < points.length; i++){
points[i] = points[i-1]+diffs[i-1];
}
return points;
}
private static int[] generateDists (int[] points){
int N = points.length;
int[] dists = new int[N*(N-1)/2];
int k = 0;
for (int i = 0; i < N-1; i++){
for (int j = i+1; j < N; j++){
dists[k++] = points[j] - points[i];
}
}
return dists;
}

private static void print (int[] arry){
for (int i = 0; i < arry.length; i++){
System.out.print(arry[i]+", ");
}
System.out.println("");
}
}

【在 h*****t 的大作中提到】
: 我的优化后是33秒，CPU是C2D T8100. 递归的次数是58539.
: D:\download>d:\Python27\python.exe milestone_pos.py
: [4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5, 6]
: cnt 58539
: time 33.2269999981
: Mod:
: @@ -1,10 +1,15 @@
: #! /usr/bin/env python
: import sys
: +import time
avatar
b*r
110 楼
Can anyone try this example?
10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
the all dists is
1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
50, 51, 51, 53, 53, 54, 54, 54, 55, 55, 56, 56, 57, 57, 58, 59, 60, 61,
62, 62, 64, 64, 66, 66, 68, 69, 70, 72, 74, 74, 76, 76, 78, 80, 82, 84,
86, 94

an
random

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
h*t
111 楼
如果我理解的不错的话，map数据结构很精巧，在选择candidate时避免了数组的copy。
佩服！学
习了：）

156,
139,

【在 b**********r 的大作中提到】
: Run the ultimate example around 400 ms
: here is my code
: 4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
: 0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167,
: 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
: 152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
: 145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
: 145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
avatar
h*t
112 楼
This one is harder! Still running after 12 minutes...
Now got the results:
time ./milestone_pos.py
[8, 4, 2, 2, 2, 2, 10, 7, 1, 6, 9, 2, 4, 3, 7, 5, 10, 10]
cnt 1227534
time 859.453764915
real 14m19.570s
user 14m19.070s
sys 0m0.280s

8,
8,
15,
20,
25,
33,
41,
50,

【在 b**********r 的大作中提到】
: Can anyone try this example?
: 10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
: the all dists is
: 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
: 8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
: 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
: 20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
: 25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
: 35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
: 41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
avatar
s*y
113 楼
今天研究了一下你的算法，写了一个c++版本的，实在很巧妙，
grass的算法太高了，一般人肯定想不到，你的算法比较适合平常人。
你的算法其实关键的地方在于:
你一开始用这个方程式算出了有多少个点
int N = (int)((1+Math.sqrt(1+8*L))/2);
因为N 个点，总的数组大小就是N + (N-1) + .....+1； 只要解了这个方程式，就知道
点数了。
然后后面，你应用同样的方程式
lb = Math.max(remaining*(remaining-1)/2-1, lb-1);
去推断剩下你只需要search 数组里面的哪些点，这个范围一般就是1-2之内，从而大大
减少了search的空间
真得很巧妙，很容易学习。而且速度的确快，运行火鸡同学的终极测试大概只需要200-
300ms的样子。
但是你得code似乎有个小bug，算
{7,10,5,2,8,3}; 得出2,3,5
原因是因为你的founded 里面是10,8的时候，你check 5的时候没有先把map[5]-- ,但
是10- 5 = 5,所以后面return 了true.
所以我觉得你的function 一进去就应该map[cand]--， 然后return的时候map[cand]++；
private static boolean isCandidate (List founded, int cand, int
[] map){
boolean isCan = true;
if (map[cand] == 0){
return false;
}
for (int val : founded){
int diff = val-cand;
if (map[diff] == 0){
isCan = false;
break;
}
}
return isCan;

【在 b**********r 的大作中提到】
: Run the ultimate example around 400 ms
: here is my code
: 4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
: 0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167,
: 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
: 152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
: 145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
: 145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
avatar
d*l
114 楼
上面的方法都非常好，区别在于搜索的目标不一样。感觉上搜索点的话，要搜索的空间
小一些，数据大了应该更有优势。这道题当时自己想了半天也没什么思路，实在惭愧，
大家给出这么多好的思路，受益匪浅。
avatar
m*k
115 楼
23
8
why bother?
2 7 2 4 8 8 8 10 7
--->reverse(2 7 2 4 8 8 8 10 7)
---->7 10 8 8 8 4 2 7 2
8
avatar
g*y
116 楼
赞思路！稍微改了一点，运行我给的那个ultimate test只递归了232次，0ms.
运行bravethinker后面那个例子用了723234次递归，运行了469ms。

【在 b**********r 的大作中提到】
: Run the ultimate example around 400 ms
: here is my code
: 4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
: 0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167,
: 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
: 162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
: 152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
: 145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
: 145, 13, 19, 27, 39, 55, 64, 77, 90, 103, 119, 128, 130, 136, 141, 6,
avatar
s*y
117 楼
can you share your optimization?

【在 g**********y 的大作中提到】
: 赞思路！稍微改了一点，运行我给的那个ultimate test只递归了232次，0ms.
: 运行bravethinker后面那个例子用了723234次递归，运行了469ms。
avatar
g*y
118 楼
主要是Bravethinker的code, 改动很小：
1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
2. founded不用ArrayList, 改成数组，速度更快。
3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
紧要，不怎么影响速度。
public class BraveThinker implements IMilestone {
private int dfsCount = 0;
public int[] findMilestones(int[] dists) {
long t0 = System.currentTimeMillis();

dfsCount = 0;

int L = dists.length;
int N = (int) ((Math.sqrt(1 + 8 * L) - 1) / 2);
int[] founded = new int[N+1];
int max = dists[dists.length - 1];
int[] map = new int[max + 1];
for (int i = 0; i < map.length; i++) {
map[i] = 0;
}
for (int i = 0; i < dists.length; i++) {
map[dists[i]]++;
}
int cur = dists.length - 1;
search(founded, 0, dists, N, cur, map);
int[] solution = new int[N];
for (int i=0; isolution[i] = founded[i] - founded[i+1];
}

long t1 = System.currentTimeMillis();
System.out.println("DFS count = " + dfsCount + ", takes " + (t1-t0)
+ "ms.");
return solution;
}
private boolean search(int[] founded, int len, int[] dists,
int N, int cur, int[] map) {
dfsCount++;
if (len == N) return true;
// Optimize the lower bound of the index for the next search nodes
int nextMax = dists[cur];
int delta = 0;
if (len >= 2) {
delta = founded[0] - founded[len-1];
}
int minPossible = nextMax - delta;
int lb = 0;
if (minPossible > 0) {
lb = Math.abs(Arrays.binarySearch(dists, minPossible));
}
int remaining = N - len;
lb = Math.max(remaining * (remaining + 1) / 2 - 1, lb - 1);
for (int i = cur; i >= lb; i--) {
int candidate = dists[i];
while (i>=lb && candidate==dists[i-1]) i--;

if (isCandidate(founded, len, candidate, map)) {
founded[len] = candidate;
if (search(founded, len+1, dists, N, i - 1, map)) {
return true;
}
map[candidate]++;
for (int j=0; jmap[founded[j] - candidate]++;
}
}
}
return false;
}
private boolean isCandidate(int[] founded, int len, int candidate
, int[] map) {
if (map[candidate] == 0) return false;
map[candidate]--;
for (int i=0; iif (map[founded[i]-candidate] == 0) { // revert
map[candidate]++;
for (int j=0; jmap[founded[j]-candidate]++;
}
return false;
}
else {
map[founded[i]-candidate]--;
}
}
return true;
}
}

【在 s*****y 的大作中提到】
: can you share your optimization?
avatar
s*y
119 楼
赞，我今晚也要try try。

【在 g**********y 的大作中提到】
: 主要是Bravethinker的code, 改动很小：
: 1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
: 2. founded不用ArrayList, 改成数组，速度更快。
: 3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
: 紧要，不怎么影响速度。
: public class BraveThinker implements IMilestone {
: private int dfsCount = 0;
: public int[] findMilestones(int[] dists) {
: long t0 = System.currentTimeMillis();
:
avatar
b*r
120 楼
Refined the search logic by calculate the lower bound more precisely
Now even this example can be done around 1 second
0, 10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
50, 51, 51, 53, 53, 54, 54, 54, 55, 55, 56, 56, 57, 57, 58, 59, 60, 61,
62, 62, 64, 64, 66, 66, 68, 69, 70, 72, 74, 74, 76, 76, 78, 80, 82, 84,
86, 94,
1094 ms
Recursion count 408249
[10, 20, 25, 32, 35, 39, 41, 50, 56, 57, 64, 74, 76, 78, 80, 82, 86, 94]
10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8,
following is the improved code
private static boolean search (List founded, int[]
sortedDists, int N, int cur, int[] map){
recurCount++;
if (founded.size() == N-1){
return true;
}
if (cur < 0){
return false;
}
int remaining = N-founded.size();

//The mini possible candidate would be the max of the
following 2 cases
//(1) The sum of the least remaining-2 intervals in the
map
//(2) or the remaining*(remaining-1)/2 -th smallest
value in the map

int order = remaining*(remaining-1)/2-1;
int minDist = -1; //The calculate order-th value int the
remaining map
int prevValid = 0;
int count = 0;
int minPossible = 0; //The sum of the least remaining-2
intervals in the map
for (int i = 0; i < map.length; i++){
if (order <= 0){
minDist = prevValid;
break;
}
if (map[i] > 0){
prevValid = i;
if (count < remaining-1){
minPossible += map[i]*i;
count += map[i];
if (count > remaining-1){
minPossible -= (count-
remaining+1)*i;
}
}
}
order -= map[i];
}

minDist = Math.max(minDist, minPossible);
int lb0 = Math.abs(Arrays.binarySearch(sortedDists,
minDist))-1;
int lb = Math.max(lb0, 0);
int prevVal = -1;
for (int i = cur; i>=lb; i--){
int can = sortedDists[i];
if (can == prevVal){
prevVal = can;
continue;
}
prevVal = can;
if (isCandidate(founded, can, map)){
for (int val : founded){
map[val-can]--;
}
map[can]--;
founded.add(can);
if (search(founded, sortedDists, N, i-1,
map)){
return true;
}
founded.remove(founded.size()-1);
map[can]++;
for (int val : founded){
map[val-can]++;
}
}
}
return false;
}

【在 g**********y 的大作中提到】
: 主要是Bravethinker的code, 改动很小：
: 1. 试candidate时，对相同值，用index最小的那个，这样往下滑得更快。
: 2. founded不用ArrayList, 改成数组，速度更快。
: 3. 测试candidate时，直接改map; 测试不通过时revert修改。不过这个改动好象无关
: 紧要，不怎么影响速度。
: public class BraveThinker implements IMilestone {
: private int dfsCount = 0;
: public int[] findMilestones(int[] dists) {
: long t0 = System.currentTimeMillis();
:
avatar
g*y
121 楼
这个计算我可以理解。
昨天的code, 仔细想一下，算low bound是：
delta = founded[0] - founded[last]
founded序列不外乎两种可能：
a[1]+a[2]+...a[n], a[1]+a[2]+..a[n-1], ..., a1+a2, a1
或
a[1]+a[2]+...a[n], a[2]+... + a[n], ... a[n-1]+a[n], a[n]
以第一种为例
delta = founded[0] - founded[k] = a[n]+...+a[n-k+1]
下面要找的数是a[1]+...+a[n-k-1]，也就是founded[k+1]
这两个数之间有什么必然联系？nextMax是一个比founded[k]小的下一个数。
计算里假设founded[k+1] >= nextMax - delta, 这个为什么？

【在 b**********r 的大作中提到】
: Refined the search logic by calculate the lower bound more precisely
: Now even this example can be done around 1 second
: 0, 10, 10, 5, 7, 3, 4, 2, 9, 6, 1, 7, 10, 2, 2, 2, 2, 4, 8
: 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8,
: 8, 8, 9, 9, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15,
: 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 19, 19, 20, 20,
: 20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 25, 25, 25,
: 25, 26, 26, 28, 29, 29, 29, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33,
: 35, 35, 35, 36, 36, 37, 37, 37, 37, 38, 39, 39, 39, 39, 39, 40, 41, 41,
: 41, 41, 42, 43, 43, 44, 44, 44, 45, 45, 46, 46, 47, 47, 47, 48, 49, 50,
avatar
g*y
122 楼
另外计算lower-bound, 只用remaining*(remaing-1)/2-1也行，效率差别不大，最复杂的那个例子，只要单条件，我机器上也只算了600ms； 加上额外条件，也要算469ms.
avatar
c*n
123 楼
有没有人同意题目说给的是 all the pairs of milestones 意思是
如果是 4 milestones的，那排序后的输入肯定是下面序列？
||||
a b c a+b b+c a+b+c
如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
avatar
g*y
124 楼
不是，你看前面例子就知道。

【在 c*******n 的大作中提到】
: 有没有人同意题目说给的是 all the pairs of milestones 意思是
: 如果是 4 milestones的，那排序后的输入肯定是下面序列？
: ||||
: a b c a+b b+c a+b+c
: 如果是的话，会不会就是求在 a[1]...a[n-1]中求“和为a[n]”的最长子序列？
avatar
c*n
125 楼

我看LZ的就符合..
其他牛人给的是更通用的解法，那些太难了
I just wanna make my life easier

【在 g**********y 的大作中提到】
: 不是，你看前面例子就知道。
avatar
g*y
126 楼
我们都希望life有个easy button, 但是没有 :)

【在 c*******n 的大作中提到】
:
: 我看LZ的就符合..
: 其他牛人给的是更通用的解法，那些太难了
: I just wanna make my life easier
avatar
c*n
127 楼

好吧，我希望题目中的all the pairs可以理解成这个easy button
不知道你是怎么理解的，莫非是 only some of pairs of milestone are given?
不过不管怎么说，严格要求自己还是没有错的

【在 g**********y 的大作中提到】
: 我们都希望life有个easy button, 但是没有 :)
avatar
g*y
128 楼
all the pairs就是all the pairs, n个点，当然就是n(n-1)/2个距离值。这个没什么
歧义。
问题是你不能指望这些值排序后符合什么规律，除了一两条显然的。

【在 c*******n 的大作中提到】
:
: 好吧，我希望题目中的all the pairs可以理解成这个easy button
: 不知道你是怎么理解的，莫非是 only some of pairs of milestone are given?
: 不过不管怎么说，严格要求自己还是没有错的
avatar
c*n
129 楼

哦，对
我举的4个milestones的例子还有可能是
a b a+b c b+c a+b+c 可能c > a+b
不过肯定有个规律是 a+b+c肯定是最大的一个（升序排序序列的最后一个），其他的不
能保证顺序。
另外，和为a+b+c的最长子序列一定是 a, b ,c
如果是这样，就转成我说的那个求“指定和”找“最长子序列”的问题

【在 g**********y 的大作中提到】
: all the pairs就是all the pairs, n个点，当然就是n(n-1)/2个距离值。这个没什么
: 歧义。
: 问题是你不能指望这些值排序后符合什么规律，除了一两条显然的。
avatar
r*g
130 楼
考个古，这道题有没有人愿意把grass的算法的讲解一下，关键是不清楚如果dfs下去失
败了之后怎么往回走。
这题好难，如果考我我准备直接放弃了。

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
avatar
C*l
131 楼
印象中LSAT有很多类似题目，不过是靠人自己分析的。
觉得这条可以计算出来，不用尝试的。
avatar
f*3
132 楼
i have an idea，not sure if it is correct:
1.先找到最小的2个，假设是a和b.
2.remove ab, a+b from the array
3. find the next smallest left in the array - c, which must be a stone to stone distance.
4. remove a+c, b+c, a+b+c from the array if the array contain those values.
5 find the next smallest value left in the array, repeat the process from 4,
until the value you got a+b+c+d+e...adds up to the biggest value in the
array.
avatar
q*x
133 楼
这个讨论很不错。能不能做成合集啊？
所以大家的思路都是暴力加剪枝，各有巧妙。但这个可能是Amazon面试题吗？topcoder也没这么难
吧。

an
random

【在 h*********3 的大作中提到】
: There is a straight roads with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones(a,b,c,d) :
: a bcd
: Distance between a and b = 3
: Distance between a and c = 8
: Distance between a and d = 10
: Distance between b and c = 5
相关阅读
oh shit国际象棋嫁缠头那个怎么还姓zhu？一张图告诉你为什么在中国不适合做极限运动。。。 (转载)不过习胖政府确实有个优点 (转载)Re: 威州著名华人医生罗军先生因病骤然离世，家庭陷入困顿，告年入30万，至少还每月给500呢！Re: 比特币造就了多少百万富豪？ (转载)找一大管子把加州大火的热量投送到河北 (转载)中山大学到底在哪校园的傍晚，男女生并肩坐在墙角美国风光 (转载)斗鸡眼？魔都高速邻道爆胎引发车祸，法院判定四方均有责任 (转载)这个好玩儿白宫中的特朗普每天看8小时电视喝12罐可乐 (转载)Re: 聖鬥士星矢片頭主題曲中国驻美公使李克新：武力统一台湾 (转载)Re: 上海有个老头出名了 (转载)北京城里这一带，一路都是被摘的招牌见到漂亮得不行的女人我冲洞的想法
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。