Paying up

I dunno wat d problem seems to be im gettin perfect output for the sample input given and iv even tested other cases.. y does it give wrong answer iv implemented all conditions like bank notes must be less than 20 and currency <=1000

My program is giving output perfectly fine. Still it is suggesting me as wrong answer. Unable to understand whats wrong.

The test cases are correct. You should spend some more time in going over the problem statement and trying to find corner cases where your code might fail.

@aniruddha. I have tried all possible test cases and its working fine from my side. Cant we get a copy of some of the test cases? Not all but some would definitely work out. And since its a practice session, it shouldnt matter much. Thanks

No matter how many test cases i try, this problem keeps on giving me wrong answer error !

Initially I was getting a time limit exceed error. After some optimization it started giving run-time error while I have checked all the example test cases along with some other. May I know, which test case fails?

Nope, figuring that out yourself is the most important part of solving a problem :)

what could be the possible corner cases? is m=0 a valid proposition?
though i didnt get right answer even after allowing for m=0.

OH MY GOD. I WAS PRINTING YES IN PLACE OF Yes. SILLY

please,provide someone provide details about dynamic programming.
regards

Yes, something to that effect will be put up soon :)

 

 

The pow() function is not always very precise. You should probably use end = (1<<noc) instead of the function pow().

 

Hi Drupal, Thanks for ur reply but "end = (1<<noc)" did not fix it. still am getting WA.

                    Any idea ?

Well, for one, you appear to be printing YesYesYesNoYes for the sample input, rather than what you are meant to print.

oh my god... missing endl made it - WA !!!

Thanks Stephen, Thank you very much.

After i put endl in the cout, it got accepted.

Thanks!

There is also a tutorial for this problem: blog.codechef.com/2009/07/09/tutorial-for-problem-paying-up/

How to handle the case when number of notes>20 or the following value is >1000 are we supposed to exit

The problem says the number of banknotes will be <= 20  and the value is <= 1000.

It doesn't say 'sometimes that is true, the rest of the time it isn't'..

@tryingtocode Such a case will not be there in the input

don't you think we should get the test case also with our code in the mail we get from codechef for which my solution failed because i am trying to figure out input for which my program failed and i am not able to find the test case . Can you please suggest some border testcases ?

Of course you shouldn't be emailed it, a large part of solving problems is figuring out why your code isn't working yourself :)

Also, if we did that, it would be possible for people to hard code the test cases and output the answers. :)

What will be the output for the following 3 cases ?

a) 0 0

b) 0 13

c) 2 0

   1

   1

Please read the tutorial for this problem

can the value of a banknote be 0 ?

hello guyz... take into consideration that the value of m(amount of money the mugger asks for) can also be 0... i got correct answer on including this condition

I've made multiple attempts at this now, and the results seem very accurate to me. Anitha's advice was helpful. However, even accounting for these situations, it's still not certain what the answer SHOULD be in those cases. My program gives the following results to each condition you proposed:

a. Yes

b. No

c. Yes

I wrote the code for the explained algorithm and i got a correct answer but for an input file where the answer is No for all test cases, my program runs in about 13 secs.

 

Thus the algorithm provided in the tutorial is not efficient enough, and the control mechanism is not strict enough. I shouldn't have gotten a 'correct answer' response by any means.

I am getting runtime error everytime i uplaod the code ..

its running perfectly fine on my system

..

can anyone help me why i am getting runtime error ...

...

the code is as below...

-----------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

int notes[100][20] = {0};
int mask[20] = {0};
int isSum(int caseNum,int sumReq,int notesAv);
int main()
{
int numCases;
int reqSum[20],availNotes[20];

int LoopCount,i;
int result;
scanf("%d",&numCases);

for(LoopCount=0; LoopCount<numCases; LoopCount++)
{
scanf("%d",&availNotes[LoopCount]);
scanf("%d",&reqSum[LoopCount]);
for(i=0; i<availNotes[LoopCount]; i++)
{
scanf("%d",&notes[LoopCount][i]);
}
}

mask[0] = 1;
for(i=1;i<20;i++)
{
mask[i] = mask[i-1]<<1;
}

for( LoopCount=0;LoopCount<numCases;LoopCount++)   
{
result = isSum(LoopCount,reqSum[LoopCount],availNotes[LoopCount]);
if(result == 1)
printf("Yesn",result);
else
printf("Non",result);
}
return 0;
}

