How to solve D-Or cook off october 2019?

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?

https://www.codechef.com/COOK111B/problems/DOR

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.

My submission.

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

https://www.codechef.com/viewsolution/27500960 This is my python solution

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:

  1. if li==1 and ri==1, simply add (1<<i) to answer
  2. 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 : https://www.codechef.com/viewsolution/27503957

Best solution : https://www.codechef.com/viewsolution/27495414
TBH

Just 2 lines

1 Like

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

  1. 4 and 5
  2. 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

why my code is going TLE :tired_face::tired_face::tired_face::tired_face:

https://www.codechef.com/viewsolution/27504842