XORCOMP - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes

DIFFICULTY:

Simple

PREREQUISITES:

Bitwise operations

PROBLEM:

You are given three non-negative integers x, y, n.

Find the number of integers z, such that 0 \leq z \leq n and (x \oplus z) < (y \oplus z).

QUICK EXPLANATION:

  • Brute force all possible suffixes for which z[i] \neq n[i], and z[j]=n[j] for all j \gt i.
  • If z[i..31] \oplus x[i..31] \lt z[i..31] \oplus y[i..31], then there are 2^i ways of filling the first i bits of z.
  • If z[i..31] \oplus x[i..31] = z[i..31] \oplus y[i..31], then there are 2^{i-1} ways of filling the first i bits of z.

EXPLANATION:

In problems involving bitwise operations is useful to consider the binary representation of intergers. From now on we’ll represent the integers as binary strings of length 32, for example B = 13 = 1011000..000 and B[0]=1, B[1]=0, B[2..4]=110. Note that the string is given from least significant bit to most significant bit.

For simplicity let’s assume that z \lt n. We can check the case z=n as an special case. Also we can consider that x \neq y, because there is no valid z when x = y.

Let i be the rightmost (most significant) position in which z[i] \neq n[i], then the following holds:

  • z[j]=n[j] for each j \gt i, i.e z and n have the same suffix starting from i+1.
  • z[i]=0 and n[i]=1, because z \lt n

To find the number of possible z, we can brute force all possible i from most significant bit to less significant bit.

The problem is now reduced to count the number of distinct values of z, such that x \oplus z \lt y \oplus z, given that we know a suffix (with length 32-i) of z.

We don’t know the first i bits of z, but is possible that given the last 32-i bits we can be sure that z \oplus x is greater or smaller than z \oplus y, For example in the following picture we can be sure that z \oplus x \gt z \oplus y because it has a bit of higher order.

                      i
    n   = [*********][110]
    z   = [?????????][010]
    x   = [010110110][101]
    y   = [101010100][011]
P = z^x = [?????????][111]
Q = z^y = [?????????][001]

Let P= z \oplus x and Q=z \oplus y, there are three cases:

  • P[i..31] \gt Q[i..31], it doesn’t matter how we fill the first i bits of z, is not possible to make P \lt Q.
  • P[i..31] \lt Q[i..31], it doesn’t matter how we fill the first i bits of z, P will always be smaller than Q, there are 2^i ways of filling the first i bits.
  • P[i..31] = Q=[i..31], that means x and y have the same suffix, to make P smaller than Q, we have to look for the largest index j in which x[j] \neq y[j]. There are two possibilities:
    • x[j]=1, y[j]=0: we can set z[j]=1.
    • x[j]=0, y[j]=1: we can set z[j]=0.
      We have the freedom to set an arbitrary value to the other indices different than j, so there are 2^{i-1} different ways.

SOLUTIONS:

Setter's Solution
int main() {
  auto f = [&] (int n, int i) {
    return ((n >> (i + 1)) << i) + max(0, n % (1 << (i + 1)) - (1 << i) + 1);
  };
  int t;
  cin >> t;
  while (t--) {
    int x, y, n;
    cin >> x >> y >> n;
    if (x == y) {
      cout << 0 << '\n';
    } else {
      for (int i = 30; i >= 0; i--) {
        if (((x ^ y) >> i) & 1) {
          if (x > y) {
            cout << f(n, i) << '\n';
          } else {
            cout << n + 1 - f(n, i) << '\n';
          }
          break;
        }
      }
    }
  }
}
Tester's Solution
void solve() {
  int x, y, n;
  cin >> x >> y >> n;

  if (x == y) {
    cout << "0\n";
    return;
  }

  auto calc = [&](int pref, int left_len) {
    if ((x & ~((1 << left_len) - 1)) != (y & ~((1 << left_len) - 1))) {
      if (((x & ~((1 << left_len) - 1)) ^ pref) < ((y & ~((1 << left_len) - 1)) ^ pref)) {
        return 1 << left_len;
      }
      return 0;
    }

    return 1 << (left_len - 1);
  };

  int ans = 0;
  int pref = 0;
  for (int i = 29; i >= 0; --i) {
    if (n & (1 << i)) {
      ans += calc(pref, i);
      pref |= 1 << i;
    }
  }
  ans += calc(pref, 0);
  cout << ans << "\n";
}

