473 - Raucous Rockers

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

farzad.shbfn
New poster
Posts: 1
Joined: Wed Aug 29, 2012 11:42 am

Re:

Post by farzad.shbfn »

Adrian Kuegel wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 473 - Raucous Rockers

Post by 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)
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 4 (400-499)”