Problem Alibaba from SouthEastern Europe 2004/2005

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
EfEr
New poster
Posts: 5
Joined: Thu Sep 22, 2005 8:56 pm
Location: Bucuresti, Romania
Contact:

Problem Alibaba from SouthEastern Europe 2004/2005

Post by EfEr » Thu Sep 22, 2005 9:09 pm

A link to this problem: http://acmicpc-live-archive.uva.es/nuev ... php?p=3032

I managed to build a O(N^2) time and O(N) space algorithm using dynamic programming, but I still get time limit exceeded...
Please reply to this message if you have a better ideea. (I suspect a greedy strategy works, but I wasn't able to find one to prove correct)

PS: my dp solution is something like: bst[k][j] = best time to get all the treasures before their deadlines from i to j and be in i (k = 0) or in j (k = 1), based on the particular form of an optimal solution to this problem. (Of course, I keep only the last values computed since bst[0][j] can be computed from bst[0][i+1][j] and bst[1][i+1][j] and a similar relation for bst[1][j] holds)

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas » Sat Oct 01, 2005 9:02 pm

See the discussion here.:
http://forums.topcoder.com/?module=Thre ... =12#398479

In the last message in the thread I discuss an algorithm, which is still O(N^2) but with some tricks to speed up the code. I haven't implemented the algo. If you decide to try it, please tell me if it is enough to get AC.

Post Reply

Return to “ACM ICPC Archive Board”