int isSum(int caseNum,int sumReq,int notesAv)
{
int loopLim;
int i,j,sum;

//loopLim = pow(2,notesAv);
loopLim = 1<<notesAv;

for(i=1;i<loopLim;i++)
{
sum = 0;
for(j=0;j<notesAv;j++)
{
if((mask[j] & i) != 0)
sum = sum + notes[caseNum][j];
}
if(sum == sumReq)
return 1;
}
return 0;
}

It is not working perfectly fine on your system. You just aren't testing it properly.

Have you tried any input with 100 test cases like the problem says will happen?

do we need to check the case when any of t,n or m is negative? if not, then can anyone please tell me wt's wrong with this code?

 

1. #include<stdio.h>
2. main()
3. {
4. int t,n,m,i,j,sum,flag;
5. int val;
6. scanf("%d",&t);
7. if(t<=100)
8. {
9.   for(j=0;j<t;j++)
10.   {
11.    sum=0;  
12.    flag=0;
13.    scanf("%d %d",&n,&m);
14.    if(n<=20)
15.    {
16.     for(i=0;i<n;i++)
17.     {   
18.      scanf("%d",&val);
19.      if(val<=1000)
20.      sum=sum+val;  
21.      if(sum==m)
22.      flag=1;
23.     }
24.     if(flag!=1)
25.     printf("Non");
26.     else
27.     printf("Yesn");
28.    }
29.   }
30. }
31. return 0;
32. }    

it's printf("Non") and printf("Yesn") in the code that i have submitted...dont know what happened while copying it here...

i may have asked something really silly...but someone please help..

Well, your code will obviously not work if there are 101 test cases. It will also fail on most test cases; for example, if the correct sum is made up of the first and last numbers and nothing else.

i know...thank you so much...i misunderstood the problem...should have read the tutorial first...

can smone fnd error in my code i dnt kno why it's giving wrong answer...............

pls

#include<stdio.h>

int main(void) {

int t,n,m;
int i,j,s,a[20];


scanf("%d",&t);

while(t--) {

scanf("%d %d",&n,&m);

for(i=0;i<n;i++)
scanf("%d",&a[i]);

for(i=1;i<(1<<n);i++) {

s=0;

for(j=0;j<n;j++)
if(i&(1<<j)>0)
s=s+a[j];

if(s==m) {
printf("YESn");
goto end;
}


}


printf("NOn");

end : continue;

}
return 0;
}

will there be test cases only with n <= 20 or we have to take any 20 banknotes out of n ??

what does the Source limit 50000 means

is it 50000 byte or something else

@ Dal - the problem statement tells you n can be at most 20.

@ Shaurya - yes.

 

What's wrong in this procedure ???

int solve(int note[],int m,int i){
if(i<0) return 0;
if(m<note[i])return solve(note,m,i-1);
else return max(solve(note,m,i-1), note[i]+solve(note,m-note[i],i-1));
}

. . . . . . .

if(m == solve(note,m,n-1)) puts("YES");

else puts("NO");

oh!! sorry i figure out my problem..

Tell me what's the problem with my code,in my computer it is giving f9 output

#include<iostream.h>
int main()
{int ban,mug,test;
int a[20],i=0,p=0,l=0;int m[100];
cin>>test;
while(test)
{cin>>ban>>mug;
while(ban)
{cin>>a[i];
i++;
ban--;}
i--;
while(i+1)
{p=p+a[i];
i--;
}
if(p==mug)
m[l]=1;
else
m[l]=0;
test--;i=0;p=0;l++;}
i=l;
l=0;
while(l!=i)
{if(m[l]==1)
cout<<"Yes";
else
cout<<"No";
cout<<"n";
l++;}
return 0;
}

It is showing that my programme compiled successfully,but lacks the desired output

if we have a note that matches the value of m, then will be considered as the subset or is it necessary that the sum of a certain number of notes equals the value of m???

import java.util.*;

 

public class PayingUp {

public static Scanner s=new Scanner(System.in);

public static void main(String[] args) {

int t;

t=s.nextInt();

ArrayList<String> res=new ArrayList<String>();

for(int i=0;i<t;i++) {

int n=s.nextInt();

int sum=s.nextInt();

int[] elements=new int[n];

for(int j=0;j<n;j++)

elements[j]=s.nextInt();

if(solve(elements,sum))

res.add("Yes");

else

res.add("No");

}

for(int i=0;i<res.size();i++)

System.out.println(res.get(i));

}

public static boolean solve(int[] arr,int sum) {

int n=(int)Math.pow(2,arr.length);

for(int i=1;i<=n;i++) {

int temp=0;

int k=1;

for(int j=arr.length-1;j>=0;j--) {

if((k&i)!=0)

temp+=arr[j];

k=k<<1;

}

if(temp==sum)

return true;

}

return false;

}

}

