XORXORSUM - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Yahor Dubovik
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

2502

PREREQUISITES:

XOR

PROBLEM:

You are given an array A, consisting of N distinct integers.
Calculate number of pairs (i,j) (1 \le i < j \le N), such that 2 \cdot (A_i \oplus A_j) = A_i + A_j, where \oplus denotes bitwise XOR.

EXPLANATION:

Generally it’s better to think about bitwise operations, so let’s try to transform the condition into something only consists of bitwise operations. We know that A + B = (A \oplus B) + 2 \cdot (A \land B), where \land is bitwise AND (semantically, A \oplus B is the carry-less addition, while A \land B finds the positions which induces carry in addition). Therefore, the condition is transformed to A \oplus B = 2 \cdot (A \land B). There is another way to think of this condition: for any i, bit i of A \land B must be bit i + 1 of A \oplus B.

Let’s see how does this condition helps us. We know for sure that the first bit of A \oplus B is 0 (because A \oplus B is even). Since we also know the first bit of A (because it is fixed), we then know the first bit of B, which means we can infer the first bit of A \land B. The condition then comes in: we then can infer the second bit of A \oplus B, and then the second bit of B, then the second bit of A \land B, the third bit of A \oplus B, etc. Simply put, we can directly construct one and only one possible B from any fixed A.

Therefore, our problem becomes super simple: for each element in the array, construct the only other possible corresponding value, then check if that value is also an element in the array. If it is, we increase the answer by 1.

TIME COMPLEXITY:

Time complexity is O(N \log N).

SOLUTION:

Setter's Solution
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = 1e6 + 10;
ll a[maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ll x = a[i];
        ll y = 0;
        int bit = 0;
        while (bit < 60) {
            int bt = (int)((a[i] >> bit) & 1);
            if (bt == 0) {
                bit++;
                continue;
            }
            y |= (1LL << bit);
            if (!(a[i] & (1LL << (bit + 1)))) {
                y |= (1LL << (bit + 1));
            }
            bit += 2;
        }
        assert((x ^ y) * 2 == (x + y));
        int pos = lower_bound(a, a + n, y) - a;
        if (pos < n && a[pos] == y) {
            ans++;
        }
    }
    assert(ans % 2 == 0);
    ans /= 2;
    cout << ans << '\n';
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e5+1;
const int iu=30;
map<ll,int>mp;
int n;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	ll ans=0;
	for(int i=1; i<=n ;i++){
		ll x;cin >> x;mp[x]++;
		ll y=x;
		for(int j=0; j<60 ;j++){
			if((x>>j)&1){
				y^=(1LL<<(j+1));
				j++;
			}
		}
		ans+=mp[y];
	}
	cout << ans << '\n';
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    set<long long> se;
    int ans = 0;
    while (n--) {
        long long u; cin >> u;
        long long oth = 0;
        for (int i = 0; i < 60; i++) {
            if (u >> i & 1) {
                oth ^= (1LL << i); i++;
                oth ^= (((u >> i & 1) ^ 1) << i);
            }
        }
        ans += se.count(oth);
        se.insert(u);
    }
    cout << ans;
}
2 Likes

we don’t

13 Likes

Because A⊕B is even, not odd. (Since A⊕B = 2 x (A ∧ B) = 2 x some integer, A⊕B is even)

2 Likes

We know for sure that the first bit of A⊕B is 0 (because A⊕B is odd).
Shouldn’t this be because A xor B is even?

1 Like

Sorry it was a typo, fixed!

In Tester’s Solution

What is 1LL<<(j+1) exactly is ?? and what’s it’s use??
Please explain !!

Well this was a fun one to investigate. I started by writing a little program to find out which pairs might be valid and it became evident that each number has a single corresponding partner for which this relationship holds.

Consider A_i and A_j for which the given relationship R(A_i,A_j) holds. Since we know A_i+A_j is even, A_i and A_j are the same parity. This also means A_i⊕A_j must be even and then A_i+A_j is divisible by 4.

Now if both A_i and A_j are even, we can see that R(A_i/2,A_j/2) also holds. And if both are odd, then one of them is 1\bmod 4 and the other is 3\bmod 4, then using x{\rfloor}_4 to mean “round x down to a multiple of 4”, R(A_i{\rfloor}_4,A_j{\rfloor}_4) also holds since (A_i{\rfloor}_4)⊕(A_j{\rfloor}_4) = (A_i{⊕}A_j) -2 and (A_i{\rfloor}_4)+(A_j{\rfloor}_4) = (A_i+A_j) -4 . In this way we can find the partner of a given number by tracking these steps back to zero (since trivially R(0,0) holds) and then reversing the steps to find the appropriate partner number - which also demonstrate the uniqueness of the partner.

Working with a binary string, the process of finding the partner becomes simpler - we can work from right to left and each time we encounter “01” or “11”, replace it with the opposite value to reflect the treatment of odd numbers above. Otherwise zeroes are left in place to reflect the even number rule. The following does this in Python:

def xor2ptnr(val):
    # convert to binary with leading zero then split from the right on instances of "11"
    sb = f'0{val:b}'.rsplit("11") 
    # replace every "01" with "11" in each split section ...
    # then add "01" into the splits made earlier and convert to decimal
    return int("01".join(s.replace("01","11") for s in sb),2)

We can also find partners for just half of the numbers, depending on which way the first replacement (from the right) goes, and check whether that partner exists in the other half of the population, either directly or by building and intersecting sets.

Can anyone tell why my code is giving wrong answer
#include <bits/stdc++.h>

#define ull unsigned long long int

#define ui unsigned int

#define ll long long int

#define f(i, n) for (ll i = 0; i < n; i++)

const ll m = 10e9 + 7;

// const ll N = 10e5 + 5;

using namespace std;

ll binpow(ll a, ll b, ll m)

{

a %= m;

ll res = 1;

while (b > 0)

{

    if (b & 1)

        res = res * a % m;

    a = a * a % m;

    b >>= 1;

}

return res;

}
int main()

{

ios_base::sync_with_stdio(0);

cin.tie(0);

int n;

cin >> n;

ll arr[n];

unordered_map<ll, bool> map;

f(i, n)

{

    cin >> arr[i];

    map[arr[i]] = true;

}

ll ans = 0;

for (int i = 0; i < n; i++)

{

    bool pre = 0,curr = 0;

    ll second = 0;

    for (int j = 0; j <= 60; j++)

    {

        curr = (pre) ^ (arr[i] >> j & 1);

        if (curr)

        {

            second = second | 1 << j;

        }

        pre = curr & (arr[i] >> j & 1);

    }

    // cout << arr[i] << " " << second << endl;

    if (map[second])

    {

        ans++;

    }

}

cout << ans / 2 << endl;

return 0;

}

correction: (because A⊕B is even**)