473  Raucous Rockers
Moderator: Board moderators
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
473  Raucous Rockers
Hello,
I tried to solve problem 473 by a greedy algorithm:
1. S := sequence of song lengths (as given in input)
2. determine number of disks needed for the songs in S
3. if disks <= m return S
4. otherwise remove longest song from S and go to 2.
I assumed that the song order given in the input must be maintained over all disks, so I put songs on disk 1 until it's full, then on disk 2 until it's full, and so on.
I didn't find any case where the result differs from my (too slow) backtracking solution. Obviously, there must be such cases, because I received WA.
Thanks,
Christian
I tried to solve problem 473 by a greedy algorithm:
1. S := sequence of song lengths (as given in input)
2. determine number of disks needed for the songs in S
3. if disks <= m return S
4. otherwise remove longest song from S and go to 2.
I assumed that the song order given in the input must be maintained over all disks, so I put songs on disk 1 until it's full, then on disk 2 until it's full, and so on.
I didn't find any case where the result differs from my (too slow) backtracking solution. Obviously, there must be such cases, because I received WA.
Thanks,
Christian

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Your greedy is correct if you apply it to one disk only. So to get a correct overall algorithm, use dynamic programming to partition the n songs into m intervals of songs which will be assigned to disks. Within one disk, apply your greedy algorithm until the songs fit on that disk. The dynamic programming part is similar to problems 709 and 10239.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Code: Select all
The songs will be recorded on the set of disks in the order of the dates they were written.
If only I had as much free time as I did in college...
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am

 Experienced poster
 Posts: 122
 Joined: Sun Nov 13, 2005 10:25 am
 Location: Taiwan
Can you tell me what the ouputs are of these inputs?(ACM473)
I got WA on this problem
Now I want to find out why it was wrong
But I need the ouputs of these inputs
Can anyone help me? Thanks
Now I want to find out why it was wrong
But I need the ouputs of these inputs
Can anyone help me? Thanks
Code: Select all
3
8 4 3
2, 4, 8, 1, 1, 2, 3, 5
7 4 2
3, 4, 4, 1, 4, 4, 4
10 5 7
3, 6, 9, 1, 9, 1, 5, 10, 10, 2
473...WA,need I/O
And can anybody tell me what is the upper bound of the number n,t and m?

 Experienced poster
 Posts: 145
 Joined: Thu Aug 14, 2003 8:42 am
 Location: Mountain View, California
 Contact:
Re: 473...WA,need I/O
You can check this post (http://acm.uva.es/board/viewtopic.php?f ... 82dea1139a), and the upper bound of n, t, and m are clearly illustrated in there.
I got A.C. by following this article.
I got A.C. by following this article.
Have you ever...
 Wanted to work at best companies?
 Struggled with interview problems that could be solved in 15 minutes?
 Wished you could study realworld problems?
Re: 473  Raucous Rockers
Hello,
Does this problem is a binary knapsack problem with some constraint? The recursion formula:
The second line is standard 1/0 knapsack formula. The first line gives constraint that single track cannot begin in first CD and ens at second?
Does my reasoning is correct?
Does this problem is a binary knapsack problem with some constraint? The recursion formula:
Code: Select all
M(i, j) = M(i1, j) if jt(i) and j belongs to diffrent discs
M(i, j) = max{M(i1, j), M(i1, jt(i)) + 1} otherwise
1 <= i <= n
1<= j <= m*t
M(i, j)  maximum number of songs from range 1..i that could be placed on discs with whole size of j
Does my reasoning is correct?
Re: 473  Raucous Rockers
its easy to solve in N^2*m..but i can't get he m*n*t solution
Could anyone Give some hints ....?
thanks in advance ...
Could anyone Give some hints ....?
thanks in advance ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)

 New poster
 Posts: 5
 Joined: Sat Aug 14, 2010 10:31 pm
