473 - Raucous Rockers

[farzad.shbfn]

I also just found a counterexample for your current greedy algorithm:
4 11 2
9, 10, 2, 11

optimal solution is:
9 2
11
but your greedy will get:
9
2

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

[brianfry713]

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)