Hello,

The problem “Paying Up” was one of the easy ones in the March 2009 contest on Codechef. It is considered an easy problem, because it has a couple of approaches that work. The problem statement boils down to finding a subset of banknotes such that their sum is exactly equal to a certain value. Now, this problem is somewhat similar to the knapsack problem which asks for ways to fill up a knapsack of a certain size optimally with the given blocks. There is a solution based on dynamic programming for this problem, but we will be taking up a solution which makes good use of the way integers are represented in binary to solve this problem.

Now, the limit on the number of banknotes is ‘n’. Let us see how many subsets exist for these banknotes. For finding the number of subsets, we see that for every banknote, we have two choices, either to choose it in our calculation for the sum of notes or to ignore it in calculating the sum. Thus, we have 2 options per banknote and ‘n’ banknotes. So, the total number of subsets thus becomes 2^n where ^ represents the power operation. The number of subsets are small enough for us to bruteforce through them and the program to run in time.

An interesting way to generate all subsets of ‘n’ objects when ‘n’ is considerably small (n <= 20) is to use the properties of how unsigned integers are stored. Consider the number 2^n. This number is represented in binary form as ‘10000…0’, that is, 1 followed by n 0s. Also, any number containing a 1 at the same position will surely be greater than 2^n. Thus, all numbers below 2^n do not have a 1 in a position greater than or equal to ‘n’ starting from the LSB. By induction, we can do the same for values of n = n-1 and n-2 and so on. Thus, we can see that any number between 2^(n-1) and 2^n will have a 1 in the position n-1. Extending this logic, we can say that if we consider the numbers from 1 to 2^n, we would be considering all possible ways in which we can choose some objects from ‘n’ objects.

For example, consider n = 3, so 2^n = 8. Let us list ‘i’ and its binary representation

i Binary representation using ‘n’ bits

0 000

1 001

2 010

3 011

4 100

5 101

6 110

7 111

As you can see, if we consider that 1 means that we have selected object at that position and 0 means that we have not selected the object at that position, we can get all possible subsets of ‘n’ objects by looping over numbers from 1 to 2^n.

For calculating the sum of the subset represented by ‘i’, we loop from 0 to ‘n’ and we check whether the corresponding bit is set in the value for ‘i’ or not. If it is, we include that object in calculating our sum else we don’t. In this way, we can get the sum for all possible subsets of the ‘n’ objects.

This is exactly what we need for this problem. After taking in the number of objects, we loop ‘i’ from 1 to 2^n incrementing the value of ‘i’ by 1 at every stage to give us a new subset. Then for a particular value of ‘i’, we loop ‘j’ from 0 to n and check if the bit at that particular value is set or not. Languages like C / C++ provide bit-wise operators for leftshift and rightshift. For checking if the bit is set at position ‘j'(starting from 0) we can just check if the value of (i & (1<<j)) is 0. If it is 0, then the bit is not set, while if it is greater than 0, then the bit is set. Alternatively, we can also loop from 0 to n and at each stage check whether ‘i’ modulo 2 is equal to 1 or not. If it is 1, then the bit at that position is set, else it’s not. Then we divide ‘i’ by 2 and proceed. At the end of the ‘n’ iterations, ‘i’ will equal 0. The problem with this appraoch is that the modulo operations take much more time compared to the bitwise operations. Thus, now that we know how to check if the bit is set, we initialize a value ‘sum’ equal to 0 at the start of the ‘n’ iterations for a value of ‘i’ and if the bit at position ‘j’ is set, we add the corresponding banknote value to ‘sum’ else we don’t. At the end of these iterations, we check if the value of ‘sum’ equals the required value. If it does, then we have found a subset with the required sum and so we print a “Yes” and exit. Else, if at the end of 2^n iterations of ‘i’ we don’t have a subset with the required sum, then we print a “No” and exit.

The program should look something like this :

Start

Take in the value of 'n' and the required value of sum 'm'

Take in all the values for the banknotes in array 'd[]'

For i = 1 and i < (2^n)

sum = 0

For j = 0 and j < n

if jth bit of i is set

sum = sum + d[j]

if sum equals m

print Yes and return

Print No and return

