All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
- New poster
- Posts: 1
- Joined: Wed Aug 29, 2012 11:42 am
Adrian Kuegel wrote:I also just found a counterexample for your current greedy algorithm:
4 11 2
9, 10, 2, 11
optimal solution is:
but your greedy will get:
unfortunately, the O(n^2 * m) dynamic programming algorithm I have is too slow. And the pruning I inserted seems to be wrong.
actually O(n^2 * m) algorithm works, i just got accepted using save space trick, instead of O(m*n) memory i used O(2*n) memory, algorithm runs a little faster because of CPU's CASH. my time was 0.989,
but i like to know O(m*n*t) algorithm too!:D
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
I solved it using DP in O(n * m * t) with O(n + m * t) memory.
The dp array stores the number of songs up to and including the current song that will fit on that location of that disk.
For the first song, initialize the dp array so that anywhere on the second or later disks or on the first disk after or at the length of that song will hold 1 song.
For each remaining song, initialize to the previous song's dp array at the same disk and location.
See if you can do better by putting the current song ending at the current location on the current disk (the dp array[previous song][current disk][at the current position minus the length of the current song] + 1)
or the end of the previous disk (the dp array[previous song][current disk - 1][t - the length of the current song] + 1)
Check input and AC output for thousands of problems on uDebug