Paying upProblem code: MARCHA1 |
A tutorial for this problem is available here
The following problem appeared in the CodeChef March '09 Challenge
In the mysterious country of Byteland, everything is quite different from what you'd normally expect. In most places, if you were approached by two mobsters in a dark alley, they would probably tell you to give them all the money that you have. If you refused, or didn't have any - they might even beat you up.
In Byteland the government decided that even the slightest chance of someone getting injured has to be ruled out. So, they introduced a strict policy. When a mobster approaches you in a dark alley, he asks you for a specific amount of money. You are obliged to show him all the money that you have, but you only need to pay up if he can find a subset of your banknotes whose total value matches his demand. Since banknotes in Byteland can have any positive integer value smaller than one thousand you are quite likely to get off without paying.
Both the citizens and the gangsters of Byteland have very positive feelings about the system. No one ever gets hurt, the gangsters don't lose their jobs, and there are quite a few rules that minimize that probability of getting mugged (the first one is: don't go into dark alleys - and this one is said to work in other places also).
Input
The first line contains integer t, the number of test cases (about 100). Then t test cases follow. Each test case starts with n, the number of banknotes in your wallet, and m, the amount of money the muggers asked of you. Then n numbers follow, representing values of your banknotes. Your wallet does not hold more than 20 banknotes, and the value of a single banknote is never more than 1000.
Output
For each test case output a single line with the word 'Yes' if there is a subset of your banknotes that sums to m, and 'No' otherwise.
Example
Input: 5 3 3 1 1 1 5 11 1 2 4 8 16 5 23 1 2 4 8 16 5 13 1 5 5 10 10 20 132 17 6 4 998 254 137 259 153 154 3 28 19 123 542 857 23 687 35 99 999 Output: Yes Yes Yes No Yes
Explanation: For example, in the last case you have to pay up, since: 6+3+123=132.
| Date: | 2009-03-17 |
| Time limit: | 7s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
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 :)
Hi Guys, Am getting WA.
#include <algorithm>
#include <cmath>
#include<cstring>
#include <list>
#include <iterator>
{
int sum=0;
for(int i=0;i<noc;i++)
{
if(index & (1<<i))
{
sum+=a[i];
}
}
return sum;
}
{
int t,i,j,noc,mon;
cin>>t;
while(t–)
{
bool found=false;
cin>>noc;
cin>>mon;
int c[noc];
for(i=0;i<noc;i++) {cin>>c[i];}
int start=0,end=(int)pow(2,(float)noc);
{
int val=cal(c,noc,start);
if(val==mon) {found=true;break;}
start++;
}
else cout<<”No”;
}
//cin>>t;
return 0;
}
1. /*sorry guys..
#include<iostream>
#include <algorithm>
#include <cmath>
#include<cstring>
#include <list>
#include <iterator>
{
int sum=0;
for(int i=0;i<noc;i++)
{
if(index & (1<<i))
{
sum+=a[i];
}
}
return sum;
}
{
int t,i,j,noc,mon;
cin>>t;
while(t–)
{
bool found=false;
cin>>noc;
cin>>mon;
int c[noc];
for(i=0;i<noc;i++) {cin>>c[i];}
int start=0,end=(int)pow(2,(float)noc);
{
int val=cal(c,noc,start);
if(val==mon) {found=true;break;}
start++;
}
else cout<<”No”;
}
//cin>>t;
return 0;
}
The pow() function is not
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
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
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
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
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
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
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
@tryingtocode Such a case will not be there in the input
don't you think we should get
Of course you shouldn't be
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
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
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
Please read the tutorial for this problem
can the value of a banknote
can the value of a banknote be 0 ?
hello guyz... take into
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
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
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
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",¬es[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
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
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?
it's printf("No\n") and
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
i may have asked something really silly...but someone please help..
Well, your code will
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
i know...thank you so much...i misunderstood the problem...should have read the tutorial first...
can smone fnd error in my
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
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
what does the Source limit 50000 means
is it 50000 byte or something else
@ Dal - the problem statement
@ Dal - the problem statement tells you n can be at most 20.
@ Shaurya - yes.
What's wrong in this
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
oh!! sorry i figure out my problem..
Tell me what's the 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
It is showing that my programme compiled successfully,but lacks the desired output
if we have a note that
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
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.