ABITEZ-Editorial

PROBLEM LINK:

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

Setter: Vibhu Garg
Tester: Manan Grover, Abhinav sharma
Editorialist: Devendra Singh

DIFFICULTY:

2256

PREREQUISITES:

Bitwise operations, std::map

PROBLEM:

Chef was impressed by an array A of N non-negative integers. But, he was asked to solve the following problem in order to get this array.

Given a non-negative integer k, find the number of pairs (i, j) (1 \leq i < j \leq N) such that the following condition holds true:
(A_i | A_j) + (A_i \oplus A_j) + (A_i \& A_j) = k + A_j, where

You, being Chef’s friend, help him get this array by solving the above problem.

EXPLANATION:

Observation

(a|b) = (a \oplus b) + (a & b).
(a + b) = (a \oplus b) + 2\cdot (a & b)
\therefore (a| b) + (a \oplus b) + (a & b) = (a \oplus b) + (a \oplus b) + (a & b) + (a & b) = (a \oplus b) + (a + b).

The equation in the question is same as (A_i \oplus A_j) + (A_i + A_j)=(K + A_j).
\implies(A_i \oplus A_j) = (K-A_i).
\implies A_j = ((K-A_i) \oplus A_i).
Thus for each index i we need to find indices j such that i<j and A_j = ((K-A_i) \oplus A_i). This can easily be done using a map.

TIME COMPLEXITY:

O(Nlog(N)) for each test case.

SOLUTION:

Setter's solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main(){
    
    int t;
    cin >> t;
    
    while(t--){
        
        ll n, k;
        cin >> n >> k;
        
        vector <ll> v(n);
        map <ll, ll> freq;
        
        for(ll i = 0; i < n; i++){
            cin >> v[i];
        }
        
        ll ans = 0;
        
        for(ll i = n - 1; i >= 0; i--){
            ll req = (k - v[i]) ^ (v[i]);
            ans += freq[req];
            freq[v[i]]++;
        }
        
        cout << ans << endl;
    }
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    ll n, k, ans = 0;
    cin >> n >> k;
    vll v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    map<ll, ll> cnt;
    for (int i = n - 1; i >= 0; i--)
    {
        if (k >= v[i])
            ans += cnt[v[i] ^ (k - v[i])];
        cnt[v[i]]++;
    }
    cout << ans << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}

12 Likes

how the equation is same as (Ai^Aj)+(Ai+Aj)=K+Aj
i didn’t get it

1 Like

(Ai | Aj ) + (Ai & Aj ) = Ai + Aj

OR captures bits present in both Ai and Aj
AND captures bits when present in both Ai and Aj
so combined captures all the bits of Ai and Aj

example
Ai => 6 = 110
Aj => 5 = 101
bitCount= 211

  Ai|Aj = 111
  Ai&Aj = 100
bitCount= 211

hence sum would be same

5 Likes
   (Ai xor Aj) + (Ai or Aj) + (Ai and Aj) = k + Aj
⟹ (Ai xor Aj) + ( (Ai xor Aj) + (Ai and Aj) ) + (Ai and Aj) = k + Aj [As,or = xor + and ]
⟹ (Ai xor Aj) + (Ai xor Aj) + 2*(Ai and Aj) = k + Aj
⟹ (Ai xor Aj) + (Ai + Aj) = k + Aj [As,sum = xor + 2*and ]
3 Likes

Nice problem!

A&B = SET BITS that are BOTH in A&B
A-(A&B) = SET BITS that are ONLY in A
A-(A&B) + B = SET BITS that are either in A or B – >( A|B)
therefore :
A - (A&B) + B = (A|B)
A+B = (A&B)+(A|B)

1 Like

Wouldn’t having a map/hash table for all the indices of the array create a huge auxillary space issue?

Given: (Ai | Aj) + (Ai ^ Aj) + (Ai & Aj) = k +Aj
Try this: 2 * (Ai | Aj) == k + Aj
because:
& OR^ == Bitwise OR (|)
i j & ^ |
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 0 1