Cook-off July 2021 (XORORED) Answer not accepted but my code

1

(Answer not accepted but my code is giving correct answer for the inputs I have tested it for the inputs I have tested it for)

Can y’all help me debug my code the answer is not getting accepted but the logic I have used seems correct and I am also getting answers for the inputs I am trying.

By boolean logic I have reduced the expression given in the question to:-

say input is: A, B

reduced form of expression: x & ~(A&B) | ~x(A|B)
above operators are bitwise.

My Solution

#include<bits/stdc++.h>

#define nl "\n"
#define loop(n) for(int i = 0; i < n; i++)
#define fo(i, end) for(int i = 0; i < end; i++)
#define foo(i, begin, end) for(int i = begin; i < end; i++)
#define lld long long int


using namespace std;

int MSB(int n)
{
    return  floor(log(n)/log(2)) + 1;
}

int flipBits(int n) {
    int mask = 1;
    int k = MSB(n);
    for (int i = 1; i < k; ++i)
        mask |= mask << 1;

    return ~n & mask;
}


void solve()
{
    int A[100], N;
    int alpha, beta;
    int x, min;
    cin>>N;
    
  
        fo(i,N)
        {
            cin>>A[i];
        }
        alpha = A[0];
        beta = 0;
        fo(i,N)
        {
            alpha = alpha & A[i];
            beta = beta | A[i];
        }
        
        alpha = flipBits(alpha);
        
        if(alpha > beta)
        {
            x = flipBits(alpha);
            min = alpha & beta;
        }
        else
        {   
            x = beta;
            min = alpha & beta;
        }
        
       
        
        
        cout<<x<<" "<<min<<nl;

}


int main()
{
    int T;
   
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>T;
    while(T--)
        solve();
    
    return 0;
}
2

Try this test case :-

1
5
7 5 2 6 4
Your O/P :- 7 1
Correct :- 6 7
3

How is six the correct answer? It should be seven,since 1<7. Imo, just find the largest number, and take XOR of all numbers with it, and perform the union with the transformed numbers.

4

My logic was to make an array of all set bits and if some index was present in all elements then we put a binary one in that index, this way all the elements will have a zero at that position after xor.

1 Like
5

This approach doesn’t convince me. Can you elaborate?

6

That’s pretty good and fair approach.

7

For X = 6 we will get ( A1 xor X ) ∨ ⋯ ∨ ( An xor X ) as 7 which is minimum possbile .

8

we don’t have to minimize X , so we can just take X = union of all elements. :slight_smile:

9

can you show your code , My approach is also same but getting wrong answer, I am just checking if at a particular bit position its count is greater or equal to half the size of array, then this bit will be “ON” in X.

10

Can you prove this will work?

Edit: Provide your code too.

11

I dont have a real proof, what I observed was
bitpos: 0123456
num1: 1011101
num2: 1011000
num3: 0010110
num4: 0010001
num5: 0010000
Here If in the value of X i take 0th bit then xor operation will turn ON “0th position” in num3, num4, num5 and will turn off for num1, num2. its like increasing the value by (1<<bitpos) in num3, num4, num5 and decreasing the (1<<bitpos) in num1 and num2. Since i want OR value to be as min as possible I also want all numbers of array to be min.
here at 2nd bit pos all bit are 1 so (1<<2) will be taken in value of X.

code

the conditon should be ceil(n/2) instead of n/2 got Correct Answer

13

For your previous code, try this test case:

1
1
1024
14

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

15

yes suman , even I tried this too , obviously you can see if number of I count how many number having i’th bit set , and count is > (n/2) , then I will take a number such that whose i’th bit is set so XOR will be zero , means Higher chances for minimum OR.

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

16

No. The approach is not convincing and it is not a good approach. It gave AC because it was mentioned in the problem statement that we can output any value of X that gives minimum bitwise OR of array elements.

Consider the binary representations of few numbers.

0\ 0\ 1\ 1\ 0\ 1\ 0\ 0\\ 1\ 1\ 0\ 1\ 1\ 0\ 0\ 0\\ 1\ 0\ 1\ 1\ 1\ 1\ 1\ 1\\ 0\ 0\ 0\ 1\ 1\ 0\ 0\ 0\\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\\

The count array will look like this

2\ 1\ 2\ 5\ 3\ 2\ 1\ 1

Now, according to your logic, the binary representation of the answer will be

0 0 0 1 1 0 0 0
        ^

Look at the marked bit. There are 3 numbers whose marked bit is set. Since 3\gt(5/2), the marked bit is set to 1.

It doesn’t matter whether the marked bit is set or reset. It will still give the minimum bitwise OR of array elements.

So,

This is absolutely wrong. I just showed that setting a bit based on whether count \gt (n/2) will not affect the minimum bitwise OR of array values.

Unless the (count == N) condition holds true, there is no need to set that bit to 1.

17

so what is the solution of this problem , I just think this only as there may be multiple X which gives us Min OR , yeah if question says give min X too then it will fail.

18

Yeah, this is not the right approach. But it passed because the value of X will not matter unless you’re minimising the Bitwise OR of the array elements.

The right approach would be, setting the bit to one if and only if the count is N, thereby setting this bit to 0 in all array elements which minimises the bitwise OR of array elements.

1 Like