can anyone check, what's wrong in this code snippet? it's according to that tutorial.

my code is giving correct outpit but im getting a runtime error on submission, please help

is algorithm library allowed?

im using codeblocks in windows

plz somebody help me to get rid of Non-zero exit code runtime errror.

plz help....here is my code...

 

import java.io.*;

import java.util.*;

class Main

{

public static void main(String args[])throws IOException

{

int m=0,t,x,i,flag=1,c,p;

Scanner in=new Scanner(System.in);

t=in.nextInt();

if(t>=1 && t<=1000000)

{

for(p=1;p<=t;p++)

{

m=0;

flag=1;

x=in.nextInt();

if(x>1 && x<=1000000000)

{

int a[]=new int[x];

for(i=0;i<x;i++)

{

a[i]=i+1;

}

while(flag==1)

{

for(c=1;c<x;c=c+2)

{

a[m]=a[c];

m++;

}

if(m==1)

{flag=0;

break;}

else

{

x=m;

m=0;

continue;

}

}

System.out.println(a[0]);

}

else if(x==1)

System.out.println(x);

}

}

}

}

hey got a idea!!

 

Can some1 submit a solution in php, perl , java (watever makes the following possible... ) to write the test cases of any specific problem to a file present in any server .. :D

Full Nulled Script English & Arabic Scripts

 

#include<iostream.h>
int main()
{int ban,mug,test;
int a[20],i=0,p=0,l=0;int m[100];
cin>>test;
while(test)
{cin>>ban>>mug;
while(ban)
{cin>>a[i];
i++;
ban--;}
i--;
while(i+1)
{p=p+a[i];
i--;
}
if(p==mug)
m[l]=1;
else
m[l]=0;
test--;i=0;p=0;l++;}
i=l;
l=0;
while(l!=i)
{if(m[l]==1)
cout<<"Yes";
else
cout<<"No";
cout<<"n";
l++;}
return 0;
}

 

 

it's ok

can anybody help me wid this? i get wrong answer though it's working fine wid my gcc compiler!

thanx...!

/*paying up*/
#include<stdio.h>
int main(){
unsigned int i,j,flag,k,sum,inputs,m,n,notes[20];
scanf("%d",&inputs);
for(i=0;i<inputs;i++){
scanf("%d%d",&n,&m);
for(j=0;j<n;j++)scanf("%d",&notes[j]);
for(j=0;j<(1<<n);j++){
sum=0;
flag=0;
for(k=0;k<n;k++){
if((j&(1<<k))>0)
sum+=notes[k];
}
if(sum==m){
flag=1;
break;
}
}
if(flag)printf("Yes");
else printf("Non");
}
return 0;
}

please someone help me with the code... I don't understand what's the problem

 

#include<stdio.h>

#include<math.h>

 

long binary[105000][21],input[21];

long i,j,n,m,nn,it1,it2,p,sum;

 

int main(){

freopen("input.txt","r",stdin);

scanf("%ld",&nn);

for(it1=0; it1<nn; it1++){

scanf("%ld %ld",&n, &m);

for(it2=0; it2<n; it2++)scanf("%ld",&input[it2]);

 

for(i=1; i<pow(2,n); i++){

p=i;

for(j=0; j<n; j++){

binary[i][j]=p%2;

p=p/2;

}

}

 

for(i=1; i<pow(2,n); i++){

sum=0;

for(j=0; j<n; j++){

if(binary[i][j]>0){

sum = sum+input[j];

if(sum == m){

printf("Yesn");goto end;

}

}

}

}

printf("Non");

end: continue;

}

return 0;

}

@Admin

I have a perfectly working DP solution for the problem, but still it is giving wrong answer. Can you post some test cases apart from the ones given in the problem?

Why do we need 7 seconds for?

Are we going to check all possibilities?

Hey Everyone,

Its working fine on my computer but the compiler shows "RUNTIME ERROR"....

My sol. is -> http://www.codechef.com/viewsolution/357265

Please tell me whats going wrong!!!

What is the largest index of b you access?

What is the largest index of b you can access?

@Stephen - Thank you very much...I got it...

admin-

please check for any error in my code...!!!

i am not able to get hold of it!!!

the sumbission id is -- 362123

--thank you

