b***e
发帖数: 1419 | 1 Given a list of strings, find a concatenation of all the strings such that
its dictionary order is the smallest among all the possibilities.
For instance, by joining the list ["ab", "cd", "ef"] we can get:
"abcdef",
"cdabef",
"cdefab",
..., ...
where "abcdef" is the one of the least dictionary order. | b******u
发帖数: 469 | 2 排序?
【在 b***e 的大作中提到】
: Given a list of strings, find a concatenation of all the strings such that
: its dictionary order is the smallest among all the possibilities.
: For instance, by joining the list ["ab", "cd", "ef"] we can get:
: "abcdef",
: "cdabef",
: "cdefab",
: ..., ...
: where "abcdef" is the one of the least dictionary order.
| b***e
发帖数: 1419 | 3 The question is: how?
【在 b******u 的大作中提到】
: 排序?
| b******u
发帖数: 469 | 4 如果输入很大，建个树之类的，每条边是一个字母，然后做一个遍历
【在 b***e 的大作中提到】
: The question is: how?
| b***e
发帖数: 1419 | 5 You just didn't get it.
I am not asking a trivial question that you can have an answer within 2 mins
without knowing the answer already. If you do, there are only 2
possibilities:
1. you are Einstein, or
2. you are wrong.
I know Einstein never came (and will never come) to this BBS. So there's
only 1 option for you.
Please, give it some serious thinking before you reply.
【在 b******u 的大作中提到】
: 如果输入很大，建个树之类的，每条边是一个字母，然后做一个遍历
| z**k
发帖数: 629 | | h***r
发帖数: 726 | 7 easy.
cat your-list | sort | concat
done.
【在 b***e 的大作中提到】
: Given a list of strings, find a concatenation of all the strings such that
: its dictionary order is the smallest among all the possibilities.
: For instance, by joining the list ["ab", "cd", "ef"] we can get:
: "abcdef",
: "cdabef",
: "cdefab",
: ..., ...
: where "abcdef" is the one of the least dictionary order.
| X****r
发帖数: 3557 | 8 Let me try it. I definitely spent more than two minutes, but it
doesn't mean I'm right though.
Assume the strings are s_i, we are going to find k so that s_k is the
first string in the concatenated result.
a <- ""
j <- 0
while sum_i(len(s_i)) > j:
c <- min_i(s_i[j]); if len(s_i) <= j, use a[len(s_i)-j] as s_i[j]
if there is single minimal c from s_k:
break
else:
a <- a + c
discard all s_i that s_i[j] != c from further consideration
j++
if k is still undecided:
pick any k
【在 b***e 的大作中提到】
: You just didn't get it.
: I am not asking a trivial question that you can have an answer within 2 mins
: without knowing the answer already. If you do, there are only 2
: possibilities:
: 1. you are Einstein, or
: 2. you are wrong.
: I know Einstein never came (and will never come) to this BBS. So there's
: only 1 option for you.
: Please, give it some serious thinking before you reply.
| b***e
发帖数: 1419 | 9 Somewhat I expected a good one from you. And here we go.
This looks very promising, but man, you are going with a real operational
approach while I am looking for some sort of denotational explanation.
Nonetheless, here's the question (where I believe you have a typo):
by
if len(s_i) <= j, use a[len(s_i)-j] as s_i[j] // negative index?
do you really mean:
if len(s_i) <= j, use s[j-len(s_i)] as s_i[j]
There are further questions, but let's figure out the most essential one
first. | i*******e
发帖数: 29 | 10 最笨的办法：每个string建个链表，然后scoring串起来的string，慢慢排去。。。 | | | X****r
发帖数: 3557 | 11 Actually I meant a[j-len(s_i)] as s_i[j] for len(s_i) <= j
where a is the best concatenated string built so far.
Okay let me explain what I'm thinking. Obviously if all strings
are of the same length we can just simply sort them. However
for shorter strings we need to fill the blanks with the characters
that from the best concatenated string built without this
particular shorter string in question. Given that we needed to
compare characters up to this position so far, which means there
is at lea
【在 b***e 的大作中提到】
: Somewhat I expected a good one from you. And here we go.
: This looks very promising, but man, you are going with a real operational
: approach while I am looking for some sort of denotational explanation.
: Nonetheless, here's the question (where I believe you have a typo):
: by
: if len(s_i) <= j, use a[len(s_i)-j] as s_i[j] // negative index?
: do you really mean:
: if len(s_i) <= j, use s[j-len(s_i)] as s_i[j]
: There are further questions, but let's figure out the most essential one
: first.
| m**********8
发帖数: 103 | 12 sort with criterion str1 < str2 if str1 + str2 < str2 + str1. | b***e
发帖数: 1419 | 13 Clever!
However, not the end of the story. Why is your ordering well defined? In
other words, sorting according to your order will terminate.
Let me give concrete example: we all know sissor/paper/stone. There is a
overcoming relation among them, but that relation is not an well-defined
ordering, because there is a infinite descending sequence:
...< paper < sissor < stone < paper
To justify your answer, you need to justify we can do sorting with the
relation you defined. In other words, is t
【在 m**********8 的大作中提到】
: sort with criterion str1 < str2 if str1 + str2 < str2 + str1.
| b***e
发帖数: 1419 | 14 Yes. I believe the algorithm works.
But the real question is, how do you convince us why your algorithm will
give the optimal, i.e., can you sketch a proof why by your operations an
optimal can be reached. I do not see a trivial argument here.
See, here's why I like this problem. It is not hard to derive an
algorithm that you so much believe is correct, but it is truly non-
trivial to justify why it is the case.
【在 X****r 的大作中提到】
: Actually I meant a[j-len(s_i)] as s_i[j] for len(s_i) <= j
: where a is the best concatenated string built so far.
: Okay let me explain what I'm thinking. Obviously if all strings
: are of the same length we can just simply sort them. However
: for shorter strings we need to fill the blanks with the characters
: that from the best concatenated string built without this
: particular shorter string in question. Given that we needed to
: compare characters up to this position so far, which means there
: is at lea
| X****r
发帖数: 3557 | 15 Hmm interesting, I had thought of this but just didn't think it
would be a total order. But upon a closer look it is quite obvious:
assume the size of character set is n, then all strings can be mapped
to numbers in base n. Denote x(s) as the number for string s, and l(s)
as its length, ab <= ba then is as same as
x(a)*n^(l(b)) + x(b) <= x(b)*n^(l(a)) + x(a)
which is equivalent to
x(a)/(n^(l(a))-1) <= x(b)/(n^(l(b))-1)
so obviously it is transitive. The above means that you may as well
repeat th
【在 b***e 的大作中提到】
: Clever!
: However, not the end of the story. Why is your ordering well defined? In
: other words, sorting according to your order will terminate.
: Let me give concrete example: we all know sissor/paper/stone. There is a
: overcoming relation among them, but that relation is not an well-defined
: ordering, because there is a infinite descending sequence:
: ...< paper < sissor < stone < paper
: To justify your answer, you need to justify we can do sorting with the
: relation you defined. In other words, is t
| b***e
发帖数: 1419 | 16 Yes, so in fact the ordering is on s* rather than s. The algorithm you
gave somewhat does that.
After this understanding, we can have a dictionary tree to handle it in
a
linear order (of the number of characters).
【在 X****r 的大作中提到】
: Hmm interesting, I had thought of this but just didn't think it
: would be a total order. But upon a closer look it is quite obvious:
: assume the size of character set is n, then all strings can be mapped
: to numbers in base n. Denote x(s) as the number for string s, and l(s)
: as its length, ab <= ba then is as same as
: x(a)*n^(l(b)) + x(b) <= x(b)*n^(l(a)) + x(a)
: which is equivalent to
: x(a)/(n^(l(a))-1) <= x(b)/(n^(l(b))-1)
: so obviously it is transitive. The above means that you may as well
: repeat th
| b***e
发帖数: 1419 | 17 In fact, there's a meta question:
Why is an ordering relation important here? What breaks if there's no
transitivity or anti-symmetry?
【在 X****r 的大作中提到】
: Hmm interesting, I had thought of this but just didn't think it
: would be a total order. But upon a closer look it is quite obvious:
: assume the size of character set is n, then all strings can be mapped
: to numbers in base n. Denote x(s) as the number for string s, and l(s)
: as its length, ab <= ba then is as same as
: x(a)*n^(l(b)) + x(b) <= x(b)*n^(l(a)) + x(a)
: which is equivalent to
: x(a)/(n^(l(a))-1) <= x(b)/(n^(l(b))-1)
: so obviously it is transitive. The above means that you may as well
: repeat th
| X****r
发帖数: 3557 | 18 I'm not sure I understand your question here.
For strings a and b we define a relation a <= b iff ab <= ba in
dictionary order. This definition of the relation is useful later,
but only if the relation is a total order, because being a total
order is a necessary and sufficient condition of being able to
sort a finite set ascendingly, i.e. a bijection to [1,n].
(Strictly speaking we need to define equvalent classes to satisty
anti-symmetry)
If the strings can be sorted in s_1,..., s_n, using the
【在 b***e 的大作中提到】
: In fact, there's a meta question:
: Why is an ordering relation important here? What breaks if there's no
: transitivity or anti-symmetry?
| b***e
发帖数: 1419 | 19 It is a bit vague, I would say. Here is a more concrete version:
If I claim the following:
Define the relation "a < b iff ab < ba". Then based on the relation,
I repeat the simple operation of finding an adjacent pair of strings
of inverted order and swap them, until I cannot find any such pairs.
After all the swapping is done, I get the result.
Apparently, I didn't use transitivity in this argument. Why is the
argument defective without the discussion about transitivity?
【在 X****r 的大作中提到】
: I'm not sure I understand your question here.
: For strings a and b we define a relation a <= b iff ab <= ba in
: dictionary order. This definition of the relation is useful later,
: but only if the relation is a total order, because being a total
: order is a necessary and sufficient condition of being able to
: sort a finite set ascendingly, i.e. a bijection to [1,n].
: (Strictly speaking we need to define equvalent classes to satisty
: anti-symmetry)
: If the strings can be sorted in s_1,..., s_n, using the
| X****r
发帖数: 3557 | 20 What you have described only gets the local minimal, not the global
minimal required by the original question.
【在 b***e 的大作中提到】
: It is a bit vague, I would say. Here is a more concrete version:
: If I claim the following:
: Define the relation "a < b iff ab < ba". Then based on the relation,
: I repeat the simple operation of finding an adjacent pair of strings
: of inverted order and swap them, until I cannot find any such pairs.
: After all the swapping is done, I get the result.
: Apparently, I didn't use transitivity in this argument. Why is the
: argument defective without the discussion about transitivity?
| | | b***e
发帖数: 1419 | 21 Yes. This is part that interest me the most. In fact, anti-symmetry
guarantees that the swapping process will terminate, and transitivity
guarantees that local optimal is also global optimal. These 2 are necessary
for the correctness proofs.
From where I saw this problem, people reach the solution quickly, but had
quite some discussion on the correctness proof, where transitivity is the
key part.
【在 X****r 的大作中提到】
: What you have described only gets the local minimal, not the global
: minimal required by the original question.
| h***r
发帖数: 726 | 22 do you have a counter example for the simplest sort + concatenate method?
thanks!
necessary
【在 b***e 的大作中提到】
: Yes. This is part that interest me the most. In fact, anti-symmetry
: guarantees that the swapping process will terminate, and transitivity
: guarantees that local optimal is also global optimal. These 2 are necessary
: for the correctness proofs.
: From where I saw this problem, people reach the solution quickly, but had
: quite some discussion on the correctness proof, where transitivity is the
: key part.
| t****t
发帖数: 6806 | 23 两个大侠讨论了这么久你还没看明白么.问题的重点就是怎么sort.
长度一样的,没问题,按字典序排
长度不一样的,多出来的部分怎么算
例1: "b" "bc" 结果="bbc"
例2: "b" "ba" 结果="bab"
【在 h***r 的大作中提到】
: do you have a counter example for the simplest sort + concatenate method?
: thanks!
:
: necessary
| z***e
发帖数: 5393 | 24 能不能这样？
Min_Order(A[1...N]) = (Min_Order(A[1...i-1, i+1...N]) insert A[i])
也就是说，最后排好的结果里面，随便抽一个出来，剩下的仍然是dictionary order，
问题是抽出来的这个应该怎么插回去，这个...呃, O(n)一个个试...
然后类似dynamic programming这样下去...
实际上我觉得还是先直接sort，比如{ab, a, acb, b,ba,bcc, ca, cb}
再怎么搞，排第一个的肯定是a开头的，对吧，按照上面的算法，剩下来的仍然是
dictionary order排最开头，不管怎么说, a**不会排到 b**后面去因为 a**(order{a*
*, b**, c**})，后面这个还是a**开头。
那么剩下就是把a**归一类比如a[...]，对这个就是：
bool flags[...]; //全部false，这个用来记录a[i]是否已经用了
currentValue = a[0] + a[1]; //这个加起来是个linked list，方便后面插
flags[0]=fla
【在 t****t 的大作中提到】
: 两个大侠讨论了这么久你还没看明白么.问题的重点就是怎么sort.
: 长度一样的,没问题,按字典序排
: 长度不一样的,多出来的部分怎么算
: 例1: "b" "bc" 结果="bbc"
: 例2: "b" "ba" 结果="bab"
| l******e
发帖数: 12192 | 25 长度不一样的时候，可以这样比较：
假设len(s1[1:m]) < len(s2[1:n])，那么比较 s1[1:m] + s2[1:n-m]和s2[1:n]如果不
等，则可以排序；如果相等，则继续比较s1[1:m]+s2[1:n-m+i]和s2[1:n]+s1[1:i](
loop
i)直至n=m或者不等。
举例：
"b" "bc" => "bb" < "bc" => "bbc"
"b" "ba" => "bb" > "ba" => "bab"
"ab" "aba"=> "aba"=="aba" => "abab" > "abaa"=> "abaab"
"a" "aa" => "aa" == "aa" => "aaa"
【在 t****t 的大作中提到】
: 两个大侠讨论了这么久你还没看明白么.问题的重点就是怎么sort.
: 长度一样的,没问题,按字典序排
: 长度不一样的,多出来的部分怎么算
: 例1: "b" "bc" 结果="bbc"
: 例2: "b" "ba" 结果="bab"
| h***r
发帖数: 726 | 26 字典排序呀，有什么问题。
反例呢 : ) 谢谢！
【在 t****t 的大作中提到】
: 两个大侠讨论了这么久你还没看明白么.问题的重点就是怎么sort.
: 长度一样的,没问题,按字典序排
: 长度不一样的,多出来的部分怎么算
: 例1: "b" "bc" 结果="bbc"
: 例2: "b" "ba" 结果="bab"
| z***e
发帖数: 5393 | 27 我想出一个排序的方法了：
关键问题是 "b" "ba"这种怎么判定，这不是长短问题，而是说如果一个是另一个的开
头部分：s2==s1+otherValue;
我的做法是把短的那个duplicate： "b" => "bb",直到两个长度相等（或者前者较大也
可以），然后再比较；
同样，如果是 "ad" "adc",那么"ad"=>"adad" 再比。总之：
s1
s2 = s1 s1 s1 others
then
temp = s1 s1 s1 s1;
compare s1 and s2;
写了段code如下:
bool Compare(string s1, string s2)
{
if (s1.length() < s2.length())
{
string temp = s1;
while(temp.length()
{
temp+=s1;
}
return temp.compare(s2) < 0;
}
else if (s1.length() > s2.l
【在 t****t 的大作中提到】
: 两个大侠讨论了这么久你还没看明白么.问题的重点就是怎么sort.
: 长度一样的,没问题,按字典序排
: 长度不一样的,多出来的部分怎么算
: 例1: "b" "bc" 结果="bbc"
: 例2: "b" "ba" 结果="bab"
| l******e
发帖数: 12192 | 28 你这个错了
"ab"和"aba"怎么比的？
【在 z***e 的大作中提到】
: 我想出一个排序的方法了：
: 关键问题是 "b" "ba"这种怎么判定，这不是长短问题，而是说如果一个是另一个的开
: 头部分：s2==s1+otherValue;
: 我的做法是把短的那个duplicate： "b" => "bb",直到两个长度相等（或者前者较大也
: 可以），然后再比较；
: 同样，如果是 "ad" "adc",那么"ad"=>"adad" 再比。总之：
: s1
: s2 = s1 s1 s1 others
: then
: temp = s1 s1 s1 s1;
| z***e
发帖数: 5393 | 29 我把aba加进入，结果是这样：
原始序列：ab adb ba bab adca aa a bad baa aab aba
直接排序: a aa aab ab aba adb adca ba baa bab bad
按要求排: a aa aab aba ab adb adca baa bab ba bad
aba < ab （因为aba < abab)，所以是abaab，而不是ababa，没错啊？
【在 l******e 的大作中提到】
: 你这个错了
: "ab"和"aba"怎么比的？
| l******e
发帖数: 12192 | 30 你是整个duplicate呀
还不如我那个算法。
【在 z***e 的大作中提到】
: 我把aba加进入，结果是这样：
: 原始序列：ab adb ba bab adca aa a bad baa aab aba
: 直接排序: a aa aab ab aba adb adca ba baa bab bad
: 按要求排: a aa aab aba ab adb adca baa bab ba bad
: aba < ab （因为aba < abab)，所以是abaab，而不是ababa，没错啊？
| | | b***e
发帖数: 1419 | 31 我不是说了按 s* 排序了吗？ 你们没看见？
【在 l******e 的大作中提到】
: 你是整个duplicate呀
: 还不如我那个算法。
| z***e
发帖数: 5393 | 32 你们都太抽象了，我抽象思维弱:D
你的思路跟我一样，只不过我图简单，直接把短的那个string反复concatenate，
production code的话就该直接比较substring,这些都无所谓。反正总体思路是在长的
里面找到第一个不匹配短的那个的部分，然后进行cmp. 其实这并不是字符串长短问题
，而是说短的string是长string的第一个substring.就像上面说的，其实是 s1=s*, s2
=s*, 然后比较s1和s2.
【在 l******e 的大作中提到】
: 你是整个duplicate呀
: 还不如我那个算法。
| c*****t
发帖数: 1879 | 33 刚注意到，Xentar 早就把答案写在那里了。。
这题没啥好办法。最多稍微 optimize 一下。举几个极端的例子
a
aa
aaa
aaaa
aaaaa
... // all prefix = a
b
ba
baba
... // all prefix = b
所有的 prefix 的长度都是 1+ 。而且没有一个 prefix 是另外一个
prefix 的 prefix 。
很明显，我们最终的选择的 string 有在是 sort 里面最小的那个
prefix 的组里面。但是在该组里面，应该取什么是个 recursive
的问题（也就是去掉 common prefix 以后，去掉产生的 ""，sort
该组以及其它所有的 string。当然，其它 prefix 的已经 sort）。 | t****t
发帖数: 6806 | 34 给你反例了你还看不懂就是你自己的问题了
【在 h***r 的大作中提到】
: 字典排序呀，有什么问题。
: 反例呢 : ) 谢谢！
| l******e
发帖数: 12192 | 35 你们全是英文，懒得看
看了thrust的贴，就回了一个
【在 b***e 的大作中提到】
: 我不是说了按 s* 排序了吗？ 你们没看见？
| b***e
发帖数: 1419 | 36 如果一个帖子, 能把我, thrust, xentar, coconut几个老家伙都扯进来, 就算是成功
了. 本帖显然很成功.
我已经记不清这几个人可以回溯到什么时候了. coconut好像99/00就在了, thrust和
xentar可能是01或02的样子. 其实还有个netghost, 也是很面熟的样子, 大概也是99/
00吧. 我从开天辟地的时候就在了. Sometimes when you look at it, it's
amazing that after these many years, it is still us here.
coconut和我原来好像还混过数学版, 后来那边越来越牛了, 我不得不转战到这里了. | l******e
发帖数: 12192 | 37 其实很多人都在
只不过换马甲了......
99/
【在 b***e 的大作中提到】
: 如果一个帖子, 能把我, thrust, xentar, coconut几个老家伙都扯进来, 就算是成功
: 了. 本帖显然很成功.
: 我已经记不清这几个人可以回溯到什么时候了. coconut好像99/00就在了, thrust和
: xentar可能是01或02的样子. 其实还有个netghost, 也是很面熟的样子, 大概也是99/
: 00吧. 我从开天辟地的时候就在了. Sometimes when you look at it, it's
: amazing that after these many years, it is still us here.
: coconut和我原来好像还混过数学版, 后来那边越来越牛了, 我不得不转战到这里了.
| t****t
发帖数: 6806 | 38 表扯我, 我算法不熟. 我是业余写程序的! 你们都是大牛.
其实我和xentar也99年就在了.
99/
【在 b***e 的大作中提到】
: 如果一个帖子, 能把我, thrust, xentar, coconut几个老家伙都扯进来, 就算是成功
: 了. 本帖显然很成功.
: 我已经记不清这几个人可以回溯到什么时候了. coconut好像99/00就在了, thrust和
: xentar可能是01或02的样子. 其实还有个netghost, 也是很面熟的样子, 大概也是99/
: 00吧. 我从开天辟地的时候就在了. Sometimes when you look at it, it's
: amazing that after these many years, it is still us here.
: coconut和我原来好像还混过数学版, 后来那边越来越牛了, 我不得不转战到这里了.
| z***e
发帖数: 5393 | 39 我说，如果你们公司要招人的话，我very愿意过来拜见的...
【在 t****t 的大作中提到】
: 表扯我, 我算法不熟. 我是业余写程序的! 你们都是大牛.
: 其实我和xentar也99年就在了.
:
: 99/
| t****t
发帖数: 6806 | 40 你干啥子的, 不是M$的人吗? 我是做硬件的, 你也会业余做硬件吗?
【在 z***e 的大作中提到】
: 我说，如果你们公司要招人的话，我very愿意过来拜见的...
| | | z***e
发帖数: 5393 | 41 ...
完了，我是纯软工...
但是intel这些也要招软工啊...
【在 t****t 的大作中提到】
: 你干啥子的, 不是M$的人吗? 我是做硬件的, 你也会业余做硬件吗?
| h***r
发帖数: 726 | 42 别太欺负人啦,wuwu
反例还是能看懂的。
就是每看到。在第几楼呀？
【在 t****t 的大作中提到】
: 给你反例了你还看不懂就是你自己的问题了
| l******e
发帖数: 12192 | 43 i fule u
22266
【在 h***r 的大作中提到】
: 别太欺负人啦,wuwu
: 反例还是能看懂的。
: 就是每看到。在第几楼呀？
| h***r
发帖数: 726 | 44 thanks. That's is a good conter example : )
【在 l******e 的大作中提到】
: i fule u
: 22266
| d****j
发帖数: 293 | 45 这道题好像是facebook hacker cup 2011的第三题吧
刚开始没仔细看掉到陷阱了,直接sort连接..-_-
看到板上举得例子 "bc" "bca" 正解是 bcabc 而不是bcbca，才恍然大悟...
再看这个例子，如果是"bc" "bcd",那么sort再连接就没问题了
（楼上其他人举的例子和这个类似啦）
明显发现：如果一个词A=wx是另外一个词B=w的前缀，那么就需要考虑长单词多余部分x
和前缀w的大小,才能决定结果是AB 还是BA。
如果没有前缀关系，顺序连接打印就行了。
这就是我的idea，sort+栈+额外处理。
1.先sort.
2.第一个单词入栈
3.检查下一个单词cur是否以栈顶单词top为前缀，
a.如果不是，栈中元素全部 pop出，打印; cur入栈
b.是, 检查cur多余的部分x和top的大小
i. x<=top小，cur入栈
ii. x>top, top出栈打印
4. 重复3步骤直到单词表尾
5. 如果栈不为空，全部pop出栈打印
其中3步骤的几种情况，有的要下移一个单词检查，有的要继续检查当前cur单词
复杂度的话，假设检查前缀的时间为constant，总共有N个单词
排序O(NlogN) + O(N)
最坏情况:后一个都是前一个单词前缀，且多余的x都小于前缀，全部入栈，最后全部出
栈，2N时间. 如果x为空，既所有的单词都一样的，x="", 也是2N时间
写出来的程序应该可以继续优化合并代码。
我试了一下貌似是对的，但不完全确定。
谁能检查一下，多谢 | d****j
发帖数: 293 | 46 JobHunting有个更简单的答案，我想多了.......sigh | g**e
发帖数: 6127 | 47 link pls? thx
【在 d****j 的大作中提到】
: JobHunting有个更简单的答案，我想多了.......sigh
| b*****p
发帖数: 9649 | |
|
