624 - CD

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 624 - CD-PE

Post by Caren » Thu Oct 25, 2012 11:58 pm

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 by brianfry713 » Fri Oct 26, 2012 12:20 am

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

Post by Caren » Fri Oct 26, 2012 9:58 am

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

Post by Munchor » Wed Mar 20, 2013 12:48 am

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

Re: 624 - CD

Post by brianfry713 » Wed Mar 20, 2013 10:01 pm

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

Post by Munchor » Thu Mar 21, 2013 6:47 pm

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

Post by brianfry713 » Thu Mar 21, 2013 11:57 pm

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

Post by felixtsui » Fri Jun 14, 2013 8:07 am

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

Post by brianfry713 » Fri Jun 14, 2013 8:53 pm

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

Post by dibery » Thu Jul 25, 2013 10:56 am

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.
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

Post by brianfry713 » Sat Jul 27, 2013 2:09 am

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

Post by gautamsingh » Thu Sep 04, 2014 2:23 pm

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

Post by mhsn06 » Tue Sep 09, 2014 9:40 pm

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 :D

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

Re: 624 - CD

Post by brianfry713 » Wed Sep 10, 2014 9:43 pm

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

Post by kimbbakar » Wed Dec 31, 2014 10:33 pm

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

Post Reply

Return to “Volume 6 (600-699)”