<pre>
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader s= new BufferedReader(new InputStreamReader(System.in));
int n;
n=Integer.parseInt(s.readLine());
for(int t=0;t<n;t++){
String[] m;
m=s.readLine().split(" ");
int value=Integer.valueOf(m[1]);
int[] v=new int[Integer.valueOf(m[0])];
int pa=Integer.valueOf(m[0]);
if(Integer.valueOf(m[0])>20)
{
break;
}
for(int i=0;i<Integer.valueOf(m[0]);i++){
int cv =Integer.parseInt(s.readLine());
if(cv>1000){
break;
}else{
v[i]=cv;
}
}
Arrays.sort(v);
boolean ca=false;
for(int i=1;i<=Math.pow(2,pa);i++){
int sum=0;
for(int j=0;j<pa;j++){
if((i & (1<<j))!=0){
sum=sum+v[j];
}
if(sum==value){
ca=true;
break;
}
}
if(sum==value){
ca=true;
break;
}
}
if(ca==true){System.out.println("Yes");}else{System.out.println("No");}
}}}
</pre>
Check for the inputs
2
1 2
1
3 7
1
2
3
Both the cases are giving “Yes”. But answers should be “No”. And one wrong thing I find in your program is, you are adding v[i - 1]th
term twice to sum in every iteration. You are taking sum = v[i], and in every loop of j, you start adding from v[i] again, so its adding up twice.
EDIT: Since you changed the code but still getting WA, here is another case it fails…
7 112
14
21
33
40
54
65
76
Answer should be “Yes” (14+33+65 = 112). But your code outputs “No”. link
I advice you take help of editorial when you are stuck on some problem for long time.
at last solution accepted…thank you all for the support…@vinayawsm ,@kunal361, @shubhamsingh.sky
#include
#include
using namespace std;
bool l_subsetOfMoneyFlag = false;
bool check_subset_Money(std::vector &p_obj,int position,int &p_numberOfNotes_n,int &p_moneyAsked_n,int p_prevSubsetValue);
int main()
{
int l_testcases_n;
cin>>l_testcases_n;
while(l_testcases_n–)
{
int l_numberOfNotes_n,l_moneyAsked_n,l_eachMoneyValue;
cin>>l_numberOfNotes_n>>l_moneyAsked_n;
vector l_moneyDetails;
l_moneyDetails.clear();
for(int i=0;i<l_numberOfNotes_n;i++)
{
cin>>l_eachMoneyValue;
l_moneyDetails.push_back(l_eachMoneyValue);
}
int l_tempSubSetMoney;
l_subsetOfMoneyFlag = false;
for(int i = 0;i<l_numberOfNotes_n;i++)
{
if(true == check_subset_Money(l_moneyDetails,i,l_numberOfNotes_n,l_moneyAsked_n,0))
{
l_subsetOfMoneyFlag = true;
break;
}
}
if (true == l_subsetOfMoneyFlag) {
cout<<endl;
cout<<“Yes”;
}
else
{
cout<<endl;
cout<<“No”;
}
}
return 0;
}
bool check_subset_Money(std::vector &p_obj,int position,int &p_numberOfNotes_n,int &p_moneyAsked_n,int p_prevSubsetValue)
{
int l_prevSubSetValue = p_prevSubsetValue;
if(p_moneyAsked_n == l_prevSubSetValue+p_obj[position])
return true;
for(int i=position;i<p_numberOfNotes_n;i++)
{
if(true == check_subset_Money(p_obj,i+1,p_numberOfNotes_n,p_moneyAsked_n,(l_prevSubSetValue+p_obj[position])))
{
return true;
}
}
return false;
}
can anybody tell me what is wrong in that code?
#include
#include
using namespace std;
bool l_subsetOfMoneyFlag = false;
bool check_subset_Money(std::vector &p_obj,int position,int &p_numberOfNotes_n,int &p_moneyAsked_n,int p_prevSubsetValue);
int main()
{
int l_testcases_n;
cin>>l_testcases_n;
while(l_testcases_n–)
{
int l_numberOfNotes_n,l_moneyAsked_n,l_eachMoneyValue;
cin>>l_numberOfNotes_n>>l_moneyAsked_n;
vector l_moneyDetails;
l_moneyDetails.clear();
for(int i=0;i<l_numberOfNotes_n;i++)
{
cin>>l_eachMoneyValue;
l_moneyDetails.push_back(l_eachMoneyValue);
}
int l_tempSubSetMoney;
l_subsetOfMoneyFlag = false;
/for(int i=0;i<l_numberOfNotes_n;i++)
{
l_tempSubSetMoney = 0;
l_tempSubSetMoney = l_tempSubSetMoney+l_moneyDetails[i];
for(int j=i;j<l_numberOfNotes_n;j++)
{
l_tempSubSetMoney = l_tempSubSetMoney+l_moneyDetails[j];
if(l_tempSubSetMoney == l_moneyAsked_n)
{
l_subsetOfMoneyFlag = true;
break;
}
}
if(l_subsetOfMoneyFlag == true)
break;
else
{
if(l_moneyDetails[i] == l_moneyAsked_n)
{
l_subsetOfMoneyFlag = true;
break;
}
}
}/
for(int i = 0;i<l_numberOfNotes_n;i++)
{
if(true == check_subset_Money(l_moneyDetails,i,l_numberOfNotes_n,l_moneyAsked_n,0))
{
l_subsetOfMoneyFlag = true;
break;
}
}
if (true == l_subsetOfMoneyFlag) {
cout<<endl;
cout<<“Yes”;
}
else
{
cout<<endl;
cout<<“No”;
}
}
return 0;
}
bool check_subset_Money(std::vector &p_obj,int position,int &p_numberOfNotes_n,int &p_moneyAsked_n,int p_prevSubsetValue)
{
int l_prevSubSetValue = p_prevSubsetValue;
if(p_moneyAsked_n == l_prevSubSetValue+p_obj[position])
return true;
for(int i=position;i<p_numberOfNotes_n;i++)
{
if(true == check_subset_Money(p_obj,i+1,p_numberOfNotes_n,p_moneyAsked_n,(l_prevSubSetValue+p_obj[position])))
{
return true;
}
}
return false;
}
can anybod tell me what is wrong in that code for marcha1 problem?
Its seems you are using greedy aproach. This is a very easy problem if u solve it by using vry little concept of dynamic programming . you have n note and money asked my mugger is 'm' , As we can see it is a subset sum problem , so we have to choose some of n notes which gives sum 'm' Acc to my approach , check all the subset if any subset sum is equal to money print "Yes" else print "No" See my solution , its very easy and small
hey @vinayawsm according your input test cases mentioned above my code gives correct output but i am getting “Runtime error” on codechef can u help me?
here is link to ideone:-
it is wrong
I think he knows that…
i know it is wrong …but i dont know where i have made mistake/s…or may be logic is incorrect…please help me solve this…@kunal361…@shubhamsingh.sky
i checked …and made correction to it…but still it shows wrong answer…cant figure out where …above solution is updated solution
Can some one provide some more input?so i could test more …every input i try gives correct answer…may be your input could help me out…
Can some one provide some more input?so i could test more …every input i try gives correct answer…may be your input could help me out…
Best of luck…also please indent your code properly…make it a bit readable…at least before sharing…
@kunal361 thanks for the quick reply…its my 1st question to codechef …will fix the error and make it more readable one…
i updated the solution…but still its wrong…help me with some more input which makes my answer wrong…more input would be better…
i updated the solution…but still its wrong…help me with some more input which makes my answer wrong…more input would be better…