How to solve D-Or cook off october 2019?

help
21

Ohh my bad, i was thinking of XOR instead of OR

22

A is larger number in binary form
B is smaller one.
C is the answer in binary form.

        int flg=0;
        for(int i=0;i<A.size();i++){//A is the bigger lumber, B is smaller, C is answer
            if(flg){
                C+="1";
                continue;
            }
            if(A[i]=='1' && B[i]=='0'){
                flg=1;
                C+="1";
            }else{
                if(A[i]=='1' || B[i]=='1')C+="1";
                else C+="0";
            }
        }

Code: CodeChef: Practical coding for everyone

23

Preety neet solution
consider two random numbers in sorted fashion;

1101 1000000101
1101 0000000000;

now note the common part from the start i.e
1101 .This will always be there in the final resultant to maximize it (WHY?).
Now what would be the ans?
Hint : second num changes to 1101 0000000000 =>1101 0111111111

24

I have essentially done the same thing. In case when the number of bits are the same, I find the first bit which the differently set in l and r, and put 1 at that position and 0s after that(Let’s say that new number is n). Then I take the OR of n and n-1 which should give the same answer as yours. Can you pls find the error in my code?
My solution
@huylou @hitik @sanket_j_shah1 @officialnitish @hetp111

25

simplify the problem: find 2 numbers X,Y between [A,B] so that Z = X | Y is max.
the idea is we maximizing the appearance of bit 1 from left to right of Z.
the binaries of A and B will have the pattern like this:
A: OOO…OOO0XXX…XXX
B: OOO…OOO1YYY…YYY
OOO…OOO is the overlapped part.

  • if B>A, there must be 1 bit at someplace that binary_B[i] is 1 and binary_A[i] is 0 before anything else.
  • if B=A, just print B
    Hence, it’s clear that there’s a number that has a pattern like this:
    OOO…OOO111…111
27

Why are you putting zero after that, fill them with 1s, see you can directly get the answer if you just copy the bit till they are equal and when they become unequal fill the rest of the bits with 1. I couldn’t understand the logic of filling with zeros then OR’ing with ans - 1.

28

Different Approach

See this
0000
0001
0010
0011
0100
0101
0110
0111
1000 …

The numbers are formed in such a way that the least significant bit is repeated after 1 number similarly 2nd least significant bit repeated after 2 numbers and hence i-th bit is repeated after 2^i numbers. We can just subtract L from R to find the gap. Now iterate for every bit and check if it repeats range is less that the obtained difference. If yes, then our answer number must have that bit set for it. If the range of repeat is larger than the difference then check two conditions

  • if the two range numbers have different bits at that location or

  • Both the bits are set for our range number.

if any of the above conditions met than we have to set that bit for our answer also

Here is my solution - CodeChef: Practical coding for everyone

1 Like
29

I was having the motive of finding the 2 numbers. But that won’t anyways effect the answer, as if a number has the form a1000... then a-1 will have the format a0111.. and a or a-1 will have the form a1111....So that shouldn’t effect the answer. Am I missing any edge cases here?

:joy: I forgot to typecast pow, I thought when I am using the variable as ll, it should do the trick but it seems that doesn’t work.