I hope u all doing good, During the whole contest. I am just thinking about it after solving the first two. Try different approaches but nothing works.Is this Dp or direct formula,Hint please?
1 Like
I am pretty sure it is not dp
1 Like
just greedy
ntest = int(raw_input())
for test in range(ntest):
A,B = [int(x) for x in raw_input().split()]
bin_B = bin(B)[2:]
bin_A = bin(A)[2:]
lb = len(bin_B)
while (len(bin_A) < lb):
bin_A = '0' + bin_A
X = 0
i = 0
while (i < lb and bin_A[i] == bin_B[i]):
i+=1
while i <= lb:
X += int(pow(2,lb-1-i))
i +=1
print X | B
Can you tell the logic?
https://www.codechef.com/viewsolution/27510843
Can anyone explain this solution. And why is the value of c 576460752303423488
Its pure binary search.
What I found out was:
That maximum can only be found when all bits are set.
So suppose you have L = 16, R = 31.
We apply binary search on it, so mid will be 23.
Now, we check on two conditions:
1) mid > l
2) mid <= r
If yes, answer is
((mid) | (mid - 1))
If no, apply binary search with a bit of a modification and you will get it.
I had proved it myself, you can also see, it works. You just need to look into edge cases.
3 Likes
If there is a transition point from “one 2 power number” to “another two power number”, then you can always make all bits 1.
Because during the transition for example,
(2^3) - 1 = 7 which is 111 in binary
(2^3) = 8 (transition happened to 4 bits). Hence 8’s binary is 1000
Hence OR = 0111|1000 => 1111
This is 1 part of the solution.
My logic seems correct but I got a TLE and couldn’t think of a faster method.
I flip the bits of the max number ®. If that value is < L, then I keep adding increasing powers of 2 ( like +2 + 2^2 + 2^3) so that it becomes just >= L and then take the bitwise OR of that number and R.
Can someone tell how to think about it better?
You had to find the number which lies between l and r , that converts the maximum number of zeroes in the binary of r from 0 to 1
For e.g if the binary of some number is 1000100110
then the maximum value bitwise OR can give is 111111111,
so any number with a 1’s in binary notations at the place 0’s in binary notation of r is valid
therefore take base case as binary of l , then compare it with binary of r
then turn the binary representation of l into 1’s wherever r has 0’s while also taking care not to make the number greater than r
First take binary equivalents of l and r (let l=1031 and r= 93714)
Then ans would be like : find first different bit then set all bits to 1 from that bit. And bits before that will be same as bits of r
eg:
93714 = 10110111000010010
1031 = 00000010000000111
The ans is : 11111111111111111 i.e. 131071 as first bit is different
if binary equivalent of l= 100101
and binary equivalent of r= 101010
then ans= 101111 as 3rd bit is different so all bits 1 from 3rd bit
1 Like
i solved it like this:
starting from the highest bit down to 0th bit , compare that bit position of l and r at position i:
- if li==1 and ri==1, simply add (1<<i) to answer
- if li==0 and ri==1, for all bits position smaller than i add (1<<i) to answer and return it
the main thing was if li==0 and ri==1 there will definitely exists a number between l and r whose all bits are set from 0th bit to (i-1)th bit
My solution was, to check if the bits in binary representation of l and r are equal then the answer will have same bit, if at any point they become unequal then the rest of the bits in the answer are 1.
Example
1031 93714
>>> bin(93714)[2:]
'10110111000010010'
>>> bin(1031)[2:].zfill(17)
'00000010000000111'
>>>
Since the first bit is unequal the bits in the answer will all be 1
>>> bin(131071)[2:].zfill(17)
'11111111111111111'
1000000000123
'1110100011010100101001010001000001111011'
1000000123456
'1110100011010100101001101111001001000000'
1000000192511
'1110100011010100101001111111111111111111'
Solution link : CodeChef: Practical coding for everyone
Can anyone explain the 2nd test cases?
how will “4 5” , give “5” as output?
5|5 => 5 or with 5 gives you 5
1 Like
If we do bitwise operations between
- 4 and 5
- 5 and 5
The answer to the above will be 5.
Try using bitset in c++ and see in l if it’s bit can be changed to 1 so that l or r can give us 1 ,in this way check for all such bits but keeping in mind that it doesn’t exceed r.
The two numbers would be 4 and 5.
4 -> 100
5-> 101
The OR of the two numbers would be
101 , that is, 5
1 Like
