10130 - SuperSale

[backbencher]

sorry i've made a mistake

no need to bother with my code

[tan_Yui]

My program outputs correct answer to the sample input,
but I got "wrong answer"....

I want to know the sample I/O for debugging.
Could someone help me?

Input :

• 4
  2
  77 7
  66 6
  2
  5
  5
  6
  32 16
  43 12
  26 4
  50 8
  20 3
  27 9
  4
  25
  23
  21
  19
  5
  1 1
  2 1
  3 1
  2 2
  5 5
  10
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  10
  1 1
  4 3
  4 3
  4 4
  5 4
  8 6
  10 7
  9 7
  11 8
  13 9
  30
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30

(My) Output :

• 0
  467
  82
  617

Thank you.

[Mohammad Mahmudur Rahman]

My AC program gives -

Code: Select all

0
435
83
646

Hope it helps.

[Mohammad Mahmudur Rahman]

Hi,
I solved this problem by running bottom-up Knapsack g times with a very poor timing of around 1.7 sec. Then the problem arose when I had come back to the problem & recoded it using top-down Knapsack to get an even worse timing of 4.4 sec. Now, AFAIK theoritically top-down knapsack should give better performance than bottom-up which seems to be proved completely wrong in this case . Can someone tell me what's really wrong?

Thanks.

[sumankar]

Hello All,

Can someone point out if there is a trick input I am missing out?

No one could have - I made a really really stupid mistake
Now I have it fixed, I had a macro for the max size of array, which was
lesser than the max input size.

Regards,
Suman.

[tan_Yui]

