10130 - SuperSale
Moderator: Board moderators
-
- New poster
- Posts: 5
- Joined: Thu Sep 23, 2004 12:10 am
- Location: Bangladesh
- Contact:
sorry
sorry i've made a mistake
no need to bother with my code
no need to bother with my code
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 :
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
- 0
467
82
617
-
- Experienced poster
- Posts: 154
- Joined: Sat Apr 17, 2004 9:34 am
- Location: EEE, BUET
My AC program gives -
Hope it helps.
Code: Select all
0
435
83
646
You should never take more than you give in the circle of life.
-
- Experienced poster
- Posts: 154
- Joined: Sat Apr 17, 2004 9:34 am
- Location: EEE, BUET
10130 [SuperSale] - Strange Knapsack behaviour
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.
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.


Thanks.
You should never take more than you give in the circle of life.
No one could have - I made a really really stupid mistakeHello All,
Can someone point out if there is a trick input I am missing out?

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.
10130
Hi,
I am getting RTE(SIG.) . Can any one tell me ,what's wrong ? Following
is my code.
Thanks.
Rony.
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.
10130
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:
Thanks in advance.
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;
}
}
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact:
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 ?
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.
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
The array
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Try the input
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 intobefore it compiled without errors and warnings on my system.
Good luck.
Code: Select all
1
4
17 4
93 5
61 8
83 3
1
18
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(){
...
Good luck.
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.

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.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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.
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!
So so sorry!
You're right. The code I've posted here outputs 193.
This the code which outputs 237 and gets WA:
I can't find its bug? Can you help me, please?
Sorry again for not being careful.
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;
}
Sorry again for not being careful.