Tutorial for problem “Paying Up”

3 min read

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

India Wins Four Medals At IOI 2020

The 32nd International Olympiads in Informatics 2020 final results are out. All the four finalists from India are bringing back a medal each! A defining...
debanjan321
1 min read

How Amit Upadhyay got placed at Cleartax

At CodeChef, we constantly stay in touch with CCDSAP holders to make the experience better for you and to fine-tune the certification. We spoke...
admin
1 min read

ACM ICPC Kolkata Regionals 2016 – Live Updates

Welcome to ACM ICPC Kolkata Regional 2016, the last leg regional before the India Final! Animesh and I will be giving you live updates throughout...
wittyceaser
2 min read

48 Replies to “Tutorial for problem “Paying Up””

  1. 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

    1. def search(k,m):
      start=0
      end=len(k)-1
      res=-1
      while start<=end:
      mid=start+(end-start)//2
      if k[mid]==m:
      return m
      elif k[mid]0:
      t=search(k,m)
      if t==-1:
      break
      k.remove(t)
      sum=sum+t
      m=m-t
      if sum==r:
      print(“Yes”)
      else:
      print(“No”)

      Why it is not correct

  2. 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

  3. 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…….

    1. please suggest what is incorrect in my code because it is returning all correct outputs corresponding to given inputs but on submitting it returns wrong answer.
      #include
      #include

      using namespace std;

      int main()
      {
      int t,n,m;
      cin>>t;
      while(t–){
      cin>>n>>m;
      int x=m;
      int a[n];
      for(int i=0;i>a[i];
      int sum=0;
      sort(a,a+n);

      for(int i=n-1;i>=0;i–)
      {
      if(a[i]<=x)
      {sum+=a[i];
      x=x-a[i];

      }
      if(sum==m)
      break;

      }
      if(sum==m)
      cout<<"Yes"<<endl;
      else
      cout<<"No"<<endl;

      }
      return 0;
      }

  4. 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…….

  5. 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….

  6. 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

    1. 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..

    2. 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.

  7. 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;

    }

  8. 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;
    }

  9. 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 !!

  10. 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

  11. 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

  12. //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;
    }

  13. 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;
    }

  14. 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’);

    }

    }

  15. 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;
    }

  16. 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’)

  17. #include

    using namespace std;

    bool subset_sum(int arr[], int sum, int n){
    bool dp[n+1][sum+1];
    for(int i=0;i<n+1;i++){
    for(int j=0;j<sum+1;j++){
    if(i == 0)
    dp[i][j] = false;

    if(j == 0)
    dp[i][j] = true;
    }
    }
    for(int i=1;i<n+1;i++){
    for(int j=1;j<sum+1;j++){
    if(arr[i-1] >test;
    while(test–){
    cin>>n;
    cin>>sum;
    int arr[n];
    for(int i=0;i>arr[i];
    bool check;
    check = subset_sum(arr, sum, n);
    if(check == true)
    cout<<"yes"<<"\n";
    else
    cout<<"no"<<"\n";
    }
    }

    this is my dp solution . it passed all the example test cases but still got wrong answer when submited. idk what is the error !

Leave a Reply