## 624 - CD

Moderator: Board moderators

Caren
New poster
Posts: 7
Joined: Thu Oct 25, 2012 11:42 pm

### Re: 624 - CD-PE

Can anybody tell why this code gives PE ?? I have looked for every possible case but every time it gives just PE. This same thing is happening with problem 10168 also. I have posted about that problem in related thread too. Please help. Thanx in advance

Code: Select all

``````Removed after AC . Codes were fine.There was an online judge problem . Now it's solved and all the solutions are accepted
``````
Last edited by Caren on Sat Oct 27, 2012 12:16 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 624 - CD

Post the full code, this won't compile without any includes. There seems to be an issue with all special judges right now always giving PE.
Check input and AC output for thousands of problems on uDebug!

Caren
New poster
Posts: 7
Joined: Thu Oct 25, 2012 11:42 pm

### Re: 624 - CD-PE

Sorry I posted full code this time.

Code: Select all

``AC``

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

### Re: 624 - CD

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <vector>

#define MAX 21

using namespace std;

unsigned int n, n_tracks, i, u, k;
int max_result;
int tracks[MAX];
int used[MAX];
vector<int> current_list;

int max(int a, int b)
{
return a > b ? a : b;
}

int get_maximum_tracks(int j, int current_max)
{
used[j] = 1;
current_max += tracks[j];

if (current_max > n)
{
return -1;
}

if (current_max > max_result)
{

for (k = 0; k < (int) current_list.size(); k++)
{
}

max_result = current_max;
}

for (u = 0; u < n_tracks; u++)
{
if (!used[u] && u != j)
{
current_list.push_back(u);
get_maximum_tracks(u, current_max);
current_list.pop_back();
}
}

return current_max;
}

int main()
{
while (scanf("%d %d", &n, &n_tracks) != EOF)
{
memset(tracks, 0, sizeof tracks);
current_list.clear();
max_result = -1;

for (i = 0; i < n_tracks; i++)
{
scanf("%d", &tracks[i]);
}

/* Program Logic */
for (i = 0; i < n_tracks; i++)
{
memset(used, 0, sizeof used);
current_list.push_back(i);
get_maximum_tracks(i, 0);
current_list.pop_back();
}

for (i = 0; i < (int) answer.size(); i++)
{
}

printf("sum:%d\n", max_result);
}

return 0;
}
``````
That's my code, and I've been wondering how to make the results sort like in the example. There are no "instructions" about the order of the tracks on the output.

I get:

Code: Select all

``````4 1 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45
``````
But the example output is:

Code: Select all

``````1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45
``````
I know it's the same thing and only the "1 4" are switched but I get WA for that I think.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 624 - CD

Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

### Re: 624 - CD

brianfry713 wrote:Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
Yeah, I've realized that, but I have no idea of how to oredr them like in the input. I'm asking for help with this part.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 624 - CD

You can try every possible combination of tracks and find the best one.
Check input and AC output for thousands of problems on uDebug!

felixtsui
New poster
Posts: 1
Joined: Fri Jun 14, 2013 8:03 am

### Help Me! 624 - CD - RE

This problem has took me a whole morning!
I can pass all the sample input, However, I've tried "a thousand times" to submit my code but all RE.
What's wrong..
Here's my code.

Code: Select all

``````#include<stdio.h>
#include<string.h>
int d[250][150005],a[250],s[250],t,n,i,j;
int main()
{
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&t);
for(i=1;i<=t;i++)
scanf("%d",&a[i]);
memset(d,0,sizeof(d));
memset(s,0,sizeof(s));

for(i=1;i<=t;i++)
for(j=0;j<=n;j++)
if(j<a[i])
d[i][j]=d[i-1][j];
else
d[i][j]=(d[i-1][j]>(d[i-1][j-a[i]]+a[i]))?d[i-1][j]:(d[i-1][j-a[i]]+a[i]);

for(i=t,j=n;i>=1&&j>0;i--)
if(d[i][j]==(d[i-1][j-a[i]]+a[i]))
{
s[i]=1;j-=a[i];
}

for(i=1;i<=t;i++)
if(s[i])
printf("%d ",a[i]);
printf("sum:%d\n",d[t][n]);
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Help Me! 624 - CD - RE

Try changing your algorithm to brute force instead of DP. You can try every possible combination of tracks and find the best one.
Check input and AC output for thousands of problems on uDebug!

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 624 - CD

Hi, I'm having a few problems. Can someone help me? Kept getting WA...

My code:

Code: Select all

``Got AC using brute force method. Thanks brianfry.``
Last edited by dibery on Sun Jul 28, 2013 10:57 am, edited 1 time in total.
Life shouldn't be null.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 624 - CD

PM sent
Check input and AC output for thousands of problems on uDebug!

gautamsingh
New poster
Posts: 5
Joined: Tue Apr 22, 2014 6:28 pm

### Re: 624 - CD

Why am I getting TLE? I am generating all subsets and finding the subset with the max sum.

EDIT: Got AC. TLE was due to declaring temporary list of tracks each team inside the loop.

Code: Select all

``````#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define pb push_back
using namespace std;

typedef vector<int> vi;