Mohammad Mahmudur Rahman, thank you for your reply! (^^
I try to debug my code.

[Rony]

Hi,
I am getting RTE(SIG.) . Can any one tell me ,what's wrong ? Following
is my code.

#include<stdio.h>
#define max 500
#define MAX 1005
#define MYMAX(x,y) ((x>y?x:y));
int main(){

int C[max][max],i,N,MW,w,Wi[MAX],Vi[MAX];
int tcase,T_cost=0,persons;
//freopen("input.txt","r",stdin);
scanf("%d",&tcase);
while(tcase--){

scanf("%d",&N);
for(i=1;i<=N;++i)
scanf("%d %d\n",&Vi,&Wi);

scanf("%d",&persons);
while(persons--){
scanf("%d",&MW);
for (i=0;i<=N ;i++) C[0] = 0;
for (w=0;w<=MW;w++) C[0][w] = 0;

for (i=1;i<=N;i++)
for (w=1;w<=MW;w++) {
if (Wi > w)
C[w] = C[i-1][w];
else
C[w] = MYMAX(C[i-1][w] ,C[i-1][w-Wi]+Vi);
}

T_cost+=C[N][MW];
}

printf("%d\n",T_cost);
T_cost=0;

}
return 0;
}

Thanks.
Rony.

[jagadish]

#define max as 1005

[sarah]

Coulde someone help me about this problem ,please?
I've checked test cases in the board and output correctly, but still get wrong answer.
This is my code:

Code: Select all

# include <iostream.h>
//# include <fstream.h>

void main(){
	int op[1000],ow[1000],pw[35],pp[35];
	int sw[35][1001];
	int len[35];
	int i,j,k,t,n,h,pn,max,sum;
	cin>>t;
	for(h=0;h<t;h++){
		cin>>n;
		for(i=0;i<n;i++){
			cin>>op[i]>>ow[i];
		}
		cin>>pn;
		max=0;
		for(i=0;i<pn;i++){
			cin>>pw[i];
			if(pw[i]>max)
				max=pw[i];
		}
		for (i=0 ; i<=max ; i++){
			len[i]=0;
			pp[i]=0;
		}
        for(i=0;i<n;i++)
			for(j=i+1;j<n;j++)
				if(ow[i]>ow[j]){
					k=ow[i];
					ow[i]=ow[j];
					ow[j]=k;
					k=op[i];
					op[i]=op[j];
					op[j]=k;
				}
				for(i=0;i<ow[0];i++)
					pp[i]=0;
				for(i=ow[0];i<=max;i++){
					for(j=0 ; j<n && i-ow[j]>=0 ; j++)
					{
						if (pp[i]<pp[i-ow[j]]+op[j]){							
							for (k=0 ; k<len[i-ow[j]] ; k++)
								if (sw[i-ow[j]][k]==j)
									break;
								if (k==len[i-ow[j]]){
									pp[i]=pp[i-ow[j]]+op[j];
									for (k=0 ; k<len[i-ow[j]] ; k++)
										sw[i][k]=sw[i-ow[j]][k];
									sw[i][k]=j;
									len[i]=len[i-ow[j]]+1;
								}
								else{
									if (pp[i]<pp[i-ow[j]]){
										pp[i]=pp[i-ow[j]];
										for (k=0 ; k<len[i-ow[j]] ; k++)
											sw[i][k]=sw[i-ow[j]][k];
										len[i]=len[i-ow[j]];
									}
								}

						}
					}
				}
		sum=0;
		for (i=0 ; i<pn ; i++)
			sum+=pp[pw[i]];
		cout<<sum<<endl;
	}
}

Thanks in advance.

[Raiyan Kamal]

Please write some lines on your algorithm. Its hard to understand anything from you code. I have tested your code with some input-output and it seemed OK. So there might be some critical case where your code fails and we need to know about the algo you are using to figure that out.

I tried to understand you algo from you code. I see that you are sorting the objects according to their weight. Why is that needed ? Are you using some greedy approach ?

[sarah]

I use DP. And I just sort the objects according to their weight for a little optimization and nothing else! This is what I do:
The array

[little joey]

Try the input

Code: Select all

1
4
17 4
93 5
61 8
83 3
1
18

Your program picks the objects 1, 2 and 4 for a total price of 17+93+83=193 and a total weight of 4+5+3=12. The optimal pick is objects 2, 3 and 4 (93+61+83=237, 5+8+3=16).

Did your code compile on the Online Judge? I had to change the first lines into

Code: Select all

#include <iostream>

using namespace std;

int main(){
...

before it compiled without errors and warnings on my system.

Good luck.

[sarah]

Sorry for the delay.
I checked the input you mentioned and my output was 237!!??
Could you please check it again?
I always write my codes in this format and never get Compile Error in UVA.
Can you tell what the compiler you use is? I use 'MS Visual C++'.
Is it possible the difference in the output is because of the different compilers?
Thanks in advance.

[little joey]

Well, that's strange. I compiled it under linux using g++ 3.3, and under windows98 using Borland C++ 5.5, and both gave 193 to my testcase. Are you sure it's the same code as above that returns 237?

You were right about the judge; it compiles your code, probably because it uses the older g++ 2.95 which accepts main() to return void in stead of int.

[sarah]

So so sorry!
You're right. The code I've posted here outputs 193.
This the code which outputs 237 and gets WA:

Code: Select all

# include <iostream.h>
# include <limits.h>
# include <string.h>
//# include <fstream.h>

char st[31][10001];

void main(){
	//ifstream cin("10130.in") ;
	int po[1000],w[1000],mw[31],mp[31],sum;
	int n,t,i,j,minw,maxw,k,h,pn,te;
	cin>>t;
	for (h=0 ; h<t ; h++){
		minw=INT_MAX;
		maxw=0;
		cin>>n;
		for (i=0 ; i<n ; i++){
			cin>>po[i]>>w[i];
			if (w[i]<minw)
					minw=w[i];
		}
		cin>>pn;
		for (i=0 ; i<pn ; i++){
			cin>>mw[i];
			if (maxw<mw[i])
				maxw=mw[i];
		}
		for (i=0 ; i<n ; i++)
			for (j=i+1 ; j<n ; j++)
				if (w[i]>w[j]){
					te=w[i];
					w[i]=w[j];
					w[j]=te;
					te=po[i];
					po[i]=po[j];
					po[j]=te;
				}
		for (i=0 ; i<maxw ; i++)
			strcpy(st[i],"") ;
		for (i=0 ; i<minw ; i++)
			mp[i]=0;
		for (i=minw ; i<=maxw ; i++){
			if (i){
				mp[i]=mp[i-1];
				strcpy(st[i],st[i-1]) ;
			}
			for (j=0 ; j<n ; j++){
				if (i-w[j]>=0){
					for (k=0 ; st[i-w[j]][k] ; k++)
						if (st[i-w[j]][k]==j+'0')
							break;
					if (!st[i-w[j]][k]){
						if (mp[i]<mp[i-w[j]]+po[j]){
							mp[i]=mp[i-w[j]]+po[j];
							strcpy(st[i],st[i-w[j]]) ;
							st[i][strlen(st[i])+1]=0;
							st[i][strlen(st[i])]=j+'0';
						}
					}
				}
				else break;
			}
		}
		sum=0;
		for (i=0 ; i<pn ; i++)
			sum+=mp[mw[i]];
		cout<<sum<<endl;
	}
//	cin>>i;
}

I can't find its bug? Can you help me, please?
Sorry again for not being careful.