Page 2 of 6

sorry

Posted: Thu Sep 23, 2004 1:08 am
by backbencher
sorry i've made a mistake

no need to bother with my code

Posted: Wed Feb 23, 2005 4:49 pm
by 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.

Posted: Thu Feb 24, 2005 12:06 am
by Mohammad Mahmudur Rahman
My AC program gives -

Code: Select all

0
435
83
646
Hope it helps.

10130 [SuperSale] - Strange Knapsack behaviour

Posted: Thu Feb 24, 2005 3:41 am
by 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. :o Now, AFAIK theoritically top-down knapsack should give better performance than bottom-up which seems to be proved completely wrong in this case :roll:. Can someone tell me what's really wrong?

Thanks.

Posted: Thu Feb 24, 2005 11:27 am
by 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 :D
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.

Posted: Thu Feb 24, 2005 1:42 pm
by tan_Yui
Mohammad Mahmudur Rahman, thank you for your reply! (^^
I try to debug my code.

10130

Posted: Mon May 02, 2005 9:35 am
by 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.

Posted: Sun May 15, 2005 1:58 pm
by jagadish
#define max as 1005

10130

Posted: Tue Aug 30, 2005 3:11 pm
by 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. :x
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.

Posted: Wed Sep 21, 2005 3:31 pm
by 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 ?

Thanks for paying attention.

Posted: Fri Sep 23, 2005 7:49 am
by 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

Posted: Fri Sep 23, 2005 9:35 am
by 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.

Posted: Mon Oct 24, 2005 6:23 pm
by sarah
Sorry for the delay. :oops:
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.

Posted: Tue Oct 25, 2005 5:05 pm
by 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.

You're right!

Posted: Tue Oct 25, 2005 10:44 pm
by sarah
So so sorry!
You're right. The code I've posted here outputs 193. :oops:
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.