Page 1 of 1

How to solve the problem

Posted: Sun Jun 12, 2005 5:32 am
by windows2k
http://acm.pku.edu.cn/JudgeOnline/show ... m_id=1738
It looks an classic DP problem, but it seems have terrible time limit.
Could someone give some hints? Thx

Posted: Sun Jun 12, 2005 4:05 pm
by Per
Looks like Huffman coding.

Posted: Mon Jun 13, 2005 2:50 am
by windows2k
Per wrote:Looks like Huffman coding.
Huffman coding can change it's sequence, but the problem doesn't.
for example, 5 3 4 5
( ( 5 ( 3 4 ) ) 5 ) it needs 36
( ( 5 3 ) ( 4 5 ) ) it needs 34

Posted: Mon Jun 13, 2005 7:29 am
by Per
Whoops, sorry. That does seem to make the problem harder.

Re: How to solve the problem

Posted: Thu Jun 16, 2005 6:36 pm
by gawry
windows2k wrote: http://acm.pku.edu.cn/JudgeOnline/show ... m_id=1738
It looks an classic DP problem, but it seems have terrible time limit.
Could someone give some hints? Thx
I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.

Re: How to solve the problem

Posted: Sat Jun 18, 2005 6:42 am
by windows2k
gawry wrote:
windows2k wrote: http://acm.pku.edu.cn/JudgeOnline/show ... m_id=1738
It looks an classic DP problem, but it seems have terrible time limit.
Could someone give some hints? Thx
I think you could solve it using Hu-Tucker algorithm, but it seems to be very complicated.
I thoguht I have found a rough method to solve.
But I don't know how to reduce the time complexity from O(n^2) to O(nlogn)
Could someone give me some hints? thx

Posted: Sun Jun 19, 2005 1:09 pm
by Cosmin.ro
This seems similar to optimal matrix chain multiplication, maybe you could modify the O(n log n) algorithm for matrix chain multiplication described here http://historical.ncstrl.org/litesite-d ... 81-875.pdf , to solve this problem.