You are not logged in. Please login at www.codechef.com to post your questions!

×

Binary Implementation of Paying Up

I just learned the basics of the binary system, but am still struggling to implement this in Java for Paying Up. Looked at other problems and still not understanding the basics.
How do we look at/process the different ways 2^n where n=3 = 8 can be 0 0 0, 0 1 0 ... etc.

These are only 3 digits in this tutorial example - isn't this a byte? and aren't bytes composed of 8 digits?

Also what is really happening when "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"

Below is my basic code with just the input taken care of - I'd really appreciate help figuring out where and how to represent the problem in binary.

Thanks,

public class Main {

public static void main(String[] args)throws java.io.IOException{

    java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    java.io.BufferedWriter out = new java.io.BufferedWriter(new java.io.OutputStreamWriter(System.out));

    int tests = Integer.parseInt(reader.readLine());
    while(tests-->0){
        String[] params = reader.readLine().split(" ");
        int n = Integer.parseInt(params[0]); //quantity of different notes in wallet <= 20
        int m = Integer.parseInt(params[1]); //demanded amount $

        int[] noteValues = new int[n]; //store each distinct note
        for(int i = 0; i < n; i += 1)
            noteValues[i] = Integer.parseInt(reader.readLine());

        if(validSet(noteValues,m))
            out.write("Yes\r\n");
        else
            out.write("No\r\n");
    }
    out.flush();
}
/**check if a set of sorted notes can meet the exact demand.*/
public static boolean validSet(int[] notes, int demand){

    return false;
}

}

asked 06 Jul '14, 14:20

slaynen's gravatar image

2★slaynen
12
accept rate: 0%


The concept used in the tutorial is bitmasking. It is similar to having a visited array where 1 represents the value is present in the set and 0 represents its not present.

E.g. if bitmask = 1011 in binary

The bit at position 0,1,and 3 are 1. So it means 0,1 & 3rd term are in d set.

1 << j = j th bit as 1 (j th item in the set)

So (i & 1 << j) != 0 means the j th bit of i is also 1.

(i & 1 << j) != 0 implies j th item is in the set 'i'

So as per tutorial:

we iterate i from 0 to 2^n (all possible sets)

Then check if j th item is present (( i & 1 << j) != 0) if present add it to sum

Once you have checked for all j values if sum = demand print Yes

If non of the sum is equal to demand print No

link

answered 06 Jul '14, 21:15

abbas's gravatar image

4★abbas
4118
accept rate: 28%

You can look at this Wonderful tutorial.If you have any doubts, comment below.

link

answered 06 Jul '14, 16:39

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61748
accept rate: 10%

I don't know much java but let me help you with the basic idea if I understood your problem right! Correct me if I am wrong.

This type of implementation helps when the input is small(so that 2^n is not large). This situation arises when you have to select items from a collection which will yield a definite sum or something else. For example in this problem you have to select the notes from your wallet which will sum up to certain number. If there 3 items, 110 means you included the first and second items and excluded the third one. You can also look at the link given above (Wonderful Tutorial), it gives a detailed explanation. Hope this helps!

link

answered 06 Jul '14, 16:48

sunny210's gravatar image

2★sunny210
1011512
accept rate: 0%

edited 06 Jul '14, 16:52

thanks for the pointers, i've read this tutorial but i suppose this is my biggest confusion: i understand if the person has 4 notes in his wallet, there are 2^4=16 different combinations of notes we can check to see if it meets the demand. but how are we converting all these numbers into binary?

what are we exactly looping? how is the array (of ints?) initialized? what is the data value type of "0 0 1 0" , i know this equals 2, but how do we know/make sure we are checking every combination?

ex. i would set it up like

for(int i = 1; i < Math.pow(2,n); i += 1){
  int sum = 0;
  for(int j = 0; j < n; j += 1){
    if bit is 1, add sum += corresponding note
  }
  if sum == demand, return true
}
return false

I just don't know how to convert and check all these possible combinations into binary representations and loop them.

link

answered 06 Jul '14, 21:43

slaynen's gravatar image

2★slaynen
12
accept rate: 0%

1

Just use int. Int has 32 bit which can represent 2^32 sets and each set is nothing but a unique number.

We dont convert numbers to binary they are already stored that way.We are using them as it is with the help of bitwise operators like (& |) and shift operators.

Your implementation is right. The variable 'i' represents the set. And to check if corresponding bit is 1 just use (i & 1<<j) != 0 and your code should work.

Also store the value of 2^n and then use it in loop to reduce run time.

(07 Jul '14, 02:31) abbas4★

Thank you everyone for the help; I understand how it works now and submitted a detailed solution in Java ( http://www.codechef.com/viewsolution/4238701 ) for anyone who was curious.

link

answered 07 Jul '14, 02:55

slaynen's gravatar image

2★slaynen
12
accept rate: 0%

edited 07 Jul '14, 03:09

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,313
×166
×45
×37

question asked: 06 Jul '14, 14:20

question was seen: 1,167 times

last updated: 07 Jul '14, 03:09