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)
Problem Alibaba from SouthEastern Europe 2004/2005
Moderator: Board moderators
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.
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.