How to solve the problem

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

How to solve the problem

Post by windows2k » Sun Jun 12, 2005 5:32 am

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Jun 12, 2005 4:05 pm

Looks like Huffman coding.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Mon Jun 13, 2005 2:50 am

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jun 13, 2005 7:29 am

Whoops, sorry. That does seem to make the problem harder.

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm

Re: How to solve the problem

Post by gawry » Thu Jun 16, 2005 6:36 pm

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.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: How to solve the problem

Post by windows2k » Sat Jun 18, 2005 6:42 am

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

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sun Jun 19, 2005 1:09 pm

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.

Post Reply

Return to “Other words”