PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given an array A containing distinct integers.
Count the number of ordered tuples (i, j, k, l) such that the values A_i\oplus A_j, A_j\oplus A_k, A_k\oplus A_l, A_l\oplus A_i in order can be the sides of a rectangle with positive area.
EXPLANATION:
Let’s fix a tuple (i, j, k, l) and see what it means for the values to be the sides of a rectangle.
Opposite sides must be equal, so:
- A_i\oplus A_j = A_k \oplus A_l should hold, which upon taking the right side to the left tells us that
A_i\oplus A_j\oplus A_k \oplus A_l = 0 - A_j\oplus A_k = A_l \oplus A_i should hold, which in fact tells us the exact same thing: that all the four values should XOR to 0.
So, we’re really just looking for tuples such that the elements all XOR to 0.
Note that if (i, j, k, l) satisfies this, so will any other ordering of these indices (such as (k, j, i, l) or (l, i, k, j)), since XOR is independent of order.
Once four distinct indices have been chosen, there are 24 ways to order them.
So, we can focus on just counting tuples such that i \lt j \lt k \lt l, and multiply the final answer by 24.
To count tuples, we’ll use a somewhat smart brute force.
Let \text{freq}[x] denote the number of pairs of indices (i, j) such that A_i\oplus A_j = x.
Initially, we have \text{freq}[x] = 0 for all x.
Then, consider the following algorithm:
- For each j = 1, 2, 3, \ldots, N in order, do the following:
- First, for each index i \lt j, increase \text{freq}[A_i \oplus A_j] by 1.
- Then, for each index l \gt j+1, increase the answer by \text{freq}[A_{j+1} \oplus A_l]
The idea here is as follows:
- The first step, considering i \lt j, updates the \text{freq} array with all pairs whose right endpoint is j.
Since we’re processing j in ascending order, the same has been done previously for smaller indices too: so \text{freq} now contains information about all pairs with both indices being less than or equal to j. - The second step, considering l \gt j+1, is us essentially fixing k = j+1 and iterating over l \gt k.
Note that when k and l are fixed, we just want the number of pairs before k such that their XOR equals A_k \oplus A_l.
This information is exactly what the \text{freq} array holds, as noted in the previous point!
The algorithm clearly takes \mathcal{O}(N^2) time, and so is fast enough.
Note that nowhere in the above discussion did we worry about the side lengths becoming zero: this is because, in the easy version, it’s impossible for any side lengths to ever become 0.
After all, x\oplus y = 0 \iff x = y, but we’re dealing with distinct elements here so this won’t become a problem.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll cnt[2000005];
int main() {
ll tt=1;
cin>>tt;
while(tt--){
ll n;
cin>>n;
ll a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
ll ans=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
ans+=8*cnt[a[i]^a[j]];
cnt[a[i]^a[j]]++;
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
cnt[a[i]^a[j]]=0;
}
}
cout<<ans<<"\n";
}
}
Tester's code (C++)
// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
int fr[2000001];
int frx[2000001];
int comb(int n){
return n*(n-1)/2;
}
int smn = 0;
void solve()
{
int n;
cin >> n;
assert(n >= 4);
assert(n <= 5000);
// n = inp.readInt(4,50000);
// inp.readEoln();
smn += n;
vi a(n);
take(a,n);
repin{
assert(a[i] >= 0);
assert(a[i] <= 1000000);
}
// cout << "hi\n";return;
// repin{
// a[i] = inp.readInt(0,1000'0000);
// if(i == n-1)inp.readEoln();
// else inp.readSpace();
// }
int mx = (*max_element(be(a)));
si s(be(a));
assert(s.size() == n);
int ans = 0;
vi oc;
rep(i,0,n){
rep(j,i+1,n){
if(frx[a[i]^a[j]] == 0)oc.pb(a[i]^a[j]);
frx[a[i]^a[j]] ++;
}
}
for(auto x : oc){
ans += comb(frx[x]);
}
ans *= 8;
cout << ans << "\n";
rep(i,0,n){
rep(j,i+1,n){
frx[a[i]^a[j]] --;
}
}
repin{
fr[a[i]]--;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
cin >> t;
// cout << t << "hi\n";return 0;
assert(t >= 1);
assert(t <= 1000);
// t = inp.readInt(1,1000);
// inp.readEoln();
while(t--)
solve();
// inp.readEof();
assert(smn <= 5000);
return 0;
}
Editorialist's code (Python)
M = 1 << 21
freq = [0]*M
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
for j in range(i+1, n):
ans += freq[a[i] ^ a[j]]
freq[a[i] ^ a[j]] += 1
for i in range(n):
for j in range(i+1, n):
freq[a[i] ^ a[j]] = 0
print(ans * 8)