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

toni
New poster
Posts: 7
Joined: Wed Jul 25, 2007 6:03 pm

Post by toni » Tue Sep 18, 2007 5:12 am

thanks Jan again ! your test cases is very helpful. I indeed ignore to initialized the array :)

ithenewguyi
New poster
Posts: 5
Joined: Tue Nov 20, 2007 11:27 pm

Post by ithenewguyi » Fri Dec 21, 2007 6:36 am

Sample Input

5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

Sample Output

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
that was straight from the site, the output should be sorted right? because the sample output isnt sorted..... :-?

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Wed Jan 09, 2008 5:45 pm

This problem has a special correction program. It's ok to output any correct solution. (At this time, the new site does not show the information about the special judgement.)

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

N

Post by WingletE » Fri May 30, 2008 6:43 am

I assumed N <= 5000 and got AC.

jknisely
New poster
Posts: 2
Joined: Tue Sep 16, 2008 6:35 pm

Getting RE from the judge

Post by jknisely » Tue Sep 16, 2008 6:48 pm

I am getting a RE from the judge. My code solves all the inputs listed on this thread, but it does not handle negative track lengths. Does anyone know if that is necessary? I am posting my code below.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
/* used to indicate which tracks are used for each possible solution */
unsigned int codes[] = { 0x80000, 0x40000, 0x20000, 0x10000, 0x8000, 0x4000, 0x2000, 0x1000, 0x800, 0x400, 0x200, 0x100, 0x80, 0x40, 0x20, 0x10, 0x8, 0x4, 0x2, 0x1};

int main() {
    unsigned int code, k,n, nTapeLength, nTracks;
    unsigned int tracks[20];
    unsigned int *sols;
    unsigned int nMaxFound;
    
    while (2 == scanf("%u %u", &nTapeLength, &nTracks)) {
		if (0 == nTracks) {
			puts("sum:0");
			continue;
		}
        sols = (unsigned int *)calloc(nTapeLength+1, sizeof(unsigned int));
        scanf("%u", tracks); 
        nMaxFound = tracks[0];
        sols[tracks[0]] = codes[0];
        
        for (n=1; n < nTracks; ++n) { 
            scanf("%u", tracks+n); 
            for (k=nMaxFound; k > 0; --k) {
                if (sols[k] > 0 && k+tracks[n] <= nTapeLength) {
                    code = sols[k] | codes[n];
                    if (sols[k+tracks[n]] < code) {
                        sols[k+tracks[n]] = code;
                        if (nMaxFound < k+tracks[n]) { nMaxFound = k+tracks[n]; }
                    } /* end of if a better solution was found */
                } /* end of if a solution was found */
            } /* end of for each possible solution */
            
            code = codes[n];
            if (sols[tracks[n]] < code) {
                sols[tracks[n]] = code;
                if (nMaxFound < tracks[n]) { nMaxFound = tracks[n]; }
            } 
        } /* end of for each number which needs to be read */
        
        for (n=nTapeLength; !sols[n]; --n) { ; }
        for (k=0; k < 20; ++k) {
            if (sols[n] & codes[k]) { printf("%u ", tracks[k]); }
        }
        printf("sum:%u\n", n);       
        free(sols);
    }
}


Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: N

Post by Igor9669 » Wed Nov 04, 2009 5:37 pm

WingletE wrote:I assumed N <= 5000 and got AC.
I assumed N <= 2000 and got AC. :D

ryen
New poster
Posts: 5
Joined: Mon Feb 01, 2010 6:25 pm

Re: Get WA, Need Help!!!

Post by ryen » Thu Feb 11, 2010 6:55 am

Could anybody help me? I've passed all the test case in this post, but still get WA. I use dp and assumu N < 20000
here is my code.

Code: Select all

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

int track[21];
int N,cnt;
int d[20000][21];