im gving an example.can any1 tell me whats wrong with it?

 

#include <iostream>
using namespace std;
int main()
{
int a[2] = {1,2};
int sum = 0;
for(int i=1;i<4;i++)
{   
sum = 0;
for(int j=0;j<2;j++)
{
if(i&(1<<j)!=0)
{
sum += a[j];
}
}
cout << sum <<" ";
}
}

You aren't meant to hardcode a test case in your program, you're meant to read it from standard input! Read the FAQ.

var

t:integer;

nb:integer;

m:integer;

bc:integer;

b:array [1..25] of integer;

r:array [1..100] of boolean;

l:integer;

z,y:integer;

function grd(n,i:integer):boolean;

var x,temp:integer;

bo:boolean;

begin

temp:=n-b[i];

if temp<0 then

grd:=false

else if temp=0 then

grd:=true

else

begin

x:=i-1;

bo:=false;

while (x>0) and (not bo) do

begin

bo:=grd(temp,x);

x:=x-1;

end;

grd:=bo;

end;

end;

function chk(i:integer):boolean;

var

x:integer;

temp:boolean;

begin

temp:=false;

x:=i;

while (x>0) and (not temp) do

begin

temp:=grd(m,x);

x:=x-1;

end;

chk:=temp;

end;

begin

readln(t);

for z:=1 to t do

begin

readln(nb,m);

l:=0;

for y:=1 to nb do

begin

readln(bc);

if bc<=m then

begin

l:=l+1;

b[l]:=bc;

end;

end;

r[z]:=chk(l);

end;

for z:=1 to t do

if r[z] then

writeln('Yes')

else

writeln('No');

end.

@Admin: My solution is working fine with the provided test cases and I think it should work fine with any possible test case, still I am getting Wrong Answer. Pleaes provide me with the test case on which my solution is failing. Have a look at my solution here: http://www.codechef.com/viewsolution/406574

If you can figure out any mistake from looking at the solution, it'll be of a great help.

1
2 1
2 1

@Stephen: You drive everyone crazy!!! You are the BOND! Thank you so much!!

wat shud be done if n>20 and value>1000.....no clear explanations given in description

The description is very clear.. it tells you that n<=20 and value<=1000 always.

@admin: i ve checked all the test cases and followed the tutorial but still i am getting runtime error. please look at my code and tell me where i am using memory.

url: http://www.codechef.com/viewsolution/435048

I am facing same problem for my other solution. Pls help me.

@admin m getting wrong answer please help!!

#include<stdio.h>
#include<conio.h>
main()
{
int t,a[25],m,s,u,j,n,temp,y,i,v;
scanf("%d",&t);
while(t>0)
{

s=0;
scanf("%d",&n);
scanf("%d",&m);
for(y=1;y<=n;y++)
scanf("%d",&a[y]);
for(i=1;i<n;i++)
{

for(v=i+1;v<=n;v++)
{
if(a[v]<a[i])
{
temp=a[i];
a[i]=a[v];
a[v]=temp;
}
}
}
for(u=n;u>0;u--)
{
for(j=u;j>0;j--)
{
if(s+a[j]>m)
continue;
if(s+a[j]<m)
s+=a[j];
else
{
s+=a[j];
break;
}
}//j
if(s==m)
break;
s=0;
}// u

if(s==m)
{
printf("Yesn");
}
else
printf("Non");
t--;

}
getch();
}

it was n   but it shows Non  WHY

back slash n

Because, like the FAQ says, you aren't supposed to post code here.

@ stephen plz go through the code and pleeez tell me y its nt woking in code chef

it works on my pc

@ stephen the faq tells about testing a code using a txt file

java test < in.txt > out.txt

or

test.exe < in.txt > out.txt

 

I USE C I DONT KNOW JAVA HELP

@ STEPHEN OR TELL me the command for doing this

@stephen we are told here to write a code for say t cases

now what i do is print the output for every case as soon as the output is calculated (u can see that in the code post above)

OR PLEASE SUGGEST

another approach is to store all outputs and in the end display them....

@stephen i got it READ THE FAQ BUT HELP ME WITH THE CODE POSTED @admin provide something to delete the posts

Is the DP approach not good for this problem?