VIDEO EDITORIAL:

8 Likes

DIFFICULTY: Simple

it was fu*king not simple

49 Likes

Submissions: 113, Accuracy :1.85 but question is simple :slight_smile:

20 Likes

if this is a simple problem then it means I don’t know how to code !!!

12 Likes

The SIMPLE tag really hurts

8 Likes

Simple : } !!
Editorial bhi nhi smjh ayi mujhe to
;-;

17 Likes

bhai chinta mat kr tu akela nai hai

2 Likes

I solved it with another approach based on purely some observation. If anyone can help prove the correctness of it, it would be really helpful. Let a = min(x,y) and b = max(x,y). Then using brute force on some sample values of a,b and z you notice that at first there are c values for which a^z < b^z and then there are c values for which for a^z > b^z and this continues till the end. This implies a cyclicity of c. On further observation you notice that all pattern (a^z , b^z) is cyclic for any and b with powers of 2 only, that is c= 2^n.
So in O(k) time we can test all powers to 2 to check the smallest value where the mismatch occurs (i.e a^z > b^z) and that would be our c value.
Once we have the c value, it is just a matter of implementation of finding out of N+1 values how many actually satisfy our condition.
Submission Link : https://www.codechef.com/viewsolution/39877744

I have solved it using digit dp. this is my solution https://www.codechef.com/viewsolution/39867972

3 Likes

can anyone tell me why are we taking till 31 in this P[i…31]<Q[i…31] ?

1 Like

I followed same approach but constantly got wrong answer, I didn’t knew why.

This approach works as the deferred MSB((k+1)th bit ) in smaller number(assume ‘a’) will be 0 and the bigger number(assume ‘b’) would be 1. So when pow(2, MSB-1) is XORed with ‘a’ then kth bit will become 1 and the kth bit of ‘b’ will become 0 => (a^z)>(b^z). So for the all the possible values of z having kth bit as 1 would result in the change of comparison sign.

Eg:
a = 50 and b = 62
a = 110010
b = 111110
k = 3 (deferred MSB = 4th bit)

So if I want ‘a’^z to always be less than b^z the, we need to make sure that the 4th bit of ‘a’^z should be 0 and b^z should always be 1. So we need to remove all the possible values of z whose 4th bit is set. (Property of xor: x=0 => x^1 = 1and x=1 => x^1 = 0 )

The 4th bit will be changing from 0 to 1 after every 8 values of z. That is the reason the cyclicity is observed in this question.

2 Likes

There are 32 bits …but we start indexing from 0.
Like: 0 1 2 3…31.

Right that works, so for finding that differed bit you just start from 100000 and then keep on trying for smaller values such as 010000 and so on. Why are you dividing a by 2 in your code ? Will right shift by 1 bit work as well ?

Yeah right shift will work. The right shift in any case gives us the result obtained by division of 2. Anyways right shift is a better modification to my code. (During the contest that right shift operator didn’t strike me :P.)

@uknowme1 can you explain your logic its really difficult to understand ?

1 Like

I see both solutions are iterating 32 times but I did not get why we are doing it while we can calculate number of bits using log? Here is solution I wrote iterating over only on necessary bits.
https://www.codechef.com/viewsolution/39906928
Please let me know guys which one is better? is log too slow to use here?

Bro your dp is awesome !! :joy::joy:

<3 :"’’’ )

i be the most significant position in which z[i]!=n[i],the following holds:
–>z[j]=n[j] for each j>i
Can anyone please help me understanding this point?