int dp(int cur, int s)
{
	int& ans = d[cur][s];
	if(ans)return ans;

	if(s == cnt) return 0;

	for(int i = s; i < cnt; i++)
	{
		if(cur >= track[i])
		{
			int t = dp(cur-track[i], i+1) + track[i];
			if(t > ans)ans = t;
		}
	}
	return ans;
}

int main()
{
	while(scanf("%d%d", &N, &cnt) != EOF)
	{
		for(int i = 0; i < cnt; i++)
		{
			scanf("%d", &track[i]);
		}
		memset(d, 0, sizeof(d));

		dp(N,0);
		int cur = N;
		// print answer
		for(int i = 0; i < cnt-1; i++)
		{
			for(int j = i; j < cnt; j++)
			{
				if(cur >= track[j])
				{
					if(d[cur][i] - d[cur-track[j]][j+1] == track[j])
					{
						printf("%d ",track[j]);
						cur = cur - track[j];
					}
				}
			}
		}
		if(cur >= track[cnt-1])printf("%d ", track[cnt-1]); // check the last 
		printf("sum:%d\n", d[N][0]);
	}
	return 0; 
}

ryen
New poster
Posts: 5
Joined: Mon Feb 01, 2010 6:25 pm

Re: 624 - CD

Post by ryen » Thu Feb 11, 2010 9:26 pm

could somebody give some more critical I/O? I just cannot find where am wrong!

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

Re: 624 - CD

Post by qwerty » Mon Mar 01, 2010 1:41 pm

i also passed all i/o of the board but still wa.no idea what's wrong.some hints plz.here my code

Code: Select all

ac
i was using less arraysize.finally changed my approach to dp :D
Last edited by qwerty on Wed Jul 27, 2011 12:52 pm, edited 1 time in total.

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

Re: 624 - CD

Post by qwerty » Mon Mar 01, 2010 4:14 pm

ok here is a question which sequence is better

20 7
or
15 5 7

oys135
New poster
Posts: 1
Joined: Fri Mar 26, 2010 1:51 pm

I got WA. Somebody help me plz~

Post by oys135 » Fri Mar 26, 2010 1:54 pm

Hello, this is my code. I've read all the posts about 624, but I still can't find where my problem is. I sent this code and got WA. Would you please help me find where My code is wrong? Thank you very much!

#include <iostream>

using namespace std;

class Depth{
private :
int n;
int P;
int maxprofit;
int *p;
bool bestset[21];
bool include[21];
public :
void start(int n, int P, int *p);
void knapsack(int i, int profit);
bool promising(int i, int profit);
void display(void);
};

void bubble(int *p, int n);

int main(void)
{
int i, n, P, p[21];
Depth depth;

while(1) {
cin >> P;
if(cin.eof())
break;

cin >> n;

for(i=1; i <= n; i++) {
cin >> p;
}
bubble(p, n);

depth.start(n, P, p);
depth.display();
}

return 0;
}

/***************************************************/
/* Depth-first Search (Backtracking) */
/***************************************************/
void Depth::start(int nN, int nP, int *np)
{
n = nN;
P = nP;
p = np;
maxprofit = 0;

knapsack(0, 0);
}

void Depth::knapsack(int i, int profit)
{
if(profit<=P && profit > maxprofit) {
maxprofit = profit;
for(int j=1; j<=n; j++)
bestset[j] = include[j];
}

if(promising(i, profit)) {
include[i+1] = true;
knapsack(i+1, profit+p[i+1]);
include[i+1] = false;
knapsack(i+1, profit);
}
}

bool Depth::promising(int i, int profit)
{
int j;
int bound;

if(profit >= P)
return false;
else {
j = i+1;
bound = profit;
while((j <= n) && (bound+p[j] <= P)) {
bound = bound + p[j];
j++;
}

if(j <= n)
bound += (P - bound);

return bound > maxprofit;
}
}

void Depth::display()
{
int i;

for(i=1; i<=n; i++) {
if(bestset == true){
cout << p << " ";
}
}
cout << "sum:" << maxprofit << endl;
}