I have implemented DP and it is giving "Time Limit Exceeded" :(

or i will try tutorial's approach.

Hi, I have used recursion in my program. Though it is giving correct results, on submission it gives "Time Limit Exceeded". I have read the tutorial, and their runtime is O(2^n) which is very large, while i have implemented a polynomial algo, i am getting time limit error. Please point out my error. Here is the code http://www.codechef.com/viewsolution/483085 I don't understand how the tutorial's algo is working under the time limit, we have 2^20 subsets, and it need a huge calculation. :(

Umm, i really think my logic and solution is correct. Can somebody please check my solution ?

http://www.codechef.com/viewsolution/491186

Help will be appreciated

 

 

Thanks :D

Solved it. Thanks anyways :)

hi, I submitted this. But I am getting a "wrong answer". Can anyone please tell me what's wrong with my program?

 

#include<stdio.h>

#include<math.h>

 

int main()

{

int m, n, sum;

int notes[30], test[30];

int i, j;

int count=0, t, k;

scanf("%d", &t);

while(count<t)

{

scanf("%d %d", &n , &m);

for(k=0; k<n; k++)

{

scanf("%d", &notes[k]);

}

for(j=1; j<pow(2, n); j++)

{

sum=0;

for(i=0; i<n; i++)

{

if((unsigned)j & (0x1<<i))

{

sum = sum + notes[i];

}

}

if(sum==m)

{

test[count]=1;

}

}

count++;

}

for(k=0; k<t; k++)

{

if(test[k] == 1)

printf("Yesn");

else

printf("Non");

}

return(0);

}

please help me

i am getting runtime error

http://www.codechef.com/viewsolution/509357

but in my compiler i m getting all answers are correct

please somebody help me

@Admin:

Here is my solution.....it works fine for all the given testcases (plus 3/4 more that i designed on my own)...can you please tell me why its showing wrong answer? Thanks a lot

http://www.codechef.com/viewsolution/519056

 

@Admin and @Stephen

Posting for the 1st time. Please if you people can tell me some test case where my solution would fail. The submission link is:

http://www.codechef.com/viewsolution/528086

Got the test case where my solution would fail:

4 7

1 3 3 5

More importantly figured out the classical theoretical mistake of my solution :)

can anybody find problem with this code.It is giving right output in dev c. but showing wrong answer here //Paying up #include int main() { int t,sum,d[21],i,j,l,n,m,a=1; // n=number of notes ,d=array of notes // m=money to match scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0;i

please can anybody check out my code it is satisfying all the test cases that i am running... but on submission it is giving wrong answer,.... import java.io.*; import java.lang.*; class March1 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw = new PrintWriter(System.out,true); int a=0; int b=0; boolean bool = false; int n = Integer.parseInt(br.readLine()); for(int i=0;i=i+1;l--) { if(sum + m[l]

0 0 Yes 0 1 No 1 0 0 Yes 1 0 1 Yes 0 5 No 4 7 1 3 3 5 Yes 4 15 5 5 5 6 Yes 5 9 5 8 4 16 20 Yes Here are my some of tries.But eventually i get wrong answer when i submit.

my algorithm fails at this: 4 20 4 6 9 10 answer should be 'Yes' as 10+6+4.Someone else has stated it before on forums.I wanted to enter it here if it helps other ones whose algorithm fails too.

I am using the bitset for this and it times out in C++. Can it be improved using somw way by following an approach similar to the tutorial? My solution is here: http://www.codechef.com/viewsolution/596281

I am getting a WA can anyone help.. it runs for 0 0 YES 1 0 YES 0 1 N0 code is here http://www.codechef.com/viewsolution/624002

Note for C++ Users: If you want to follow the permutation technique explained in the tutorial, take a look at "next_permutation ()" in the header "algorithm" for fast permutation generation.

hi , i solved the problem as explained in tutorial by finding all subsets . can someone explain dynamic approach or any optimum approach for it. thanks in advance .

Everytime I am submitting a solution, I am encountering runtime error. @Admin, please help me if you can, by letting me know the exact cause of the error. here is the link to my solution http://www.codechef.com/viewsolution/739791 it is working fine in my computer.

package trial; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Trial { public static boolean sum (int[] notes,int a,int m) { if (notes[a]==-1) return false; if (notes[a]==m) return true; if (notes[a]0) Arrays.sort(notes,0,n-1); if(sum(notes,0,m)) System.out.println("Yes"); else System.out.println("No"); } } catch (Exception e) { System.err.println("Error:" + e.getMessage()); } } }

@admin please give the test case for which i failed. I really want to do this correctly. please see program id 797852 http://www.codechef.com/viewsolution/797852 if m = 0 then i think since n=0 means beating up then No should come also no subset of my bank notes can make 0 can we have null sub set ?