10130 - SuperSale

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

Moderator: Board moderators

backbencher
New poster
Posts: 5
Joined: Thu Sep 23, 2004 12:10 am
Location: Bangladesh
Contact:

sorry

Post by backbencher » Thu Sep 23, 2004 1:08 am

sorry i've made a mistake

no need to bother with my code

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Wed Feb 23, 2005 4:49 pm

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
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Thu Feb 24, 2005 12:06 am

My AC program gives -

Code: Select all

0
435
83
646
Hope it helps.
You should never take more than you give in the circle of life.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

10130 [SuperSale] - Strange Knapsack behaviour

Post by Mohammad Mahmudur Rahman » Thu Feb 24, 2005 3:41 am

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.
You should never take more than you give in the circle of life.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu Feb 24, 2005 11:27 am

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.
Last edited by sumankar on Thu Feb 24, 2005 2:09 pm, edited 1 time in total.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Thu Feb 24, 2005 1:42 pm

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

Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:

10130

Post by Rony » Mon May 02, 2005 9:35 am

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
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Sun May 15, 2005 1:58 pm

#define max as 1005

sarah
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

10130

Post by sarah » Tue Aug 30, 2005 3:11 pm

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.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Wed Sep 21, 2005 3:31 pm

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
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

Thanks for paying attention.

Post by sarah » Fri Sep 23, 2005 7:49 am

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Sep 23, 2005 9:35 am

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
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

Post by sarah » Mon Oct 24, 2005 6:23 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Oct 25, 2005 5:05 pm

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
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

You're right!

Post by sarah » Tue Oct 25, 2005 10:44 pm

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.

Post Reply

Return to “Volume 101 (10100-10199)”