MAXANDOR - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: yash5507
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

2028

PREREQUISITES:

Familiarity with bitwise operations

PROBLEM:

Let F(x, y, z) = (x\mid y) - (x\ \& \ z).

Given A, B, C, find the number of integers 0 \leq x \lt 2^C such that F(x, A, B) is maximum.

EXPLANATION:

Almost everything in this problem is a bitwise operation, except the subtraction in F(x, y, z).
However, notice that (x\mid y) will contain all the set bits of x, while (x \ \& \ z) cannot contain any bits that aren’t set in x.
So, (x\ \& \ z) is a submask of (x\mid y), and this means the subtraction operation is really just bitwise XOR.
That is, we can rewrite the function as F(x, y, z) = (x\mid y) \oplus (x\ \& \ z).

Now that everything we’re dealing with is bitwise operation, it helps to look at what’s going on bit-by-bit.

Let’s fix a bit k and see what happens.
Let x_k denote the value of the k-th bit of x (which is either 0 or 1). Similarly define A_k, B_k, F_k(x, A, B).
We already know A_k and B_k, our aim is to find out what values x_k can possibly take.

We have F_k(x, A, B) = (x_k\mid A_k) \oplus (x_k\ \& \ B_k), and we’d like to maximize F_k(x, A, B).

There are 4 cases depending on their values:

  • A_k = B_k = 1
    Here, (x_k \mid A_k) = 1, and (x_k \ \& \ B_k) = x_k.
    So, F_k(x, A, B) =1 \oplus x_k, which is maximized when x_k = 0.
  • A_k = B_k = 0
    Here, (x_k \mid A_k) = x_k, and (x_k \ \& \ B_k) = 0.
    So, F_k(x, A, B) = x_k \oplus 0, which is maximized when x_k = 1.
  • A_k = 1 and B_k = 0
    Here, F_k(x, A, B) = 1\oplus 0 = 1, and is independent of x_k. So, we can choose x_k to be either 0 or 1
  • A_k = 0 and B_k = 1
    Here, F_k(x, A, B) = x_k\oplus x_k = 0, once again we can choose x_k freely.

Putting the above together:

  • If A_k = B_k, x_k is fixed and we have no choice.
  • If A_k \neq B_k, x_k can be chosen freely.

So, the answer is simply 2^d, where d is the number of bits where A and B differ in their binary representations.
d can be computed by iterating over each bit independently; or you can notice that it’s just the number of set bits in (A\oplus B) for an \mathcal{O}(1) solution.

TIME COMPLEXITY

\mathcal{O}(C) or \mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    a, b, c = map(int, input().split())
    dif = bin(a ^ b).count('1')
    print(2 ** dif)
2 Likes
2

what is wrong in this method ?

‘’’
ll int cnt1=0;
ll int cnt2=0;

    for(int i=0;i<c;i++)
    {
        ll int st=(a&(1LL<<i));
        ll int st2=(b&(1LL<<i));
        if(st2>0 && st==0)
        {
            cnt1++;
        }
        if(st>0 && st2==0)
        {
            cnt2++;
        }
    }
    cout<<1LL*pow(2,cnt1+cnt2)<<endl;
3

Isn’t that supposed to be F(x,y,z)=(x∣z)−(x & z) ?

2 Likes
4

Right, good catch on the typo. I’ll fix it.
Edit: fixed

1 Like
5

The idea looks correct, I recommend not using the pow function because it works with floating point numbers and isn’t necessarily exact.

6

At the beginning of the problem statement, it’s defined F(P, Q, R) = (R|P) - (Q\&P)

But it seems everywhere else (sample explanation and editorial) author meant F(P, Q, R) = (Q|P) - (R\&P)

3 Likes
7

Yep, use for loop, it will give correct answer

for(int i=0;i<cnt2+cnt1;i++)
            ans*=2;
9

You don’t have to

Simply use left shift operator. So,

cout<<(1<<(cnt2+cnt1))<<endl;

Should be good enough.

10

Why wasn’t the value of C used in the editorialist’s code?

11

Can you explain ,
how for following test cases
1
1 2 1 ,
o/p - 4

1
2 1 1
o/p - 4

of editorialist code ?

How , if you take F(x,a,b) = (x | b) - (x & b)
or F(x,a,b) = (x | a) - (x &b) .

Because ordering is messed up in problem , example explanation and in editoiral.

2 Likes
12

Note the constraint 0 \leq A, B \lt 2^C, that’s what allows me to ignore the constraint on C entirely.
If that wasn’t guaranteed then yes, I’d have to iterate over bits from 0 to C-1.

@pkpawan123 for the same reason the input you provided isn’t valid, 2 isn’t strictly less than 2^1.

13

ok and what is the ordering of F(X,A,B) ?,

  1. (X | A) - (X & B)
  2. (X | B) - (X & A)
1 Like
14

I probably typo’d in the editorial, go with whatever the statement says.

In fact, it doesn’t really matter which one it is, the answer remains the same. The number of X that maximize both is the same because you only compare bits of A against bits of B, which is symmetric w.r.t A and B (which is how I made the typo in the editorial in the first place)

1 Like
15

For A = 1 , B = 2 and C = 1.
How can be the answer is 4? There even only two values of x (0,1).

16

I was stuck there for about an hour wondering how can, f(4,1,2) = 5 according to the sample explanation but on solving f(4,1,2) using the definition given in the problem statement i was getting 6.

17

Didn’t understand this part, how did you come up with this?
A more thorough explanation will be useful.

Thanks!

1 Like
18
19

That’s just something you observe if you’re familiar with bitwise operations.

If x is a submask of y, then y - x and y\oplus x are the same thing, because both operations just remove all the bits of x from y.
Similarly, if x and y are disjoint masks (i.e, if x & y == 0), then x + y and x \mid y are the same thing.

You might’ve also seen the ‘identity’ x+y = (x\oplus y) + 2\cdot (x\ \& \ y), for example here.
The above points I mentioned are just a special case of that:

  • If x is a submask of y, then x\ \&\ y = x. So, that identity tells you that x+y = (x\oplus y) - 2x, or y-x = x\oplus y
  • If x\ \& \ y = 0, once again that identity says x+y = x\oplus y
2 Likes
20

How can be the answer is 4? There even only two values of x (0,1)..

.

21

Yeah, answer is 2, as in my solution
https://www.codechef.com/viewsolution/95639500

(It is in Rust Language though )