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

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

473 - Raucous Rockers

Post by Christian Schuster » Fri Feb 04, 2005 5:31 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Feb 04, 2005 8:58 pm

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Feb 04, 2005 9:59 pm

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.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Sat Feb 05, 2005 10:41 pm

Thanks, I just got AC with an O(n*m*t) DP algorithm.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun May 08, 2005 10:01 pm

Code: Select all

 The songs will be recorded on the set of disks in the order of the dates they were written.
Does this mean that we will record disk 1 first, then disk 2, then 3, etc.? Or can we record song 1 onto disk 1, then song 2 onto disk 2 and then song 3 onto disk 1 again?
If only I had as much free time as I did in college...

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Mon May 09, 2005 10:00 am

It's not allowed to put songs 1 and 3 on disk 1 and song 2 on disk 2. More formally, for every possible pair (a,b) of chosen song numbers having a>b, the relation disk(a)>=disk(b) must hold.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 10, 2005 8:36 pm

Ok. I got it accepted in 2 seconds with a O(n*m*t) DP using O(m*t) memory. n is at most 10240, t is at most 128 and m is at most 128. They are probably smaller than this, but they are certainly not larger (checked with assert()).
If only I had as much free time as I did in college...

Wei-Ming Chen
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)

Post by Wei-Ming Chen » Fri Aug 04, 2006 2:06 pm

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

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

xish
New poster
Posts: 5
Joined: Mon Feb 13, 2006 9:45 am

473...WA,need I/O

Post by xish » Thu Sep 07, 2006 12:29 pm

And can anybody tell me what is the upper bound of the number n,t and m?

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 473...WA,need I/O

Post by DD » Tue Nov 04, 2008 12:40 pm

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. :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

rnd
New poster
Posts: 1
Joined: Mon Feb 08, 2010 11:02 pm

Re: 473 - Raucous Rockers

Post by rnd » Sun Feb 28, 2010 4:08 pm

Hello,
Does this problem is a binary knapsack problem with some constraint? The recursion formula:

Code: Select all

M(i, j) = M(i-1, j) if j-t(i) and j belongs to diffrent discs
M(i, j) = max{M(i-1, j), M(i-1, j-t(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 
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?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 473 - Raucous Rockers

Post by Angeh » Wed May 05, 2010 9:34 am

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 ...:)
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

fernandohbc
New poster
Posts: 5
Joined: Sat Aug 14, 2010 10:31 pm

473 - Raucous Rockers - RTE

Post by fernandohbc » Fri Mar 11, 2011 4:40 pm

This code works on my box, but keeps giving me RTEs.
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;
   }
}

shibly
New poster
Posts: 5
Joined: Wed Sep 22, 2010 7:32 am

Re: 473 - Raucous Rockers

Post by shibly » Mon Jul 04, 2011 9:17 pm

n<=800 , m<=100 and t<=100.
I got AC with this limits.

shopnobaj_raju
New poster
Posts: 7
Joined: Wed Oct 19, 2011 5:07 pm

Re: 473 - Raucous Rockers

Post by shopnobaj_raju » Fri Jul 27, 2012 2:16 am

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<n-1;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[n-1]<=t) for(i=1;i<=m;i++) dp[n-1][i]=1;
        else for(i=1;i<=m;i++) dp[n-1][i]=0;
        for(i=n-2;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][j-1];
                            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;
}

Post Reply

Return to “Volume 4 (400-499)”