Can AnyOne Give Me A Good Link Or Tutorial for Bit Operations and Its Applications For Questions Like codechef.com/problems/CHRL3 ?

editorial
, , ,
1

EVEN I AM NOT ABLE TO UNDERSTAND THE EDITORIAL AS I DON"T KNOW THE CONCEPTS
and yaa I HAVE READ THE EXISTING EDITORIAL ON bit operations by codechef
Or If SomeOne Can Help Me On This Above Question CHRL3

5 Likes
2

Have you gone through this - https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/ ?

3 Likes
3

Codechef itself has a tutorial for Bitwise Operators with some practice problems.

Here is the link:

1 Like
4

I guess you are referring to the solution of subtask 1 in CHRL3.

the first thing to understand is why we are using the binary representation of numbers in this question. The state of the dynamic programming in this case depends on subsets of a given set. Here the set are the first (at most 10) values of the sequence. To be more precise we need to know which of these are terminating a subsequence in the current state. Algorithmically we could represent this by a 10 component binary vector (vector). Say you are in a state were you have 3 subsequences ending with the 2nd, 3rd resp. 4th element of the array. Then the state would be represented by

(0,1,1,1,0,0,0,0,0,0)

The whole DP could be implemented using these vectors, but it would be terribly slow. So the trick is to compress the vector in a binary sequence and store it in a single int. To make thing easier it’s better to store the sequence in a reversed way. The example from above would be 0000001110, which is just the binary representation of the number 14. For n-component binary vectors we need the numbers up to 2^n-1 to represent them all.

When working with the numbers, you will need the equivalents of array access. Thats were the bit operations come into play. The operations are:

set nth bit : j=j| (1<<n)

unset nth bit : j=j &~(1<<n)

check if nth bit is set: j&(1<<n)

BTW: the first subtask of the problem CHRL3 is imho more difficult than the solution for the second subtask (which is obviously also a solution for the first). But the concept of representing subsets as numbers is quite important.

2 Likes
5

actually i have read this but its not helping me understanding this CHRL3 problem…

3 Likes
6

actually i have read this but its not helping me understanding this CHRL3 problem

4 Likes
7

thanks a lot and can you give me some great questions like these and ya :smiley: which have editorial on them

4 Likes
8

here are some problems for bitmasking:

3 Likes
9

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1346

1 Like
10

try this http://www.thegeekstuff.com/2012/10/bitwise-operators/

1 Like
11

try this http://www.thegeekstuff.com/2012/10/bitwise-operators/

12

Try these -

https://www.youtube.com/watch?v=

1 Like
13

https://graphics.stanford.edu/~seander/bithacks.html

1 Like