PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: saksham441
Tester & Editorialist: iceknight1093
DIFFICULTY:
2014
PREREQUISITES:
Familiarity with bitwise XOR, frequency tables, observation
PROBLEM:
Given an array A, count the number of pairs (i, j) such that 1 \leq i \leq j \leq N and A_i \oplus A_j is a palindrome.
It’s known that A_i \lt 2^{15}.
EXPLANATION:
A brute force algorithm would be to check for each (i, j) pair whether their XOR forms a palindrome; of course, this is too slow.
Notice that the number of distinct palindromes we care about is really quite small.
In particular, there are only about \mathcal{O}(10^{\frac{\log_{10}X}{2}}) (which is about \mathcal{O}( \sqrt X)) palindromes below X, because fixing one half of the palindrome fixes the other half as well.
In particular, only 427 of the numbers upto 2^{15} are palindromes.
Further, recall that XOR is an involution, i.e, x\oplus y = z also means that x = z\oplus y.
So, instead of fixing i and j and checking if A_i\oplus A_j is a palindrome, we can fix i and the target palindrome; which then uniquely fixes A_j; after which we only need to count the number of valid j.
That is,
- Let \text{Pal} be a list of palindromes upto 2^{15}. This can be precomputed, and has length 427.
- Then, for each i from 1 to N, and each x in \text{Pal},
- Let y = A_i \oplus x.
- We then want to know the number of indices j such that A_j = y.
This can be found in \mathcal{O}(1) using a frequency table.
Make sure not to overcount pairs of indices, since the above algorithm didn’t account for the i \leq j condition.
That’s not too hard: all pairs except (i, i) will be counted twice, so divide by 2 appropriately.
The complexity is something like \mathcal{O}(430\cdot N) (more formally, \mathcal{O}(N\cdot \sqrt{\max A})), which is good enough to get AC.
Note that the frequency table can be implemented using either an array or a hashmap (std::unordered_map, dict, HashMap) and should run in time without much issue.
Using std::map will likely be too slow because of the extra \log factor.
TIME COMPLEXITY
\mathcal{O}(N\cdot P) per test case, where P is the number of palindromes not exceeding 2^{15} (approximately 430).
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
vector<int>allPalindrome;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
bool isPalindrome(int num){
int rev=0;
int temp=num;
while (num>0){
rev=rev*10 + (num%10);
num/=10;
}
return (rev==temp);
}
void solve(){
long long int n;
cin>>n;
long long int v[n];
long long int freq[(1<<17)];
memset(freq,0,sizeof(freq));
for (int i=0;i<n;i++){
cin>>v[i];
freq[v[i]]++;
}
long long int ans=0;
for (int i=0;i<allPalindrome.size();i++){
long long int num=allPalindrome[i];
for (int j=0;j<n;j++){
ans+=freq[v[j]^num];
}
}
//Divide ans by 2 as each pair will be calculated twice
ans/=2;
//add all pairs such that A[i]^A[j] = 0 means A[i] and A[j] are same
for (int i=0;i<(1<<17);i++){
ans = ans + (freq[i] * (freq[i]+1))/2;
}
cout<<ans<<endl;
}
void generatePalindromes(){
for (int i=1;i<=(1<<17);i++){
if (isPalindrome(i)){
allPalindrome.push_back(i);
}
}
}
int main(){
int t;
fast;
cin>>t;
generatePalindromes();
while (t--){
solve();
}
}
Editorialist's code (Python)
mx = 1 << 15
palindromes = []
for i in range(mx):
if str(i) == str(i)[::-1]: palindromes.append(i)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = {}
ans = 0
for x in a:
if x in freq: freq[x] += 1
else: freq[x] = 1
for x in a:
for y in palindromes:
if x^y <= x: continue
if x^y in freq: ans += freq[x^y]
for x in freq.values(): ans += x*(x+1)//2
print(ans)