624 - CD

[Caren]

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

[brianfry713]

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.

[Caren]

Sorry I posted full code this time.

Code: Select all

AC

[Munchor]

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> answer;
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)
  {
    answer.clear();

    for (k = 0; k < (int) current_list.size(); k++)
    {
      answer.push_back(current_list[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("%d ", tracks[answer[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]

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

[Munchor]

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]

You can try every possible combination of tracks and find the best one.

[felixtsui]

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]

Try changing your algorithm to brute force instead of DP. You can try every possible combination of tracks and find the best one.

[dibery]

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.

Thanks in advance.

[brianfry713]

PM sent

[gautamsingh]

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]

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]

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.

[kimbbakar]

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

Thanx in advance ...

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;
}