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:
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
- (A_i | A_j) denotes Bitwise OR operation,
- (A_i \oplus A_j) denotes Bitwise XOR operation,
- (A_i \& A_j) denotes Bitwise AND operation.
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();
}