Good tutorials always are welcome, but the code template doesn’t appear clear on Firefox 3.5 (it happened the same with the before tutorial.

It’s easy what I may do to see it right, however I think it’s a usability problem that should be fixed easily (w/CSS).

Kind Regards

German

Good tutorials always are welcome, but the code template doesn’t appear clear on Firefox 3.5 (it happened the same with the before tutorial.

It’s easy what I may do to see it right, however I think it’s a usability problem that should be fixed easily (w/CSS).

Kind Regards

German

code appears properly on safari

code appears properly on safari

This is fixed. Thanks for pointing it out.

This is fixed. Thanks for pointing it out.

thanks 4 d tutorial…itz helpin newbies like me 2 get 2 kno better ways….pls keep on postim more!!!

thanks 4 d tutorial…itz helpin newbies like me 2 get 2 kno better ways….pls keep on postim more!!!

Gr8 one sir! ! !

Gr8 one sir! ! !

Thanks a lot for tutorials.Its like a guide to newbies for getting accustomed to the problems…

keep posting them.

regards..

Thanks a lot for tutorials.Its like a guide to newbies for getting accustomed to the problems…

keep posting them.

regards..

I have another solution for this problem……

We can find all possible additions and store it in another array and compare the sum with each element

Let me give u an example…..

lets have 3 banknotes as 2,4,7 so possible combinations are 2,4,6,7,9,11,13 which we will store in another array

here is the algo for it

1.Start

2.Accept the value of n and m

3.Accept all values of banknotes in an array a[]

4.declare an array b[] having first element initialised as 0 i.e. b[0]=0

5.set flag=0 and top=0

//here top is used as continuous insertion of

//elements in b[] and flag is used to add all

//elements in b[] with a new banknote and store

//it further in b[]

6.for i=0 till i<n incremented each time by 1

7. for j=0 till j<=flag incremented each time by 1

8. top=top+1 , b[top]=a[i]+b[j]

9. flag=top

10.Now compare each element of b[] with m and print

yes if search is successful otherwise no

11.End

The above algo can be modified depending upon the problem…….

this is awesome solution..thanks,man

Awesome solution

I have another solution for this problem……

We can find all possible additions and store it in another array and compare the sum with each element

Let me give u an example…..

lets have 3 banknotes as 2,4,7 so possible combinations are 2,4,6,7,9,11,13 which we will store in another array

here is the algo for it

1.Start

2.Accept the value of n and m

3.Accept all values of banknotes in an array a[]

4.declare an array b[] having first element initialised as 0 i.e. b[0]=0

5.set flag=0 and top=0

//here top is used as continuous insertion of

//elements in b[] and flag is used to add all

//elements in b[] with a new banknote and store

//it further in b[]

6.for i=0 till i<n incremented each time by 1

7. for j=0 till j<=flag incremented each time by 1

8. top=top+1 , b[top]=a[i]+b[j]

9. flag=top

10.Now compare each element of b[] with m and print

yes if search is successful otherwise no

11.End

The above algo can be modified depending upon the problem…….

i forgot to add that step 8 is inside inner for and step 9 is inside outer for i.e.

step 6

{

step 7

{

step 8

}

step 9

}

i forgot to add that step 8 is inside inner for and step 9 is inside outer for i.e.

step 6

{

step 7

{

step 8

}

step 9

}

Please don’t post code in the comments section on the blog. Post your doubts on the problem page and not here.

in case where n=20, a loop from i=1 till i<(2^20) takes too much time, doesn't it?

2^20 is approx 10^6, so it will pass within 1 sec … 🙂

2^20 is approx 10^6 . how u can say

becuase 2^32 is less than 10^9

And there are 100 testcases as well..

import java.util.Scanner;

class Immutable{

public static void main(String[] args){

Scanner s = new Scanner(System.in);

int t = s.nextInt();

while(t– > 0){

int n = s.nextInt();

int m = s.nextInt();

int[] arr = new int[n];

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

arr[i] = s.nextInt();

}

int i = 0;

for( ; i < (int)Math.pow(2, n); i++){

int sum = 0;

String check = Integer.toBinaryString(i);

for(int j = 0;j = (int)Math.pow(2, n))

System.out.println(“No”);

}

}

}

Instead of checking the bit using the shift operator, I am doing it by first converting the number i to a binary String and then iterating each character of the string and if the character is ‘1’ I am adding it to the sum….this program shows correct output for the sample case but it shows WA..can anyone please tell what is the flaw in this method….

I am not getting the logic behind including the object in the sum based on the decision that corresponding bit for ‘i’ is set or not. It will be really kind if someone explain me that

1st banknote is assigned to LSB (let’s say) ,2nd note assigned to 2nd bit from left and so on..the logic is , in order to consider all the subsets that can be formed using these ‘n’ banknotes ,they are assigned to some bit in the n-bit number and we’ll iterate from 1 to 2^n . Now, if ‘i’th bit is set implies we’ll consider the corresponding banknote in our subset and add it to our sum.

Hope this clearifies..

@disqus_iZPpYTsCbQ:disqus @samjoearmy:disqus Can you explain with a example. The example in the post is too vague for me to understand at this point.

Think of it as a binary number. If we have 3 elements, then think of numbers as: 000, 001, 010 , 011, 100, 101, 111 these are the only 2^3 possibilities. Now we make a subset of elements where the number is set at 1. So actually we took care of all subsets. Combinatorially, each place in array has either to come in the subset or not. So two possibilites for every N. Thus a total of 2^N.

Please help me in getting rid of the TLE!!!

I think the logic is correct as per the editorial.

#include

#include

int main() {

// your code goes here

int t,n,m,i,a[21],s,j,b,c;

scanf(“%d”,&t);

while(t–)

{

scanf(“%d%d”,&n,&m);

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

scanf("%d",&a[i]);

b=pow(2,n);

c=0;

for(j=0;j

>=1;i++;

}

if(s==m)

{

c=1; break;

}

}

if(c)

printf(“yesn”);

else

printf(“non”);

}

return 0;

}while reading inputs there is no point in reading > m and == 0. some optimization. 🙂 nice problem though.

Can someone please explain me the meaning of the statement

i & (1<<j)

please help me in getting the correct answer for test case

n=6 m=8

1,2,9,11,13,22,25

i have used some different logic max test cases are passing except the above one….

#include

#include

int main()

{

int t,n,m,a[100000],k,i,j,temp,flag,flag1;

scanf(“%d”,&t);

while(t>=1)

{

scanf(“%d”,&n);

scanf(“%d”,&m);

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

{

scanf("%d",&a[i]);

}

k=1;

while(k<=n-1)

{

for(j=0;ja[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

k++;

}

flag=m;

while(flag>0)

{

for(i=0;iflag)

{flag1=0;

break;

}

else if(a[i]==flag)

{

flag1 =flag;

break;

}

else

{

flag1=0;

c++;}

}

if (flag1!=0)

{

printf(“YES”);

break;

}

if(c==1)

{

if(flag!=a[c-1])

{

printf(“NOn”);

break;

}

else

{

printf(“YESn”);

break;

}

}

else if (c==0&&a[0]!=flag)

{

printf(“NO”);

break;}

else

{

flag=flag-a[c-1];

}

}

t–;

}

return 0;

}

while(t>0){

int n,m,j;

cin>>n>>m;

int a[n];

for(int i=0;i>a[i];

sort(a,a+n,greater());

int sum=0;

for(j=0;jm)

continue;

if(a[j]==m)

{

cout<<"Yes"<<endl;

break;

}

else if(a[j]<m)

{

m=m-a[j];

}

}

if(j==n)

cout<<"No"<<endl;

t–;

}

why my code shows wrong answer ,passed all given test cases !!

What it means by saying “if jth bit of i is set?? Can someone please explain

is set maens it is 1 or selected.

Please tell me why I am getting wrong answer ? This code passed all sample test cases

import sys

def pay():

n, total = map(int,raw_input().split())

notes = []

for j in range(n):

x = input()

if(x>total):

continue

else:

notes.append(x)

notes.sort(reverse = True)

for k in xrange(len(notes)):

summ = notes[k]

for m in xrange(k+1,len(notes)):

if(summ>total):

summ -= notes[m-1]

summ += notes[m]

else:

summ += notes[m]

if(summ==total):

return ‘Yes’

return ‘No’

t = input()

for i in range(t):

y = pay()

print y

Can Someone please explain me the Example

For example, consider n = 3, so 2^n = 8. Let us list ‘i’ and its binary representation

i Binary representation using ‘n’ bits

0 000

1 001

2 010

3 011

4 100

5 101

6 110

7 111

As you can see, if we consider that 1 means that we have selected object at that position and 0 means that we have not selected the object at that position, we can get all possible subsets of ‘n’ objects by looping over numbers from 1 to 2^n.

What are the 2 subset the Post is mentioning over here.

I’m not able to figure out which subset will it form my assumption is

(000, 001, 010, 011) and (100, 101, 110, 111) based on n(i.e) position value.

is that correct ?

If I’m correcting woudn’t that be slower then comparing directly with n < 3

//GIVING WRONG ANSWERS. BUT ALL TESTCASES ARE PASSED //AND ANY RANDOM CASE IS ALSO CORRECT. PLEASE HELP.

#include

int main()

{

int t;

scanf(“%d”,&t);

while(t–)

{

int n,sum,i,flag,t;

x:

scanf(“%d %d”,&n,&sum);

int a[n];

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

{

scanf("%d",&a[i]);

}

if(sum==0){printf("Yesn");

goto x;}

flag=0;

while(flag==0)

{

flag=1;

for(i=0;ia[i+1])

{

t=a[i];

a[i]=a[i+1];

a[i+1]=t;

flag=0;

}

}

}

for(i=n-1;i>=0;i–)

{

if(sum-a[i]>=0)

{

if(sum-a[i]>0)

{

sum=sum-a[i];

}

else{printf(“Yesn”);

flag=0;

break;}

}

}

if(flag!=0)

printf(“Non”);

}

return 0;

}

why following code is giving wrong answer please anyone help???

#include

#define ll long int

using namespace std;

int main()

{

int t;

cin>>t;

while(t–)

{

int n;

ll m;

cin>>n>>m;

int a[n];

for(int i=0;i>a[i];

}

int flag=0;

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

{

ll sum=0;

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

{

if(((i)&(1<<j))==1)

{

sum+=a[j];

}

}

if(sum==m)

{

flag=1;break;

}

}

if(flag==1)

{

cout<<"Yes"<<endl;

}

else

{

cout<<"No"<<endl;

}

}

return 0;

}

why is this program giving wrong answer

#include

using namespace std;

char f(int a[20],int no,int n);

void generatesubsets(int a[20],int n,int k);

int main()

{

int t;

cin>>t;

while(t>0)

{

int n,k;

cin>>n>>k;

int a[n];

for ( int i=0;i>a[i];

generatesubsets(a,n,k);

t–;

}

return 0;

}

void generatesubsets(int a[20],int n,int k)

{

int range=(1<<n)-1;

char c='n';

for( int i=0;i<=range;i++)

{ c=f(a,i,k);

if(c=='y')

break;}

if(c=='y')

cout<<"Yes"<<endl;

else cout<<"No"<0)

{

if(no&1)

x+=a[i];

i++;

no=no>>1;

}

if(x==k)

{

return(‘y’);

}

}

I have used dp to solve this problem

But getting TLE error

Any idea whats wrong in this?

#include

using namespace std;

int main() {

// your code goes here

unsigned int T,N,s,i,j;

cin>>T;

while(T–)

{

cin>>N>>s;

unsigned int A[N];

for(i=0;i>A[i];

bool dp[N+1][s+1];

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

dp[i][0]=true;

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

{

dp[0][i]=false;

}

for(i=1;i<=N;i++)

{

for(j=1;j<=s;j++)

{

if(j<A[i-1])

dp[i][j]=dp[i-1][j];

else

dp[i][j]=dp[i-1][j] || dp[i-1][j-A[i-1]];

}

}

if(dp[N][s])

cout<<"Yesn";

else

cout<<"Non";

}

return 0;

}

I got same error if you got then plz tell .

thanks

my code is correct and output getting also correct ,though i get wrong answer,why?

t=int(input())

for s in range(t):

n,m=map(int,input().split())

lst=[]

for i in range(n):

x=int(input())

lst.append(x)

l=len(lst)

import itertools

def subset(lst,l):

v=[]

for i in range(1,l+1):

lt=list(map(list,itertools.combinations(lst,i)))

v.extend(lt)

return v

k=0

for i in subset(lst,l):

sum=0

for j in i:

sum+=j

if(sum==m):

k=1

break

if(k==1):

print(‘yes’)

else:

print(‘no’)