Problem Alibaba from SouthEastern Europe 2004/2005
Posted: 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)
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)