void bubble(int *p, int n)
{
int i, j, tmp;
for(i=n-1; i>=0; i--) {
for(j=1; j<=i ; j++) {
if(p[j] > p[j+1]) {
tmp = p[j];
p[j] = p[j+1];
p[j+1] = tmp;
}
}
}
}

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 624 - CD

Post by amishera » Wed May 19, 2010 3:26 am

For the sample input/ouput sequence:

45 8 4 10 44 43 12 9 8 2

why is the solution not

43 2?

I tested this sequence (the permutation of the above):

45 8 43 2 4 10 44 12 9 8

with

http://uvatoolkit.com/problemssolve.php

and the output is coming out as

43 2

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 624 - CD

Post by sazzadcsedu » Thu Aug 12, 2010 12:48 pm

In fact, in this problem the number of track used is not important,the main thing is to maximize used space.So

Code: Select all

for input 
45 8 4 10 44 43 12 9 8 2

output 1: 4 10 12 9 8 2 sum:45
output 2:43 2 sum:45

Both are correct.

Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

solon_aguiar
New poster
Posts: 7
Joined: Mon Jun 08, 2009 11:16 pm

Re: 624 - CD

Post by solon_aguiar » Fri Nov 05, 2010 6:53 pm

Hello guys,

I've searched on all inputs and outputs available here. My code seems to work on all of them, but I still get RE. Can you guys help me?
I'm using 0/1 knapsack.
Thank you very much

Code: Select all

#include <cstdio>
#include <algorithm>
#define MAX 20000

using namespace std;

long long tracks[MAX], resp[MAX];
long long current, N, n_tracks, sum, tam;
long long tab[MAX][MAX];

long long max(long long a, long long b){
    if(a > b)
        return a;
    return b;
}

long long print(long long n, long long W){
    long long indiceAtual = 0;
    long long linhaAtual = n;
    long long colunaAtual = W;
    while(linhaAtual != 0 && colunaAtual != 0){
        int num = tab[linhaAtual][colunaAtual];
        int sup = tab[linhaAtual - 1][colunaAtual];
        if(num == sup){
            linhaAtual--;
        }else{
	    resp[indiceAtual] = tracks[linhaAtual - 1];
	    indiceAtual++;
            colunaAtual = colunaAtual - tracks[linhaAtual - 1];
            linhaAtual--;
        }
    }
    return indiceAtual;
}

long long custo(long long n, long long W){
    for(long long i = 0; i <= n; i++)
        tab[i][0] = 0;
    for(long long i = 0; i <= W; i++)
        tab[0][i] = 0;
    for(long long i = 1; i <= n; i++){
    for(long long j = 1; j <= W; j++){
        if(tracks[i - 1] > j){
            tab[i][j] = tab[i-1][j];
        }else{
            tab[i][j] = max(tab[i-1][j], tracks[i - 1] + tab[i-1][j - tracks[i - 1]]);
        }
    }
    }
    return tab[n][W];
}

int main(){
    while(scanf("%lld", &N)!=EOF){
        scanf("%lld", &n_tracks);
    	sum = 0;
        for(long long i = 0; i < n_tracks; i++){
            scanf("%lld", &current);
            tracks[i] = current;
        }
        //sort(tracks, tracks + n_tracks + 2);
  	sum = custo(n_tracks, N);
  	tam = print(n_tracks, N);
   	for(long long i = tam - 1; i >= 0; i--)
		printf("%lld ", resp[i]);
	printf("sum:%lld\n", sum);
    }
    return 0;
}

Bidhan
New poster
Posts: 6
Joined: Mon May 17, 2010 5:07 pm
Location: University Of Dhaka, Bangladesh.
Contact:

Re: 624 - CD

Post by Bidhan » Mon Feb 07, 2011 5:50 pm

N will not exceed 5000.
Can be solved by 0-1 Knapsack/Coin Change/Backtrack.
Any correct output is acceptable. My output for the sample was

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
43 2 sum:45

Post Reply

Return to “Volume 6 (600-699)”