473  Raucous Rockers  RTE
This code works on my box, but keeps giving me RTEs.
Any ideas?
Any ideas?
Code: Select all
#include <iostream>
#define MAX 2000000
using namespace std;
struct Disk {
int totalTime;
int capacity;
};
class DiskCollection {
private:
Disk currentDisk;
int totalTracks;
int diskToWrite;
int qtdDisks;
public:
DiskCollection(int qtdDisks, int capacity) {
this>currentDisk.totalTime = 0;
this>currentDisk.capacity = capacity;
this>qtdDisks = qtdDisks;
this>totalTracks = 0;
this>diskToWrite = 0;
}
int getTotalTracks() {
return this>totalTracks;
}
bool isBetterThan(DiskCollection * diskCollection) {
if (this>totalTracks > diskCollection>totalTracks) {
return true;
}
if (this>totalTracks == diskCollection>totalTracks) {
if (this>diskToWrite < diskCollection>diskToWrite) {
return true;
}
if (this>diskToWrite == diskCollection>diskToWrite) {
if (this>currentDisk.totalTime <
diskCollection>currentDisk.totalTime) {
return true;
}
return false;
}
return false;
}
return false;
}
DiskCollection * insertTrack(int trackTime) {
DiskCollection * result = NULL;
if (this>currentDisk.capacity  this>currentDisk.totalTime >=
trackTime) {
result = new DiskCollection(this>qtdDisks,
this>currentDisk.capacity);
result>totalTracks = this>totalTracks + 1;
result>diskToWrite = this>diskToWrite;
result>currentDisk.capacity = this>currentDisk.capacity;
result>currentDisk.totalTime = this>currentDisk.totalTime
+ trackTime;
} else if (this>diskToWrite != this>qtdDisks  1) {
result = new DiskCollection(this>qtdDisks,
this>currentDisk.capacity);
result>totalTracks = this>totalTracks + 1;
result>diskToWrite = this>diskToWrite + 1;
result>currentDisk.capacity = this>currentDisk.capacity;
result>currentDisk.totalTime = trackTime;
}
return result;
}
};
DiskCollection * emptyCollection(int qtdDisks, int capacity) {
DiskCollection * empty = new DiskCollection(qtdDisks, capacity);
return empty;
}
int main() {
char line[MAX];
cin.getline(line, MAX);
int qtdTc = atoi(line);
for (int tc = 1; tc <= qtdTc; tc++) {
// Ignora linha em branco
cin.getline(line, MAX);
// Leitura dos parâmetros
cin.getline(line, MAX);
int n = atoi(strtok(line, " "));
int t = atoi(strtok(NULL, " "));
int m = atoi(strtok(NULL, " "));
// Ignora o resto da linha
cin.getline(line, MAX);
char * tok = strtok(line, " ,");
int trackTimes[n + 1];
int i = 1;
while (tok) {
trackTimes[i++] = atoi(tok);
tok = strtok(NULL, " ,");
}
DiskCollection * dc[n + 1][t * m + 1];
for (i = 0; i <= n; i++) {
for (int j = 0; j <= t * m; j++) {
if (i == 0) {
dc[i][j] = emptyCollection(m, t);
} else if (j  trackTimes[i] < 0) {
dc[i][j] = dc[i  1][j];
} else {
DiskCollection * newCollection = dc[i  1][j
 trackTimes[i]]>insertTrack(trackTimes[i]);
if (newCollection
&& newCollection>isBetterThan(dc[i  1][j])) {
dc[i][j] = newCollection;
} else {
dc[i][j] = dc[i  1][j];
}
}
}
}
cout << dc[n][t * m]>getTotalTracks() << endl << endl;
}
}
Re: 473  Raucous Rockers
n<=800 , m<=100 and t<=100.
I got AC with this limits.

 New poster
 Posts: 7
 Joined: Wed Oct 19, 2011 5:07 pm
Re: 473  Raucous Rockers
Got WA . Can anoyone help??
Code: Select all
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int c,i,j,k,ans,n,t,m,temp,tem2,tk,x;
vector<int> songs;
vector<vector<int> > dp;
scanf("%d",&c);
for(x=1;x<=c;x++)
{
songs.clear();
dp.clear();
scanf("%d %d %d",&n,&t,&m);
for(i=0;i<n1;i++)
{
scanf("%d, ",&temp);
songs.push_back(temp);
}
scanf("%d",&temp);
songs.push_back(temp);
//for(i=0;i<n;i++) cout<<songs[i]<<' ';
dp.resize(n+1);
for(i=0;i<dp.size();i++) dp[i].resize(m+1);
for(i=0;i<=m;i++) dp[n][i]=0;
for(i=0;i<=n;i++) dp[i][0]=0;
if(songs[n1]<=t) for(i=1;i<=m;i++) dp[n1][i]=1;
else for(i=1;i<=m;i++) dp[n1][i]=0;
for(i=n2;i>=0;i)
{
for(j=1;j<=m;j++)
{
dp[i][j]=dp[i+1][j];
if(songs[i]<=t)
{
temp=0;
tk=0;
for(k=i;k<n;k++)
{
if(temp+songs[k]<=t)
{
tk++;
temp+=songs[k];
tem2=dp[k+1][j1];
if(tem2+tk>dp[i][j]) dp[i][j]=tem2+tk;
}
}
}
}
}
if(x!=1) printf("\n%d\n",dp[0][m]);
else printf("%d\n",dp[0][m]);
}
return 0;
}