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

×

# Binary Implementation of Paying Up

 0 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<0){ String[] params = reader.readLine().split(" "); int n = Integer.parseInt(params); //quantity of different notes in wallet <= 20 int m = Integer.parseInt(params); //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 2★slaynen 1●2 accept rate: 0%  2 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 answered 06 Jul '14, 21:15 4★abbas 411●8 accept rate: 28%  1 You can look at this Wonderful tutorial.If you have any doubts, comment below. answered 06 Jul '14, 16:39 2.2k●6●17●48 accept rate: 10%  1 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! answered 06 Jul '14, 16:48 2★sunny210 101●1●5●12 accept rate: 0%  0 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. answered 06 Jul '14, 21:43 2★slaynen 1●2 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<  0 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. answered 07 Jul '14, 02:55 2★slaynen 1●2 accept rate: 0%  toggle preview community wiki: 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