Paying up ,MARCHA1 ,Wrong Answer...please help me..

general
, ,
21

#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?

22 
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
1 Like
23

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:-

24

is there anyone who can help me?