int main ()
{
int n;
while ((scanf ("%d", &n)) != EOF)
{
int tracks;
scanf ("%d", &tracks);
int a[tracks];
for (int i = 0; i < tracks; ++i)
scanf ("%d", &a[i]);
int lim = (int) pow(2, tracks);
int ans = 0;
vi track;
for (int i = 1; i <= lim; ++i)
{
int temp = i;
int sum = 0;
vi temp_list;
for (int j = 0; j < tracks; ++j)
{
if (temp & (1<<j))
{
sum += a[j], temp_list.pb(a[j]);
}
}
if (sum <= n && sum > ans)
ans = sum, track = temp_list;
}
for (int i = 0; i < track.size(); ++i)
printf ("%d ", track[i]);
printf ("sum:%d\n", ans);
}
return 0;
}	``````

mhsn06
New poster
Posts: 16
Joined: Tue Apr 01, 2014 7:36 pm

### Re: 624 - CD

At first I thought the number of tracks must be maximum but it's ok with multiple solution.
For Example: for this last sample input

45 8 4 10 44 43 12 9 8 2

the sample output is

4 10 12 9 8 2 sum:45

but my AC code output the minimum number of tracks

43 2 sum:45

though it is ok but how can I find the max number of tracks from the table of dynamic programming. This is knapsack problem. And I used dynamic programming to solve this.

Thanks all and specially thanks DJWS

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 624 - CD

I used a DP int table as [N + 1][number of tracks + 1] that stores the total number of tracks used, and a bool table of the same size that lists if that track was used.
It is straightforward to modify the code to use either minimum or maximum number of tracks, and either way gets AC as this problem has a special judge.
Check input and AC output for thousands of problems on uDebug!

kimbbakar
New poster
Posts: 5
Joined: Wed Nov 13, 2013 8:48 am

### Re: 624 - CD

Im getting WA again and again ,but can't find any bug . Can anyone help me to fix this ?

Code: Select all

``````/*
Problem name :
Algorithm : Not Sure Yet
Contest/Practice :
Source :
Comment : Whenever you start to believe  yourself, people also start to believe in you
Date : --
Last Update : 23-Dec-2014
*/

#include<bits/stdc++.h>

#define pause           system("pause");
#define FOR(s,e,inc)    for(int i=s;i<=e;i+=inc)
#define mod             1000000007
#define inf             1<<30
#define pb              push_back
#define ppb             pop_back
#define mp              make_pair
#define F               first
#define S               second
#define sz(x)           ((int)x.size())
#define sqr(x)          ( (x)* (x) )
#define eps             1e-9
#define gcd(x,y)         __gcd(x,y)
#define lcm(x,y)        (x/gcd(x,y))*y
#define on(x,w)         x|(1<<w)
#define check(x,w)      (x&(1<<w))
#define all(x)          (x).begin(),(x).end()
#define pf              printf
#define pi              acos(-1.0)
#define reset(x,v)      memset(x,v,sizeof(x));
#define AND             &&
#define OR              ||

typedef long long ll;
typedef unsigned long long llu;

using namespace std;

template<class T>
inline T mod_v(T num)
{
if(num>=0)
return num%mod;
else
return (num%mod+mod)%mod;
}

template<class T>
T fast_pow(T n , T p)
{
if(p==0) return 1;
if(p%2)
{
T g=mod_v ( mod_v(n) * mod_v(fast_pow(n,p-1)) );
return g;
}
else
{
T g=fast_pow(n,p/2);
g=mod_v( mod_v(g) * mod_v(g) ) ;
return g;
}
}

template<class T>
inline T modInverse(T n)
{
return fast_pow(n,mod-2);
}

template<class T>
inline void debug(string S1,T S2,string S3)
{
cout<<S1<<S2<<S3;
}

template<class T>
inline T in()
{
register char c=0;
register T num=0;
bool n=false;
while(c<33)c=getchar();
while(c>33){
if(c=='-')
n=true;
else num=num*10+c-'0';
c=getchar();
}
return n?-num:num;
}

#ifndef ONLINE_JUDGE
#  define p(x) cout<<x<<endl;
#else if
#  define p(x) 0;
#endif

/*...... ! Code start from here ! ......*/

int dp[25][5000] ;
int ok[25][5000]={0} ;
int track[25];

int cc;
int n,t;

int re(int i,int sum)
{
if(i==t)
{
if(sum<=n) return sum;
else return -inf;
}

if(ok[i][sum]==cc) return dp[i][sum];

dp[i][sum]=-inf;

dp[i][sum]=max(dp[i][sum], re(i+1,sum+track[i] ));
dp[i][sum]=max(dp[i][sum], re(i+1,sum ));
ok[i][sum]=cc;

return dp[i][sum];
}

void print_path(int i,int sum,int st)
{//printf("%d %d %d\n",i,sum,st);
if(i==t || st==sum)
{
return;
}

if(sum==re(i+1,st+track[i]) )
{
printf("%d ",track[i]);
//        ans.pb(track[i] );
print_path(i+1,sum,st+track[i]);
return;
}
else
{
print_path(i+1,sum,st);
return;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen ( "in.txt", "r", stdin );
#endif

cc=1;

while(scanf("%d %d",&n,&t)==2)
{
int res;
for(int i=0;i<t;i++)
{
scanf("%d",&track[i]);
}

res=re(0,0);
print_path(0,res,0);

printf("sum:%d\n",res);

cc++;
}

return 0;
}
``````